进化算法(一)：遗传算法理论及引例

进化算法(evolutionary algorithms，EA)

以达尔文的进化论思想为基础，通过模拟生物进化过程与机制来求解问题
基于自然选择和自然遗传等生物进化机制的一种随机搜索算法。
生物进化是通过繁殖、变异、竞争和选择实现的；
而进化算法则主要通过选择、重组和变异这三种操作实现优化问题的求解。
这些方法本质上从不同的角度对达尔文的进化原理进行了不同的运用和阐述，非常适用于处理传统搜索方法难以解决的非线性优化问题。
进化算法是一个**“算法簇”，包括:
遗传算法(genetic algorithms，GA)
遗传规划(genetic programming)
进化策略(evolution strategies)
进化规划(evolution programming)等。
尽管它有很多的变化，有不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但它们产生的灵感都来自大自然的生物进化，进化算法的基本框架是遗传算法所描述的框架。
与普通搜索算法一样，进化算法也是一种迭代算法**。不同的是在最优解的搜索过程中，普通搜索算法是从某个单一的初始点开始搜索，而进化算法是从原问题的一组解出发改进到另一组而较好的解，再从这组改进的解出发进一步改进。而且，进化算法不是直接对问题的具体参数进行处理，而是要求当原问题的优化模型建立后，还必须对原问题的解进行编码。
进化算法在搜索过程中利用结构化和随机性的信息，使最满足目标的决策获得最大的生存可能，是一种概率型的算法。
在进化搜索中用目标函数值的信息，可以不必用目标函数的导数信息或与具体问题有关的特殊知识
因而进化算法具有广泛的应用性，高度的非线性，易修改性和可并行性。
因此，与传统的基于微积分的方法和穷举法等优化算法相比，进化算法是一种具有高健壮性和广泛适用性的全局优化方法
具有自组织、自适应、自学习的特性，能够不受问题性质的限制，能适应不同的环境和不同的问题

进化算法的生物学背景

进化算法类似于生物进化,需要经过长时间的成长演化,最后收敛到最优化问题的一个或者多个解。
“适者生存”揭示了大自然生物进化过程中的一个规律:最适合自然环境的个体产生后代的可能性大。
生物进化的基本过程如图所示。

生物遗传物质的主要载体是染色体(chromosome),DNA是其中最主要的遗传物质。
染色体中基因的位置称作基因座,而基因所取的值又叫作等位基因。
基因和基因座决定了染色体的特征,也决定了生物个体(individual)的性状。如头发的颜色是黑色、棕色或者金黄色等。
以一个初始生物群体(population)为起点,经过竞争后,一部分个体被淘汰而无法再进入这个循环圈,而另一部分则成为种群。
竞争过程遵循生物进化中“适者生存,优胜劣汰”的基本规律,所以都有一个竞争标准,或者生物适应环境的评价标准。
适应程度高的个体只是进入种群的可能性比较大,并不一定进入种群。而适应程度低的个体只是进入种群的可能性比较小,但并不一定被淘汰。这一重要特性保证了种群的多样性。
生物进化中种群经过婚配产生子代群体(简称子群)。在进化的过程中,可能会因为变异而产生新的个体。
每个基因(数组的某位数)表示了生物机体的某种特征,如头发的颜色、耳朵的形状等。**综合变异的作用使子群成长为新的群体而取代旧群体。**在新的一个循环过程中,新的群体代替旧的群体而成为循环的开始。

进化算法的求解步骤

给定一组初始解;
评价当前这组解的性能;
从当前这组解中选择一定数量的解作为迭代后的解的基础:
再对其进行操作,得到迭代后的解;
若这些解满足要求则停止,否则将这些迭代得到的解作为当前解重新操作。

设计进化算法的基本原则

