毕业设计（论文）-雄性偏向的遗传算法的改进研究.doc

本科生毕业论文（设计）题 目: 雄性偏向的遗传算法的改进研究 姓 名: 学 院: 信息科技学院 专 业: 计算机科学与技术 班 级: 计科121班 学 号: 指导教师: 职称: 副教授 2016 年 5月 10 日南京农业大学教务处制目 录摘要：关键词：Abstract: Key words: 1 绪论1.1 研究背景1.2 遗传算法的改进研究综述1.2.1 遗传算法改进研究进展1.2.2 目前存在的问题1.2.3 相应问题分析1.2.4 启发思想引入1.3 研究内容与技术路线1.3.1 研究内容1.3.2 技术路线2 基础理论2.1 遗传算法基本框架2.2 遗传算法构成要素2.2.1 编码方式2.2.2 初始群体设定2.2.3 个体适应度评价2.2.4 遗传操作算子3 算法仿真3.1 基本遗传算法3.1.1 算法流程3.1.2 算法流程图3.3 考虑性别特征的种群划分遗传算法3.3.1 算法流程3.3.2 算法流程图3.4 基于雄性偏向的遗传算法3.4.1 算法流程3.4.2 算法流程图4 实验数据分析4.1 测试函数4.2部分函数特点分析4.3 基本遗传算法实验及性能分析4.4 简单性别遗传算法实验及性能分析4.5 基于雄性偏向的遗传算法实验及性能分析4.6 结果比较4.6.1 收敛性比较4.6.2 寻优能力比较5 总结与展望5.1 总结5.2 展望致谢参考文献：附件1附件2全套设计加扣 3012250582基于雄性偏向的遗传算法的改进研究计算机科学与技术专业 摘要：通过对传统遗传算法的实现以及存在的早熟等问题的分析，结合考虑性别的遗传算法，在生物遗传学中有性生殖与雄性偏向影响种群进化的启发下，提出了基于雄性偏向的遗传算法。认为若想要最后获得最优个体，则既需要有当前优秀个体，也需要有好的进化方向。而雄性与雌性配子在变异几率等方面的差异为这一想法的实现提供了新的思路。结合考虑具有性别特征的种群划分遗传算法，最终得出了基于雄性偏向的遗传算法。对比基本遗传算法、简单性别遗传算法、考虑性别的种群划分遗传算法与提出的基于雄性偏向的遗传算法，试验结果可验证改进算法有一定的优化效果。关键词：遗传算法；性别特征；改进策略；早熟现象；雄性偏向A study of genetic algorithm with male biasmajoring in computer science and technology Tutor Abstract: Understanding the implementation of the simple genetic algorithm and premature convergence, this paper introduces a genetic algorithm with male bias by combining genetic algorithm with sex character with sexual reproduction in biological genetics and strong males bias in the evolution of the population. We applied genetic algorithm to two subpopulation with different rossover probability and mutation probability.Obtaining the optimal point not only need a good point,but also need a good volutionary direction Differences in male and female gametes variation probability, it will provide a new way for the realization of this idea . Considering the genetic algorithm dividing the population by sex character, we finally come to favor the genetic algorithm with male bias.The results btained from contrasting the simple genetic algorithm, the simple genetic algorithm with sex character, the genetic algorithm dividing the population by sex character and the genetic algorithm with male bias can show that the new approach is a general,effective and robust method.Key words: genetic algorithm; sex character; improvement strategies; mature convergence; male bias1 绪论1.1 研究背景遗传算法的概念是1975年由美国密歇根大学的Holland教授首次提出的，后来，De Jong、Goldberg等人不断对这一理论进行归纳和总结【1 Ehrlich PR,Raven PH.Butterflies and plants:a study in coevolution evolution. 1965,18:586-608.2 熊伟清，魏平，赵杰煜.遗传算法的一个调节算子研究.小型微型计算机系统 2003 24(3):531-5333 李敏强,寇纪淞.遗传算法的模式欺骗性 中国科学(E), 20024 曹先彬，罗文坚，王煦法.基于生态种群竞争模型的协同进化J.软件学报，2001,12(4):556-5625 Wang Yong-jun,Zhang Jiang-she,Zhang Gai-ying.A Dynamic Clustering Based Differential Evolution Algorithm for Global optimizationJ.European Journal of Operational Research,2007,183:56-73.6王秀坤,赫然，张晓峰.一种改进的最优保存遗传算法.小型微型计算机统,2005,26(4):833-836.7 慕彩虹，焦李成，刘毅逸.M-精英协同进化数值优化算法J.软件学报，2009,20（11）： 2925-29388 Eiben A, Aarts E, Van Hee K. Global convergence of genetic algorithms: A markov chain analysisJ. Parallel problem solving from nature, 1991: 3-12.9窦全胜,周春光,徐中宇.用群体启发进化规划求解高维优化问题J.吉林大学学报:理学版,2005,5(43):622-626.10王湘中,喻寿益.适用于高维优化问题的改进进化策略J.控制理论与应用,2006,1(23):148-151.11 任子武,伞冶.实数遗传算法的改进及性能研究J.电子学报,2007,35(2):269-275.12 边霞，米良. 遗传算法理论及其应用研究发展J . 计算机应用研究，2010，27(7)：2425-2428】，最终形成了一种模拟进化算法。它是模拟达尔文进化论中的自然选择以及遗传学中生物进化相关过程的一个计算模型，常用来搜索最优解。遗传算法有很强的鲁棒性，因其自身固有并行性，也有一定并行计算的能力。在求解多峰函数、非连续问题以及含噪声问题等情况时，算法有很大的可能性能够收敛到最优解（或近似最优解），可以用来解决复杂的非结构化问题。虽然遗传算法有一定的理论基础支撑并在越来越多的领域中成功应用，但同时其自身局限性也是显而易见的，还有许多问题需要解决。如随机游走现象导致的收敛性差，局部搜索能力弱，未成熟收敛（早熟）问题等等。这些不足阻碍了遗传算法一些优良性能的完全体现与发挥，不利于其推广应用。为了克服这些问题，越来越多的研究人员致力于遗传算法的研究与改进。1.2 遗传算法的改进研究综述1.2.1 遗传算法改进研究进展随着越来越多的研究人员对遗传算法问题的研究深入，并致力于找到改善解决方法，多种多样的改进算法被提出来，经过验证具有较好的效果且比较常见的改进算法有这些：并行遗传算法，混合遗传算法，协同进化算法，精英策略遗传算法，基于免疫的遗传算法等等。作为进化算法的主要方法之一，遗传算法与其他几种具有较好局部优化效果的算法进行结合，可以得到多种不同的混合优化算法，且都具有一定的改良优化效果。例如，Mathefoud 所提的遗传模拟退火算法;Miller 等通过增加局部改善运算等等到遗传算法中，从而提出的对于 NP 难问题的优化问题；Ackley 建议的遗传爬山法;由于不同算法在不同方向上的互补性，混合遗传算法常有较好的平衡能力。1.2.2 目前存在的问题实际应用时,遗传算法经常会出现的问题就是未成熟收敛（早熟），未成熟收敛基本表现为：在还未达到全局最优或满意解时，种群中已不再产生性能超过亲代的子代个体。而这时，群体中不同个体之间相似度极高，群体多样性急剧减少，最终致使算法收敛于某一非优个体附近而不再进化。或是不断淘汰距离最优解更近的个体，进化过程一直无法达到效收敛等。除此之外，遗传算法还存在着随机游走，随着函数维数的不断提高后期收敛速度太慢，欺骗问题等。1.2.3 相应问题分析是否满足以高适应度模式为祖先模式中，是判断遗传算法在求解某个具体问题时是否有效的关键。不能满足这个条件的问题，在利用遗传算法求解时通常都会出现未成熟收敛。种群中适应度值相差不多的个体，在求解过程中每次产生后代的个数也是基本相同的。在这种情况下，优秀个体无法获得更多机会来繁殖后代，从而最终减缓了算法的速度，导致了停滞现象的出现。有效等位基因的缺失是导致早熟问题的直接原因，选择策略是为了加快基因的收敛，而交叉操作无法产生新基因，这样势必会降低某些特定基因位上某一类基因的比例，从而致使该基因位上的基因缺损。假如想要恢复丢失的互补字符值，则只能依靠变异算子进行变异，然而同一基因位上基因的多样性是无法依靠变异算子有效保持的。事实上，群体中某些模式的浓度减少到一定程度时，未必需要等到发生模式丢失，就会严重影响算法搜索的全局性，而这些早熟问题是无法依靠传统遗传算子根本解决。随着函数维数的增加，多峰函数最优解的个数相应地呈指数增长。针对求解高维优化问题，许多研究人员分别研究了粒子群算法、进化策略和其他改进的遗传算法等,但总是无法避免不收敛问题。总结其研究成果，我们发现函数维数的增加主要造成这些问题:过小的种群规模,不能有效地模拟问题的高维特性但是随着种群规模的增大，优秀种子被选中进行遗传操作的概率反而减小,因而种群太大,也会降低进化速度。变异算子在遗传算法中主要目的是增加种群多样性朱灿,梁昔明，颜东煌.一种考虑性别特征的遗传算法J.武汉理工大学学报报,2008,12:110-113+128.,扩大搜索可能性，但除此之外，变异算子还相当于对自变量的扰动, 给函数值提供一个合适的下降方向；我们将变异算子对每个变量都进行一次扰动称为一轮扰动，由于每代变异算子运行次数都很少（设定的变异几率通常都很低）,变异算子想要完成一轮扰动通常需要较多的进化代数。与此同时，先发生扰动的变量的个体逐渐进化的相对更加成熟,拥有较高的适应度值,能够获得较多的被抽中机会,故而从选择池中将后发生变量方向扰动的个体挤出,使后发生的变量方向扰动无法进行下去最终导致陷入局部极值点。1.2.4 启发思想引入现代生物学用博弈论的方法，对生物学中有性生殖进化过程的许多具体现象以及一些关键环节，做出了满意的说明。通过基因的重新组合等确定的变异，以及基因突变等不确定的变异可能，可以产生众多的变异个体，这是有性生殖一个众所周知的优越性。无论何种生活环境下的高等动物，基本上都是有性繁殖。可以这么说，动物物种中，几乎全部是有性别的。同样的，有性植物在植物物种中也占到了压倒优势。包括有性生殖在内，无论哪一种为争取长远利益（维持多样性）的措施都是要以牺牲眼前的最佳收益为代价的。一些有害的隐性基因在有性生殖中较易于受到保护。当有害基因在种群中所占比例极小，有性生殖时它是不容易被清除的，而无性生殖时很容易被自然选择所淘汰。尤其是，近年生物学家对于性别在种群进化中的作用，影响以及雄性偏向在促进种群进化的意义有了新的发现。Nature杂志有新论文指出，雄性个体承担了种群突变的大多数，而有性生殖的过程能更好地进行基因筛选，促进种群进化。在此启发下，参考现有论文中的简单性别遗传，提出了雄性偏向的遗传算法改进。1.3 研究内容与技术路线1.3.1 研究内容（1） 为了考察基本遗传算法、简单性别遗传算法、考虑性别特征的种群划分遗传算法在不同维度函数中的效果，从已有结果的论文中选取具有代表性的29种测试函数，并对测试函数进行分析。其中17种高维函数，12种低维测试函数，8种单峰函数，21种多峰函数。（2） 在计算机上将已有的基本遗传算法、简单性别遗传算法、考虑性别特征的种群划分遗传算法实现，并添加测试函数，在收敛性、平均收敛代数、最优值等方面进行测试，并分析结果。（3） 尝试将雄性偏向对种群进化的影响与考虑性别特征的种群划分思想相结合设计实现基于性别划分的遗传算法，设计实现基于雄性偏向的遗传算法。（4） 对基于雄性偏向的遗传算法进行函数测试，将实验数据进行整合，对比不同算法在高维，低维，单峰，多峰等不同测试函数下的收敛性能，寻优能力，运算速度等来分析算法是否有所改进。（5） 得出实验结论。1.3.2 技术路线（1） 首先先学习遗传算法的有关知识，包括遗传算法执行过程，遗传算法的要素，遗传算法所涉及到的相关名词的意思，以及遗传算法常采用的程序架构。（2） 因为研究的改进算法是基于自然界的生物学新进展，所以查阅文献了解生物遗传学上的进化过程与遗传原理机制，并学习论文提出的最新结果：性别筛选与雄性偏向种群进化的促进作用。（3）接下来则要查找是否已有引入性别因子的遗传算法改进，效果如何，并具体学习操作过程。（4）在充分理解算法的基础上建立已有算法的程序架构，在计算机上对三种算法进行仿真，选取不同的测试函数进行性能测试。（5）在设计完善出完整的基于雄性偏向的遗传算法流程后，参照之前建立的程序框架实现该算法并选取测试函数进行性能测试。（6）对算法的实验结果进行整理，从所求函数的平均值、最优值、最差值、收敛率、收敛时间等方面进行对比，分析算法在寻找全局最优解，收敛速度等方面的效果，判断算法是否有改进。2 基础理论2.1 遗传算法基本框架基本遗传算法（标准遗传算法，简单遗传算法，Simple Genetic Algorithm，简称SGA），该操作以群体中所有个体为对象，只使用基本遗传算子，操作过程简单，易于理解，是其他一些遗传算法的基础夏知伟. 遗传算法概述J . 科学教育研究，2011(39)：71-7315 De Jong K A. An analysis of the behavior of a class of genetic adaptive systemsD. PhD thesis, Dept. of Computer and Comm. Sciences, Univ. of Michigan, Ann Arbor, MI, 1975. Univ. Microfilms, 1975.16 金菊良, 杨晓华, 丁晶. 标准遗传算法的改进方案加速遗传算法J. 系统工程理论与实践, 2001, 21(4): 8-13.17 金菊良, 杨晓华. 基于实数编码的加速遗传算法J. 四川大学学报: 工程科学版, 2000, 32(4): 20-24.18 邓武.基于协同进化的混合智能优化算法及其应用研究D.大连：大连海事大学，2012:1-12119 孟红云.多目标进化算法及其应用研究D.西安：西安电子科技大学，2005:1-14220 李冬黎，何湘宁.二进制遗传算法和八进制遗传算法的函数优化结果比较J.浙江工业大学学报，2001,29（3）：308-31121熊伟清,刘明达,张少宇.一种具有性别特征的遗传算法.J计算机工程,2005,01:165-166+190.22魏平,熊伟清. 一种改进的实数编码遗传算法J. 计算机应用研究,2004,09:87-88+91.附件1轮盘赌选择算子：适应度比例选择法也叫轮盘赌选择法，它根据个体的适应度值计算选择概率，公式如下： （i = 1,2, ,N）式中，表示个体i的选择概率，表示个体j的适应度值；N为种群大小。具体实现过程如下：首先产生区间0,1内的随机数r，若，则选择个体i，设。假如种群中有6个个体，其选择概率和累计概率如表1所示。需要进行多轮选择产生进行交叉和变异操作的个体，每轮产生一个区间0,1内的均匀随机数，作为确定被选个体的指针。设4轮随机数分别为0.69，0.06，0.51，0.93，则被选中个体依次为4，1，3，6（图1）。经过选择操作产生的种群由下列个体组成：1，3，4，6。表 适应度比例选择法的选择概率计算个体123456适应度2.0 1.8 1.6 2.4 1.2 1.0 选择概率0.20 0.18 0.16 0.24 0.12 0.10 累加概率0.20 0.38 0.54 0.78 0.90 1.00 图 适应度比例选择法半粒子群变异算子：传统的遗传算法的变异操作完全是随机的，目的是增加种群的多样性，防止算法陷入局部最优解中，但是却没有考虑完全随机的变异会使种群中的个体向最优解的靠拢速度相对缓慢，半粒子群变异是一种寻找精英个体并利用其信息进行变异的算子。设种群所包含个体集合P(0)=a1,a2, ,aN，和分别表示个体ai第d维变异前后的分量值。种群最优个体记为。则SPSMO的计算公式如下： （2）其中,i=1,2,3,N*(1-Pa),Gbestd表示种群最优个体的第d维分量值。是社会认知项信息，代表个体从上一代种群继承的个体信息。c为加速系数，一般在0,4范围取值，本文中c取值为2。r为0,1内的随机数。表示传统的变异算子，代表个体自身信息的继承，可保证个体变异操作具有随机性。 （3） 越界处理 种群个体在执行变异操作后，会或多或少使变异后个体基因值超出其对应决策变量的取值范围，遇到这种情况需要进行越界处理。越界处理函数如下式所示： （4）式中，和分别表示个体i第d维变异前后的分量值，和分别是第d维上决策变量的最大值和最小值，rand()为0,1范围内的随机数。上述越界处理函数可使变异后的值有1/2的机会恢复到变异前的值，可弥补因越界处理而带来种群多样性的损失，同时可间接减少变异操作越界的次数。但是要注意的是该越界处理只存在一定的概率对越界的个体进行处理。决策变量范围更新策略设种群大小为N，进化到第t代的种群为P(t)=a1,a2, ,aN，其中ai=ai1,ai2, ,aij，j=1,2, ,L。L表示个体长度，即决策变量的个数（算法采用实数编码）。则第j个决策变量的范围Rangej更新如下： （5）其中i=1,2,3, N，和分别表示第j个决策变量的最小值和最大值。交叉算子采用了一种传统的交叉算子定义4（交叉算子）设实数编码的两个父代个体为，被选中个体的基因按照如下公式进行交叉操作： （7） 其中，u为区间0,1内的均匀分布随机数，为交叉参数，一般取值为2。附件2测试函数三维图： 图1 f1、f12、f28三维图 图2 f2、f14三维图 图3 f3、f13三维图 图4 f4三维图 图5 f5、f15三维图 图6 f6三维图 图7 f7三维图 图8 f8三维图 图9 f9三维图 图10 f10三维图 图11 f11三维图 图12 f16三维图 图13 f17三维图 图14 f18二维图 图15 f19二维图 图16 f20三维图 图17 f21三维图 图18 f22三维图 图19 f23三维图 图20 f24三维图 图21 f25三维图 图22 f26三维图 图23 f27三维图 图24 f29三维图，给其他各种遗传算法提供了一个基本框架。基本遗传算法的数学模型可以表示为：SGA=（C,E,P,M,T）式中：C 个体的编码方法 E 个体适应度评价函数 P 初始种群 M 种群大小 选择算子 交叉算子 变异算子 T 遗传运算中止条件遗传算法的具体工作流程如图2-1图2-1 遗传算法具体工作流程2.2 遗传算法构成要素2.2.1 编码方式在实现遗传算法时，我们需要采用某种方式把问题解空间映射到编码空间13，这种编码操作就相当于将待求问题的解构造成一个生物的染色体，这样的结构可以方便使用生物遗传理论来解释遗传算法的过程，各种遗传操作也易于实现。现在比较常用的编码方式有二进制编码和实数编码，而且采用二进制编码的算法在执行过程中往往要与实数编码相互转化。二进制编码位数用如下公式计算20：Vmax就是决策变量的上限，Vmin即为下限，p为实数编码所能取到的精度。2.2.2 初始群体设定 问题的每一个解都有一个编码串与之相对应，我们一般称它为染色体或个体。同理，每一个个体或染色体经过解码转换后，均可以对应于所求解问题的一个解，一组固定数量的染色体构成一个种群或群体，群体中染色体可重复。随机或者有规律地产生第一代种群的操作就是初始化种群。在遗传算法的每次实现过程中，有目的地多次进行种群初始化可以增强算法搜索全局最优解的能力。试验中的四种算法用到的初始种群都在规定范围内随机生成。2.2.3 个体适应度评价 个体的适应度是评价一个个体生存能力的关键指标，它决定了该个体在选择操作中被选中的概率。评价函数是评价染色体适应度的标准，实验中包含两种评价策略，一种是仅与目标函数值相关的评价策略，另一种是将个体差异度和目标函数结合的方式。2.2.4 遗传操作算子选择算子：选择操作就是从当代种群中按照特定规则选择一定数量的个体，这些个体有机会将自身基因遗传到下一代群体中14，它是模拟自然选择现象,进行优胜劣汰的操作;前人已经研究了许多种不同的选择方法对遗传算法搜索性能的影响。基本遗传算法，简单性别遗传算法以及考虑性别的种群划分的遗传算法中采用的是轮盘赌选择法，基于雄性偏向的遗传算法中除了轮盘赌选择法还使用了随机竞争选择。交叉算子：交叉操作是将选择的两个个体的部分基因互换，保证在产生新个体的同时,将能够父体的优良基因遗传给新个体。它模拟了生物学界有性生殖过程中的基因重组。交叉是生物遗传和进化的主要环节14,因此它也是遗传算法区别于其它进化算法的重要特征；试验中采用了一种常用的交叉算子，单点交叉算子，即将随机产生的交叉点后的基因相互交换。 变异算子：变异操作是用相应的等位基因将某些基因位上的基因替换掉14，从而产生新个体的过程；它模拟生物学界遗传和进化过程中,染色体上某些基因发生的突变现象;遗传算法中,变异操作主要作用于个体的等位基因上，目前使用较多的变异算子包括基本位变异、自适应变异、均匀变异、非均匀变异、边界变异和高斯变异等。一般而言,在遗传算法中，执行概率取值常设定的比较小,执行变异操作的可能性也较小，变异算子的作用没有交叉算子那么显著。但在本实验中，基于雄性偏向的遗传算法中雄性变异概率取值设定较高且明显高于女性。3 算法仿真3.1 基本遗传算法3.1.1 算法流程Step1. 种群初始化，并计算适应度值；Step2. 使用轮盘赌选择法进行选择操作；Step3. 按一定概率进行交叉和变异操作；Step4. 更新种群，并重新计算种群的适应度值；Step5. 判断是否满足终止条件；若是，则结束；否则转至Step2；3.1.2 算法流程图图3-1 SGA进化模型3.2 简单性别遗传算法简单性别遗传算法基本流程与上面的基本遗传算法一致，仅在编码时选取第一位表示性别（取值0/1），在进行交叉操作时，操作个体必须性别不同。3.3 考虑性别特征的种群划分遗传算法3.3.1 算法流程Step1设置主要参数,种群大小记为size,最优种群(简称种群1)记为pop1,剩余种群(种群2)记为pop2,最优种群个体数取 pop1size=size0.5,其它种群的个体数则可取Step2确定当前最优点 x：Step3给定一个精度参数precsion,并定义距离函数norm(x, x)（欧氏距离）,按种群中个体到当前最优点的距离大小将种群划分为两个部分,当种群1中个体到最优个体的最大距离小于precison时,种群1只保留最优个体,然后将两个种群合并。计算公式为： Step4分别采用不同的进化策略控制两个种群的进化:种群1主要进行交叉操作,配合少量的变异操作。种群2的则以变异操作为主。为了加快种群1的收敛,我们设定种群1的变异操作必须在x的distk邻域内进行。也就是说种群1变异范围为:Step5按轮盘赌选择法从两个种群里选择个体保存，然后将两个种群混合,并将精英保存,判断进化是否结束,否则gen=gen+1,返回Step2； 3.3.2 算法流程图图3-3 考虑性别特征的种群划分遗传算法进化模型 3.4 基于雄性偏向的遗传算法3.4.1 算法流程Step1. 种群初始化，计算适应度值；Step2. 对雌性个体使用轮盘赌选择法进行选择操作，对雄性个体采用随机竞争法进行选择操作。Step3. 分别进行变异考虑，雄性变异率设置高于雌性；Step4. 选择性别不同的个体进行交叉操作Step5. 判断是否满足终止条件；若是，则结束；否则转至Step2。3.4.2 算法流程图图3-4基于雄性偏向的遗传算法进化模型4 实验数据分析4.1 测试函数此次课程设计选用了29个测试函数作为目标函数，其中，f1f17是多维的测试函数，f18f29是低维的测试函数（f18和f19是一维，其余是二维函数），分别用来检测几种算法在低维函数与多维函数中的表现，从寻优能力和收敛效果两方面对比分析结果。其中f1f4、f6、f7、f10f14、f17f19、f22、f24f29为多峰函数，剩下的是单峰函数。f1、f12和f28，f2和f14，f3和f13，f4和f11，f5和f15均公式相同，维数不同；除f18、f19、f21、f22和f24所求目标的是函数最大值外，其余都为求函数最小值。具体测试函数为：表4.1测试函数Function nameTest functionnSRastrigins100Griewanks100Ackleys100Schwefels10-4189.8289De jong 300300300300300De jong 300Schwefels30-12569.4866Rastrigins300Ackleys300Griewanks300De jong300Michalewiczs100-99.2784Leung&Wangs100-78.3323610.1481473(max)152.1666(max)Rosenbrocks20Bohachevsky24.7(max)Schaffer21.0(max)2-1.0Easom21.0(max)Six-hump Camel Back2-1.0316285Shubert2-186.7309Schaffer20Rastrigins20Goldstein and Price23.0 图4-1 f1、f12、f28三维图 图4-2 f10三维图 图4-3 f17三维图 图4-4 f4三维图 图4-5 f16三维图 4.2部分函数特点分析F1、F12、F28：Rastrigins function具有大量的局部极值点, 经常用来检验算法的群体多样性，是一个复杂的多模问题,F2、F14：Griewangks function与Rastrigins function类似，同样具有大量的局部极值点, 主要用于检验算法的群体多样性。F3、F13：Ackleys function，有一个全局极小值点在（0,0）处，函数取值为0.有许多局部极值点存在于狭长的全局极值点附近, 是测试算法收敛性常用的函数。F4、F11：Schwefels function有一个全局极小值点,且距离局部极值点很远，很难跳出局部最优（假如陷入局部极值的话）。是一个典型的欺骗问题。F16：该函数随着维数的增加会出现平地和山谷，而平地会阻碍算法依靠目标函数值（适应度）的变化寻找最优解，于是有导向性的搜素很难再起作用，尤其是平地上的搜索点，同时盲目性的随机搜索更多地呈现。且仅当搜索点随机落入山谷时，搜索才有可能向最优方向进行。因此，高维的该函数寻优难度较大，其搜索的偶尔性很大，取得最优解的成功率不高。一般临界点取在n=10处，n=10时很容易求得最优解，当维数继续增高后难度增加。F20：它具有一个全局极小点f(1,1)=0，在求解极小值时该函数虽然是单峰函数,但它却是病态的（螺旋型），难以进行全局极小化。F25：六驼峰函数，这个函数一共有六个局部极小点，其中有两个全局最小点，分别是f(-0.089842,0.71266)=f(0.089842, -0.71265) = -1.031628489。F27：它有一个全局极小值点在（0,0）处，函数取值为0，它虽然存在局部极小值点，但是临近全局极小值点的与全局极值之间有较高的阻碍度。F26：该函数是一个多模函数。4.3 基本遗传算法实验及性能分析表4.3给出了基本遗传算法独立运行50次的结果，包括每个测试函数的全局最优解，种群进化1000代后的最好值，最差值，平均值，运行时间，以及算法的收敛率。表4.3基本遗传算法实验结果测试函数全局最优解平均值最好值最差值运行时间收敛率F103.35902E-064.69137E-071.51928E-058.503100%F200.0427476557.38391E-090373100%F300.0002154345.62822E-050.00046009112.656100%F4-4189.8289-4189.334442-4188.828749-4184.48668610.555100%F5017.466770573.8418211969.1098044919.54728%F600.5640084880.303097061.05680566517.45642%F70182.33026630.3792224859.074728327.77926%F8018.43639778.88825111942.4992527121.041100%F90521911322.972100%F1000.1239023980.0566139960.22199436122.004100%F11-12569.4866-12487.68656-12568.15767-12279.546622.60412%F12011.722959655.05000350818.5911193917.17738%F1301.7556642530.704768073.12914714920.46334%F1401.1476718350.9799757551.47741584822,19612%F1500.0013430230.0002220780.00532470115.78774%F16-99.2784-72.83007755-76.75178534-69.88962658.822100%F17-78.33236-73.86831955-75.53722785-72.2246465762.15934%F180.14814730.1481471940.1481471940.1481471945.313100%F1952.166652.1666311452.1666311452.166631145.336100%F2000.0030374922.43436E-070.0232215794.845100%F214.74.7-3.57983E-104.7-3.57983E-104.7-3.57983E-104.673100%F221.01.0-1.83718E-101.0-1.83718E-101.0-1.83718E-106.231100%F23-1.0-1-1-14.950100%F241.01.0-3.47408E-051.0-2.27376E-091.0-7.89534E-054.895100%F25-1.0316285-1.031628453-1.031628453-1.0316284534.984100%F26-186.7309-186.7308686-186.7309088-186.72988235.03074%F2700.0095780760.0053934910.0868768646.920100%F2803.78404E-083.78404E-083.78404E-084.892100%F293.03.0000000373.0000000153.000000094.797100%从上表中可以我们可以知道，基本遗传算法在低维度函数（f18f29）中表现的很好，无论是收敛效果还是寻优能力，运行时间也比较平稳；但是，随着维数的增加，基本遗传算法的收敛率普遍降低，搜索到的值与全局最优解的差距也比较明显，运行1000代的平均时间急剧增加。可见，基本遗传算法都不适用于高维函数，不论是从运算效率还是搜寻效果上来看。4.4 简单性别遗传算法实验及性能分析表4.4给出了简单性别遗传算法独立运行50次的实验结果，包括每个测试函数的全局最优解，种群进化1000代后的最好值，最差值，平均值，运行时间，以及算法的收敛率。表4.4 简单性别遗传算法算法实验结果测试函数全局最优解平均值最好值最差值运行时间收敛率F101.82449E-051.77636E-150.0004076851.120100%F200.06015560.0123165540.1886198822.960100%F300.0004330.000001410.001821.442100%F4-4189.8289-4189.828873-4189.828873-4189.8288731.509100%F500.0407044020.0055155340.2265173452.15246%F601.660.8892.652.40988%F700.480.06531.472.78626%F804.9784898842.97716486110.088678293.029100%F900.32021.579100%F1000.0177053060.0036043610.0404390013.366100%F11-12569.4866-12255.27954-12570-10959.360262.74478%F12039.8054535118.4426937673.271988352.80498%F1303.932.655.963.12698%F1400.0972553550.0089947490.2871976072.41314%F1502.02286E-075.6911E-087.21212E-071.460100