遗传算法概念:
基于达尔文的进化论,物竞天择,适者生存;认为生物总是向着更加贴合于环境的方向进化;通过各种基因
的遗传、杂交、变异、复制等手段,慢慢使整个种群更加贴合于自然环境;遗传算法也是模拟生物的遗传、
杂交、变异、复制手段逐渐进化为最优解!
名词概念解析:
基因和染色体:
染色体在数学建模上可以看作是可行解,例如 3x+4y+5z<100,它的可行解为[1,2,3]、[1,3,2]、[3,2,1],那么
这个可行解就是它的染色体。每一个染色体有无数个基因控制,所以在这些可行解中,里面的每一元素称之
为基因。
适应度函数:
在自然界中,生物的进化总是遵循优胜略汰,适者生存;一些适应不了环境的个体和染色体逐渐被淘汰,而
那些基因强大,能够很好的适应环境的个体和染色体则被保留和遗传;同样遗传算法 中的适应度函数就扮演
者这个 优胜略汰,适者生存 的角色,在运行过程中,会进行多次迭代,每一迭代都会产生多个染色体即可行
解,适应度函数会为每一个染色体打分,适应度高的保留,适应度低的淘汰,这样会使整个解种群的染色体
更加优良。更加贴近环境。
交叉:
遗传算法每一次迭代都会产生n条染色体,我们称之为进化,每一次进化所需要的染色体从哪来,这里就要引
入交叉的概念,可以理解为交配;交叉过程需要选择两条染色体,一个充当母亲,一个充当父亲;将这两条
染色体从某一结点切开,再组合在一起,组成一个新的染色体;这样新染色体既包含了父亲的其因也包含了
母亲的基因。
但是如何从上一代选出父母基因呢!可以通过轮盘赌算法来实现适应度越高的染色体被选中的概率越高,公
式如下:
染色体i被选择的概率 = 染色体i的适应度 / 所有染色体的适应度之和
变异:
交叉能保证每次进化留下优良的基因,但它仅仅是对原有的结果集进行选择,基因还是那么几个,只不过交
换了他们的组合顺序。这只能保证经过N次进化后,计算结果更接近于局部最优解,而永远没办法达到全局
最优解,为了解决这一个问题,我们需要引入变异。变异很好理解。当我们通过交叉生成了一条新的染色体
后,需要在新染色体上随机选择若干个基因,然后随机修改基因的值,从而给现有的染色体引入了新的基
因,突破了当前搜索的限制,更有利于算法寻找到全局最优解。
复制
为了保证上一代的优良染色体,会将上一代适应度最高的几条染色体原封不动的复制给下一代
算法思路
1. 算法初期阶段会随机生成一组可行解,就是祖先代染色体
2. 采用适应度函数计算每一条染色体的适应度,并根据适应度计算再下一次进化中被选中当作父体母体的
概率。
3. 通过交叉产生N-M条染色体