(1)适用性原则:一个算法的适用性是指该算法所能适用的问题种类,它取决于算法所需的限制与假定。优化问题的不同,则相应的处理方式也不同。
(2)可靠性原则:一个算法的可靠性是指算法对于所设计的问题,以适当的精度求解其中大多数问题的能力。因为演化计算的结果带有一定的随机性和不确定性,所以,在设计算法时应尽量经过较大样本的检验,以确认算法是否具有较大的可靠度。
(3)收敛性原则:指算法能否收敛到全局最优。在收敛的前提下,希望算法具有较快的收敛速度。
(4)稳定性原则:指算法对其控制参数及问题的数据的敏感度。如果算法对其控制参数或问题的数据十分敏感,则依据它们取值的不同,将可能产生不同的结果,甚至过早地收敛到某一局部最优解。所以,在设计算法时应尽量使得算法对一组固定的控制参数能在较广泛的问题的数据范围内解题,而且对一组给定的问题数据,算法对其控制参数的微小扰动不很敏感。
(5)生物类比原则:因为进化算法的设计思想是基于生物演化过程的,所以那些在生物界被认为是有效的方法及操作可以通过类比的方法引入到算法中,有时会带来较好的结果。

基本遗传算法(simplegenetie algorihms,SCA)

对于自然界中生物遗传与进化机理的模仿,针对不同的问题来设计不同的编码方法来表示问题的可行解,以产生不同的遗传算子来模仿不同环境下的生物遗传特性。这样,由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。
但这些遗传算法都具有共性是通过对生物遗传和进化过程中选择、交叉、变异机理的模仿,来完成对问题最优解的自适应搜索过程。基于这个共同的特点,使用选择算子,交叉算子和变异算子三种基本进传算子,给各种遗传算法提供了一个基本框架。进化算法的基本框架也是基本遗传算法所描述的框架。

!!!遗传算法的基本思想:用多个可行解模拟生物,让生物模拟进化,这些经过多轮迭代进化的生物,极好的适应了环境(限制条件),就是最优解!!!

遗传算法主要借用生物进化中“适者生存”的规律。
在遗传算法中,染色体对应的是数据或数组,通常是由一维的串结构数据来表示的。串上各个位置对应上述的基因座,而各位置上所取的值对应上述的等位基因。遗传算法处理的是染色体,或者称为基因型个体。一定数量的个体组成了群体。群体中个体的数量称为种群的大小,也叫种群的规模。各个个体对环境的适应程度叫适应度。适应度大的个体被选择进行遗传操作产生新个体,体现了生物遗传中适者生存的原理。
选择两个染色体进行交叉产生一组新的染色体的过程,类似生物遗传中的婚配。编码的某一个分量发生变化的过程,类似生物遗传中的变异。

遗传算法包含两个数据转换操作:
从表现型到基因型的转换,将搜索空间中的参数或解转换成遗传空间中的染色体或个体,这个过程称为编码(coding)。
从基因型到表现型的转换,即将个体转换成搜索空间中的参数,这个过程称为解码**(decode)。
遗传算法在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解这多个解的集合称为一个种群,记为p(t)。这里t表示迭代步,称为演化代。一般地,p(t)中元素的个数在整个演化过程中是不变的,可将群体的规模记为N。p(t)中的元素称为个体或染色体,记为x1(t),x2(t),…在进行演化时,要选择当前解进行交叉以产生新解**。这些当前解称为新解的父解(parent),产生的新解称为后代解(offspring)。

写在前面

一个数组可以称作染色体(chromosomes),数组的每一个数是染色体上的基因(gene)
初代的染色体可以随机生成,但需要大量且有个体差异的染色体才可以构成一个种群(population),个体数量足够多的时候,才会有一定几率出现我们想要的基因
我们对个体的考察指标,反映在个体身上称为适应度(fitness)
自然选择:不断淘汰掉无法适应环境的个体,从而让好的基因重复进入竞争的循环
自然选择有多种不同的实现,此处我们可以创建一个生物数组,根据适应度的大小克隆等长个个体放入数组,也就是说,如果个体A适应度为10那么数组的前十个个体为A,生物B的适应度为1,那么就放入1个B进入生物数组,然后随机从数组中选择(这样的放置方法,可以提升高适应度的个体可以尽可能的被选择到)
选择完毕后进入繁殖(reproduction):让被选择的生物自由进行繁殖,产生新一代个体,同理按照之前的选择方法选出一对生物进行染色体交叉互换(crossover),有几率继承父母好的基因,从而产生更优秀的新个体
繁殖有多种不同方式实现,此处按照单点杂交(single-point crossover),对于一个数组,指定个体1的位序K前的数字给孩子,个体2位序K后的数字给孩子

