组合优化算法-现代优化算法 （二）： 遗传算法 及应用举例
遗传算法简介遗传算法（Genetic Algorithms，简称 GA）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目 标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，终 得到优解或准优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、 根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色 体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化， 直到满足进化终止条件。其实现方法如下：
（1） 根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示 可行解域的每一解。
（2） 对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。
（3） 确定进化参数群体规模M 、交叉概率 https://private.codecogs.com/gif.latex?%5Cdpi%7B150%7D%20%5Csmall%20p_%7Bc%7D、变异概率 https://private.codecogs.com/gif.latex?%5Cdpi%7B150%7D%20%5Csmall%20p_%7Bm%7D 、进化终止条件。
为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时 间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进 化结束，也可能根据找出近似优是否满足精度要求来确定。表 2 列出了生物遗传概念 在遗传算法中的对应关系。
https://img-blog.csdnimg.cn/20190422195842460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
2 模型及算法 我们用遗传算法研究 1.2 中的问题。（1）研究 1.2 中同样的问题。https://img-blog.csdnimg.cn/20190429112220109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
https://img-blog.csdnimg.cn/20190429112254104.png
我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目 标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。
https://img-blog.csdnimg.cn/20190429112343350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
问题（2）我方有三个基地，经度、纬度分别为（70,40），（72,45），（68,48）。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标， 怎样划分任务，才能使时间最短，且任务比较均衡。
https://img-blog.csdnimg.cn/20190422195939261.png
（2） 初始种群
https://img-blog.csdnimg.cn/20190429104800737.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
（3） 目标函数
https://img-blog.csdnimg.cn/20190429104828410.png
（4） 交叉操作
https://img-blog.csdnimg.cn/2019042910485274.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继 承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。（5） 变异操作https://img-blog.csdnimg.cn/20190429104938530.png
（6） 选择采用确定性的选择策略，也就是说选择目标函数值最小的 M 个个体进化到下一代，这 样可以保证父代的优良特性被保存下来。2.3 模型求解及结论编写 MATLAB 程序如下：
tic
clc,clear
load sj.txt %加载敌方 100 个目标的数据
x=sj(:,1:2:8);x=x(:);
y=sj(:,2:2:8);y=y(:);
sj=;
d1=;
sj0=;
%距离矩阵 d
sj=sj0*pi/180;
d=zeros(102);
for i=1:101
for j=i+1:102
temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
d(i,j)=6370*acos(temp);
end
end
d=d+d';L=102;w=50;dai=100;
%通过改良圈算法选取优良父代 A
for k=1:w
c=randperm(100);
c1=;
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:102;
end
J=J/102;
J(:,1)=0;J(:,102)=1;
rand('state',sum(clock));
%遗传算法实现过程
A=J;
for k=1:dai %产生 0～1 间随机数列进行编码
B=A;
c=randperm(w);
%交配产生子代 B
for i=1:2:w
F=2+floor(100*rand(1));
temp=B(c(i),F:102);
B(c(i),F:102)=B(c(i+1),F:102);
B(c(i+1),F:102)=temp;
end
%变异产生子代 C
by=find(rand(1,w)<0.1);
if length(by)==0
by=floor(w*rand(1))+1;
end
C=A(by,:);
L3=length(by);
for j=1:L3
bw=2+floor(100*rand(1,3));
bw=sort(bw);
C(j,:)=C(j,);
end
G=;
TL=size(G,1);
%在父代和子代中选择优良品种作为新的父代
=sort(G,2);temp(1:TL)=0;
for j=1:TL
for i=1:101
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
end
end
=sort(temp);
A=G(IZ(1:w),:);
end
path=IX(IZ(1),:)
long=DZ(1)
toc
xx=sj0(path,1);yy=sj0(path,2);
plot(xx,yy,'-o')
计算结果为 40 小时左右。其中的一个巡航路径如图 2 所示。
https://img-blog.csdnimg.cn/20190429105613336.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5ODMxMTYz,size_16,color_FFFFFF,t_70
————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89459503
感谢分享
页:
[1]