遗传算法求解yx2副本.docx
《遗传算法求解yx2副本.docx》由会员分享，可在线阅读，更多相关《遗传算法求解yx2副本.docx（19页珍藏版）》请在冰点文库上搜索。
遗传算法求解yx2副本
初始遗传算法及一个简单的例子
遗传算法（GeneticAlgorithms,GA）是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。
下面我以一个实例来详细表述遗传算法的过程
例：
求下述二元函数的最大值：
1、编码：
用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。
因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。
在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。
反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。
编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。
迄今为止人们已经设计出了许多种不同的编码方法。
基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。
每个个体的染色体中所包含的数字的个数L称为染色体的长度或称为符号串的长度。
一般染色体的长度L为一固定的数，如本例的编码为
s1=10010（17）
s2=11110（30）
s3=10101（21）
s4=00100（4）
表示四个个体，该个体的染色体长度L=5。
2、个体适应度函数
在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。
个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。
基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。
为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。
这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。
如所求解的问题为：
直接设定个体的适应度函数值就等于相应的目标函数值，即
.
3、遗传算子
（1）比例选择：
选择或称复制，建立在对个体适应度进行评价的基础之上。
其作用是从当前群体中选择出一些比较优良的个体，并将其复制到下一代群体中。
基本遗传算法采用比例选择的方法，所谓比例选择，是指个体在选择操作中被选中的概率与该个体的适应度大小成正比。
本例选择概率的计算公式为：
其中f为适度函数；
为个体
的适应值，显然，适应值最高的个体被随机选定的概率就越大，被选择的次数就越多，从而被繁殖的次数也就越多。
（2）单点交叉。
单点交叉又称简单交叉，是遗传算法所使用的交叉操作方法。
选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。
如：
交叉前：
100|10
101|01
交叉后：
100|01
101|10
（3）基本位变异。
基本位变异石最简单和最基本的变异操作，也是基本遗传算法中所使用的变异操作方法。
对于基本遗传算法中用二进制编码符号串所表示的个体，对需要进行变异操作的某一基因，若原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为1，则变异操作将其变为0.
基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。
如：
变异前：
1001|0
变异后：
1001|1
（4）基本遗传算法的运行参数
本例中指定四个基本参数
种群大小：
popsize
最大世代数maxgeneration
交叉率pc
变异率pm
至于遗传算法的终止条件，还可以利用某种判定准则，当判定出群体已经进化成熟且不再有进化趋势时就可终止算法的运行过程。
如连续几代个体平均适应度的差异小于某一个极小的值；或者群体中所有个体适应度的方差小于某一个极小的值。
这4个参数对遗传算法的搜索结果及搜索效率都有一定的影响，目前尚无合理选择它们的理论根据在遗传算法的实际应用中，往往需要经过多次的试算后才能确定出这些参数合理的取值范围或取值大小
4、遗传算法的应用步骤如下：
遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的领域和种类。
对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法。
第一步：
建立优化模型，即确定出目标函数、决策变量及各种约束条件以及数学描述形式或量化方法。
第二步：
确定表示可行解的染色体编码方法，也即确定出个体的基因型x及遗传算法的搜索空间。
第三步：
确定解码方法，即确定出个体基因型x到个体表现型x的对应关系或转换方法。
第四步：
确定个体适应度的量化评价方法，即确定出由目标函数值
到个体适应度
的转换规则。
第五步：
设计遗传操作方法，即确定出选择运算、交叉运算、变异运算等具体操作方法。
第六步：
确定遗传算法的有关运行参数，即确定出遗传算法的种群大小（popsize）、最大世代数（maxgeneration）、交叉率（pc）、变异率（pm）等参数。
由上述构造步骤可以看出，可行解的编码方法、遗传操作的设计是构造遗传算法时需要考虑的两个主要问题，也是设计遗传算法时的两个关键步骤。
对不同的优化问题需要使用不同的编码方法和不同的遗传操作，它们与所求解的具体问题密切相关，因而对所求解问题的理解程度是遗传算法应用成功与否的关键。
本例c语言代码
////////////////////////////////////
//遗传算法解决y=x2问题
//编译环境vc++6.0
//声明：
部分代码来自网
#include
#include
#include
#include
#definePOPSIZE500//种群大小
#definechromlength5//染色体长
intpopsize;//种群大小
intmaxgeneration;//最大世代数
doublepc=0.0;//交叉率
doublepm=0.0;//变异率
structindividual//定义染色体个体结构体
{
intchrom[chromlength];//定义染色体二进制表达形式，editbyppme将char转为int
doublevalue;//染色体的值
doublefitness;//染色体的适应值
};
intgeneration;//当前执行的世代数
intbest_index;//最好的染色体索引序号
intworst_index;//最差的染色体索引序号
structindividualbestindividual;//最佳染色体个体
structindividualworstindividual;//最差染色体个体
structindividualcurrentbest;//当前最好的染色体个体currentbest
structindividualpopulation[POPSIZE];//种群数组
//函数声明
voidgenerateinitialpopulation（）;//ok-初始化当代种群
voidgeneratenextpopulation（）;//产生下一代种群
voidevaluatepopulation（）;//评价种群
voidcalculateobjectfitness（）;//计算种群适应度
doubledecodechromosome（int,int）;//染色体解码
voidfindbestandworstindividual（）;//寻找最好的和最坏的染色体个体
voidperformevolution（）;//进行演变进化
voidselectoperator（）;//选择操作
voidcrossoveroperator（）;//交换操作
voidmutationoperator（）;//变异操作
voidinput（）;//输入接口
voidoutputtextreport（）;//输出文字报告
voidmain（）//主函数
{
inti;
srand（（unsigned）time（NULL））;//强制类型转化，以当前时间戳定义随机数种子
printf（"本程序为求函数y=x*x的最大值\n"）;
generation=0;//初始化generation当前执行的代
input（）;//初始化种群大小、交叉率、变异率
/*editbyppme*/
//调试用。
。
。
。
。
显示input（）结果
printf（"种群规模（popsize）:
%d;\n最大世代数（maxgeneration）%d;\n交叉率（pc）%f;变异率（pm）%f\n\n",popsize,maxgeneration,pc,pm）;
/*editbyppme*/
generateinitialpopulation（）;//产生初始化种群
evaluatepopulation（）;//评价当前种群,（A.计算种群/个体的适应度;B.找出最好和最差的个体）
while（generation{
generation++;
generatenextpopulation（）;//生成子代种群（A.选择;B.交叉;C.变异）
evaluatepopulation（）;//评价新生子代种群
performevolution（）;//进行子代进化
outputtextreport（）;//输入当代最终种群
}
printf（"\n"）;
printf（"统计结果:
"）;
printf（"\n"）;
printf（"最大函数值等于：
%f\n",currentbest.fitness）;
printf（"其染色体编码为：
"）;
//计算currentbest的value
for（i=0;iprintf（"%d",currentbest.chrom[i]）;
printf（"\n"）;
}
voidgenerateinitialpopulation（）//种群初始化
{
inti,j;
srand（（unsigned）time（NULL））;//强制类型转化，以当前时间戳定义随机数种子
for（i=0;i{
for（j=0;j{
population[i].chrom[j]=（rand（）%10<5）?
0:
1;//rand（）%10随机产生0-9的整数
//,小于5标注0,否则标注1
}
}
//调试显示初始化结果
printf（"显示初始化结果:
\n"）;
for（i=0;i{
for（j=0;j{
printf（"%d",population[i].chrom[j]）;
}
printf（"\n"）;
}
}
voidgeneratenextpopulation（）//生成下一代
{
selectoperator（）;
crossoveroperator（）;
mutationoperator（）;
}
voidevaluatepopulation（）//评价种群?
?
?
{
calculateobjectfitness（）;//计算种群?
个体的适应度
findbestandworstindividual（）;//赵到最好和最差的染色体个体
}
voidcalculateobjectfitness（）//计算染色体个体适应值和适应度
{
inti;
intj;
printf（"calculateobjectfitnessisexecuting!
\n"）;
for（i=0;i{
doubletemp;
temp=decodechromosome（i,chromlength）;//计算个体适应值
population[i].value=（double）temp;
population[i].fitness=population[i].value*population[i].value;
}
//调试用
printf（"显示当前种群结果:
\n"）;
for（i=0;i{
for（j=0;j{
printf（"%d",population[i].chrom[j]）;
}
printf（"%lf",population[i].value）;
printf（"%lf",population[i].fitness）;
printf（"\n"）;
}
}
doubledecodechromosome（intpop_index,intlength）//给染色体解码
{
inti;
doubledecimal=0;
for（i=length;i>=0;i--）
decimal+=population[pop_index].chrom[i]*pow（2,i）;//遍历染色体二进制编码,
return（decimal）;//并计算出其10进制的value值
}
voidfindbestandworstindividual（）//求最佳个体和最差个体
{
inti;
doublesum=0.0;
bestindividual=population[0];
worstindividual=population[0];
for（i=1;i{
if（population[i].fitness>bestindividual.fitness）//依次比较,找出最佳个体
{
bestindividual=population[i];
best_index=i;
}
elseif（population[i].fitness{
worstindividual=population[i];
worst_index=i;
}
sum+=population[i].fitness;//sum存放种群总体适应值
}//for
if（generation==0）
{
currentbest=bestindividual;//第一代最好的暂时存放在currentbest
}
else
{
if（bestindividual.fitness>=currentbest.fitness）//第n代最好的，通过比较大于以往最好个体的话，
{//暂时存放在currentbest
currentbest=bestindividual;
}
}
}
voidperformevolution（）//演示评价结果
{
if（bestindividual.fitness>currentbest.fitness）
{
currentbest=population[best_index];
}
else
{
population[worst_index]=currentbest;
}
}
voidselectoperator（）//比例选择算法
{
inti,index;
doublep,sum=0.0;//p存放随机概率，sum存放个体适应率和累计适应率
doublecfitness[POPSIZE];//当代种群染色体个体的适应率
structindividualnewpopulation[POPSIZE];//新种群
srand（（unsigned）time（NULL））;//种下随机种子
for（i=0;i{
sum+=population[i].fitness;//sum存放种群适应值总和
}
for（i=0;icfitness[i]=population[i].fitness/sum;//cfitness[]=fitness/sum得到个体适应率
}
for（i=1;icfitness[i]=cfitness[i-1]+cfitness[i];//cfitness[]=cfitness[i-1]+cfitness[i]得到种群
}//累计适应率
for（i=0;i{
p=rand（）%1000/1000.0;//得到千分位小数
index=0;
while（p>cfitness[index]）
{
index++;
}
newpopulation[i]=population[index];//选出的个体组成新的一代,暂时存放于newpopulation[]中
}
for（i=0;ipopulation[i]=newpopulation[i];//全局变量populaiton存放新的种群（有重复的值）
}
}
voidcrossoveroperator（）//交叉算法
{
inti,j;
intindex[POPSIZE];
intpoint,temp;
doublep;
srand（（unsigned）time（NULL））;//种下随机种子
for（i=0;iindex[i]=i;
}
for（i=0;ipoint=rand（）%（popsize-i）;//打乱种群顺序
temp=index[i];
index[i]=index[point+i];
index[point+i]=temp;
}
for（i=0;ip=rand（）%1000/1000.0;
if（ppoint=rand（）%（chromlength-1）+1;
for（j=point;jtemp=population[index[i]].chrom[j];
population[index[i]].chrom[j]=population[index[i+1]].chrom[j];
population[index[i+1]].chrom[j]=temp;
}
}
}
}
voidmutationoperator（）//变异操作
{
inti,j;
doublep;
srand（（unsigned）time（NULL））;//种下随机种子
for（i=0;ifor（j=0;jp=rand（）%1000/1000.0;
if（ppopulation[i].chrom[j]=（population[i].chrom[j]==0）?
1:
0;
}
}
}
}
voidinput（）//数据输入
{
printf（"初始化全局变量:
\n"）;
printf（"种群大小（4-500偶数）：
"）;
scanf（"%d",&popsize）;//输入种群大小，必须为偶数
if（（popsize%2）!
=0）
{
printf（"种群大小已设置为偶数\n"）;
popsize++;
};
printf（"最大世代数（10-300）：
"）;//输入最大世代数
scanf（"%d",&maxgeneration）;
printf（"交叉率（0.2-1.0）：
"）;//输入交叉率
scanf（"%lf",&pc）;
printf（"变异率（0.00）:
"）;//输入变异率
scanf（"%lf",&pm）;
}
voidoutputtextreport（）//数据输出
{
inti;
doublesum;
doubleaverage;
sum=0.0;
for（i=0;i{
sum+=population[i].value;
}
average=sum/popsize;
printf（"当前世代=%d\n当前世代染色体平均值=%f\n当前世代染色体最高值=%f\n",generation,average,population[best_index].value）;
}
运行结果：
/*
本程序为求函数y=x*x的最大值
初始化全局变量:
种群大小（4-500偶数）：
4
最大世代数（10-300）：
5
交叉率（0.2-1.0）：
0.9
变异率（0.00）:
0.01
种群规模（popsize）:
4;
最大世代数（maxgeneration）5;
交叉率（pc）0.900000;变异率（pm）0.010000
显示初始化结果:
01001
11111
00010
01111
calculateobjectfitnessisexecuting!
显示当前种
升级会员 