• 遗传算法的应用

  遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。

  遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。

• 遗传算法定义

  遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出。该算法模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型，它采用简单的编码技术来表示各种复杂的结构，通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。

  遗传算法的操作对象是种群。其中每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。

• 许多应用问题的结构很复杂，但可以化为简单的位串形式编码表示：

  将问题结构变换为位串形式编码表示的过程叫编码；

  而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。

  把位串形式编码表示叫染色体。

• 遗传算法最常用的编码方法是二进制编码：

  二进制编码的最大缺点之一是长度较大，对很多问题用其他编码方法可能更有利。其他编码方法主要有：浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。

• 适应度函数

  为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数（fitness function）。

  适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。

• 遗传操作

  交叉，就是互换两个染色体某些位上的基因。

  变异，就是改变染色体某个(些)位上的基因。

简单遗传算法的遗传操作主要有三种:

选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。

交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。

变异操作的简单方式是改变数码串的某个位置上的数码。二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0。

改进的遗传算法大量扩充了遗传操作，以达到更高的效率

• 遗传算法一般步骤

1. 定义一个目标（适应度）函数；

2. 将可行解群体在一定的约束条件下初始化，每一个可行解用一个向量 X 来编码（染色体），向量的分量代表基因，它对应可行解的某一决策变量；

3. 计算群体中每条染色体xi（i＝1，2，…，n）所对应的目标函数值（适应值）Fi，按Fi的大小来评价该可行解的好坏；

4. 以优胜劣汰的机制，将适应值差的染色体淘汰掉，对幸存的染色体根据其适应值的好坏，按概率随机选择，进行繁殖，形成新的群体；

5. 通过杂交和变异的操作，产生子代。杂交是随机选择两条染色体（双亲），将某一点或多点的基因互换而产生两个新个体，变异是基因中的某一点或多点发生突变；

6. 对子代群体重复步骤(3)～(5)的操作，进行新一轮遗传进化过程，直到迭代收敛（适应值趋稳定）即找到了最优解或准最优解。

image

• 算法中的一些控制参数

  交叉率(crossover rate)是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc，取值范围一般为0.4～0.99。

  变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.0001～0.1

• 遗传算法的特点与优势

1. 遗传算法一般是直接在解空间搜索, 而不像图搜索那样一般是在问题空间搜索, 最后才找到解。

2. 遗传算法的搜索随机地始于搜索空间的一个点集, 而不像图搜索那样固定地始于搜索空间的初始节点或终止节点, 所以遗传算法是一种随机搜索算法。

3. 遗传算法总是在寻找优解, 而不像图搜索那样并非总是要求优解, 而一般是设法尽快找到解, 所以遗传算法又是一种优化搜索算法。

4. 遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索, 适合大规模并行计算,而且这种种群到种群的搜索有能力跳出局部最优解。

5. 遗传算法的适用性强, 除需知适应度函数外, 几乎不需要其他的先验知识。

6. 遗传算法长于全局搜索, 它不受搜索空间的限制性假设的约束,不要求连续性, 能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。

• 举列：

** 利用遗传算法求解区间［0,31］上的二次函数y=x^2的最大值。**

** 解：**

(1) 设定种群规模,编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:

    s1= 13 (01101),  

    s2= 24 (11000)， 

    s3= 8 (01000),    

    s4= 19 (10011) 

(2) 定义适应度函数，取适应度函数：f (x)=x2

