查看: 3331|回复: 0

组合优化算法-现代优化算法（四）：改进的遗传算法

[复制链接]

字体大小: 正常放大

浅夏110

542 主题	15 听众	1万积分

TA的每日心情

	开心 2020-11-14 17:15

签到天数: 74 天

[LV.6]常住居民II

群组: 2019美赛冲刺课程

群组: 站长地区赛培训

群组: 2019考研数学桃子老师

群组: 2018教师培训（呼伦贝

群组: 2019考研数学站长系列

电梯直达

1^#

发表于 2020-5-22 15:31 |只看该作者 |正序浏览

|招呼Ta 关注Ta |邮箱已经成功绑定

无人机航路规划问题实际上是一个组合优化问题，是优化理论中的 NP—hard 问题。因为其解空间不连续，解邻域表达困难，所以难以用通常的算法求解。遗传算法作为现代优化算法之一[1]，其主要特点是对非线性极值问题能以概率 1 跳出局部最优解，找到全局最优解。而遗传算法这种跳出局部最优寻找全局最优特性都基于算法中的交叉和变异。在传统遗传算法的结构中，变异操作在交叉操作基础上进行，强调的是交叉作用，认为变异只是一个生物学背景机制[2]。在具体交叉操作中，人们通常采用断点交叉法（段交叉）多点交叉与均匀交叉，其中断点交叉是指随机地在基因序列中选择一个断点，然后交换双亲上断点右端的所有染色体。在变异操作中，变异算子一般是用 Guassian 分布的随机变异来实现[3,4]。近年来，也有学者尝试用 Cauchy 分布的随机序列来实现变异[5], 希望通过 Cauchy 分布宽大的两翼特性实现更大范围的变异，以利于找到全局最优解。[6]从理论上分析了采用 Cauchy 分布随机变异进化算法的局部收敛性。[7]进一步把二者结合起来, 采用两种分布的线性叠加，但仿真结果显示，算法改进效果并不十分明显。文献[8]将生物进化看成是随机性加上反馈，并指出其中的随机性主要是由系统的内在因素所引起，而不是由外部环境的随机扰动所造成。而混沌系统在其混沌域中表现为随机性，它是确定系统内部随机性的反映，不同于外在的随机特性。

本文根据以上特点对基于求解航路规划的遗传算法进行改进，首先将变异操作从交叉操作中分离出来，使其成为独立的并列于交叉的寻优操作，在具体遗传操作中，混沌与遗传操作联系在一起，在交叉操作中，以“门当户对”原则进行个体的配对，利用混沌序列确定交叉点，实行强度最弱的单点交叉，以确保算法收敛精度，削弱和避免寻优抖振问题；在变异操作中，利用混沌序列对染色体中多个基因进行变异，以避免算法早熟。

下面我们研究 1.2 中同样的问题。

我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为 1000 公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。

2）我方有三个基地，经度、纬度分别为（70,40），（72,45），（68,48）。假设我方所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标，怎样划分任务，才能使时间最短，且任务比较均衡。

2 模型及算法
与标准的遗传算法相比，我们做了如下的两点改进。

（1）交叉操作

很明显这种单点交叉对原来的解改动很小，这可以削弱避免遗传算法在组合优化应用中产生的寻优抖振问题，可以提高算法收敛精度。

（2）变异操作
变异也是实现群体多样性的一种手段，是跳出局部最优，全局寻优的重要保证。在本文具体变异算子设计如下，首先根据给定的变异率(本文选为 0.02)，随机地取两个在 2 到 101 之间的整数，对这两个数对应位置的基因进行变异，具体变异以当前的基因值为初值利用混沌序列 x(n +1) = 4x(n)(1− x(n)) 进行适当次数的迭代，得到变异后新的基因值，从而得到新的染色体。

3 仿真结果对比及算法性能分析
计算的 MATLAB 程序如下：

tic
clc,clear
load sj.txt %加载敌方 100 个目标的数据
x=sj(:,1:2:8);x=x(

;
y=sj(:,2:2:8);y=y(

;
sj=[x y];
d1=[70,40];
sj=[d1;sj;d1];
%距离矩阵 d
sj=sj*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=[1,c+1,102];
flag=1;
while flag>0
      flag=0;
      for m=1

-3
for n=m+2

-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;
%交配产生子代 B
for i=1:2:w
      ch0=rand;ch(1)=4*ch0*(1-ch0);
      for j=2:50
         ch(j)=4*ch(j-1)*(1-ch(j-1));
      end
      ch=2+floor(100*ch);
      temp=B(i,ch);
      B(i,ch)=B(i+1,ch);
      B(i+1,ch)=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

3
   bw=2+floor(100*rand(1,3));
   bw=sort(bw);
   C(j,

=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
end
G=[A;B;C];
TL=size(G,1);
%在父代和子代中选择优良品种作为新的父代
[dd,IX]=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
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),

;
end
path=IX(IZ(1),

long=DZ(1)
toc

在仿真试验中，我们对文中航路规划问题分别利用断点交叉和换位变异结合的遗传算法，多点交叉和移位变异结合的遗传算法[10]和文中提出的改进算法进行求解比较。表 1 是各种算法种群规模（ M = 50）和迭代次数（G = 100 ）都相同时连续 20 次求解的平均值（公里），算法平均运算时间（秒）。

本文从算法结构到具体的遗传操作都进行了改进，其中变异操作从交叉操作中分离出来，使得遗传算法也可以通过并行计算实现，提高算法实现效率。其次改进后的算法，分别采用变化强度不同的交叉操作和变异操作，其中交叉操作采用强度最弱的单点交叉，保证了算法收敛精度，削弱和避免算法因交叉强度大而产生的寻优抖振问题。当然单一的单点交叉很容易使算法早熟，文中采用较大强度的多个基因变异正好解决早熟问题。从仿真结果可以看到改进后的算法效果较为明显。

————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_29831163/article/details/89672986

zan