正文 字体大小： 中
算法设计：关于遗传算法的研究 [整理] (2010-06-12 10:49:13)
标签： 算法设计 遗传算法 基本原理 算法思想 研究 源代码 it 分类： 算法之道
关于遗传算法的研究
---July、06.12。
------------------
网络上一大堆关于此问题的文章，但大都是你抄我的，而后我抄你的。
没有自己的思维和想法。
----------------------------------------------------------------------
遗传算法的原理
遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。
-----------------------------------------
遗传算法的目的
典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：
考虑对于一群长度为L的二进制编码bi，i＝1，2，…，n；有
bi∈{0,1}L
给定目标函数f，有f(bi)，并且
0<f(bi)<∞
同时
f(bi)≠f(bi+1)
求满足下式
max{f(bi)|bi∈{0,1}L} 的bi。
//很明显，遗传算法是一种最优化方法，它通过进化和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的串bi处，即求出最优解。
------------------------------------------------
遗传算法的基本原理
长度为L的n个二进制串bi(i＝1，2，…，n)组成了遗传算法的初解群，也称为初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对群体执行的操作有三种：
1．选择(Selection)
这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。
2．交叉(Crossover)
这是在选中用于繁殖下一代的个体中，对两个不同的个体的相同位置的基因进行交换，从而产生新的个体。
3．变异(Mutation)
这是在选中的个体中，对个体中的某些基因执行异向转化。在串bi中，如果某位基因为1，产生变异时就是把它变成0；反亦反之。
--------------------------------------------------------
遗传算法思想：
(1) 初始化群体;
(2) 计算群体上每个个体的适应度值;
(3) 按由个体适应度值所决定的某个规则选择将进入下一代的个体;
(4) 按概率Pc进行交叉操作;
(5) 按概率Pc进行突变操作;
(6) 没有满足某种停止条件，则转第(2)步，否则进入(7)。
(7) 输出种群中适应度值最优的染色体作为问题的满意解或最优解。
程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。
---- ----------------------------------------------------------
遗传算法的步骤和意义
1．初始化
选择一个群体，即选择一个串或个体的集合bi，i=1，2，...n。这个初始的群体也就是问题假设解的集合。一般取n＝30-160。
通常以随机方法产生串或个体的集合bi,i＝1，2，...n。问题的最优解将通过这些初始假设解进化而求出。
2．选择
根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
给出目标函数f，则f(bi)称为个体bi的适应度。以
f(bi)
P{选中bi}=------------------*n
求和f(bj)(j=1....n)
为选中bi为下一代个体的次数。
显然．从上式可知：
(1)适应度较高的个体，繁殖下一代的数目较多。
(2)适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。
这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选择出和最优解较接近的中间解。
3．交叉
对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率P。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。
例如有个体
S1=100101
S2=010111
选择它们的左边3位进行交叉操作，则有
S1=010101
S2=100111
一般而言，交叉幌宰P。取值为0.25—0.75。
4．变异
根据生物遗传中基因变异的原理，以变异概率Pm对某些个体的某些位执行变异。在变异时，对执行变异的串的对应位求反，即把1变为0，把0变为1。变异概率Pm与生物变异极小的情况一致，所以，Pm的取值较小，一般取0.01-0.2。
例如有个体S＝101011。
对其的第1，4位置的基因进行变异，则有
S'=001111
单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠变异产生新的个体。也就是说，变异增加了全局优化的特质。
5．全局最优收敛(Convergence to the global optimum)
当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到第2步即选择操作处继续循环执行。
------------------------------------------------------------------------------------------------------
遗传算法问题的具体设计与研究
#define
popsize
100
//种群密度
#define
length1
10
#define
length2
10
//基因大小
#define
chromlength
length1+length2
//染色体大小
int
maxgeneration=100;
//遗传的总代数
double
pc=0.3;
//交叉位概率
double
pm=0.05;
//变异概率
struct
individual
//定义个体形状
{
char
chrom[chromlength+1];
//染色体
double
value;
//FG(x)值
double
fitness;
//适配值
};
int
generation;
//每一次计算代数
int
best_index;
//最佳值
struct individual
bestindividual;
//最佳个体
struct individual
currentbest;
struct individual
population[popsize]; //种群
void
generateinitialpopulation(void);
//初始化编码函数：对每一个体（总数100）的染色体的每一个二进制位（总为10位）
//用random(10)随机产生一个0~9之间的整数，判断，小于5这一位为 ” 0 ”，大于5则为 ” 1 ”。
void generatenextpopulation(void); //生成下一代基因的函数：选择，交叉，变异。
void evaluatepopulation(void);
//统计函数：计算每一个体的FG(x)值，适配值，并找出每一代种群中的最佳值与最差值。
long decodechromosome(char*, int,
int);
//解码函数：将20位无符号的二进制数解码成两个有符号的十进制数。
void calculateobjectvalue(void); //计算每一个体中的“FG(x)值函数。
void calculatefitnessvalue(void); //计算每一个体的适配值函数。
void findbestandworstindividual(void); //找出每一代中的最佳值与最差值函数
void performevolution(void); //保留最大适配值
void selectionoperator(void); //选择复制函数
void crossoveroperator(void); //交叉函数
void mutationoperator(void); //变异函数
void outputtextreport(FILE *fp1, FILE *fp2); //输出函数
void
main(void)
//主程序开始
{
FILE *fp1, *fp2;
fp1=fopen("show1.txt",
"w");
//显示输出结果
fp2=fopen("show2.txt", "w");
generation=0;
//从第0代开始
generateinitialpopulation();
//初始化随机产生100个个体
evaluatepopulation();
//统计
while
(generation<maxgeneration)
//继续计算直到最大代数
{
generation++;
generatenextpopulation();
evaluatepopulation();
performevolution();
outputtextreport(fp1,
fp2);
}
}
void
calculateobjectvalue(void);
//计算每一个体中的“FG(x)值函数：将染色体解码（调用解码函数）得出x1、x2值代入FG(x)公式中得出FG(x)值。
{
int i;
long temp1, temp2;
double x1, x2;
for(i=0;i<popsize;i++)
{
temp1=decodechromosome(population[i].chrom,
0, length1);
temp2=decodechromosome(population[i].chrom,
length1, length2);
x1=10.24*temp1/1023.0-5.12;
x2=10.24*temp2/1023.0-5.12;
population[i].value=(1+(x1+x2+1)*(x1+x2+1)*(19-14*x1+3*x1*x1-14*x2+6*x1*x2+3*x2*x2))*(30+(2*x1-3*x2)*(2*x1-3*x2)*(18-32*x1+12*x1*x1+48*x2-36*x1*x2+27*x2*x2));
}
}
void selectionoperator(void)
//选择函数：利用轮盘赌法选择个体
{
int i, index;
double p, sum=0.0;
double cfitness[popsize];
struct individual newpopulation[popsize];
for(i=0;i<popsize;i++)
sum+=population[i].fitness;
//计算总的适配值
for(i=0;i<popsize;i++)
cfitness[i]=population[i].fitness/sum;
//计算每一个体适配值复制的概率
for(i=1;i<popsize;i++)
cfitness[i]= cfitness[i-1]+
cfitness[i];
for(i=0;i<popsize;i++)
{
p=rand( )%1000/1000.0;
index=0;
while
(p>cfitness[index])
//随机生成数p若大于复制概率，
index++;
//就进行复制，经选择后复制生成
newpopulation[i]=population[index];
//子代*/
}
for(i=0;i<popsize;i++)
population[i]=newpopulation[i];
//将子代赋值给计算的这一代
}
void
crossoveroperator(void)
//交叉函数：对复制后的个体按交叉概率pc实施交叉操作
{
int i, j;
int index[popsize];
int point, temp;
double p;
char ch;
for(i=0;i<popsize;i++)
index[i]=i;
for(i=0;i<popsize;i++)
//随机配对
{
point=random(popsize-i);
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for(i=0;i<popsize-1;i+=2)
{
p=rand()%1000/1000.0;
if(p<pc)
//交叉：生成随机值p与pc相比较，小于pc值便交叉，实现了pc的作用。
{
point=random(chromlength-1)+1;
for(j=point;j<chromlength;j++)
{
ch=population[index[i]].chrom[j];
//产生一个20以内的随机数point，
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j]=ch;
}
}
}
}
void
mutationoperator(void)
//变异函数
{
int i, j;
double p;
for(i=0;i<popsize;i++)
for(j=0;j<chromlength;j++)
{
p=rand()%1000/1000.0;
if(p<pm)
//变异：生成随机值p与pm相比较，小于pm值则由
”0 ” 变成 ” 1 ” 或由 ” 1 ” 变成 ” 0 ”，实现了pm的作用。
population[i].chrom[j]=(population[i].chrom[j]=='0')?'1':'0';
}
}
//有待进一步研究中。July、06.12。
分享
顶
阅读┊ ┊ ┊┊ ┊打印┊
已投稿到：
排行榜 圈子
加载中，请稍候......
前一篇：排序问题：直接插入排序的算法思想 [原创]
后一篇：排序问题：选择排序算法思想 [原创]
评论 重要提示：警惕虚假中奖信息 带你的博客进入新时代 关注每日最热门博客
发评论 Qing时代来临，不容错过 这里有属于你的小清新 关注每日最热门博客
登录名： 密码： 找回密码 注册
昵 称：
验证码： 请点击后输入验证码
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。
< 前一篇排序问题：直接插入排序的算法思想 [原创]
后一篇 >排序问题：选择排序算法思想 [原创]
