遗传算法|遗传算法（GA）原理以及matlab与python实现 python|matlab|算法|matlab

1.概述遗传算法，模拟达尔文进化论的自然选择和遗传学机理的生物进化过程的计算模型，一种选择不断选择优良个体的算法。谈到遗传，想想自然界动物遗传是怎么来的，自然主要过程包括染色体的选择，交叉，变异，这些操作后，保证了以后的个体基本上是最优的，那么以后再继续这样下去就可以一直最优了。
解决的问题：
主要还是解决优化类问题，尤其是那种不能直接解出来的很复杂的问题。
2.技术 2.1遗传编码（1）二进制编码
二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。
优点：编、解码操作简单，遗传、交叉便于实现
缺点：长度大
（2）序列编码
求解TSP问题时，使用序列编码更为合理。假如有10个城市的TSP问题，城市序号为{1,2，3，…，10}，则编码串为1 2 3 … 10。
（3）其他编码方法
格雷码、浮点数编码、符号编码、多参数编码等。
2.2适应函数（评价函数）适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。
适应度函数的选择对优化速度和平滑性都有影响。这也正是适应度函数选择的意义，选的好的话就可以加快优化效果。
对于优化问题，需要通过建立适应函数与目标函数的映射关系，保证映射后的适应值是非负的，而且目标函数的优化方向应对应于适应值的增大方向。
针对进化过程中关于遗传操作的控制的需要，选择函数变换

文章图片

需要针对进化过程，制定合适的选择策略，使得遗传算法获得最大的进化能力和最佳的搜索效果。
详解与其他的适应度变化方法参考目标函数和适应度函数内容
我们对个体的适应度调整的目的有两个：
一是维持个体之间的合理差距，加速竞争。
二是避免个体之间的差距过大，限制竞争。
对于多目标优化可以参考遗传算法关于多目标优化python（详解）。
2.3遗传算子遗传算子一般包括了复制（reproduction或选择selection）、杂交（crossover或重组recombination）、变异（mutation）三种基本形式。
2.3.1选择算子
通过选择算子模拟“优胜劣汰”，适应度高的个体被遗传到下一代的概率较大，适应度低的算子被遗传到下一代的概率较小。
常用的选择算法：
（1）轮盘赌选择法（适应值比例选择），即令
文章图片

表示群体的适应度函数值的总和，fi表示群体中第i个染色体的适应度值，则它产生后代的能力刚好为其适应度值所占的份额。
文章图片

（2）Blotzmann选择
在种群的进化过程中，不同阶段需要不同的选择压力，早期压力较小，后期压力较大。

其中f（a）表示适应度函数值
（3）联赛规则
从当前种群中随机选择一定数量的个体，将其中适应值最大的个体保存到下一代。
（4）精英选择
如果下一代群体的最佳个体适应值小于当前群体最佳个体的适应值，则将当前群体的最佳个体或者适应值大于下一代最佳个体适应值的多个个体直接复制到下一代，随机替换掉或者替换掉最差的下一代群体中的相应数据的个体。这种遗传算法一般被称为e—GA。
2.3.2交叉算子
交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体；
交叉运算是遗传算法区别于其他进化算法的重要特征，是产生新个体的主要方法。
在交叉之前需要将群体中的个体进行配对，一般采取随机配对原则。
二进制编码、十进制编码常用：

单点交叉
双点交叉（多点交叉，交叉点数越多，个体的结构被破坏的可能性越大，一般不采用多点交叉的方式）

实数编码常用：

双个体算术交叉：x1’=ax1+（1-a）x2，x2’=ax2+（1-a）x1，其中a∈（0,1）
多个体算术交叉

组合优化常用：

部分映射交叉：随机选取两个点，交换两个点之间的片段，若两点外的基因与换过来的基因重合，则替换
次序交叉
基于位置的交叉

2.3.3变异算子
遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。
就遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但也是必不可少的一个运算步骤，它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索，从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。

二进制或十进制的编码：单位置或多位置替换式变异
实数编码：扰动式变异：包括互换操作（两随机位置互换）、逆序操作（两随机位置间的数字逆转）、插入操作（讲随机选择的某个点插入到串的不同随机位置）

2.4运行参数研究参数的选取和控制是GA研究的重要内容之一。

编码长度。编码长度取决于问题解的精度，精度越高，编码越长；
种群规模N。规模小，收敛快但降低了种群的多样性，N=20-200；
交叉概率C。较大的交叉概率容易破坏种群中已形成的优良结构，使搜索具有太大随机性；较小的交叉概率发现新个体的速度太慢，一般取值为P_c=0.6-0.99
变异概率M。变异概率太小，则变异操作产生新个体的能力和抑制早熟现象的能力会较差；变异概率过高随机性过大，一般建议取值范围为0.005～0.01
终止进化代数。算法运行结束的条件之一，一般取100～1000，或者可以判断收敛程度来判断（判断基因位的相似程度）
代沟G。用于控制每代中种群被替换的比例。
尺度窗口W。作出目标值到适配值的调整。
选择策略S。通常为两种，其一为纯选择；其二为保优策略。

3.基本流程 1）种群初始化。通过随机生成的方式来创造一个种群，一般该种群的数量为100~500，采用二进制将一个染色体(解)编码为基因型，随后用进制转化，将二进制的基因型转化成十进制的表现型，或者反之亦可。
2）适应度计算(种群评估)。
3）选择(复制)操作。根据种群中个体的适应度大小，通过轮盘赌等方式将适应度高的个体从当前种群中选择出来。其中轮盘赌即是与适应度成正比的概率来确定各个个体遗传到下一代群体中的数量。
具体步骤如下：
(1)首先计算出所有个体的适应度总和Σfi。
(2)其次计算出每个个体的相对适应度大小fi/Σfi，类似于softmax。
(3)再产生一个0到1之间的随机数，依据随机数出现在上述哪个概率区域内来确定各个个体被选中的次数。
4）交叉(交配)运算。该步骤是遗传算法中产生新的个体的主要操作过程，它用一定的交配概率阈值(pc，一般是0.4到0.99)来控制是否采取单点交叉，多点交叉等方式生成新的交叉个体。
具体步骤如下：
【遗传算法|遗传算法（GA）原理以及matlab与python实现】(1)先对群体随机配对。
(2)再随机设定交叉点的位置。
(3)再互换配对染色体间的部分基因。
5）变异运算。该步骤是产生新的个体的另一种操作。一般先随机产生变异点，再根据变异概率阈值(pm,一般是0.0001到0.1)将变异点的原有基因取反。
6）终止判断。如果满足条件(迭代次数，一般是200~500)则终止算法，否则返回step2。

4.matlab代码使用matlab求解一个一元函数的最大值的代码链接点击这里
5.python代码使用python求解一个二元函数的最大值的代码链接点击这里