启发式寻解
原理讲解
启发寻解:遗传算法
作者 : 老饼 日期 : 2022-09-14 19:22:08 更新 : 2022-09-15 09:13:08


   一.算法背景   


遗传算法思想借鉴于生物遗传进化机制。
生物在多代种群迭代中,优胜劣态,最终种群越来越优秀。这种机制可以迁移到我们的数学求最优值问题上来。
种群个体就相当于我们的解,目标函数就是衡量这个个体优秀程度的指标。所以我们可以借鉴生物是怎么进化到一个优秀个体,来让我们的解,也进化(寻找)到一个更优秀的解。


  二.算法流程   

下面直接给出现有主流程(原理后面讲解):
1.初始化种群(初始化gn个解)
2.迭代T轮:
---------2.1.染色体交换,交换完后基因变异(解与解之间先进行部分交换,交换完后再抽个别解作单独的随机调整)
---------2.2.计算适应度,生成轮盘(按适应度占比,越大的占轮盘面积越大)赌轮盘选择下一代:仍抽gn个,本轮最优必须进入下一轮,剩余gn-1个则随机抽取,每次抽取先生成一个随机数,随机数指向轮盘哪个位置就抽哪个(有可能重复抽到同一个)。(以每个解的目标函数的倒数作为轮盘概率,形成0-1的数组,生成gn个随机数,根据随机数选择新的解群:每个随机数在数组哪个区间,就选哪个解(其中本轮最优解必须选中))
遗传算法是一种思想,对于具体的问题,我们需要定义好:
(1) 染色体交换的方式(即解与解之间如何进行部分交换)
(2) 基因变异的方式(即单个解如何作出随机改变)
(3) 适应度的设计(将目标函数值转换为大于0,且越优秀值越大的数)


  三.例子与代码(TSP问题)

(一)  问题:旅行商问题:


有N个城市 ,要求穿过每个城市,最终回到出发城市,问:寻找一条路径,使旅行总距离最小。


(二)  问题转化为数学问题 


我们的x可以表示成以下形式: x = [0 1 5 3 2 4], 它代表先到城市0,再到城市1,再到5.....最后由4回到0.
而总距离就是按这顺序行走的总距离。
即求一 个1到N的组合x,令总距离F最小。


(三) 算法设计


用遗传算法,需要定义好该问题的染色体交换方式(解与解之间如何进行部分交换)与基因变异的方式(即单个解如何作出随机改变)。

对本问题我们可以设计如下

(1)染色体交换方式: 
将解群两两随机配对,每一对之间(设为a,b)以如下方式交换:
设a=[0,1,5,3,2,4],b=[1,2,5,0,3,4],先随机抽出a的一个片段a_piece,
假设a_piece= [5,3,2],再在b中找出 a_piece 的排序 b_piece=[2,5,3],
将b_piece替换到a,将a_piece替换到b,得到:a=[0,1,2,5,3,4],b=[1,5,3,0,2,4]
(2)基因变异方式:
设a=[0,1,5,3,2,4], 
先随机抽出a的一个片段a_piece,假设a_piece= [5,3,2],
将a_piece翻转( [2,3,5])后再回代a,得到a=[0,1,2,3,5,4]
(3)适应度设计:
本问题的目标函数一定是大于0的,我们简单的设为 
即可(F是目标函数的值),就可以达到函数值越小,适应度越大的效果。

作完这三个设计后,只需按上述所说的算法流程,即可。


(四)  代码


代码明细详见:《遗传算法求解TSP.py》
运行结果:

可见,程序已到找一条较短的路径。



  四.例子与代码(数值函数求极值)  


(一)  问题:函数求最小值问题:

求  x=[x_1,x_2]为何值时,

取得最小值。( 易知道,y的最小值在 处取得,为0.)
下面展示用遗传算法寻找解的具体过程,看结果是否与我们预期一致。


(二)  问题转化为数学问题 

遗传算法在数值问题上会相对麻烦,
因为遗传算法是建立在基因片段的概念上得到的算法,解的形式需要是数组形式。

对数值问题我们可以巧妙的将数值转为2进制,
就成了[0,1,0,1,1,0,1,0,0]这样的数组形式。
该 过程也叫“基因编码”。转回10进制数值时,
则叫“基因解码”,反正,整个过程听起来非常的叼。



(三)算法设计:


仍是遗传算法三个重要设计:
染色体交换方式,基因变异方式,适应度设计。

对本问题我们可以设计如下
(1)染色体交换方式: 
将解群两两随机配对,每一对之间(设为a,b)以如下方式交换:
随机抽取k个位置,将a和b这k个位置的值对调。(也可以随机抽取一个连续片段,对调a,b这部分片段。)
我们这里有x1和x2, 则:a的x1(x2)与b的x1(x2)按以上方式对调,
(2)基因变异方式:
设a.x1=[0,1,0,1,1,0], 
随机抽个位置,对其取反。例如抽到3,而a.x1的第3位为0,把它变为1.
同样对a.x2进行变异。
(3)适应度设计:
函数值有可能为负数、正数、0,需要精心设计一下。

作完这三个设计后,只需按上述所说的算法流程,即可。



(四).代码与结果:


代码明细详见:《遗传算法求解函数最小值.py》
结果如下:
第0代:最优F=701736.6000976562
第1代:最优F=77232.60009765625
第2代:最优F=23506.60009765625
第3代:最优F=3561.31884765625
....
第50代:最优F=0.00323486328125
第51代:最优F=0.00079345703125
...
第99代:最优F=6.103515625e-05
第100代:最优F=6.103515625e-05
h_best_F= 6.103515625e-05
h_best_x= [2.        2.9921875]


可见,结果与预期的【2,3】几乎一致。


   五.算法理解   

我们知道,寻解算法主要三个问题:
1.产生能倾向下降的新解,
2.跳出局部最优,
3.最终阶段收敛到局部最优。


可以如下看待遗传算法:


生产新解的方式:
解与解之间交换部分片段的方式生产新解,赌轮盘方式使用目标函数引导解群往更优秀的方向产生下一代解。
跳出局部最优:
通过无脑变异,给予算法跳出局部最优的机会。生物的变异通常是有害的,但它却是种群进化更优秀,存活更长久的一个希望。
最终阶段收敛到局部最优:
随着种群进化,最后阶段无法再有优秀解时,解群趋向同质化,交换片段将无法再产生太大的差异,从而使解群逐渐趋向局部最优解。


总结


遗传算法仅是一种思想,
染色体交叉,变异,适应度设计等对算法的效果影响是非常大的。
以上的理解给我们指明方向,变异是为了跳出局部最优,
交叉和赌轮盘是为了在概率上生成更优秀的解,

在实际问题中,需要牢牢抓住思想,
尝试不同的交叉,变异方法。


联系老饼