遗传算法原理及其python实现

遗传算法简介

遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对一些常规的优化算法,通常能够较快地获得较好的优化结果

达尔文进化论的原理概括总结如下：

1. 变异：种群中单个样本的特征(性状，属性)可能会有所不同，这导致了样本彼此之间有一定程度的差异
2. 遗传：某些特征可以遗传给其后代。导致后代与双亲样本具有一定程度的相似性
3. 选择：种群通常在给定的环境中争夺资源。更适应环境的个体在生存方面更具优势，因此会产生更多的后代

遗传算法的基本概念

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到一些生物遗传学知识，下面是我们将会用一些术语：

由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到一些生物遗传学知识，下面是我们将会用一些术语：

• 基因型 (Genotype) ：在自然界中，通过基因型表征繁殖，繁殖和突变，基因型是组成染色体的一组基因的集合。
• 种群 (Population)： 可行解域，根据适应度函数选择的一组解
• 染色体(Chromosome)： 对每个可行解的编码
• 变异(Mutation)： 突变操作的目的是定期随机更新种群，将新模式引入染色体，并鼓励在解空间的未知区域中进行搜索。
• 选择 (Selection): 保留适应度函数的函数值优的解
• 交叉 (CrossOver): 将两个可行解内的组分随机交叉，产生新解
• 适应性(Fitness): 适应度函数的函数值

算法流程图

初始化原始种群

遗传算法可以同时优化一批解 (种群)， 我们在[-2, 2]的区间内随机生成10个点作为我们的初始种群

选择

选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。个体被选中的概率跟适应度值有关，个体适应度值越高，被选中的概率越大，常用的选择算法为轮盘赌算法。若种群数位 M M M, 个体 i i i的适应度为 f i f_i fi/span>，则个体 i i i被选中的概率为:
p i = f i ∑ k = 1 M f k p_i = frac{f_i}{sum_{k=1}^Mf_k} pi/span>=∑k=1M/span>fk/span>fi/span>/span>
当个体选择的概率给定后，产生[0,1]之间均匀随机数来决定哪个个体参加交配。若个体的选择概率大，则有机会被多次选中，那么它的遗传基因就会在种群中扩大；若个体的选择概率小，则被淘汰的可能性会大。

交叉

交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父串的优秀特征遗传给子串，从而产生新的优秀个体。
这里在染色体中间进行交叉。

来源：Johnson0722