交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体,将两者的部分码值进行交换。
变异操作的简单方式是改变数码串的某个位置上的数码。
4、遗传算法基本步骤
1、初始化种群;
2、计算种群上每个个体的适应度值;
3、按由个体适应度值所决定的某个规则选择将进入下一代的个体
4、按概率PC进行交叉操作
5、按概率PC进行变异操作
6、若没有满足某种停止条件,则转步骤2),否则进入下一步;
7、输入种群中适应度值最优的染色体作为问题的满足解或最优解
5、基本遗传算法框图
基本遗传算法框图
I=i+1
是
否
是
否
复制变异
交叉
6、遗传算法求解举例
利用遗传算法求解函数:
的最大值,其中,x∈[-1,2]|。
7、编程实现
constintMAX=4194304。
constintMIN=0。
#include
#include//产生随机数要用到time(int>,以使每次产生的数不同。
#include//sin(float>在这儿。
usingnamespacestd。
constdoublepi=3.1415926。
classIndividuality{
private:
intchromosome。
//染色体
public:
voidset(intchromosome>
{this->chromosome=chromosome。
}
Individualityoperator=(Individualityc>
{this->chromosome=c.chromosome。
return*this。
}
booloperator==(Individualityc>
{returnthis->chromosome==c.chromosome。
}
floatresolve(>//通过染色体取得x的值.
{return-1.0+(float>chromosome*3.0/(MAX-1>。
}
floatevaluate(>//求f(>
{
returnresolve(>*(float>sin(10*pi*resolve(>>+1.0。
}
voidprint(>{
cout<<'\t'。
for(intj=21。
j>=0。
j-->//以下循环是在以二进制串的形式打印染色体
if((1<&chromosome>cout<<'1'。
elsecout<<'0'。
cout<<"\t\tx="<<<"\tf(x>="<<}
//以下是对当前个体进行变异的操作
Individualityvariate(>
{
inti=rand(>%21+1。
this->chromosome^=1<
return*this。
}
//以下是两个个体进行交叉,并且返回两个新个体的操作
voidcrisscross(Individualityprnt1,Individualityprnt2,Individuality&child1,Individuality&child2>{
inti=rand(>%21+1。
inttemp1=prnt1.chromosome。
inttemp2=prnt2.chromosome。
inttemp=0。
for(。
i<22。
i++>
temp+=1<
temp1&=temp。
temp2&=temp。
prnt1.chromosome&=~temp。
prnt2.chromosome&=~temp。
prnt1.chromosome|=temp2。
prnt2.chromosome|=temp1。
child1=prnt1。
child2=prnt2。
}
}。
constintPOP_SIZE=200。
//建立一个种群的类,并且有固定的大小
//每次遗传,选出f(x>的排名在前50%的个体进行遗传<排名通过希尔排序实现),都会有约1%的个体变异,10%的个体发生交叉遗传,其余的直接遗传。
每次遗传都记录下本次f(x>为最大的个体Max。
遗传150次,如果过程中发现已有30代的Max一直不变了,说明已达到最优,基本不需要再遗传了,所以提前跳出循环。
classPopulation{
private:
Individualityind[POP_SIZE]。
public:
Population(>{
for(inti=0。
ii++>
ind[i].set((((double>rand(>/(double>RAND_MAX>*MAX+MIN>>。
}
voidshellSort(>{
intgap,i,j。
Individualitytemp。
for(gap=POP_SIZE/2。
gap>0。
gap/=2>
for(i=gap。
ii++>
for(j=i-gap。
j>=0&&ind[j].evaluate(>。
j-=gap>
{
temp=ind[j]。
ind[j]=ind[j+gap]。
ind[j+gap]=temp。
}
}
voidinherit(>{
Population:
:
shellSort(>。
constintNT=POP_SIZE/2。
intnc=(rand(>%(POP_SIZE/10>+(POP_SIZE/4>>/2。
intnv=rand(>%(POP_SIZE/100+1>+(POP_SIZE/100>。
inti,n1,n2。
Individualitytemp[NT]。
for(i=0。
ii++>
temp[i]=ind[i]。
for(i=0。
ii++>{
n1=rand(>%NT。
ind[i]=temp[n1].variate(>。
}
for(i=nv。
ii+=2>{
n1=rand(>%NT。
n2=rand(>%NT。
Individualitytemp1,temp2。
temp->crisscross(temp[n1],temp[n2],temp1,temp2>。
ind[i]=temp1。
ind[i+1]=temp2。
}
for(i=nv+nc*2。
ii++>{
n1=rand(>%NT。
ind[i]=temp[n1]。
}
}
IndividualitygetMax(>{
Individualitymax=ind[0]。
for(inti=0。
ii++>{
if(ind[i+1].evaluate(>>ind[i].evaluate(>>max=ind[i+1]。
}
returnmax。
}
voidtraverse(>{
for(inti=0。
ii++>
ind[i].print(>。
cout<}
}。
intmain(>{
srand((unsigned>time(NULL>>。
Populationa。
a.traverse(>。
intcount=0。
intgen=0。
for(inti=0。
i<150。
i++>{
Individualitytemp=a.getMax(>。
a.inherit(>。
if(a.getMax(>==temp>count++。
if(count>30>break。
a.traverse(>。
gen++。
}
cout<<"Themaxis:
\n"。
a.getMax(>.print(>。
cout<<"After"<return0。
}
三、实验结果结论
这是迭代60次之后的结果,求得的最大值是2.85027,此时的x为1.85054
这是迭代54次之后的结果,求得的最大值是2.85027,此时的x为1.85059
结论:
传统的搜索方法由于其应用的局限性,在某些情况下可能搜索到局部最优点,而不能达到全局最优点。
利用遗传算法搜索函数最优点的方法极大地提高了搜索全局最优点的准确性,有效地避免了组合爆炸地产生。
因此,遗传算法在求解复杂的优化问题中具有广泛的应用前景。
四、参考文献
主要参考文献:
[1]蔡自兴徐光祐.人工智能及其应用.北京:
清华大学出版社,2009。
[2]王小平,曹立明.遗传算法-理论、应用与软件实现.西安:
西安交通大学出版社,2002。
[3]Schmitt,LotharM(2001>,遗传算法理论,TheoreticalComputerScience(259>,pp.1-61
[4]陈国良等,遗传算法及其应用,北京:
人了邮电出版社,1996.
[5]蒋冬初,遗传算法及其在函数优化问题中的应用研究,毕业论文,2004
[6]维基百科http:
//zh.wikipedia.org/zh/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95
[7]XX百科
申明:
所有资料为本人收集整理,仅限个人学习使用,勿做商业用途。