(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,直到适应度最高的个体(即31（11111）)出现为止。

首先计算种群S1中各个体

    s1= 13(01101),    

    s2= 24(11000) ，    

    s3= 8(01000),    

    s4= 19(10011)

求适应度f (si) ，得

 f (s1) = f(13) = 132 = 169  ，

 f (s2) = f(24) = 242 = 576

 f (s3) = f(8) = 82 = 64 ，         

 f (s4) = f(19) = 192 = 361

再计算种群S1中各个体的选择概率。

选择概率的计算公式为

image

由此可求得

    P(s1) = P(13) = 0.14  ，  

    P(s2) = P(24) = 0.49 

    P(s3) = P(8) = 0.06 ，   

    P(s4) = P(19) = 0.31

赌轮选择法

[图片上传中...(image-48e274-1633750784838-6)]

在算法中赌轮选择法可用下面的子过程来模拟:

① 在［0, 1］区间内产生一个均匀分布的随机数r。

② 若r≤q1,则染色体x1被选中。

③ 若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。

其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为

image

设从区间［0, 1］中产生4个随机数如下:

    r1 = 0.450126,   

    r2 = 0.110347  ，  

    r3 = 0.572496,   

    r4 = 0.98503 

[图片上传中...(image-9ba7ac-1633750784838-4)]

于是，经复制得群体：

    s1’ =11000（24）,  

    s2’ =01101（13） ， 

    s3’ =11000（24）,  

    s4’ =10011（19）

交叉

设交叉率pc=100%，即S1中的全体染色体都参加交叉运算。

    设s1’与s2’配对，s3’与s4’配对。分别交换后两位基因，得新染色体：

    s1’’=11001（25）,  

    s2’’=01100（12），  

    s3’’=11011（27）,  

    s4’’=10000（16）

变异

设变异率pm=0.001。 这样，群体S1中共有  5×4×0.001=0.02  位基因可以变异。 0.02位显然不足1位，所以本轮遗传操作不做变异。

    于是，得到第二代种群S2：

    s1=11001（25）, 

    s2=01100（12） ， 

    s3=11011（27）, 

    s4=10000（16）

image

假设这一轮选择-复制操作中，种群S2中的 4个染色体都被选中，则得到群体：

     s1’=11001（25）,  

    s2’= 01100（12），  

    s3’=11011（27）,  

    s4’= 10000（16） 

做交叉运算，让s1’与s2’，s3’与s4’ 分别交换后三位基因，得

    s1’’ =11100（28）, 

    s2’’ = 01001（9）， 

    s3’’ =11000（24）, 

    s4’’ = 10011（19） 

这一轮仍然不会发生变异。

于是，得第三代种群S3：

    s1=11100（28）, 

    s2=01001（9），  

    s3=11000（24）, 

    s4=10011（19）

[图片上传中...(image-b1498d-1633750784838-2)]

设这一轮的选择-复制结果为：

    s1’=11100（28）,  

    s2’=11100（28）， 

    s3’=11000（24）,  

    s4’=10011（19）

做交叉运算，让s1’与s4’，s2’与s3’ 分别交换后两位基因，得

    s1’’=11111（31）, 

    s2’’=11100（28），  

    s3’’=11000（24）, 

    s4’’=10000（16） 

这一轮仍然不会发生变异。

于是，得第四代种群S4：

    s1=11111（31）,  

    s2=11100（28），  

    s3=11000（24）,  

    s4=10000（16）

显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于是，遗传操作终止，将染色体“11111”作为最终结果输出。

然后，将染色体“11111”解码为表现型，即得所求的最优解：31。

将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。

[图片上传中...(image-bd675d-1633750784838-1)]

• 遗传算法之父——John Holland（1929.2.2-2015.8.9）

  密歇根大学心理学系、电机工程和计算机科学系教授；

  提出“复杂自适应系统”理论；

  美国圣菲研究所的创始人之一；

  复杂性科学领域的先驱者和杰出代表人物之一；

  美国“麦克阿瑟天才奖”、IEEE Nerual Network Society颁发的先锋奖；

  《自然与人工系统的适应性》《隐次序》《涌现》

[图片上传中...(image-ad6563-1633750784837-0)]

基因组分析 微信公众号推出 《50个经典算法讲解》系列文章， 第2篇文章 《遗传算法》，争取每周更新一篇干货帖子。

关注微信公众号 ，**转发 **给同学和同事，您的认可，是对我最大的支持 ，任何问题，后台可以留言。