演化算法：模拟生物进化的智能优化之路

演化算法是一个大类是根据模拟自然界生物进化过程而发展起来的一种通用问题求解方法而非具体算法。打个比方“蛋糕”是一类食物的统称而“黑森林蛋糕”、“抹茶奶油蛋糕”才是具体的蛋糕品种同理“演化算法”就是一类算法的统称而“遗传算法”、“遗传规划”等才是具体的算法。本章节就像是一张面向新手的食谱先不细说如何制作“黑森林蛋糕”等具体繁琐的内容而是先从整体上介绍所有“蛋糕”的统一特点即主要从整体上介绍演化类算法的起源和发展以及它们共同的设计思路。下一篇介绍的遗传算法才是具体算法。一、演化计算(一) 生物进化演化计算模拟自然界生物进化过程而发展起来的一种通用问题求解方法。什么是生物进化生物进化是生物与其生存环境之间的相互作用的变化所导致的部分或整个生物种群遗传组成的一系列不可逆的改变。我们认为生物进化是生物与其生存环境互相作用过程中其遗传系统随时间发生一系列不可逆的改变从而导致生物总体对其生存环境的相对适应。生物的进化可以看作是一个优化过程而优化的结果是能够很好地适应环境的生物体。生物的进化过程也可以看作是在众多可能性中搜索“解”的一种方法。现在地球上的种类繁多、结构复杂的生物都是通过漫长的由简单到复杂、由低级到高级的进化过程而得到的优化结果。在生物中众多可能性的集合是可能遗传序列的集合而所要求的“解”则是能够适应环境的生物体。(二) 演化计算的概念演化计算的概念是在达尔文进化论和孟德尔的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则并结合孟德尔的遗传变异理论在算法中引入了生物进化过程中的繁殖、变异、竞争和选择等机制。生物进化与问题求解术语之间的联系生物进化术语问题求解术语环境问题个体可能解适应度质量二、演化算法(一) 演化算法求解问题目前用演化计算表示用模拟生物进化过程来求解问题的整个研究领域而遗传算法、遗传规划、演化策略和演化规划是演化计算研究领域的四个主要研究方向。演化计算所涉及的算法称为演化算法。有许多不同类型的演化算法但所有演化算法的一个共同特点是求解问题的过程也就是模拟大自然生物进化的过程。演化算法在求解问题的过程中怎么做保持一个个体的种群每个个体表示问题的一个可能解个体适应环境的程度用一个适应函数判断每个个体按照适应函数来度量该个体作为问题解的好坏的程度而度量值称为该个体的适应值。基于个体的适应值某些较好的个体被选择通过重组、变异等算子的作用产生一些新的个体这些个体与种群中原来的个体竞争形成下一代种群继续这个过程直到终止条件被满足。生物系统优化问题生物个体问题的一个解多个变量组成的向量染色体携带遗传信息二进制编码表示解的信息基因染色体的片段二进制编码中的一个或多个位一定数量的个体组成生物种群一定数量的二进制编码组成解的群体个体能否生存由其适应性决定解的“好坏”用适应度函数确定自然选择适者生存适应度值大的解被留住的可能性大基因的混合与重组由交叉概率控制对二进制串进行交叉基因的变异由变异概率控制对二进制串的某些位进行变异演化算法也称“进化算法”的三大分支https://zhuanlan.zhihu.com/p/479552083(二) 演化算法求解过程演化算法流程图该流程用伪代码表示就是Procedure Evolutionary_Algorithm Begin t0; initialize(P(t)); evaluate(P(t)); while(not termination condition) do P(t) parent_select(P(t)); P(t) recombine(P(t)); P(t) mutate(P(t)); evaluate(P(t)); P(t1) survivor_select(P(t)∪P(t)); t t1; end while return the best solution; Endt 表示演化代数其初始值为 0表示第 t 代种群演化算法首先产生一个初始种群其中 N 是一个常数称为种群规模通常是随机产生的初始种群但也可以用其他启发式算法得到。 初始种群中的每个个体 x 表示所求解问题的一个可能解。产生初始种群对种群中每个个体的进行适应值度量。个体的适应值度量可以是简单地计算一个适应函数也可以是个复杂的模拟过程根据种群中个体的适应值选择出一些个体作为父体。适应值较大的个体被选择的概率较大所选择的个体形成一个中间种群:对中间种群中的个体以一定的概率进行重组其目的是期望通过对适应值较大的个体进行重组得到适应值更大的个体重组后得到中间种群:对中间种群中的个体以一定的概率进行变异其目的是引进新的个体以保持种群的多样性确定中的哪些个体存活下来以形成下一代种群从初始种群开始演化算法通过选择、重组、变异、存活选择等过程得到后代种群然后再对后代种群重复上述过程直到某种终止条件满足。当算法终止后将所得到的适应值最大的个体作为问题的解。三、演化算法设计设计演化算法需要详细指明以下构成成分个体编码适应函数父体选择策略变化算子存活选择策略参数设置种群初始化终止条件(一) 个体编码个体问题的解的编码的目的是为了能够有效地执行遗传操作。如若一个优化问题的解空间由整数构成那么一种编码方式是采用整数的二进制编码整数18编码为10010。解的编码通常也称为染色体或基因型或个体。编码空间也称为基因型空间或搜索空间演化算法对个体的遗传操作是在基因型空间中完成的。一个染色体解码后所对应的解称为该染色体的表现型。解空间也称为表现型空间演化算法对个体的评估和选择是在表现型空间中完成的。(二) 适应函数适者生存同自然天气、地理条件、异种个体和同种个体进行斗争时适应能力强的群体和个体能够生存下来适应能力弱的个体被淘汰。适应函数是区别种群中个体好坏的唯一方法是进行选择的依据直接影响到演化算法的收敛速度和效率。适应函数的作用是对基因空间中的每个染色体指定一个实数称之为适应值使得我们可以区分染色体的好坏。一般来说一个染色体的适应值越大表明该染色体越好。反之亦然。概念上讲一个适应函数是从编码空间到实数域的一个函数。例如该问题的一个解为一个 n 维向量两个适应函数一种选择是直接用目标函数作为适应函数显然向量中 1 的个数越多该向量就越接近最优解其适应值也就越大最优解的适应值最大。另一方面如果取作为目标函数这时最优解的适应值还是最大但除了最优解外其他所有解的适应值均为 0。第一个适应函数允许逐步改进解的质量第二个适应函数则无此作用。在技术上适应函数通常是一个从解空间到实数域的函数。 比如某个函数f(x)输入的x为二进制编码110110101输出的适应度值为实数0.987因为我们评估一个解的好坏肯定是看一个实数指标值比较直观例如小明考了99分小刚考了64分那么明显小明在这一轮考试中更优秀而没有人愿意通过看一串二进制数来评估好坏比如小明的适应度是10010111小刚是10100101按如下过程对基因型空间的一个染色体进行评估先将该染色体解码为其对应的解即表现型然后用适应函数对表现型进行评估并将评估值作为该染色体的适应值。在许多情况下演化算法求解的问题是一个优化问题这时适应函数可以直接从目标函数得到或简单地由目标函数变换而成。(三) 父体选择策略演化算法通过从当前代种群产生下一代种群的方式使得种群不断演化从而逐步逼近问题的最优解。类似于生物产生下一代个体的一个重要手段是对当前代中的个体进行重组。而父体的选择是重组的基础。父体选择的目的是期望较好个体的重组能够得到更好的后代。若一个个体被选择通过重组产生新的个体那么该个体称为一个父体。并不是最好的一些个体总是被选择为父体。这是因为选择压力过大搜索会过早终止算法容易收敛到局部最优。当然若选择压力过小虽然可以保持种群的多样性增加算法收敛到全局最优的概率但算法的收敛的速度缓慢。有许多不同的父体选择策略通常父体的选择是随机的使得具有较高适应值的个体被选择作为父体的概率较大具有较低适应值的个体被选择作为父体的概率较小。(四) 变化算子变化算子的作用是从已有的染色体中产生新的染色体在解空间中产生新的解包括重组算子和变异算子。重组算子重组算子将两个或多个父体的信息进行组合得到一个或多个后代染色体期望通过重组较好父体的信息得到更好的后代染色体。重组算子是一个随机算子在重组父体的信息时每个父体的哪一部分信息被重组以何种方式重组是随机的。变异算子变异算子改变一个染色体的信息得到一个新的染色体。其目的是通过引入新的染色体来增加种群的多样性扩大搜索空间从而避免演化算法陷入局部最优。变异算子是一个随机算子通常假定变异算子引起染色体的一个随机、无偏的变化。在不同的演化算法中变化算子所起的作用有所不同在遗传算法中重组算子是一个主要的变化算子变异算子起辅助性的作用。在演化策略中变异算子是一种主要的遗传算子重组算子起辅助性的作用。在演化规划中只使用变异算子根本不使用重组算子。变化算子的设计与所选择的编码方案有密切的关系不同的编码方案其相应的变化算子也有所不同。(五) 存活选择策略存活选择的作用是从当前代种群和由父体所产生的后代个体中选择出个体以形成下一代种群。父体选择是随机的而存活选择倾向于适应值较高的个体。譬如说按照当前代种群中的个体和所有后代个体按照适应值排序然后选择出最好的一些个体形成下一代种群。(六) 参数设置不同的演化算法有不同的参数演化策略中的变异步长遗传算法的种群规模、杂交概率和变异概率遗传程序设计中的树的深度等参数设置有以下两种主要方法参数调整参数调整是算法设计中的一个典型方法也是实际中用的最多的方法之一。参数调整是指通过选取不同的参数值进行一系列实验运行演化算法比较实验结果然后挑出使结果最好的参数在算法运行过程中参数保持不变。参数控制参数控制是预先给定初始参数值在算法的运行过程中对参数进行动态地变更。有多种参数控制策略如将参数p作为演化代数t的一个函数p(t)随着演化代数的变化参数p(t)动态地改变因为参数的选取本身也是一个优化问题所以也可以用另一个演化算法来优化参数还可以只用一个演化算法在求解问题的同时对参数进行优化。(七) 种群初始化一个种群是编码表示的一个多重集。种群构成演化的单位。在演化算法中种群是动态的、变化的。演化算法正是通过种群的演化而得到问题的最优解或近似最优解。种群的规模即种群中个体的数目通常是一个常数在演化搜索中保持不变。随机地产生初始种群随机产生的目的是使初始种群中的个体均匀地分布在搜索空间中。使用某种启发式算法产生初始种群该法可使初始种群中包含较好的解这可能使算法能更快地发现问题的最好解。然而该法产生的初始种群中个体不是均匀分布在编码空间中这可能会导致算法过早收敛到局部最优解。(八) 终止条件若已知问题的最优适应值当最好个体的适应值与最优适应值之差的绝对值小于给定的精度Ɛ0时可终止算法。然而由于演化算法是随机算法不能确保算法收敛到最优解故上述条件有可能无法满足。为确保算法终止通常有以下终止条件算法的运行时间达到预先指定的最大运行时间算法计算个体适应值的总数达到预先指定的最大次数算法的演化代数达到预先指定的最大代数在连续若干代以后个体适应值没有明显的改进种群的多样性降低到某个预先指定的阈值算法的实际终止条件可能是上述若干条件的析取。最常用的是预先制定一个最大演化代数。