突变(mutation):使得某基因发生随机变化,突变不总是好的,设置其几率不一定过高,而突变产生的基因改变是随机的
这是一次生物进化的过程,循环往复多次可以迭代出最佳的基因,但是基因的提升幅度斜率不总是很高,越往后可能越缓

引例:旅行商问题(一笔画):

从某个点开始,相继连接到所有的点并且最终回到源点.考察总行程最短,纯暴力的实现就是全排列,但随着结点个数增加而解空间组合数爆炸

编码与群体设定:

考虑用遗传算法解决该问题,首先进行编码:
将问题的解的形式用染色体的基因序列抽象表示
遗传算法中包含了五个基本要素:参数编码、初始群体的设定、造应度函数的设计、遗传操作设计和控制参数设定。
由于遗传算法不能直接处理问题空间的参数,因此,必须通过编码将要求解的问题表示成遗传空间的染色体或者个体。
事实上,还不存在一种通用的编码方法,特殊的问题往往采用特殊的方法。
群体设定:
由于遗传算法是对群体进行操作的,所以,必须为遗传操作准备一个由若干初始解组成的初始群体。
群体设定主要包括**两个方面:**初始种群的产生和种群规模的确定。
种群规模一般取为 20~100。

左边是路径序列,视为一个染色体,而右边的图中,每一个点视为一个基因单位

建立评价指标(目标函数/适应度值)

然后建立评价指标来评价不同解(染色体)的优劣:考虑将目标抽象为一个染色体,为了达到理想的染色体,我们建立一个评价指标,也就是总路径长度,最终迭代出的最优染色体对应的路径为最短路径.
遗传算法遵循自然界优胜劣汰的原则,在进化搜索中基本上不用外部信息,而是用适应度值表示个体的优劣,作为遗传操作的依据。适应度是评价个体优劣的标准。个体的适应度高,则被选择的概率就高,反之就低。
最后通过染色体交叉变异来产生不同解并评价迭代出最优解,选择适应度更低(本问题对应了路径最短)的解作为父代来产生新子代

适应度函数(fitessfunction):

用来区分群体中的个体好坏的标准,是算法演化过程的驱动力,是进行自然选择的唯一依据。
改变种群内部结构的操作都是通过适应度值加以控制的。因此,对适应度函数的设计非常重要。
在具体应用中,适应度函数的设计要结合求解问题本身的要求而定。一般而言,适应度函数是由目标函数变换得到的。
目标函数变换成适应度函数的方法暂略

选择/复制(reproduction)

从当前群体中按照一定概率选出优良的个体,使它们有机会作为父代繁殖下一代子孙。
判断个体优良与否的准则是各个个体的适应度值。
显然这一操作借用了达尔文适者生存的进化原则,即个体适应度越高,其被选择的机会就越多。
需要注意的是:
!!如果总挑选最好的个体,遗传算法就变成了确定性优化方法,使种群过快地收敛到局部最优解。!!(贪心)
!!如果只作随机选择,则遗传算法就变成完全随机方法,需要很长时间才能收敛,甚至不收敛!!(无意义)。
因此,选择方法的关键是找一个策略,既要保证种群收敛速度,也要维持种群的多样性。

核心:交叉/复制(crossover)或者重组(recombination)

