现代智能优化算法

第十章现代智能优化算法简介引言现代优化算法包括禁忌搜索（Tabusearch）、模拟退火（Simulatedannealing）、遗传算法（Geneticalgorithms）等，这些算法涉及生物进化、人工智能、数学和物理科学、神经系统和统计力学等概念，都是以一定的直观基础而构造的算法，我们称之为启发式算法。启发式算法的兴起与计算复杂性理论的形成有密切的联系，当人们不满足常规算法求解复杂问题时，现代智能优化算法开始体现其作用。现代智能优化算法自八十年代初兴起，至今发展迅速，这些算法同人工智能、计算机科学和运筹学迅速融合，促进了复杂优化问题的分析和解决。下面我们就简要介绍这些算法的基本理论以及MATLAB实现。遗传算法特点遗传算法直接以适应度作为搜索信息，求解问题时，搜索过程不受优化函数连续性的约束，无需导数或其他辅助信息；遗传算法具有很高的并行性，可以同时搜索解空间的多个区域搜索信息，从而降低算法陷入局部最优解的可能性；遗传算法具很强的鲁棒性。在待求解问题为非连续、多峰以及有噪声的情况下，它能够以很大的可能性收敛到最优解或近似最优解；遗传算法具有较高的可扩充性。它易于与其它领域的知识或算法相结合来求解特定问题；遗传算法的基本思想简单，具有良好的可操作性和简单性；遗传算法具有较强的智能性，可以用来解决复杂的非结构化问题。遗传算法算法流程优化问题目标函数映射为适应值函数初始种群（编码成位串形式）计算个体（染色体）适应度满意否？选择交叉变异产生新一代种群输出满足问题的种群YN遗传算法基本要素问题编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定(主要是指群体大小和使用遗传操作的概率等)遗传算法问题编码要使用遗传算法，就必须把优化问题的解的参数形式转换成基因码串的表示形式，这一转换操作就叫做编码。一般来说，由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻，但编码的策略对于遗传算子，尤其是对交叉和变异算子的功能和设计有很大的影响，设计时应斟酌确定。问题的编码一般应满足以下三个规则：(1)完备性：原问题空间中的所有点（可行解）都能成为编码后的点；(2)健全性：编码后的空间中的点能对应原问题空间所有的点；(3)非冗余性：编码前后空间的点一一对应。在实际操作中，二进制编码是最基本的编码方式，它的应用非常广泛，常用的二进制编码方式是基于确定的二进制位串上：0,1LI。除了二进制编码以外，还有各种其他的编码形式，如：格雷码编码、序列编码、实数编码、符号编码等。染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。如果个体为9，用二进制编码可以将染色体表示为1001，如果个体为(2,5,6)，则用二进制编码可以将染色体表示为(010,101,110)遗传算法初始群体的设定遗传算法是群体型操作，这样必须为遗传操作准备一个由若干初始解组成的初始群体。初始种群的好坏对于遗传算法的计算结果的优劣和算法的效率有着重要影响。产生初始种群通常有两种方法。一种是完全随机的产生方法，它适用于对待求解问题的解无任何先验知识的情况；另一种是把某些先验知识转化为必须满足的一组要求，然后在满足这些要求的解中随机的选取。这种选择初始种群的方法可以使遗传算法较快地达到最优解。初始群体也称做进化的初始代，即第一代（firstgeneration）。遗传算法适应度函数的确定解析性质：连续、非负合理性：要求适应度函数设计应尽可能简单近似量小：适应度函数对某一类具体问题，应尽可能通用。目标函数的处理方法(1)直接将待求解的目标函数转化为适应度函数，即：若目标函数为最大化问题，则：Fitfxfx；若目标函数为最小化问题，则：Fitfxfx(2)将待求解的目标函数做适当处理后再转化为适应度函数若目标函数为最大化问题，则：minmin0fxcfxcFitfxotherwise式中minc为fx的最小估计值。若目标函数为最小化问题，则：maxmax0cfxfxcFitfxotherwise式中maxc为fx的最大估计值。遗传算法因此，存在目标函数到适应度函数的映射形式，一般映射形式为：f其中为个体；为个体的译码函数；f为具体求解问题的表达式；为变换函数，的作用是确保适应度为正，并且最好的个体其适应度最大。适应度函数的选取至关重要，它直接影响到算法的收敛速度即最终能否找到最优解。函数优化问题可直接将函数本身作为评价函数。而对于复杂系统的评价函数一般不那么直观，往往需要研究者自己构造出能对解的性能进行评价的函数。为了使遗传算法有效的工作，必须保持种群内位串的多样性和位串之间的竞争机制。最常见的调整方法有是线性定标法。线性定标法的原理为：设原适应度函数为f，定标后适应度函数为f，则线性定标表达式为:fafb，式中，系数,ab必须满足下述两个条件：原适应度平均值等于定标后的适应度平均值；保证在以后的选择处理中平均每个个体可贡献一个期待的子孙；定标后的适应度函数的最大值maxf要等于原适应度函数的平均值的指定倍数，控制原适应度最大的个体可贡献的子孙的数目。遗传算法遗传算子选择算子交叉算子变异算子选择算子选择（selection）算子又称复制（reprduction）算子、繁殖算子。选择是从种群中选择生命力强的染色体产生新种群的过程。依据每个染色体的适应度大小，适应度越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有以下几种。(1)适应度比例法适应度比例法是目前遗传算法中最常用的选择方法。它也叫赌轮或蒙特卡罗（Monte—Carlo）选择。在该方法中，各个个体的选择概率和其适应度成比例。设群体大小为n，其中个体i的适应度值为if，则i被选择的概率sip为：1isiMjjfpf显然，概率sip反映了个体i的适应皮在整个群体的个体适应度总和中所占的比例。个体适应度越大，其被选择的概率就越高。按上式计算出群体中各个个体的选择概率后，就可以决定哪些个体被选出。选择算子(2)期望值方法●计算群体中每个个体在下一代生存的期望数目，即：/iiiffMffn●若某个体被选中并要参与配对和交叉，则它在下一代中的生存的期望数目减去0.5；若不参与配对和交叉，则该个体的生存期望数目减去1。●在上一步的两种情况中，若一个个体的期望值小于零，则该个体不参与选择。对比实验表明，采用期望值法的性能高于前两种方法的性能。(3)比例排列法将比例法和排列法结合起来的比例排列法，即当群体中某个染色体的适应度远远大于其他染色体的适应度或群体中每个染色体的适应度相似时，按排列法进行后代选择，而在一般情形下采用比率法进行后代选择。这样既能利用两种方法各自的优点，又弥补了两种方法各自的缺点。选择算子选择-复制算子的通常操作为：对于一个规模为N的种群S，按每个染色体ixS的选择概率iPx所决定的选中机会，分N次从S中随机选定N个染色体，并进行复制。这里选择概率iPx的计算公式可以使用前面所讲到的适应度比例法来确定：1()()()iiNjjfxPxfx交叉算子两个步骤首先在新复制的群体中随机选取两个个体；沿着两个个体（字符串）随机的取一个位置，二者互换从该位置起的末尾部分在交叉过程中的具体实施方法为互换两个染色体某些位上的基因。例如，设染色体1201001011,10010101ss，交换其后4位基因，即：01001011100101010100010110011011则得到1201000101,10011011ss，可以看做是原染色体12,ss的子代染色体。变异算子变异算子模拟了自然界中生物进化过程中个体的基因突变现象，从而改变染色体的结构和物理性状。它是指将个体编码串中的某些基因位上的基因值用该基因位上的其他等位基因来替换，从而产生新的个体。在遗传运算过程中，当交叉操作产生的后代适应度值不再进化，且没有达到最优时，意味着算法陷入了早熟。早熟的根源在于有效基因的缺损，变异算子在一定程度上克服了这种情况，它可以改善遗传算法的局部搜索能力，增加种群的多样性。常见的变异算子包括位点变异、插入变异、对换变异、边界变异、非均匀变异和高斯变异等形式。变异操作就是改变染色体某个（些）位上的基因。例如，设染色体，将其第三位上的0变为1，即。也可以看做是原染色体的子代染色体。遗传算法的参数设置根据前面对遗传算法基本理论的分析，可以知道遗传算法在应用过程中需要调整的相关参数为：(1)种群规模(2)最大迭代代数(3)交叉率(crossoverrate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为cP，取值范围一般为0.4～0.99。(4)变异率(mutationrate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为mP，取值范围一般为0.0001～0.1。基本的遗传算法通过对某一代种群经过对生物基因的复制、变换和变异，特产生新一代种群。再重复此过程，直到群体或最优点的性能达到满意程度。遗传算法的基本步骤(1)选择问题的一个编码方式，在搜索空间U上定义一个适应度函数fx，给定种群规模N，交叉率cP和变异率mP，代数T；(2)随机产生U中的N个个体12,,...,Nsss，组成初始种群121,,...,NSsss，置代数计数器1t；(3)计算S中的每一个个体is的适应度函数iiffs；(4)若满足算法终止规则，则算法停止，取S中适应度最大的个体作为所求结果；否则，计算概率：1,1,2,...,iiNjjfPsiNf并按照上述选择概率分布所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体1S；(5)按交叉率cP所决定的参加交叉的染色体数c，从1S中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体2S；(6)按变异率mP所决定的变异次数m，从2S中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体3S；(7)将群体3S作为新一代种群，即用3S代替S，1tt，转(3)。遗传算法求解实例例利用遗传算法求解区间[0,31]上的二次函数2yx的最大值，如图所示。31xy2yx遗传算法求解实例原问题可转化为在区间[0,31]中搜索能使y取最大值的点a的问题。那么，[0,31]中的点x就是个体,函数值fx恰好就可以作为x的适应度，区间[0,31]就是一个(解)空间。这样,只要能给出个体x的适当染色体编码，该问题就可以用遗传算法来解决。我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个0,1二进制串。串的长度取决于求解的精度，例如假设解空间为[-1,2]，求解精度为保留六位小数，由于解空间[-1,2]的长度为3，则必须将该区间分为3106等分。因为2213106222，所以编码所用的二进制串至少需要22位。遗传算法求解实例(1)采用5位二进制数编码染色体，将种群规模设定为4，取下列个体组成初始种群1S：123413(01101),24(11000),8(01000),19(10011)ssss(2)定义适应度函数为目标函数2fxx(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作，直到适应度最高的个体，即31（11111）出现为止。迭代的过程为：首先计算种群1S中各个体is的适应度ifs如下。22122234()(13)13169;()(24)24576;()(8)864;()(19)1961fsffsffsffsf再计算种群1S中各个体的选择概率1()()()iiNjjfxPxfx如下。1234()(13)0.14