遗传算法在函数优化方面的应用

GeneticAlgorithmisakindofglobaladvancingprobabilitysearchingalgorithmwhichimitatesthenaturalselectionofthebiographyworldandtheinheritancemechanism'shighlyparallel,random,andself-adaption.InthispaperwediscusshowtouseGeneticAlgorithmtosolvefunctionoptimizationproblem.WeyzetheoperationmechanismofGeneticAlgorithm,andweshowanexampletofindtheglobalminimizerofmultimodalfunctionwithquickconvergencespeedbyGeneticAlgorithm.ThenumericalexampleillustratethatGeneticAlgorithmisagoodmethodtosolvemultimodalfunctionoptimizationproblem.:GeneticAlgorithm;functionoptimization;multimodal第一 序 文章的组 本章小 第二 两类遗传算 编码性 编码技 选择运 交叉运 变异运 本章小 第三 引 函数算 算例 算例 本章小 第四 总 致 参考文 附 第一章序遗传算法（GeneticAlgorithm，GA）是今年来迅速发展起来的一种全新的随机搜索与优化算法，其基本思想是基于Daiwin的进化论和Mendel的Holland1975遗传算法的研究引起了国内外学者的关注。自1985年以来，国际上已召开了多ICGA（IntemationalConferenceonGeneticAlgorithms）（WorkshoponFoundationofGeneticAlgorithms）1962(Holland)GA,的原则，从中选择出较适应环境 进 淘汰低适应度 ，, 一轮进化，至到最适合环境的值[1,2]。Pareto最优解和非劣解。所有的ParetoPareto前沿[3,4。单峰的和可导的[5。线性的方法，其基本思想是将多目标的优化问题转化为单目标的优化问题，然后采用单目标的优化技术来处理。这些方法具有下述缺点[6,7]：Pareto前沿的形状很敏感，不能处理前运行算法一次，只能获得一个Pareto最优解。为了获得Pareto最优Pareto搜索空间中形成分布时，搜索才有效，但这一条件在实际应用中难以满足。遗传算法与传统的搜索方法不同，具有如下特点[13]本文人研究成果的基础上，选择了用遗传算法求解函数优化问题的为研究对象，分析了遗传算法的运行机理，对适应度函数和遗传算法操作进行了深入细致的研究，针对基本遗传算法提出了一些代表性的算例，并在环MATALB究遗传算法在函数最优化问题应用的优点。如何应用遗传算法，并通过两个算例以及借助程序直观地体现了遗传算第二章遗传算法基本原理及技遗传算法的早期工作开始于二十世纪60年代。1967年。Holland的学生Bagley在他的博士 我调整的概念，虽然Bagley没有对此进行计算机模拟实验，但这些思想对于Hollstien，1971年他在<计算1975年，是遗传算法发展史上重要的一年，密执根大学的心理学教授、电子工程学与计算机科学教授Holland在专著《自然系统和人工系统的自年，DeJong的博士 《遗传自适应系统的行为分析》完成，他把Holland传算法发展进程中的一个里程碑。DeJong主要侧重于函数优化，同时提出了诸如代沟等新的遗传操作技术，建立了著名的DeJong五函数平台，定义80年代，遗传算法成为人工智能研究的一个热点。1987年，Davis《GeneticAlgorithmandSimulatedAnnealing》[3]一书，以 量的实例介绍了遗传算法的应用技术。1989年，亚拉巴马大学的DavidGoldberg了专著《搜索、优化和机器学习中的遗传算法》一书，全面介绍进入90年代，遗传算法因其能有效地求解NP难问题以及非线性、多峰函遗传算法理论研究和实际应用的不断深入与发展。1991，LawrenceDavisHolland、Goldberg、Davis为人知[1,3,6]，国内也有一些有关书籍相 [4,5]，一系列以遗传算法 国际会议变得十分活跃。从1985年开始，国际遗传算议，即ICGA每两年举行一次。在欧洲，从1990年开始也每隔一年举办一次类似的会议，即PPSNICECANN&GA、EP、GP、SEALInternet算法站点更是推动着遗传算法实质性的进展[13。迄今为止，遗传算法理论研究已取得了很大进展。Goldberg、Rudolph采用集合论的方法，提出了遗传算法的一个充分条件，Schraudolph提出了动态参数编码的方法，PotterPMBGADeJong遗传算法在各种问题的求解与应用中展现了其特点和，但同时操作技术和方法正引起人们的高度重视[13。现。交叉或变异运算生成下一代，称为后代。的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的，作为下一代群体，在继续进化，这样经过若干代之后，算法收敛于最好的，它很可函数称为适应度函数。适应度函数的定义一般与具体求解问题有关[13。优化方法，遗传算法常用到进化论和遗传学中的一些术语如下[8：（1） 也称作，是遗传算法所处理的基本对象、结构种群 的集合称为种群，是种群的元素种群的大小：在种群中的数量为种群的大小符号串 的表示形式，对应于遗传学中的 DNA位置：一 在中的位置称 位置，有时也位 适应度：适应度也称适应值，是某一对应于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性；变异：符号串或水平上 变化，可以遗传给子代 表现型：生物体的型在特定环境下的表现特征，对应于遗传算法中的符号串译码后的参数。搜索,最后才找到解[13]。遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜索算法；的搜索,而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算,而且这种种群到种群的搜索有能力遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,不要计叉发生的概率要比变异发生的概率选取得大若干个数量级。大部分遗传算法的步骤都类似，常使用如下参数[13：FitnessFitnessthreshold（适应度阀值）：适合度中P：种群的总数叫种群规模，它对算法的效率有明显的影响，其长度等于它包含的数量。太小时难以求出最优解，太大则增长收敛时间导致程Pc：在循环中进行交叉操作所用到的概率。交叉概率（Pc）0.60.95，PcPm：变异概率，从中产生变异的概率，变异概率一般取0.01至0.03之间的值变异概率Pm太小时难以产生新的结构，太大使遗传算法成了单纯行下一轮进化。标准遗传算法的基本流程如下[9：Step1令k0，随机产生N个初始构成初始种群P(0)Step2评价P(k)中各的适应度Step3