选择两个染色体AB,截取染色体A的一段,然后如果B中有该段,则逐个剔除,将剩余的基因连接重组,并且最后将A中截取的部分置入重组后的B基因尾部
遗传算法中起核心作用的是交叉算子,也称为基因重组。
采用的交叉方法应能够使父串的特征遗传给子串。子串应能够部分或者全部地继承父串的结构特征和有效基因，
当两个生物机体配对或者复制时,它们的染色体相互混合,产生一对由双方基因组成的新的染色体。
交叉得到的后代可能继承了上代的优良基因,其后代会比它们的父母更加优秀,但也可能继承了上代的不良基因,其后代则会比它们的父母差,难以生存,甚至不能再复制自己。
越能适应环境的后代越能继续复制自己并将其基因传给后代。由此形成一种趋势:每一代总是比其父母一代生存和复制得更好。

这样产生了一个新染色体,交叉完毕.重复此操作以至于产生n个新的染色体

变异:截取染色体一段打乱后重新置入形成新染色体

进化机制除了能够改进已有的特征,也能够无故地产生新的特征。
发生变异的概率通常都很小,但在经历许多代以后变异就会很明显。一些变异对生物是不利的,另一些对生物的适应性可能没有影响,但也有一些可能会给生物带来一些好处,使它们超过其他同类的生物。例如变异可能会产生眼睛更大的生物。当经历许多代以后,眼睛会越来越大。
在遗传算法中,变异是将个体编码中的一些位进行随机变化。
变异的主要目的是维持群体的多样性,为选择、交叉过程中可能丢失的某些遗传基因进行修复和补充。
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。
变异操作是按位进行的,即把某一位的内容进行变异。变异概率是在一个染色体中按位进行变化的概率。

最终交叉达到的效果就是:大幅度的寻找解空间中的最优解
而概率变异达到的效果是:小幅度的寻找解空间中的最优解

完成一轮后进行评价:

将原来的父代种群和新的子代种群放在一起,按照适应度排序


评价后择取前N个个体,作为本次迭代的前N个优解,成为新的父代种群(即替代原来的父代种群),然后继续变异交叉产生新子代,再评价置换再循环


因为每一次循环我们的操作都对应了期望适应度最低的解,当迭代循环次数达到上限后,适应度最低的解也就是最优解——最短路径或其最佳近似

完整的算法流程:

二进制/实数/混合编码
随机/启发式/混合型启发式初始化
轮盘赌博/锦标赛/精英选择
单点/多点/均匀/基本位交叉变异

遗传算法的特点:
遗传算法比起其他普通的优化搜索,采用了许多独特的方法和技术。归纳起来,主要有以下几个方面。
①遗传算法的编码操作使得它可以直接对结构对象进行操作。所谓结构对象泛指集合、序列、矩阵、树、图、链和表等各种一维、二维、甚至三维结构形式的对象。因此,遗传算法具有非常广泛的应用领域。
②遗传算法是一个利用随机技术来指导对一个被编码的参数空间进行高效率搜索的方法而不是无方向的随机搜索。这与其他随机搜索是不同的。
③许多传统搜索方法都是**(别的算法)单解搜索算法,即通过一些变动规则,将问题的解从搜索空间中的当前解移到另一解(状态转移)。对于多峰分布的搜索空间,这种点对点的搜索方法常常会陷于局部的某个单峰的优解。
而遗传算法采用(遗传算法)群体搜索策略,即采用同时处理群体中多个个体的方法,同时对搜索空间中的多个解进行评估,从而使遗传算法具有较好的全局搜索性能**,减少了陷于局部优解的风险,但还是不能保证每次都得到全局最优解。遗传算法本身也十分易于并行化。
④在基本遗传算法中,基本上不用搜索空间的知识或其他辅助信息,而仅用适应度函数值来评估个体,并在此基础上进行遗传操作,使种群中个体之间进行信息交换。特别是遗传算法的适应度函数不仅不受连续可微的约束,而且其定义域也可以任意设定。对适应度函数的唯一要求是能够算出可以比较的正值。遗传算法的这一特点使它的应用范围大大扩展,非常适合于传统优化方法难以解决的复杂优化问题。