2 遗传算法

2.1 遗传算法简介

遗传算法是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：

（1）根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。

（2）对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数，适应度函数应为非负函数。

（3）确定进化参数群体规模$M$、交叉概率$P_c$、变异概率$P_m$、进化终止条件。

为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时
间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可能根据找出近似最优是否满足精度要求来确定。表 1 列出了生物遗传概念在遗传算法中的对应关系。

生物遗传概念在遗传算法中的对应关系

2.2 模型及算法

求解的遗传算法的参数设定如下：

种群大小：$M=50$

最大代（一代代）数：$G=1000$

交叉率：$P_c=1$，交叉概率为1能保证种群的充分进化。

变异率：$P_m=0.1$，一般而言，变异发生的可能性较小。

（1）编码策略

采用十进制编码，用随机数列$\omega_1\omega_2{\cdots}\omega_{102}$作为染色体，其中$0 \lt \omega_i \lt 1(i=2,3,\cdots,101)$，$\omega_1=0$，$\omega_{102}=1$:每一个随机序列都和种群中的一个个体相对应，例如一个9城市问题的一个染色体为

[0.23， 0.82， 0.45， 0.74， 0.87， 0.11， 0.56， 0.69， 0.78]

其中编码位置$i$代表城市$i$，位置$i$的随机数表示城市$i$在巡回中的顺序，我们将这些随机数按升序排列得到如下巡回：

6-1-3-7-8-4-9-2-5

（2）初始种群

我们先利用经典的近似算法——改良圈算法求得一个较好的初始种群。即对于初始圈$C=\pi_1{\cdots}\pi_{u-1}\pi_u\pi_{u+1}{\cdots}\pi_{v-1}\pi_{v}\pi_{v+1}{\cdots}\pi_{102},2 \le u \lt v \le 101, 2 \le \pi_u \lt \pi_v \le 101$，交换$u$与$v$之间的顺序，此时的新路径为：

$$ \pi_1{\cdots}\pi_{u-1}\pi_v\pi_{v-1}{\cdots}\pi_{u+1}\pi_u\pi_{v+1}{\cdots}\pi_{102} $$

记$\Delta f=(d_{\pi_{u-1}\pi_v}+d_{\pi_u\pi_{v+1}})-(d_{\pi_{u-1}\pi_u}+d_{\pi_v\pi_{v+1}})$,若$\Delta f \lt 0$，则以新的路径修改旧的路径，直到不能修改为止

（3）目标函数

目标函数为侦察所有目标的路径长度，适应度函数就取为目标函数。我们要求

$$ \min f(\pi_1,\pi_2,\cdots,\pi_{102})=\sum^{101}_{i=1}d_{\pi_i\pi_{i+1}}\\ $$

（4）交叉操作

这里使用单点交叉，设计如下：对于选定的连个父代个体：$f_1=\omega_1\omega_2\cdots\omega_{102},f_2={\omega'_1}{\omega'_2}{\cdots}{\omega'_{102}}$，我们随机地选取第$t$个基因处为交叉点，则经过交叉运算后得到的子代编码为$s_1$和$s_2$，$s_1$的基因由$f_1$的前$t$个基因和$f_2$的后102-$t$个基因构成，$s_2$的基因由$f_2$的前$t$个基因和$f_2$的后102-$t$个基因构成，例如：

$$ f_1=[0,\quad 0.14,\quad 0.25, \quad 0.27,|0.29,\quad 0.54,\cdots,0.19,\quad 1]\\ f_2=[0,\quad 0.23,\quad 0.44, \quad 0.56,|0.74,\quad 0.21,\cdots,0.24,\quad 1]\\ $$

设交叉点为第四个基因处，则

$$ s_1=[0,\quad 0.14,\quad 0.25, \quad 0.27,|0.74,\quad 0.54,\cdots,0.19,\quad 1]\\ s_2=[0,\quad 0.23,\quad 0.44, \quad 0.56,|0.29,\quad 0.21,\cdots,0.24,\quad 1]\\ $$

交叉操作的方式有很多种选择，也应当尽可能选取较好的交叉方式，保证子代能够继承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。

（5）变异操作

变异也是实现群体多样性的一种手段，同时也是全局寻优的保证。具体设计如下，按照给定的变异率， 对选定变异的个体， 随机地取三个整数，满足$1 \lt u \lt v \lt w \lt 102 $，把$u,v$之间(包括$u$和$v$)的基因段插到$w$后面。

（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=[x y];               %形成经纬度矩阵
d1=[70,40];             %本地基地
sj0=[d1;sj;d1];         %加入本地基地称为102*2矩阵
%距离矩阵 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);  %给出100的随机序列
 c1=[1,c+1,102];   %给出给定起点与终点，但是中间部分为随机序列
 flag=1;           %给个标志，初始化为1
 while flag>0      %若标志大于0
 flag=0;           %标志置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;           %标志置1
 c1(m+1:n)=c1(n:-1:m+1);    %如果新的序列距离比旧的小则更换，进入下一次迭代
 end
 end
 end
 end
 J(k,c1)=1:102;   %记录50次迭代下的新序列
end
J=J/102;           %除以102来算出概率
J(:,1)=0;J(:,102)=1;   %第一列元素强转为0，第102列元素强转为1
rand('state',sum(clock));       %确定初始化随机器
%遗传算法实现过程
A=J;                
for k=1:dai %产生 0～1 间随机数列进行编码
 B=A;       %B=A=J
 c=randperm(w);  %产生0~50的随机序列
%交配产生子代 B
 for i=1:2:w   %步长为2，从1到50
 F=2+floor(100*rand(1));  %产生102之间的两个数字——经纬度
 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);   %找到50个数中0到1之间小于0.1的序列（随机产生）
if length(by)==0          %如果都没有
 by=floor(w*rand(1))+1;   %向下取整得到0到50之间的一个整数
end
C=A(by,:);                %对取到的数组对应数字做矩阵行切片
L3=length(by);            %确定取到数组的长度
for j=1:L3                %循环
 bw=2+floor(100*rand(1,3));     %取到三个从0到102的数
 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];   %A是基于随机选取的最小距离准则，B是在A的基础上通过单点交叉的交配得到，C是在A的基础上变异产生
 TL=size(G,1);   %给出G的行数
 %在父代和子代中选择优良品种作为新的父代
 [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     %计时结束
xx=sj0(path,1);yy=sj0(path,2);   %随机序列距离矩阵的经纬度选取
plot(xx,yy,'-o')  %画出飞机运行图像

得到巡航路径为下图：