带互动界面的遗传算法演示系统

本科毕业设计说明书（论文）（2012届）论文题目带互动界面的遗传算法演示系统I PAGEI摘要遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究，广泛应用于自动控制、计算科学、模式识别、智能故障诊断管理科学和社会科学领域，适用于解决复杂的非线性和多维空间寻优问题。带互动界面的遗传算法演示系统主要是演示运用遗传算法解决背包问题，对简单遗传算法的交叉算子和变异算子做了改进，通过实验验证了改进之后遗传算法在解决背包问题方面准确度以及效率的提高。带互动界面的遗传算法演示系统使用MyEclipse作为开发工具，使用面向对象的Java语言进行编程设计，通过键盘输入或者读取特定文件来处理数据以达到互动演示效果。带互动界面的遗传算法演示系统主要包括从文件读取数据，从键盘输入数据，参数曲线演示，关于演示系统，退出演示系统五大功能模块，其中演示的主要模块为从文件中读取数据，从键盘输入数据以及参数曲线演示。从文件中读取数据要求用户输入将要处理的有效文件名，系统将给出最终运算结果；从键盘输入数据需要用户手动输入要处理的数据，系统将给出最终运算结果；参数曲线演示模块展示了最优值关于种群大小、交叉概率、变异概率的变化曲线；关于演示系统主要介绍了本系统的一些基本信息；用户通过退出演示系统模块来退出该系统。经过各方面测试，该系统运行稳定，对于利用遗传算法解决背包问题来说，能够实现良好的互动演示效果并能给出正确的结果。关键词：遗传算法演示系统，背包问题，MyEclipse，JavaAbstractGeneticalgorithmisanadaptiveandgloballyoptimizedandprobabilisticsearchingmethodwhichformsintheprocessofsimulatingtheorganisms’geneticsandevolutioninthenaturalenvironment.ItwasfirstlyproposedbyHollandwhowastheprofessorofUniversityofMichigan.Geneticalgorithmoriginatedfromtheresearchonnaturalandartificialadaptivesysteminthe1960s.Asaresearchwiththeabilityofsystemoptimizing,adaptiveandself-learninghigh-performancecomputingandmodeling,Geneticalgorithmiswidelyusedinthefieldofautomaticcontrol,computingscience,patternrecognition,intelligentfaultdiagnosismanagementsciencesandsocialsciences.Itissuitableforsolvingthecomplexnon-linearproblemandthemulti-dimensionalspaceoptimizationproblem.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfaceistodemonstratetheuseofGeneticalgorithmtosolvetheknapsackproblem.Ithasmadesomeimprovementsoncrossoveroperatorandmutationoperator.Itisverifiedthattheimprovedgeneticalgorithmindeedimprovedtheaccuracyandefficiencyinsolvingtheknapsackproblem.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfaceuseMyEclipseasadevelopmenttool,theobject-orientedJavalanguagetoprogramanddesign,inputtingviathekeyboardorreadingaparticularfiletoprocessthedatainordertoachieveinteractivedemoeffect.TheGeneticalgorithmdemonstrationsystemwithinteractiveinterfacemainlyincludesthefollowingfunctionalmodules:readingfromaparticularfile,inputtingviathekeyboard,thedemonstrationofparametriccurves，aboutdemosystemandquit.Readingfromaparticularfile,inputtingviathekeyboardarethemainfunctionalmodules.Readingfromaparticularfilerequirestheusertoinputavalidfilenameandthesystemwillgivethefinalresultoftheoperation.Inputtingviathekeyboardrequirestheusertoinputthevaliddataandthesystemwillgivethefinalresultoftheoperationthedemonstrationofparametriccurvesdemonstratetheoptimalvaluesforpopulationsize,crossoverprobability,mutationprobabilitycurve.Theaboutdemosystemintroducessomebasicinformationofthesystem.Thequitallowstheusertoexitthesystem.Afterthecarefultest,thesystemisstable,anditcanachievegoodinteractivedemonstrationeffectandgivesthecorrectresult.Keywords：Geneticalgorithmdemonstrationsystem,knapsackproblem,myeclipse,java目录TOC\o"1-3"\f\u摘要 IAbstract I第一章绪论 11.1 研究开发的目的 11.2 国内外研究发展现状 21.3 公式 31.4 本文的主要工作 41.5 本文的组织结构 41.6 本章小结 5第二章研究开发的基本内容、方法 62.1 背包问题的基本内容 62.2 研究目标 72.3 开发工具简介 72.4 主要开发语言简介 82.5 整体开发设计简介 82.6 本章小结 9第三章遗传算法的基本原理与实现技术 103.1 模式定理 103.1.1 模式 103.1.2 模式定理 103.2 编码技术 113.2.1 群体设定 113.2.2 适应度函数 123.2.3 适应度尺度变换 123.2.4 遗传操作 123.3 本章小结 14第四章背包问题描述与实现以及对简单遗传算法的改进 154.1 背包问题描述 154.2 编码选择 154.2.1 群体设定 154.2.2 适应度函数 154.2.3 约束条件 154.2.4 选择算子的设计 164.2.5 交叉算子的设计 164.2.6 变异算子的设计 164.3 对利用遗传算法解决背包问题的改进 164.3.1 参数实验 164.3.2 改进的交叉算子：单点交叉与均匀交叉结合的算子 194.3.3 改进的变异算子：不降低适应度的变异方式 234.4 本章小结 24第五章带互动界面的遗传算法演示系统详细设计 265.1 系统功能模块详细设计 265.2 系统性能优化设计 285.3 本章小结 28第六章带互动界面的遗传算法演示系统实现 296.1 系统界面实现 296.2 系统功能模块实现 316.3 本章小结 34第七章总结 357.1完成的工作 357.2 存在的问题及下一步工作 357.2.1 存在问题 357.2.2 下一步工作 35参考文献 36致谢 38附录 39图目录TOC\c"图"图41最优值-变异概率曲线图 18图42最优值-交叉概率曲线图 18图43最优值-群体大小曲线 19图44改进的交叉算子所得最优结果图 21图45改进的交叉算子所得最优值-进化代数曲线图 21图46未改进的交叉算子所得最优结果图 22图47未改进的交叉算子所得最优值-进化代数曲线图 23图48改进的变异算子所得最优结果图 24图49改进的变异算子所得最优值-进化代数曲线图 24图51处理文件流程 26图52从键盘输入数据流程 27图61从文件读取数据模块主界面 29图62从键盘输入数据模块界面 30图63参数曲线演示模块界面 30图64关于演示系统模块界面 31图65文件不存在时发出警告 32图66文件数据有误时发出警告 32图67显示处理结果 33图68进化曲线图 33图69进化详情图 34表目录TOC\c"表"表41参数实验表 17表42参数表 20表43改进的交叉算子所得结果统计表 21表44未改进的交叉算子所得结果统计表 22表45改进的变异算子所得结果统计表 23PAGE41第一章绪论研究开发的目的遗传算法的应用无论是用来解决实际问题还是建模，其范围不断扩展，这主要依赖于遗传算法本身的逐渐成熟。近年来，许多冠以“遗传算法”的研究与Holland最初提出的算法已少有雷同之处，不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同的再生和选择方法，但这些改进方法产生的灵感都来自于大自然的生物进化，可以归为一个“算法簇”。人们用进化计算（EC）来包容这样的遗传“算法簇”。它基本划分为四个分支：遗传算法（GA）、进化规划（EP）、进化策略（ES）和遗传程序设计（GP）[1]。有些学者甚至提出，进化计算是人工智能的未来。其观点是，虽然我们不能设计人工智能（即用机器代替人的自然智能），但我们可以利用进化通过计算获得智能[2]。目前，进化计算与人工神经网络、模糊系统理论一起已经形成一个新的研究方向—计算智能（computationalintelligence）。人工智能已经从传统的基于符号处理的符号主义，向以神经网络为代表的连接主义和以进化计算为代表的进化主义方向发展。遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究，广泛应用于自动控制、计算科学、模式识别、智能故障诊断管理科学和社会科学领域，适用于解决复杂的非线性和多维空间寻优问题。利用遗传算法的搜索过程不受优化函数的连续性约束，也没有优化函数的导数必须存在的要求；遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度；遗传算法更适合大规模复杂问题的优化[3]。鉴于遗传算法有以上这些优点，所以对它的研究将具有重要意义。可以预料在不远的将来，随着理论研究的不断深入和应用领域的不断拓广，遗传算法将取得长足的进展。本文旨在就具体的背包问题来展示利用遗传算法对其解决的具体过程与结果，以显示遗传算法在解决该类问题方面的良好性能，并在简单遗传算法的基础上对交叉算子和遗传算子进行改进，进一步提高遗传算法的解决问题的准确度和效率。国内外研究发展现状在20世纪60年代，美国密歇根（Michigan）大学的Holland教授及其他一些科学家分别独立地对人工系统和自然的研究之后，提出了遗传算法的基本思想。1975年，Holland教授出版了经典著作《AdaptationinNatureandArtificialSystem》，象征着遗传算法的正式诞生。Holland教授提出的遗传算法即是后来的简单遗传算法。简单遗传算法主要由交叉算子产生新个体，个体采取二进制编码方式，通过选择操作体现“优胜劣汰”的自然选择机制。简单遗传算法以模式定理为其理论基础，认为遗传算法具有全局收敛性和隐含并行性。经过几十年的研究与发展，遗传算法的理论研究取得了重大进展，其应用研究更是取得了辉煌的成就，已经渗透到了各行各业。有关人工智能的著作中一般也有关于遗传算法的章节，现已有不少学术专著出版。近年来，有不少博士学位论文对遗传算法的理论和应用作了专题论述。遗传算法是一种非数值计算优化方法，它建立在群体遗传学和自然选择基础之上[4]。遗传算法将问题的解表示成字符串，并把这样的字符串当作染色体，许多个体便构成了一个种群。通过随机方式产生若干个个体构成初始种群，然后对群体不断进化，利用“优胜劣汰”的选择机制，使种群中的个体朝着最优值的方向进化，最终搜索到问题的近似最优解或者最优解。个体通过选择、交叉和变异算子的作用生成子代个体。通过定义个体的评价函数，也称为适应度函数，来评价个体的优劣。个体的适应度反映个体适应环境的能力，适应度大的个体生存能力强。按照自然选择的基本原理，适应度越大的个体被选择用来繁殖后代的机会越大。遗传算法是模拟遗传进化的智能算法，而遗传算法的理论研究内容主要包括染色体的遗传控制参数的选择、编码方法、遗传算子、算法的运行过程、算法的收敛性和收敛速度以及遗传算法的改进和与其它方法的综合等[5]。遗传算法虽然有诸多的优点，也已在实际中得到了大量应用,但它也存在着许多急待解决的问题。例如，如何进行算法本身的参数优化选择[6][7]，即对群体的规模、交换概率和变异概率进行优化选择。因为实践发现这些参数的选取直接关系着GA求解问题的成败。如何避免算法过早收敛的产生[8]，过早收敛是指GA在执行过程中会出现群体中的个体过早地在一个非最优点上达到完全相同或接近完全相同的现象。一旦出现该现象,利用GA就不能求得问题的全域最优解。对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再变化。针对这一问题，研究者提出了一些方法增加基因的多样性，从而防止过早地收敛。其中一种是触发式超级变异，就是当染色体群体的质量下降（彼此区别减少）时增加变异概率；另一种是随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性。还有如何改进操作手段或引入新操作手段来提高算法的执行效果，如何将该算法与其它传统优化方法有机结合起来等等问题。以上存在的问题有的已基本获得解决,而有的则正在解决当中。公式背包问题的数学模型[9]：其中=0或1，j=1,…,n。,,b均为正值（1-1）利用罚函数法时适应度函数的计算公式[9]：（1-2）求目标函数的全局最大值的转换公式[10]：（1-3）求目标函数的全局最小值的转换公式[10]：（1-4）本文的主要工作本文的主要工作是在深入理解与掌握遗传算法的基础上，详细的分析与设计利用该算法来解决背包问题，阐述在设计与开发过程中所用到的相关技术以及所遇到的技术难题与解决方案，并解析该系统的具体实现过程与结果。本系统对交叉算子和遗传算子做了改进，然后对改进的遗传算法做了实验，得出结果并分析了数据。本文的组织结构本文共分为七章，以“带互动界面的遗传算法演示系统”为背景，研究讨论了遗传算法的原理及实现，针对于具体的背包问题，设计了利用遗传算法的解决方案，并在传统遗传算法上进行了改进。各章内容如下：第一章，介绍了课题研究的背景，国内外相关领域的研究及应用，课题研究的主要任务和本文的主要工作。第二章，详细介绍了研究开发的基本内容和方法。第三章，重点介绍了遗传算法的基本原理和实现技术。第四章，具体介绍了背包问题的描述与实现，重点讲解了对简单遗传算法在交叉算子和变异算子方面的改进，并且通过数据分析了改进的效果。第五章，详细介绍了带互动界面的遗传算法演示系统在演示界面方面的详细设计。第六章，着重阐述了带互动界面的遗传算法演示系统在演示界面方面的具体实现，针对第五章提出的详细设计要求，在本章给出系统的技术实现。第七章，对系统开发进行总结并提出下一步工作。本章小结本章简要介绍项目的研究背景、在国内外相关领域的开发和应用现状以及项目的研究的任务和意义。最后，给出了本文的主要工作及本文的组织结构。第二章研究开发的基本内容、方法背包问题的基本内容背包问题是一个典型的NP完全问题[10]，主要应用于管理中的资源分配、投资决策、装载问题的建模。其求解主要依靠一些启发式算法，也可用遗传算法求解。遗传算法应用于背包问题，涉及到约束条件满足下的遗传编码方法，以及交叉、变异操作算子的设计等方面。背包问题的数学模型实际上是一个0-1规划问题。假设有n个物件，其重量用表示，价值为(j=1,…,n)，背包的最大容纳重量为b。如果物件j被选入背包时，定义变量=1，否则=0。考虑n个物件的选择与否，背包内物件的总重量为，物件的总价值为，如何决定变量的值（即确定一个物件组合）使背包内物件总价值为最大。这个问题解的总组合数有个，其数学模型表示如公式（1-1）所示。遗传算法应用于背包问题时，如果采用通常的二进制编码，一组0-1决策变量{(j=1,…,n)}直接表示为二进制字符串，作为一个个体的遗传基因表示。在这样的表示方法中，若第j位基因码为1时，则第j个物件被选择；若第j位基因码为0时，则第j个物件不被选择。处理约束条件有三种方法[11]：一种方法是用罚函数法改造目标函数；第二种方法是结合贪心算法改造染色体的解码过程；第三种是搜索空间限定法。第二种实际上可以看做是一种混合遗传算法。（1）罚函数法[12]适应度函数的计算用公式（1-2），实际上，上述适应度函数基于一个考虑违背约束条件的惩罚处理，当问题规模很大时，尽管方法可行，但搜索的效率很低，甚至很多情况下所得到的结果比贪心算法的结果还差。（2）混合遗传算法[13]将启发式搜索算法“贪心算法”引入染色体的解码过程中，具体做法很简单，对于那些不满足约束的染色体编码对应的个体，优先装入价值密度较大且编码值为1的物品，直至背包容量限制装不下为止，并将未装入的物品编码值修正为0，形成个体新的染色体编码。（3）搜索空间限定法[14]本论文所采用的即是该方法。它用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一直进行交叉运算和变异运算。虽然这个实现方法对编码方法的要求不高，但它有可能反复地进行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样有可能会降低遗传算法的运行效率。但就解决背包问题来说，该方法相对来说是简单而高效的。研究目标遗传算法是一种模拟达尔文生物进化理论的随机的优化方法，适于处理非线性，多极值，刚性甚至于不可微的目标函数，适用于连续，离散或部分连续部分离散的混合解域空间，并且原则上可望达到真正的理论“最优值”。它是一种非常有竞争性的、很有发展前途的优化方法，在近十年来，获得了巨大的研究进展。本课题在借鉴与研究国内外有关遗传算法所取得的丰硕成果的基础上，对简单遗传算法在交叉算子以及变异算子两个方面进行改进，拟用Java实现带互动界面的遗传算法演示系统，针对具体的背包问题来实现演示功能。开发工具简介本系统采用MyEclipse作为开发工具，MyEclipse企业级工作平台（MyEclipseEnterpriseWorkbench，简称MyEclipse）是对EclipseIDE的扩展，利用它可以在数据库和J2EE的开发、发布，以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的J2EE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML，Struts，JSF，CSS，Javascript，SQL，Hibernate。对于以上每一种功能上的类别，在Eclipse中都有相应的功能部件，并通过一系列的插件来实现它们。MyEclipse结构上的这种模块化，可以让在不影响其他模块的情况下，对任一模块进行单独的扩展和升级。简单而言，MyEclipse是Eclipse的插件，也是一款功能强大的J2EE集成开发环境，支持代码编写、配置、测试以及除错。主要开发语言简介本系统采用Java语言进行开发，Java是由SunMicrosystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaSE,JavaEE,JavaME）的总称，它是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java技术具有诸多优点，如卓越的平台移植性、安全性、高效性、通用性，广泛应用于移动电话和互联网、科学超级计算机、游戏控制台、数据中心、个人PC，它还拥有全球最大的专业开发者社群。整体开发设计简介系统设计方面，采用二进制0-1编码。装入背包的物品用1表示，未装入的用0表示，一种装入方法用一个染色体表示，总共产生的染色体个数等于群体规模。对各个染色体计算其适应度值，淘汰适应度值最低的，复制适应度值最高的，用最高的代替最低的，这样完成选择；再随机产生交叉点及相互交叉的染色体进行交叉。选择交叉的染色体是使用赌轮盘法或者称为比例选择法。两个父代个体通过单点交叉和均匀交叉两种方式交叉产生四个子代个体，选择其中适应度最大的个体作为交叉产生的个体而淘汰其它适应度低的个体；交叉完成后就进行变异，根据变异概率随机选择变异的染色体，随机产生变异点进行变异，若变异后的染色体其适应度小于变异之前的染色体的适应度，则仍然保留变异之前的染色体，否则，将保存变异后的染色体。变异后也需要计算染色体是否符合要求，即是否满足由该染色体结构计算出来的总体积不大于背包的容量。若不符合则变异失败，重新进行选择、交叉、变异，直到符合条件为止。在新一代种群产生之后，判断新种群中个体的最大适应度是否大于父代种群的个体最大适应度，若是则在未达到最大进化代数的条件下进行下一轮进化，否则就将父代适应度最大的个体的染色体复制到新生代种群适应度最小的个体染色体内，并相应地改变其适应度，更新种群信息。这样遗传算法的基本步骤完成，重复以上步骤，直到设计的进化次数才退出。总结起来主要步骤如下：群体的初始化、产生遗传编码，构造适应度函数，选择操作，交叉操作，变异操作。界面设计方面，根据处理数据的方式不同分别显示运算结果，包括最优值，最大体积，染色体结构以及对应的物体收益与体积。对于具体结果显示详细的进化曲线以及产生进化的具体数据。对于对遗传算法效率影响很大的三个参数分别做出了最优值关于这三个参数的变化曲线。本章小结本章以系统开发的相关理论及技术为基础，介绍系统开发过程中需要了解和掌握的方法和技术，并简要的讲解了系统开发的基本内容和研究目标，以及开发过程中所用到的相关工具和语言，最后阐述了整体的开发设计方案。第三章遗传算法的基本原理与实现技术模式定理模式遗传算法通过对群体中多个个体的迭代搜索来逐步找出问题的最优解。这个搜索过程是通过个体之间的优胜劣汰、交叉重组和变异等遗传操作来实现的，那么新一代个体的编码串组成与其父代个体的编码串组成结构之间就有一些相似的结构联系。因此引入了模式的概念。模式表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编码串的一个子集。以二进制编码方式为例，模式H=11*1*描述了长度为5，且在位置1、2、4上取值为“1”的所有字符串的集合{11010,11011,11110,11111}。模式的概念使得我们可以简明的描述具有相似结构特点的个体编码字符串。遗传算法的本质是对模式所进行的一系列运算。通过这些遗传运算，一些较差的模式逐步被淘汰，而一些较好的模式逐步被遗传和进化，最终就可得到问题的最优解。此外为便于定量的估计模式运算，还引入了模式阶和模式定义的概念。在模式中具有确定基因值的位置数目称为该模式的模式阶，模式中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度。模式定理【模式定理】遗传算法中，在选择、交叉和变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按照指数级增长[15]。模式定理阐述了遗传算法的理论基础，它说明了模式的增加规律，同时也给遗传算法的应用提供了指导作用。编码技术编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。在遗传算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。如何设计一种完美的编码方案一直是遗传算法的应用难点之一，也是遗传算法的一个重要研究方向。DeJong曾提出两条操作性较强的实用编码原则[16]：(1)有意义积木块编码原则：应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。(2)最小字符集编码原则：应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。由于遗传算法的广泛应用，迄今为止人们已经提出了许多种不同的编码方法。总的来说，这些编码方法可以分为三大类[17]：二进制编码方法、浮点数编码方法、符号编码方法。二进制编码方法是遗传算法中最常用的一种编码方法，它使用的编码符号集是由二进制符号0和1所组成的二值符号集{0,1}。二进制编码有诸多优点，例如编码、解码操作简单易行，交叉、变异等遗传操作便于实现，符合最小字符集编码原则，便于利用模式定理对算法进行理论分析。本论文便采用二进制编码的方法。浮点数编码方法适合于一些多维、高精度要求的连续函数优化问题。符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。群体设定根据问题的具体情况，把握问题的最优解的范围在整个问题空间的分布范围，然后在这个范围内设定初始种群。产生初始种群时根据约束条件来选择，此时不用考虑其适应度。关于隐含并行性的一个重要结论是：遗传算法所处理的有效模式总数约与群体规模的立方成正比[13]，所以实际应用中，群体个数的取值范围一般在几十到几百。遗传操作中的选择操作对群体规模大小确定的影响很大。群体规模越大时，群体的多样性便也越大，从而算法越不容易陷入局部最优解；但群体过大时，计算量增加，在很大程度上影响算法的效率。若群体规模过小，那么搜索空间的范围就很小，搜索有可能停止在为成熟阶段，导致未成熟收敛。适应度函数遗传算法使用适应度这个概念来度量群体中各个个体在优化计算中与可能达到或接近于或有助于找到最优解的优良程度。适应度越高遗传到下一代的概率就越大。度量个体适应度的函数称为适应度函数。目标函数与适应度函数[18]遗传算法的一个特点是它仅适用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。最优化问题可分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。对于求最大值问题，其转换公式如公式（1-3）所示，求最小值问题的转换公式如公式（1-4）所示。适应度尺度变换遗传算法中，各个个体遗传到下一代的概率是由该个体的适应度来决定的。应用实践中表明，仅仅使用公式（1-3）或公式（1-4）来计算个体适应度时，有些遗传算法会收敛得很快，也有的会很慢。过快的情况可能会使群体的多样性降低，容易导致遗传算法发生早熟现象，使遗传算法所求到的解停留在某一局部最优解上。这就需要我们可能在遗传算法运行的不同阶段，需要对个体的适应度进行适当的扩大或缩小。这种对个体适应度所做的扩大或缩小变换就称为适应度尺度变换。目前常用的个体适应度尺度变换方法主要有以下三种[19]：①线性尺度变换公式为：；②乘幂尺度变换公式为：；③指数尺度变换公式为：；遗传操作选择算子遗传算法使用选择算子来对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体中的概率较大；适应度较低的个体被遗传到下一代群体中的概率较小。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。目前常用的选择算子有[20]：①比例选择这是一种回放式随机采样的方法，其基本思想是：各个个体被选中的概率与其适应度大小成正比。但是由于随机操作的原因，这种选择方法的选择误差比较大，有时甚至连适应度较高的个体也选择不上。②最优保存策略随着群体的进化会产生越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体，这样就会降低群体的平均适应度，并且对遗传算法的运行效率、收敛性都有不利的影响。罪域保存策略进化模型的思想是：当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体。③排序选择排序选择方法的主要着眼点是个体适应度之间的大小关系，对个体适应度是否取正值或负值以及个体适应度之间的数值差异程度并无特别要求。其基本思想是：对群体中的所有个体按其适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。交叉算子交叉算子的设计交叉算子的设计与实现与所研究的问题密切相关，一般要求它既不要太多的破坏个体编码串中表示优良形状的优良模式，又要能够有效的产生出一些较好的新个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。交叉算子的设计包括以下两方面的内容[21]：如何确定交叉点的位置；如何进行部分基因交换。交叉算子的设计简要介绍几种适合于二进制编码个体或者浮点数编码个体的交叉算子。①单点交叉又称为简单交叉，它是指在个体编码串中只随机设定一个交叉点，然后在该点相互交换两个配对个体的部分染色体。其特点是：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可能性最小。②双点交叉指在个体编码串中随机设置两个交叉点，然后再进行两个部分基因交换。③均匀交叉指两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。④算术交叉[22]指由两个个体的线性组合而产生出两个新的个体。为了能够进行线性组合运算，算术交叉的操作对象一般是由浮点数编码所表示的个体。变异算子遗传算法中的所谓变异运算，是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其它等位基因来替换，从而形成一个新的个体。遗传算法中使用变异算子主要有以下两个目的：一是改善遗传算法的局部搜索能力，二是维持群体的多样性，防止出现早熟现象。变异算子的设计包括两方面的内容：如何确定变异点的位置以及如何进行基因值替换。常用的变异操作有基本位变异、均匀变异、边界变异、非均匀变异、高斯变异等，关于每种变异的特点及操作过程限于篇幅不再赘述。本章小结本章主要对遗传算法的基本原理以及实现技术作了比较系统的讲解，包括作为遗传算法基础的模式定理，所用到的编码技术，适应度函数的设置，以及选择、交叉、变异等基本的遗传操作，为后续系统设计与实现打下了基础。第四章背包问题描述与实现以及对简单遗传算法的改进背包问题描述关于背包问题已经在第二章第一节做了比较详细的描述，在此不再赘述。本系统所处理的数据请参看附录文件。编码选择群体设定根据第三章关于群体规模设定所介绍的理论方法，在设计遗传算法解决背包问题的方案中将群体规模设置为200。适应度函数所求的是在所有物体体积之和不超过背包的容量的情况下使得所有物体的价值之和达到最大，所以适应度函数就是各被装入物体的价值之和。约束条件处理约束条件有三种方法：一种方法是用罚函数法改造目标函数；第二种方法是结合贪心算法改造染色体的解码过程，即一种混合遗传算法；第三种是搜索空间限定法。对于用遗传算法解决背包问题来说，限制条件就是背包的容量。所以本系统对约束条件的设定就是保证装入物体的总体积不大于背包的最大容量，用程序来保证直到产生出在解空间中有对应可行解的染色体之前，一直进行交叉运算和变异运算。虽然这个实现方法对编码方法的要求不高，但它有可能反复地进行交叉运算和变异运算才能产生出一个满足约束条件的可行解，这样有可能会降低遗传算法的运行效率。这即是所谓的搜索空间限定法。选择算子的设计关于几种选择算子前面已经做了比较详细的描述，针对于本系统的设计来说，综合考虑各方面因素，选择用比例选择方法。交叉算子的设计交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起着关键作用，是产生新个体的主要方法。关于几类常用的交叉算子第三章也已经做了比较详细的讲解。依据本系统设计时所采用的二进制编码方案以及问题的规模，采用单点交叉与均匀交叉相结合的方法。变异算子的设计从遗传运算过程中产生新个体的能力方面来说，变异运算只是产生新个体的辅助方法，但它也是一个必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。第三章同样也已经介绍了几类常用的变异方法，本系统中采用的是基本位变异，但是增加了关于适应度的判断条件来对其进行改进。对利用遗传算法解决背包问题的改进参数实验遗传算法自身有三个参数，即群体大小，交叉概率及变异概率。下表为设置不同参数的情况下对附录文件中数据的处理结果：遗传代数交叉概率变异概率群体大小第一次第二次第三次第四次第五次平均适应度最大适应度第一组8000.80200297029913083305630543030.83083第二组8000.80.2200306730803059308230643070.43082第三组8000.80.5200304630453002301530493031.43049第四组8000.80.8200304829683040300930343019.83048第五组8000.81200304330483049300430533039.43053第六组80000.2200307030803051305330503060.83080第七组8000.20.2200307130503059305130523056.63071第八组8000.50.2200306130473049305830543053.83061第九组80010.2200308530693049305330683064.83085第十组8000.80.240306830233006301730183026.43068第十一组8000.80.2100304330583051307130683058.23071第十二组8000.80.2160304930593072307130553061.23072第十三组8000.80.2240305530863073309530703075.83095表4SEQ表\*ARABIC\s11参数实验表显而易见的是进化代数越大肯定会更有可能接近最优值。上表中之所以选择进化代数为800是为了更准确的比较各参数对结果的影响，若都会在设置的进化代数之内达到最大值，那么就将无法比较。比较一、二、三、四、五组，横轴为变异概率，纵轴为最优值。如图（4-1）图4SEQ图\*ARABIC\s11最优值-变异概率曲线图从图中可以看出最优值是关于变异概率变化的，当变异概率在0~0.4之间时能得到比较好的结果。比较六、七、八、二、九组，横轴为交叉概率，纵轴为最优值。如图（4-2）图4SEQ图\*ARABIC\s12最优值-交叉概率曲线图从图中可以看出，当交叉概率在0.5至1之间时最优值比较大，所以交叉概率最好选择在这个范围之间的值。比较十、十一、十二、二、十三组，横轴为群体大小，纵轴为最优值。如图（4-3）图4SEQ图\*ARABIC\s13最优值-群体大小曲线从图中可以看出，最优值随着群体规模的增大呈上升趋势，超过200后斜率下降，考虑运行和效率的方面，我们一般取群体大小为200左右。改进的交叉算子：单点交叉与均匀交叉结合的算子先来看一下两种交叉方式的优缺点。单点交叉P1与P2是两个进行交叉的个体：P1=11011|0010P2=10000|0010划线处为两个个体进行交叉的位置，交叉之后的子个体为：=110110010=100000010通过上面的例子可以看出，采用单点交叉方式的优点是它可以很好地保留父代个体的优良性状，是的种群向着更有利的方向进化；但正是由于此，它降低了种群的多样性，单点交叉方式也有可能使得种群向着一个局部最优解的方向进化。均匀交叉同样对于上面的两个父代个体：P1=110110010P2=100000010假设随机产生的一个屏蔽字为：W=101100110均匀交叉的过程是：若，则在第i个基因座上的基因值继承P1的对应基因值，在第i个基因座上的基因值继承P2的对应基因值；若，则在第i个基因座上的基因值继承P2的对应基因值，在第i个基因座上的基因值继承P1的对应基因值。所以：=110010010=100100010通过上面的交叉结果可以看出，均匀交叉可以增加种群的多样性，在某种程度上防止种群进化到一个局部最优解；但其缺点也显而易见，即它对个体的结构破坏的可能性很大，这样很难有效的保存较好的模式，从而可能影响遗传算法的性能。如果设计一个算子能够融合这两种算子的优点来弥补各自的不足，那就会取得有效的改进。本系统的改进方案是，让上一代个体通过两种交叉方式产生四个个体，从这四个个体中选出适应度最大的那个个体作为新一代，新一代个体就产生了很明显的进化，这样整个种群也就产生了显著地改进。下面通过改进程序所得到的数据来演示效果。数据请参考附录文件，参数设定如表（4-2）种群大小交叉概率变异概率进化代数2000.80.2800表4SEQ表\*ARABIC\s12参数表实验结果统计如表（4-3）第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最优值298529692950298529502958295230013016295429753016最小生成代数46219699816330447046128524523446表4SEQ表\*ARABIC\s13改进的交叉算子所得结果统计表最好结果：代数285，最优值3016，如图（4-4）所示：图4SEQ图\*ARABIC\s14改进的交叉算子所得最优结果图进化曲线如图（4-5）所示图4SEQ图\*ARABIC\s15改进的交叉算子所得最优值-进化代数曲线图下表是交叉算子改进之前的数据结果：第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最优值29422961295329932935294629222942297329502951.72993最小生成代数300402563101340933745131352219.313表4SEQ表\*ARABIC\s14未改进的交叉算子所得结果统计表最好结果：代数310，最优值2993，如图（4-6）所示：图4SEQ图\*ARABIC\s16未改进的交叉算子所得最优结果图进化曲线如图（4-7）所示图4SEQ图\*ARABIC\s17未改进的交叉算子所得最优值-进化代数曲线图通过以上数据及曲线可以看出，改进的交叉算子在最优值方面比改进之前仅适用单点交叉的方式所得结果有明显的改善。改进的变异算子：不降低适应度的变异方式简单遗传算法采用的变异算子是对染色体上每一个基因位以某一概率进行变异，这样的一个缺点是变异之后的染色体适应度可能会小于变异之前的染色体适应度，结果会导致这一代群体平均适应度的降低，从而影响进化的效率。本文对变异算子的改进之处是：如果染色体变异之后其适应度降低，那么就仍然让染色体保留变异之前的结构，否则便进行变异。实验参数如表（4-2）所示，实验结果统计如表（4-5）所示（本次实验数据是在交叉算子改进的基础上进行的）：第一次第二次第三次第四次第五次第六次第七次第八次第九次第十次平均值最好值最优值309530973103309530943099310331033098310330993103最小生成代数1414151313121313121413.312表4SEQ表\*ARABIC\s15改进的变异算子所得结果统计表最好结果：代数14，最优值3103，如图（4-8）所示：图4SEQ图\*ARABIC\s18改进的变异算子所得最优结果图进化曲线如图（4-9）所示：图4SEQ图\*ARABIC\s19改进的变异算子所得最优值-进化代数曲线图目前对背包问题，比较好的解决方法是混合遗传算法，它处理附录文件中的数据能够达到的最大最优值是3103[10]，本改进算法的最优值的平均值为3100，基本上已经达到使用混合遗传算法的准确度，而且本改进算法的进化速度相当快，一般可以在20代以内达到最优值。相比于改进之前的表（4-4）中的结果，可以明显的看出算法的改进效果。本章小结本章首先对待解决的问题进行了详细的描述，然后阐述了一些常用的编码技术，包括群体的设定、适应度函数、限定条件、选择算子的设计、交叉算子的设计和变异算子的设计。最后详细的分析了本系统对于传统的遗传算法在解决背包问题方面的改进之处，并用数据结果证明了改进的效果。第五章带互动界面的遗传算法演示系统详细设计系统功能模块详细设计带互动界面的遗传算法演示系统的详细设计包括从文件中读取数据、从键盘输入数据、关于演示系统、退出演示系统四个模块的详细设计。从文件中读取数据用户通过输入已存在的有效文件名或者完整路径来使系统达到演示效果。流程如图5-1所示：图5SEQ图\*ARABIC\s11处理文件流程(2)从键盘输入数据流程如图5-2所示：图5SEQ图\*ARABIC\s12从键盘输入数据流程参数曲线演示对于遗传算法的种群大小、交叉概率、变异概率三个主要参数，本模块分别做出了最优值-种群大小曲线，最优值-交叉概率曲线，最优值-变异概率曲线。关于演示系统本模块主要介绍了系统的一些基本信息，包括作者姓名，学号，专业，班级等。退出演示系统用户通过此模块退出演示系统。系统性能优化设计关于本系统在数据处理方面的改进在第四章已经做了比较详细的分析与介绍，在此不再赘述。本章小结本章在第三章、第四章的基础上对系统进行了详细设计。重点介绍系统功能模块的详细设计及其流程，紧接着对性能优化等方面进行了设计。第六章带互动界面的遗传算法演示系统实现系统界面实现本系统开发语言使用Java，使用MyEclipse作为开发工具。该项目的运行环境为MicrosoftWindows7。本系统在界面设计方面使用的是Java的Swing图形用户界面。图（6-1）为从文件中读取数据模块的演示界面：图6SEQ图\*ARABIC\s11从文件读取数据模块主界面图6-2为从键盘输入数据模块的演示界面：图6SEQ图\*ARABIC\s12从键盘输入数据模块界面图（6-3）为参数曲线演示界面：图6SEQ图\*ARABIC\s13参数曲线演示模块界面图6SEQ图\*ARABIC\s14关于演示系统模块界面系统功能模块实现以从文件中输入数据模块为例。主界面要求用户输入文件名称或者完整的文件路径，若文件不存在或者文件数据有误都会发出警告。如图所示：图6SEQ图\*ARABIC\s15文件不存在时发出警告图6SEQ图\*ARABIC\s16文件数据有误时发出警告若输入的文件名存在并且文件数据无误则系统显示处理结果，如图所示：图6SEQ图\*ARABIC\s17显示处理结果可以显示详细的进化曲线，包括平均适应度以及最大适应度曲线，如图所示：图6SEQ图\*ARABIC\s18进化曲线图可以显示详细的进化数据，不过显示的是真正进化的数据，对于那些没有进化或者退化的数据不予显示。如图所示：图6SEQ图\*ARABIC