遗传算法（Genetic Algorithm，GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J. Holland教授于1975年首先提出的。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。

遗传算法的基本思想正是基于模仿生物界的遗传过程。它把问题的参数用基因代表。把问题的解用染色体代表，从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机继承了父代的最好特征，并在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优解。

1.遗传算法中的生物遗传学概念

遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故在这个算法中要用到各种进化和遗传学的概念。 首先给出遗传学概念、遗传算法概念和数学概念三者之间的对应关系：

序号 遗传学概念 遗传算法概念 数学概念
1 个体 要处理的基本对象 可行解
2 群体 个体的集合 被选定的一组可行解
3 染色体 个体的表現形式 可行解的编码
4 基因 染色体中的元素 编码中的元素
5 基因位 某一基因在染色体中的位置 元素在编码中的位置
6 适应值 个体对于环境的适应程度 可行解所对应的适应函数值
7 种群 选定的一组染色体或个体 选定的一组可行解
8 选择 从群体中选择优胜个体 保留或复制适应值大的个体
9 交叉 一组染色体对应基因段的交换 根据交叉原则产生一组新解
10 交叉概率 染色体对应基因段交换的概率 一般为0.65-0.90
11 变异 染色体水平上基因的变化 编码某些元素被改变
12 变异概率 染色体上基因变化的概率 一般为0.001-0.01
13 进化、适者生存 个体进行优胜劣汰的进化 适应函数值最优的可行解

遗传算法的步骤

遗传算法计算优化的操作过程如生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）。

遗传算法的基本步骤是：先把问题的解表示成“染色体”，以二进制或十进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解。然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。经过这样一代一代地进化，最后收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

下面给出遗传算法的具体步骤：

遗传算法有很多具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止。

案例

问题

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

这是一个旅行商问题。给我方基地编号为 0 , 目标依次编号为 $1,2, \cdots$, 100, 最后我方基地再重复编号为 101 (这样便于程序中计算)。距离矩阵 $D=\left(d_{i j}\right)_{102 \times 102}$, 其中 $d_{i j}$ 表示表示 $i, j$ 两点的距离, $i, j=0,1, \cdots, 101$, 这里 $D$ 为 实对称矩阵。则问题是求一个从点 0 出发, 走遍所有中间点, 到达点 101 的 一个最短路径。

上面问题中给定的是大地坐标 (经度和纬度), 必须求两点间的实际距 离。设 $A, B$ 两点的大地坐标分别为 $\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right)$ (其中 $x_{1}, x_{2}$ 为经度, $x_{2}, y_{2}$ 为纬度), 过 $A, B$ 两点的大圆的劣弧长即为两点的实际距离。以地心为坐标 原点 $O$, 以赤道平面为 $X O Y$ 平面, 以零度经线圈所在的平面为 $X O Z$ 平面建 立三维直角坐标系。则 $A, B$ 两点的直角坐标分别为 $$ \begin{aligned} &A\left(R \cos x_{1} \cos y_{1}, R \sin x_{1} \cos y_{1}, R \sin y_{1}\right), \\ &B\left(R \cos x_{2} \cos y_{2}, R \sin x_{2} \cos y_{2}, R \sin y_{2}\right), \end{aligned} $$ 其中 $R=6370 \mathrm{~km}$ 为地球半径。

$A, B$ 两点的实际距离 $$ d=R \arccos \left(\frac{\overrightarrow{\mathrm{OA}} \cdot \overrightarrow{\mathrm{OB}}}{|\overrightarrow{\mathrm{OA}}| \cdot|\overrightarrow{\mathrm{OB}}|}\right) $$ 化简得 $$ d=R \arccos \left[\cos \left(x_{1}-x_{2}\right) \cos y_{1} \cos y_{2}+\sin y_{1} \sin y_{2}\right] . $$

模型及算法

遗传算法求解的参数设定如下: 种群大小 $M=50$; 最大代数 $G=10$ 。交 叉率 $\boldsymbol{p}_{c}=1$, 交叉概率为 1 能保证种群的充分进化; 变异率 $\boldsymbol{p}_{m}=\mathbf{0 . 1}$, 一般而言，变异发生的可能性较小。

例如 设交叉点为第四个基因处，则 $s_{1}=\left[\begin{array}{lllllll}0, & 0.14 & 0.25, & 0.27, & 0.74, & 0.21, \cdots, 0.24, & 1\end{array}\right]$, 交叉操作的方式有很多种选择, 应该尽可能选取好的交叉方式, 保证子代能 继承父代的优良特性。

代码

import numpy as np
from numpy.random import randint, rand, shuffle
from matplotlib.pyplot import plot, show, rc
a=np.loadtxt("data/generic.txt")
xy,d=a[:,:2],a[:,2:]; # d为两两点之间的距离
N=len(xy)
w=50; g=10  #w为种群的个数，g为进化的代数
J=[]; 
for i in np.arange(w):
    c=np.arange(1,N-1); 
    shuffle(c) # 将c中的数据打乱顺序
    c1=np.r_[0,c,101]; 
    flag=1
    while flag>0:
        flag=0
        for m in np.arange(1,N-3): # 从1至倒数第3个位置之间挑选一个点
            for n in np.arange(m+1,N-2): # 在刚刚挑选的点至倒数第二个点之间再挑选一个点
                # 如果交换两组点的连接顺序，新的连接短于旧的连接
                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]]: 
                    c1[m+1:n+1]=c1[n:m:-1]; # 更新排布方式
                    flag=1
    c1[c1]=np.arange(N); 
    J.append(c1)
J=np.array(J)/(N-1)
for k in np.arange(g):
    A=J.copy()
    c1=np.arange(w); #w个个体
    shuffle(c1) #交叉操作的染色体配对组
    c2=randint(2,100,w)  #交叉点的数据，每个个体都选择一个交叉点
    for i in np.arange(0,w,2): # 
        temp=A[c1[i],c2[i]:N-1]  #保存中间变量
        A[c1[i],c2[i]:N-1]=A[c1[i+1],c2[i]:N-1]
        A[c1[i+1],c2[i]:N-1]=temp
    B=A.copy()
    by=[]  #初始化变异染色体的序号
    while len(by)<1: 
        by=np.where(rand(w)<0.1)
    by=by[0]; B=B[by,:]
    G=np.r_[J,A,B]
    ind=np.argsort(G,axis=1)  #把染色体翻译成0,1，…，101
    NN=G.shape[0]; 
    L=np.zeros(NN)
    for j in np.arange(NN):
        for i in np.arange(101):
            L[j]=L[j]+d[ind[j,i],ind[j,i+1]]
    ind2=np.argsort(L)
    J=G[ind2,:]
path=ind[ind2[0],:]; 
zL=L[ind2[0]]
xx=xy[path,0]; yy=xy[path,1]; rc('font',size=16)
plot(xx,yy,'-*'); show()  #画巡航路径
print("所求的巡航路径长度为：",zL)

参考资料