m0Step5根据适应度，执行操作来从P(k)中选取两个Step6如果杂交概率pc0,1，则对选中 临时；否则将所选中作为临时；Step7按变异概率pm对临时执行变异操作产生两个新放P(k1，并令mm2Step8如果mNStep5；否则令kk2Step21通常，遗传算法的设计是按以下步骤进行的[9]法与传统优化方法的互补性，混合遗传算法通常比单一算法优越[13。[13]的重要因素，一般应遵循以下原则[8：（2）：遗传算法编码空间中的必须对应问题空间中某一潜在解（3）非冗余：遗传算法的与问题潜在解必须一一对应编码是遗传算法要解决的首要问题。Holland的编码方法是二进制编码，问题，问问需要构造合适的评价函数，使其适应遗传算法进行优化[9。

[9] 计算出群体中每个的适应度Fi,i1,2,...,M,计算出每 被遗传到下一代群体中的概率计算出每 的累积概率

在[0,1]区间内产生一个均匀分布的伪随机数r

rq1,则选择1；否则，选择k，使得：qk1rqk成立重复（4）、（5）共MFitness图2赌模行排序，基于这个排序来分配各个被选中的概率。其具体操作过程如下对群体中的所有按其适应度大小进行降序排序 以各个所分配到的概率值作为其遗传到下一代的概率，基于这些排序选择方法主要着眼点是适应度之间的大小关系，对适应度是否取正值或负值以及适应度之间的数值差异程度无特别要求[13]。所谓交叉运算，是指对两个相互配对的按某种方式相互交换其部分，从而形成两个新的。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新的主要方法[9]。遗传算法中，在交叉运算之前还必须对群体中的进行配对，目前常用交叉点的位置？二是如何进行部分的交换？所谓变异运算，是指 编码串中的某 值用其 值来替换

[3]。遗传算法中的变异算法是产生 的辅助方法变异运算的设计包括两方面：一是如何确定变异点的位置？二是如何进行3替换策略——精英主面几种[5：通常当遗传算法停止执行时，就把当前最优指定为遗传算法的结果论；二是Holland的模式定理尚不能清楚地解释遗传算法的早熟现象和问近，Standford大学的Wolpert和Macready教授提出了NoLunch（简称NFL）定理，其结论概括如下：NFL[13：假设有A、B（确定或随机）搜索算法，对于所有的P(c|f,N,A)P(c|f,N, 其中c为适应度的概率曲线，f为适应度函数，N为群体大小ABAB优NFL遗传算法的性能一般包括如下两个方面[5]第三章遗传算法的应用——函数优等。通常，目标函数优化问题可以描述为[13：imaxfX),fXiRnXiS或minfXi),fXiRnXii

i式(3.1)f(XRnSiXix1x2...xni1,2,...,n（n为维数）f(Xi)乘以（-1）就转化为最小f(Xi)看成一序列的函数时，上述问题就转变f(Xi在满足所有约束条件的解空间即定义域的全局最优解和满足该最优解对应的nX*HollandminFxx1,x2,...,xn gj(x)0(jaixibi(ibiaixigj(xne为约束函数的数目，利用罚cncminF(x)F(x)jrg(x)2 j ggi(x),gj(x)

cc 0,

j(x)rjjj

FmaxF(x),Fmax为大于各代群体中的最大适度的值，以保证f于0。通过适应度函数，可将优化问题转化为遗传算法L,使建立的二进制位串与设计变量映射关系能满足设计变量是连续变量的要求，二进制位串与设计变量xjxjajM(bjaj21M群体初始化。选择合适的原始群体规模，然后随机选取其中的代群体的一定数量的。杂交算法是指对优选后的父代绩效模式的重组而产生后代的繁殖机制。突变算子是指模拟生物环境在自然的遗传进算例 x2遗传算法的运算对象是表示的符号串，所以必须把变量x1、x2编码为x1x20-7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了的型，表例如，型X=101110所对应的表现型是：x=（5,6）。的表现型和型X之间可通过编码和程序相互转换本例中，群体规模的大小取为4，即群体由4个组成，每个可通过如选择运算(或称为运算)把当前群体中适应度较高的按某种规则或模型遗传到下一代群体中。一般要求适应度较高的将有的机会遗传到先计算出群体中所 的适应度的总和fi（i=1,2，...,M其次计算出每 的相对适应度的大小fi/

，它即为每 被传到下一代群体中的概率，每个概率值组成一个区域，全部概率值之和为 1351253133404712最后再相互交换配对之间的部分11-1-233-3-4然后依照某一概率将变异点的原有值取反p(t14253246p(t1135371472算例f(X,Y)0.5

sinsin2x21在点（0,0）1。此函数的最大峰周围有两圈脊，它们的取值分别0.9902840.962776，因此优化过程中很容易停滞在这些局部极大点，其4545该函数借助程序计算出的的最优解为0.998，与理论值1非常接近而且性能非常好，2901本章首先对函数优化问题进行了描述；其次通过一个简单算例和一个复杂算例，并借助程序实现了遗传算法在函数优化的应用，可以直观地看到遗传算法