什么是基因算法？
需要详细资料，越详细越好。 问题点数：200、回复次数：19Top
1 楼jadedrip（翡翠水滴）回复于 2001-07-26 08:52:31 得分 0
居然没人知道？Top
2 楼lins（Anders*小明）回复于 2001-07-26 09:23:36 得分 0
是人工智能的内容！！Top
3 楼Netguy（老家伙）回复于 2001-07-26 10:24:16 得分 0
随便找本神经网络的书都有讲这个Top
4 楼tom255（吸血鬼）回复于 2001-07-27 15:00:05 得分 0
gzTop
5 楼Kusk（Kusk）回复于 2001-07-28 18:12:48 得分 0
我也不知。Top
6 楼jadedrip（翡翠水滴）回复于 2001-07-29 19:29:07 得分 0
upTop
7 楼one_add_one（)我要睡觉：）回复于 2001-07-30 01:07:19 得分 0
是说的是不是遗传算法呀？Top
8 楼one_add_one（)我要睡觉：）回复于 2001-07-30 01:08:16 得分 50
http://www.geatbx.com/docu/algindex.html
这里有很详细的介绍！Top
9 楼Leemaasn（小鸟）回复于 2001-07-30 09:17:31 得分 0
给分，给分Top
10 楼newtoon2002（油田）回复于 2001-08-19 15:41:13 得分 0
你可以看看介绍人工智能的书Top
11 楼one_add_one（)我要睡觉：）回复于 2001-08-19 15:58:46 得分 0
?Top
12 楼vive（白起）回复于 2001-08-19 17:06:12 得分 0
模仿遗传和变异
把解作为种子进行杂交，产生下一代的解；下一代的解保留了先辈的大多数特征，再随机加入少量变异；每一代的解进行选择，太差的就淘汰，然后保留下来的重复产生下一代Top
13 楼goldcattle（海边的云）回复于 2001-08-20 01:06:03 得分 150
哈，有高分，老兄我告诉你，前几天我刚研究彻底。
你所说的基因算法应该叫遗传算法（GA)
遗传算法(Genetic Algorithm,GA)是一种抽象于生物进化过程的
、基于自然选择和生物遗传机制的优化技术.
遗传算法的基本原理
在遗传算法的执行过程中,每一代有许多不同的种群个体(染色体
)同时存在。这些染色体中哪个保留(生存)、哪个淘汰(死亡),是根据
它们对环境的适应能力来决定的,适应性强的有更多的机会保留下来
。适应性强弱是通过计算适应性函数f(x)的值来判别的,这个值称为
适应值。适应值函数f(x)的构成与目标函数有密切关系,往往是目标
函数的变种。主要的遗传算子有如下几种:
1.选择(Selection)算子
又称复制(reproduction)、繁殖算子。选择是从种群中选择生命
力强的染色体,产生新种群的过程。选择的依据是每个染色体的适应
值大小,适应值越大,被选中的概率就越大,其子孙在下一代产生的个
数就越多。选择的方法根据不同的问题,采用不同的方案。最常见的
方法有比率法、排列法和比率排列法。
2.交叉(Crossover)算子
又称重组(recombination)、配对(breeding)算子。当许多染色
体相同或后代的染色体与上一代没有多大差别时,可通过染色体重组
来产生新一代染色体。染色体重组分两个步骤进行:首先,在新复制的
群体中随机选取两个染色体,每个染色体由多个位(基因)组成;然后,
沿着这两个染色体的基因随机取一个位置,二者互换从该位置起的末
尾部分基因。例如,有两个用二进制编码的个体A和B,长度L=5,A=a1a2
a3a4a5,B=b1b2b3b4b5。随机选择一个整数k∈[1,L-1],设k=4,经交叉
后变为:
A=a1a2a3|a4a5 A'=a1a2a3b4b5
B=b1b2b3|b4b5 B'=b1b2b3a4a5
遗传算法的有效性主要来自选择和交叉操作,尤其是交叉,在遗传
算法中起着核心作用。
3.变异(Mutation)算子
选择和交叉算子基本上完成了遗传算法的大部分搜索功能,而变
异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率
,随机改变字符串某个位置上的值。在二进制编码中,就是将0变成1,
将1变成0。变异发生的概率极低(一般取值在0.001～0.02之间)。它
本身是一种随机搜索,但与选择、交叉算子结合在一起,就能避免由复
制和交叉算子引起的某些信息的永久性丢失,从而保证了遗传算法的
有效性。
传算法是多学科结合与渗透的产物,已经发展成一种自组织、
自适应的综合技术,广泛应用在计算机科学、工程技术和社会科学等
领域。其研究工作主要集中在以下几个方面
1.基础理论
包括进一步发展遗传算法的数学基础,从理论和试验研究它们的
计算复杂性。在遗传算法中,群体规模和遗传算子的控制参数的选取
非常困难,但它们又是必不可少的试验参数。在这方面,已有一些具有
指导性的试验结果。遗传算法还有一个过早收敛的问题,怎样阻止过
早收敛也是人们正在研究的问题之一。
2.分布并行遗传算法
遗传算法在操作上具有高度的并行性,许多研究人员都在探索在
并行机和分布式系统上高效执行遗传算法的策略。对分布并行遗传算
法的研究表明,只要通过保持多个群体和恰当控制群体间的相互作用
来模拟并行执行过程,即使不使用并行计算机,也能提高算法的执行效
率。
3.分类系统
分类系统属于基于遗传算法的机器学习中的一类,包括一个简单
的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统
。分类系统被人们越来越多地应用在科学、工程和经济领域中,是目
前遗传算法研究中一个十分活跃的领域。
4.遗传神经网络
包括连接权、网络结构和学习规则的进化。遗传算法与神经网络
相结合,正成功地用于从时间序列分析来进行财政预算。在这些系统
中,训练信号是模糊的,数据是有噪声的,一般很难正确给出每个执行
的定量评价。如果采用遗传算法来学习,就能克服这些困难,显著提高
系统性能。Muhlenbein分析了多层感知机网络的局限性,并猜想下一
代神经网络将是遗传神经网络。
5.进化算法
模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。遗
传算法是其三种典型的算法之一,其余两种算法是进化规划(Evolutio
nary Programming,EP)和进化策略(Evolutio nary Strategies,ES)
。这三种算法是彼此独立地发展起来的。进化规划最早由美国的L.J.
Fogel、A.J.Owens和M.J.Walsh提出;进化策略则由德国的I.Rechenb
erg和H.P.Schwefel建立。
具体应用也很广，
我就拿它解决了好几个难题。
下面我给出我们校数学建模时的程序你分析一下就明白了。
#define Ins 35 /*指令数*/
#define Com 45/*部件数*/
#define Row 100
#define JCn 0*Row/*交叉的概率*/
#define FZn .15*Row
#define PY Row-JCn-FZn
#define times 1000 /*迭代次数*/
#define hyR .4*Ins/*交叉概率*/
#define Optnum 5 /*最优解的个数*/
#include "stdlib.h"
#include "time.h"
#include "stdio.h"
#include "conio.h"
unsigned char *A[Row+1]; /*遗传矩阵*/
unsigned char *Aimg[Row+1]; /*A的备份*/
unsigned long Aused[Row+1];
unsigned long Acomnum[Row+1];
unsigned long Ainsnum[Row+1];
unsigned long Opt[Optnum+1][Ins+1]; /*最优的解*/
unsigned long Optins[Optnum+1]; /*最优解的指令个数*/
double ada[Ins+1]; /*行适应度*/
char ins[Ins+1][Com+1]={{0},{0,4,8,20,31,44},{0,8,19,22,29,37},{0,2,16,34,33,32},
{0,7,11,35,30},{0,5,13,18,21},{0,1,7,9,23,25},
{0,3,5,6,14,24},{0,7,20,21,32,35},{0,9,15,20,45},
{0,6,10,39,42,43},{0,1,11,21,34,38},{0,2,4,18,22,37},
{0,6,17,25,36},{0,22,33,34,38},{0,2,10,20,37},
{0,9,24,29,39},{0,15,18,29,31},{0,4,42,44,45},
{0,13,23,26,39},{0,7,12,40,41},{0,12,16,19,28,35},
{0,6,23,27,45},{0,33,37,40,41},{0,3,17,19,36},
{0,16,33,44,45},{0,13,19,24,25},{0,2,3,5,8},
{0,4,7,9,12,43},{0,16,17,20,32},{0,28,33,34,36},
{0,10,23,25,27},{0,1,5,44,45},{0,11,15,18,43},
{0,7,14,22,36},{0,3,15,25,39}
};/*促使*/
char inslen[Ins+1]={0,15,80,30,12,7,19,32,12,45,36,57,78,65,53,34,48,46,32,26,22,26,19,17,22,10,30,82,73,66,55,24,46,37,77,9};/*指令长度*/
unsigned long step=0;
void iniA(void); /*初始化A*/
void adaRate(void); /*适应度*/
void judge(void); /*判断*/
void elim(void); /*选取:最优的五个解*/
void JC(void); /*交叉*/
void FZ1(void); /*复制*/
void PY1(void); /*变异*/
void back(void);
void showA(void); /*给出A*/
void showOpt(void); /*给出最优解*/
double rnd(void); /*给出0~1间的随机数*/
void main(void)
{randomize();
iniA();
while(1)
{adaRate();
judge();
elim();
if(step++>=times)
break;
JC();
FZ1();
PY1();
back();
}
showOpt();
}
void iniA(void)
{unsigned long i,j,knum=0;
for(i=1;i<=Row;i++)
{A[i]=(unsigned char *)malloc(sizeof(char)*(Ins+1));
Aimg[i]=(unsigned char *)malloc(sizeof(char)*(Ins+1));
}
for(i=1;i<=Row;i++)
{for(j=1;j<=Ins;j++)
{if(rnd()>0.5) A[i][j]=1;
else a[i][j]=0;
}
}
for(i=1;i<=Optnum;i++)
{for(j=1;j<=Ins;j++)
{Opt[i][j]=1;
Optins[i]+=inslen[j];
}
}
}
void adaRate(void)
{unsigned long i,j,k;
double insnum,comnum;
int iscom[Com+1]; /** 部件是否出现 **/
for(i=1;i<=Row;i++)
{ada[i]=insnum=comnum=0;
for(j=1;j<=Com;j++)
iscom[j]=0;
for(j=1;j<=Ins;j++)
if(A[i][j])
{insnum+=inslen[j];
for(k=1;k<=Com;k++)
iscom[ins[j][k]]=1;
}
for(j=1;j<=Com;j++)
if(iscom[j]) comnum+=1;
if(insnum)
ada[i]=comnum/insnum; /**适应度函数**/
else
ada[i]=0;
Acomnum[i]=comnum;
Ainsnum[i]=insnum;
}
}
void judge(void)
{
}
void elim(void)
{unsigned long i,j,k;
for(i=1;i<=Row;i++) /*检查是否有更优解*/
if(Acomnum[i]==Com)
{for(j=1;j<=Optnum;j++)
if(Ainsnum[i]<Optins[j])
{Optins[j]=Ainsnum[i];
for(k=1;k<=Ins;k++)
Opt[j][k]=A[i][k];
break;
}
}
}
void JC(void)
{unsigned long a,i,j,F,M; /* fsum 是行适应度的和 */
unsigned char used;
double fsum=0,f,m;
for(i=1;i<=Row;i++) /*初始化*/
{Aused[i]=0;
for(j=1;j<=Ins;j++)
Aimg[i][j]=0;
}
i=0;
while(i<JCn) /*这个while选取交叉的行*/
{a=random(Row)+1; /*因为random值域是从0到Row-1*/
used=0;
for(j=1;j<=i;j++)
if(Aused[j]==a)
used=1;
if(!used)
{Aused[++i]=a;
fsum+=ada[a];
}
}
for(i=1;i<=JCn;i++) /*这个for计算P(i)的值*/
ada[Aused[i]]/=fsum;
for(i=2;i<=JCn;i++) /*把P(i)值化为范围*/
ada[Aused[i]]+=ada[Aused[i-1]];
ada[(int)JCn]=1.0;
for(i=1;i<=JCn/2;i++)
{f=rnd();
for(j=1;j<=JCn;j++)
{if(ada[Aused[j]]>=f)
{M=F=j;
break;
}
}
while(M!=F)
{m=rnd();
for(j=1;j<=JCn;j++)
{if(ada[Aused[j]]>=m)
{M=j;
break;
}
}
}
for(j=1;j<=Ins;j++)
{Aimg[i*2-1][j]=A[M][j];
Aimg[i*2][j]=A[F][j];
}
}
for(i=1;i<=JCn/2;i++)
{for(j=1;j<=hyR;j++)
Aimg[i*2-1][j]=Aimg[i*2][(int)(Ins-hyR+j)];
for(j=1;j<=Ins-hyR;j++)
Aimg[i*2][j]=Aimg[i*2-1][(int)(hyR+j)];
}
for(i=1;i<=JCn;i++)
for(j=1;j<=Ins;j++)
A[Aused[i]][j]=Aimg[i][j];
}
void FZ1(void)
{unsigned long i=0,j,k,l,a;
unsigned char used;
while(i<FZn)
{a=random(Row)+1;
used=0;
for(j=1;j<=JCn+i;j++)
if(Aused[j]==a)
used=1;
if(!used) Aused[(int)((++i)+JCn)]=1;
}
}
void PY1(void)
{unsigned long i,b,a;
for(i=1;i<=Row;i++)
if(!Aused[i])
{b=a=random(Ins)+1;
while(b!=a)
b=random(Ins)+1;
A[i][a]=(rnd()>0.5);
A[i][b]=(rnd()>0.5);
}
}
void showA(void)
{unsigned long i,j,insnum;
for(i=1;i<=Row;i++)
{printf("No.%d: %.2f ",i,ada[i]);
insnum=0;
for(j=1;j<=Ins;j++)
if(A[i][j])
{printf("%d ",j);
insnum++;
}
printf("**%d\n",insnum);
getch();
}
}
void showOpt(void)
{unsigned long j;
{printf("Ins:%d ",Optins[1]);
for(j=1;j<=Ins;j++)
if(Opt[1][j])
printf("%d ",j);
printf("\n");
}getch();
}
double rnd(void)
{double j=rand(),k=RAND_MAX;
return(j/k);
}
void back(void)
{unsigned long i,j,a;
for(i=1;i<=Optnum;i++)
{a=random(Row)+1;
for(j=1;j<=Ins;j++)
A[a][j]=Opt[i][j];
}
}
顺便介绍一个好的网址给你：http://www.cs.gmu.edu/research/gag/ 遗传算法协会
Top
14 楼goldcattle（海边的云）回复于 2001-08-20 01:11:49 得分 0
上面那个程序写了我一个下午，同志们数学建模会死人的Top
15 楼yzslj（书生）回复于 2001-08-20 11:24:05 得分 0
谢谢Top
16 楼goldcattle（海边的云）回复于 2001-08-20 12:59:36 得分 0
呵呵别忘了加分就行了：）））Top
17 楼goldcattle（海边的云）回复于 2001-08-25 19:03:41 得分 0
我推荐一下matlab中的遗传算法和算法工具箱非常好用，在matlab大观园里有下载得 Top
18 楼Arter（阿蒂尔）回复于 2001-09-17 22:04:48 得分 0
GP/EC?
Top
19 楼jadedrip（翡翠水滴）回复于 2001-09-18 09:53:03 得分 0
to:goldcattle, 你那么想要分吗？我出的题，全部200开始，以后多注意我的问题吧，呵呵
不过我问问题的次数少了点，(:-)Top
