毕业论文遗传算法在函数优化中的应用.doc

《毕业论文遗传算法在函数优化中的应用.doc》由会员分享，可在线阅读，更多相关《毕业论文遗传算法在函数优化中的应用.doc（23页珍藏版）》请在三一办公上搜索。

1、遗传算法在函数优化中的应用目录1.绪论11.1概述11.2遗传算法的发展历史与研究进展22.遗传算法流程与应用举例42.1遗传算法中各重要因素分析42.2重要参数设置62.3简单的遗传算法运算示例63.遗传算法在函数优化应用中的性能研究103.1遗传算法在实际应用中的性能影响因素103.2函数优化问题的描述123.3求解函数优化问题的最优交叉、变异率组合的研究143.4一种求解函数优化问题的自适应遗传算法173.5小结19结束语19参考文献20致谢211.绪论1.1概述遗传算法(genetic algorithms简称GA)由美国密歇根大学的John HHolland教授等创立的一类仿生型的优

2、化算法。它是以达尔文的生物进化论和孟德尔的遗传变异理论为基础、模拟生物进化过程、自适应启发式全局优化的搜索算法。由于遗传算法无需过多地考虑问题的动力学信息，如连续、可微等，该算法结构简单，并且具有全局搜索能力、信息处理的隐并行性、鲁棒性和可规模化等优点，它在思路上突破原有的最优化方法的框架，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，现己被广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，并且在经济和决策方面也有很好的应用，是21世纪有关智能计算中的关键技术之一。遗传算法的处理对象不是参数本身，而是对参数进行了编码的个体，因此不仅可以对传统的目标函数优化求解，而且可以

3、处理诸如矩阵、树和图等结构形式的对象，用适应度函数同时对搜索空间的多个解进行评估，它将每个可能的问题表示为“染色体”，然后按遗传学规律进行选择、交叉和变异操作，直到满足终止条件为止。隐含并行性和全局搜索性是遗传算法的两大特点，前者可使遗传算法只需检测少量的结构就能反映搜索空间的大量区域，后者则使遗传算法具有良好的稳健性。在遗传算法的诸多应用中，函数优化是最显而易见的应用，也是经典的应用。函数优化问题是许多领域中普遍存在的问题，也一直是人们探索的若干重要问题之一。很多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以转化为函数优化问题来求解。函数优化的本质就是从所有可能的方案中选择出最合理

4、、达到最优目标的方案。它通常可归结为求最小值问题，对于最大值问题可以通过对函数取反，将其转化为最小值问题。对于函数优化问题，传统的求解方法有最速下降法、牛顿法、拉格朗日乘数法、罚函数法等等。对于这些确定的搜索优化方法来说，函数可微通常是求解问题的前提，而且随着函数维数的增长，求解的难度大幅度增长。因此传统的优化方法并不适合于求解不可微函数以及高维函数的优化问题。一种模仿生物自然进化过程的、被称作为演化算法的随机优化技术在解这类优化难题中显示出了优于传统优化算法的性能。自70年代Holland正式提出遗传算法以来，非经典的随机搜索优化方法如演化策略、演化规划、基因表达式程序设计等层出不穷。遗传算

5、法就是其中一种具有代表性的随机算法，与传统的优化算法相比，遗传算法不是从单个点，而是从点的群体开始搜索，对初始点集的要求不高；遗传算法不是直接在参变量集上实施，而是利用参变量集的某种编码；遗传算法利用适应值信息，无需导数或其他辅助信息，这就使得它在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，它也能以较大的概率找到整体最优解。遗传算法优化求解过程与梯度信息无关，只需要目标函数是可计算的，对于复杂的优化问题只需选择、杂交、变异三种遗传运算就能得到优化解，基于这些显著的优点，GA已引起人们的广泛应用和研究。1.2遗传算法的发展历史与研究进展1.2.1遗

6、传算法的发展历史遗传算法的发展历史始于二十世纪60年代。JHHolland教授认识到生物的遗传和自然进化现象与人工自适应系统的相似关系，提出在研究和设计人工自适应系统时，可以借鉴生物的遗传机制，以群体的方式进行自适应搜索。1967年，Holland的学生Bagley在他的博士论文中首次提出了“遗传算法”这一术语，提出选择、交叉和变异，与目前遗传算法中相应的算法十分接近，引入适应度定标(Scaling)的概念。同时，他也首次提出了遗传算法自我调整的概念。第一个把遗传算法用于函数优化的是Hollstien，1971年他在论文计算机控制系统中的人工遗传自适应方法(Artificial Genetic

7、 Adaptation in Computer ControlSystems)中阐述了遗传算法用于数学反馈控制的方法，主要讨论了二变量函数的优化问题。1975年，Holland出版了第一部著名的专著自然系统和人工系统的适配(Adaptation in Natural and Artificial Systems)，该书系统地阐述遗传算法的基本理论和方法，并提出了遗传算法的基本定理模式定理(Schema Theorem)，奠定了遗传算法的理论基础。同年，美国De Jong博士在其论文遗传自适应系统的行为分析中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，将选择、交叉和

8、变异操作进一步完善和系统化，同时又提出了诸如代沟(generationgap)等新的遗传操作技术，建立了著名的De Jong五函数测试平台。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类系统(Classifier System)，开创了基于遗传算法的机器学习的新概念，为分类器在构造上提出了一个完整的框架。1987年，Davis出版了Genetic Algorithm and SimulatedAnnealing一书，以论文集形式用大量的实例介绍了遗传算法的应用技术。1989年，Goldberg出版了专著遗传算法在搜索优化和机器学习中的应用(Genetic Algorit

9、hms in Search，Optimization and Machine Learning)，该书系统总结了遗传算法的主要成果，对GA的基本原理及应用做了比较详细、全面的论述，奠定了现代遗传算法的科学基础。该书至今仍是遗传算法研究中广泛适用的经典之作。此后，许多学者对原来的遗传算法(或称基本遗传算法)进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。进入90年代后，遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，在各种不同领域如机器学习、模式识别、神经网络、控制系统优化及社会科学等中得到广泛应用，引起了许多学者的关注。1991年，Lawre

10、nce Davis出版了遗传算法手册(Handbook ofGeneticAlgorithm)一书，对有效地应用遗传算法具有重要的指导意义。国外出现了一些著名学者，如Holland，Goldberg，Davis等，其经典著作也鲜为人知，国内也有一些有关的书籍相继出版，一系列以遗传算法为主题的国际会议变得十分活跃。从1985年开始，国际遗传算法会议，即ICGA(InternationalConference on Genetic Algorithm)每两年举行一次；在欧洲，从1990年开始也每隔一年举办一次类似的会议，即PPSN(Parallel Problem Salving from Nat

11、ure)会议；目前与GA有关的学术会议有：世界计算智能大会，它是IEEE主办的综合性学术大会，有ICNN、FUZZY IEEE和ICEC三个学术会议联合组成，每四年召开一次；此外，还有ANN&GA、EP、GP、EP、SEAL等和Internet上专门的遗传算法站点更是推动着遗传算法实质性的进展。进入21世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学已成为一个研究热点。遗传算法因能有效地求解NP难问题以及非线性、多峰函数优化和多目标优化问题，得到了众多学科的高度重视，同时也极大地推动了遗传算法理论研究和实际应用的不断深入与发展，目前已在世界范围内掀起关于GA的研究与应用热潮，可以预测随着

12、进化论、遗传学、分子生物学、计算机科学的进展，GA也将在理论与应用中得到发展和完善。1.2.2遗传算法的常见应用(1)函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于解变量是实数型的优化问题，为提高GA的搜索效率，可采用动态编码和实数编码。对于带约束的优化问题，引入罚函数，把约束条件结合到且标函数定义中。樊重俊用特定的杂交、变异算子在一定程度上解决了线性等式优化问题；对于多峰函数优化问题，1987年Goldberg和Richardson用共享和限制交配机制结合的方法成功实现了多峰的搜索；袁丽华等利用小生境技术，成功实现多峰的搜索；2000年刘洪杰等M利用多种

13、算子混合的方法来搜索多极值点，该算法对等高等距、不等高等距和不等高不等距情况都有好的结果。对于多目标函数的优化问题，多数情况下，最优解是不存在的，一般找到其Pareto最优解或非劣解，这仍是个值得研究的新课题，也是当前管理科学、决策理论、系统工程、运筹学等学科研究中十分重要的内容。(2)组合优化组合优化问题，通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题，很难求出最优解。实践表明遗传算法求解组合优化问题非常有效。如GA在求解巡回旅行商问题、装箱问题、背包问题、图形划分问题等方面得到成功地应用；唐立新、张毅、曾三友等学者在各自的研究领域已取得一

14、定的成果。(3)遗传编程与学习Koza成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。Kinnear提出了基于遗传算法的移动机器人路径的新方法；基于GA的机器学习特别是分类器系统已被用于学习模糊控制规则、人工神经网络的连接权和结构优化等领域，也是目前遗传算法研究中一个十分活跃的领域。(4) 自动控制遗传算法已在自动控制领域得到了初步应用，并取得良好的效果。如基于GA的模糊控制器的优化设计，用GA进行航空控制系统的优化；20世纪80年代，Goldberg用GA学会控制天然气输气管道系统；机器人控制等等唧。此外，遗传算法也在生产调度问题、图像与信号处理、设计、人工生命等方面

15、获得了广泛的运用。这里就不一一赘述了。总之，随着研究的深入，算法不断地被改进，遗传算法的应用领域将会越来越广，效果也越来越好。2.遗传算法流程与应用举例2.1遗传算法中各重要因素分析2.1.1编码理论遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、有序串）。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码方式，算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同，采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操作，从而更易于引入相关启发式信息

16、，往往可以取得比二进制编码更高的效率。2.1.2 染色体每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群体。群体中染色体可重复。2.1.3 随机初始化随机或者有规律（如从一个已知离解较近的单点，或者等间隔分布地生成可行解）生成第一代群体。一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜索全局最有解的能力。2.1.4适应度一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取操作中被抽取到的概率。估价函数是评价染色体适应度的标准，常见的估价函数有：直接以解的权值（如01背包问

17、题以该方案装进背包物品的价值作为其适应度），累计二进制串中1/0的个数（针对以二进制串为编码理论的遗传算法），累加该染色体在各个目标上的得分。2.1.5遗传算子遗传算子作为遗传算法的核心部分，其直接作用于现有的一代群体，以生成下一代群体，因此遗传算子的选择搭配，各个算子所占的比例直接影响遗传算法的效率。一个遗传算法中一般包括多种遗传算子，每种算子都是独立运行，遗传算法本身只指定每种算子在生成下一代过程中作用的比例。算子运行时从当前这代群体中抽取相应数量的染色体，经过加工，得到一个新的染色体进入下一代群体。下面列出几种常见的遗传算子：保持算子：抽取1个染色体，直接进入下一代。该算子使算法能够收敛

18、。交配算子：抽取2个染色体，交换其中的某些片段，选择适应度高的（或者都选），进入下一代群体。该算子使得遗传算法能够利用现有的解寻求更优的解。变异算子：抽取1个染色体，对其进行随机的改变，进入下一代群体。该算子使得算法可以跳出局部最优解，拥有更强搜索全局最有解的能力，防止陷入局部搜索，该算子的概率不可过高，否则将引起解的发散，使得算法无法收敛。2.1.6 抽取抽取操作是遗传算法中一个重要基本操作，作用是按照“优胜劣汰”的原则根据各个染色体的适应度从当前这代群体中挑选用于遗传算子的染色体。通常采用的手段是偏置转盘：设算法中群体数量为，首先计算当代群体的各染色体适应度之和。将1内的整数划分成个区间段

19、，每个染色体所占的区间段的长度既是它的适应度。这样，随机产生一个1的整数，抽取该点所属区间段相对应的染色体，就可以保证任意一个染色体xi 在抽取操作中被抽取到的概率为。2.1.7 终止条件遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条件可以设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体。2.2重要参数设置在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使用不同的遗传参数。在大规模的问题上，一次遗传算法的不同时期也可以设置不同的遗传参数。对遗传算法效率影响较大的参数

20、如下：群体大小：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越多，越有利于搜索全局最有解，但是会下降收敛的速度，所需的时间也更多。迭代次数：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所需的时间也越多，如果时间允许，采用多次初始化群体的操作要比设置很大的迭代次数来得更高效些。保持率：保持算子所占的比例，通常不超过70%交配率：交配算子所占的比例，通常不超过50%变异率：变异算子所占的比例，通常不超过1%2.3简单的遗传算法运算示例在这一节，我们将运用猫和老鼠的例子详细说明遗传算法每一组成部分。假设我们希望通过遗传算法得到最优秀的猫。2.3.1染色体的表达：我们把猫的

21、染色体简单分成两部分，一部分表示奔跑速度，另一部分表示智力水平。每一项属性用一个四位的二进制数进行编码，数字越大代表该属性越好。如图2.1所示。图2.1 染色体编码猫1的染色体为（10100101），我们可以从染色体看出它的奔跑速度高，但是比较笨。相反的，猫2（00111101）速度慢，但是智力水平高。除了二进制以外，遗传算法还有很多编码方法，比如格雷码、浮点数编码和字母编码等。在这一节，我们均用二进制的编码方式来介绍遗传算法。2.3.2评估函数评估函数用以评价种群中每个染色体的适应值，又称为适应值函数（fitness function）。在遗传算法中，适应值函数起着一个环境的作用，它给与种群

22、一个生存的环境，并决定了哪些个体容易存活。在这个例子当中，猫跑得越快越聪明就越容易捉到老鼠，也就越适应环境。我们简单构造一个用以评价猫的适应值函数：适应值=速度+智力则对于猫1，我们首先把它的染色体的二进制编码转换为十进制，然后再把它的两个属性相加得到它的适应值为10+5=15。同样的，猫2的适应值为3+13=16，如图2.2所示。图2.2 适应值的计算2.3.3选择算子运用适应值函数对种群中的每个染色体进行评价以后，每个染色体都被赋予一个适应值。选择算子模仿自然的选择过程，从种群中选择出适于生存的个体，并复制到下一代。适应值越高的个体更容易被选择从而复制到下一代中，而适应值低的个体则往往不被

23、选择。假设一代种群中有4只猫，它们的染色体分别为：（01001000），（11001010），（00100010），（10000100）。我们根据预先定义的适应值函数计算出它们的适应值分别为：12，24，4，12。选择往往是基于适应值概率分布的一个随机选择过程，有轮盘赌选择（roulette wheel selection）、锦标赛选择（tournament selection）和比例选择（proportionate selection）等一系列不同的选择方法。我们以最常用的轮盘赌选择为例，首先构造一个轮盘，并将其分成4份，每一份的大小和其中一只猫的适应值相对应，如图2.3所示。图2.3轮盘赌

24、示意图随机转动轮盘，每次就会选择出一个染色体并复制到下一代。我们可以看出，适应值越大的染色体在轮盘中被选中的概率越高，随机转动轮盘4次就可以复制出新的一代种群。这一过程可以用简单的概率计算来表达，如表2.1所示。表2.1 各个染色体的选择概率分布首先将种群中所有染色体的适应值相加得到一个总的适应值，然后将每个个体的适应值除于总适应值，就可以得到每个个体被选择的概率。根据这一概率分布进行选择就可以得到下一代的种群。这种基于轮盘的选择称为轮盘赌选择。2.3.4交叉算子交叉算子用以模仿自然界群体遗传过程中发生的交配，对新一代的种群进行遗传上的改变。按照不同的交叉方法，交叉算子分为单点交叉（singl

25、e point crossover）、两点交叉（two point crossover）和均匀交叉（uniform crossover）等等。以单点交叉为例，首先对种群进行两两配对，并从中选出一对染色体，假设为（01001000）和（10000100）。如图2.4所示。图2.4 交叉过程示意图随机选取一个交叉点，并相互交换位于交叉点右边的所有位，产生出两个新的个体（01000100），（10001000）。我们可以看出，交叉产生出了适应值比父母体都要高的进化染色体，这是因为这个染色体通过交叉分别继承了父母的优良特性。虽然一些较差的染色体也会产生，但是它们在以后的选择过程中往往会被淘汰，从而不会

26、对整个过程产生大的影响。2.3.5变异算子变异以较小概率对个体编码串上的某个或某些位值进行改变，它可以分为均匀变异（uniform mutation）和非均匀变异（non-uniform mutation）等等。对于一个选定的染色体执行变异操作，就是随机改变其中的一或几位的基因，将它们从1变为0，或者从0变为1，如图2.5所示。变异在染色体中随机引入新的信息，使得进化过程趋于多样化。图2.5变异过程示意图2.3.6流程图经过上述选择，交叉和变异算子的作用，新的一代种群就产生了。我们不断反复这一过程，将这一群体一代又一代地演化下去，直到满足一定条件为止。算法的基本流程图如图2.6所示。在若干代后

27、，遗传算法就可以在种群中进化出一只跑得最快而且最聪明的猫（11111111）。图2.6 遗传算法流程图3.遗传算法在函数优化应用中的性能研究遗传算法的性能问题一直是该领域的重要内容，研究其性能不仅具有理论上的意义，尤其对实际应用特别是计算机程序更为重要。近几年来，遗传算法在这方面取得了突破性进展。如Goldberg等首先分析了简化遗传算法的性能，Eiben、Guo Guanqi等提出了一种PLS算子，有机结合实数编码与Gaussian适应性交异，以提高求解多峰函数优化问题时的收敛速度和可靠性，杨世达通过多方改进，使遗传算法在优化计算过程中性能明显改善。然而，遗传算法的性能研究至今仍然是一个悬而

28、未决的问题。本章对遗传算法在函数优化应用中的性能影响因素进行了分析，根据人们选择参数的经验主义和盲目性，提出了一种寻找求解函数优化问题的最优交叉、变异率组合的新方法，并通过了实例验证。同时，提出了一种自适应的遗传算法，其效率高，性能好，并具有一定的通用性。3.1遗传算法在实际应用中的性能影响因素在实际应用中，遗传算法的性能影响因素很多，但主要是由编码方法、操作算子和适应度函数决定。编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方法决定了个体的染色体排列形式和解码方法，也影响到交叉、变异等遗传算子的运算方法。Rudolph和 Qi等分别对二进制和浮点数编码的遗传算法

29、进行了全局收敛性分析，为遗传算法的应用提供了重要参考依据。传统的遗传算法通常采用有限长的二进制编码，这有利于数学模型的建立，便于人们对模式定理、收敛性分析、欺骗问题等理论分析和计算机的处理，但不利于人们的习惯表达。Dc Jong曾提出了两条操作性较强的编码原则：有意义积木块编码原则和最小字符集编码原则，但至今仍没有完整的理论对其进行指导。因而人们提出了多种不同的编码方法，从具体实现的角度可以分为三大类，即二进制编码方法、实数(浮点)编码方法和符号编码方法。实数(浮点)编码在90年代以来得到越来越多的重视和发展。实数编码是连续参数优化问题直接的自然描述，相对于二进制编码有许多优势：它适合在遗传算

30、法中表示范围较大的数，可以提高解的精度和运算速度，便于在较大空间的遗传搜索，避免了编码中带来的附加问露，便于和其它方法的结合等。符号编码方法是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。符号编码的主要优点是：（1）符合有意义积木块编码规则：（2）便于在遗传算法中利用所求解问题的专门知识；（3）便于遗传算法与相关近似算法之间的混合使用。遗传算法的性能与其操作算子息息相关，近年来，研究者对操作算子做了大量的分析和研究，并提出一些方法和策略以提高算法的性能。（1）选择算子选择算子的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。常见的有适应度比例、最佳个体保留、期望

31、值、排序选择、联赛选择、排挤方法等，其中适应度比例方法是遗传算法最基本也是最常用的选择方法，也叫赌轮或蒙特卡罗选择。最优保留策略可视为选择操作的一部分，它是遗传算法收敛的一个重要保证条件，可以使算法最终能收敛到全局最优值。不同的选择方法对于遗传算法的在线和离线性能的影响均不相同。在实际应用中，应根据问题求解特点采用较合适的方法或者结合使用。（2）交叉算子交叉算子是遗传算法区别于其它优化算法的本质特征，在遗传算法中起关键作用，是产生新个体的最主要方法，它决定了遗传算法的全局搜索能力。它直接影响着算法的最终实现和性能，在一定程度上决定着遗传算法的发展前景。经典的观点强调交叉的作用，其理论基础是著名

32、的积木块假设，这一观点与生物学中的实际观察最相符合。但交叉操作正受到理论与实践两方面的严峻考验与挑战，如钟国坤等啤l提出了一种单亲遗传算法，抛开交叉算子，而代之以隐含序号编码的遗传算法、交叉算子功能的基因换位等遗传算子，算法效率高，并且不要求初始群体的多样性，也不存在“早熟”问题。交叉概率以的大小也直接影响着遗传算法的性能，较大的。可增强开辟新的搜索区域的能力，但高性能的模式遭到破坏的可能性增大，若，太小，搜索可能陷入迟钝状态，因而合适的交叉概率是算法获得良好性能的条件之一。实际应用中，研究者们设计了各种新的交叉策略，并收到了良好的性能。BianRunqiang等提出了一种新的改进交叉策略，有

33、效克服了近亲繁殖引起的早熟现象，A.L.Tuson等采用自适应的调整方法对生产调度问题进行了测试，收到了可靠的性能，金聪等提出了一种每个基因位交叉概率自适应变化的新的交叉操作，算法性能远高于SGA，钟国坤等用异位交叉算子极大地提高了算法的收敛速度，而且不易陷入局部最优解，张铃等则对交叉操作进行了重新设计，提出了佳点集遗传算法，速度和精度都得到了改善，并有效地避免了早熟现象。（3）变异算子变异是传统遗传算法中一个必不可少的步骤，因其局部搜索能力而作为辅助算子，能维持群体多样性，防止出现早熟现象。在实际应用中，交叉和变异算子相互合作，共同完成对全局和局部的搜索，以获得良好的收敛性能。大量应用实例可

34、以看到遗传算法有这样一个特点，即在早期可以迅速达到次优解接近最优解，但此后搜索到最优解的速度就慢下来了。究其原因是因为应用中往往采用固定的较大的。和较小的。并且在整个搜索过程中保持不变，所以算法可以迅速接近最优解，但在最优解附近由于较小的变异率而缺乏较强的局部搜索能力以致很难找到最优解。针对这种情况，可采用动态参数自适应调整方法，即在算法开始时采用较大的和较小的，算法搜索速度放慢时动态调整参数大小，使适当减少而适当增大。但同时也要考虑De Jong在经过仔细分析和计算后所得出的其中一个重要结论：虽然的增大会增加群体的多样性，但它却降低了算法的在线性能和离线性能，并且随着的增大，算法性能越来越接

35、近于随机搜索算法的性能。因而，它们之问如何有效地协同也是目前遗传算法的一个重要研究内容。遗传算法使用个体的适应度函数对解的质量进行评价，适应值越高，解的质量就越好，该个体被选择的概率就越大，因而，适应度函数直接影响着算法的性能。针对应用中的各种不同现象，对适应度函数须进行适当调整，即适应度定标(FitnessScaling)，以提高遗传算法的优化搜索性能。目前常见定标方式有三种，即线性定标、幂函数定标和指数定标。适应度函数评价是选择操作的依据，一般以发现最大值或准最优解作为遗传算法迭代停止条件，但在许多优化问题中适应度最大值并不清楚，因而众多的实际应用中，若发现群体个钵的进化已趋于稳定状态，则

36、终止算法迭代。另外，由于遗传算法仅靠适应度来评价和引导搜索，所以求解问题所固有的约束条件不能明确表示出来，而实际应用中许多问题都是有约柬条件的，作为一种解决方法。可将问题转换为一个带罚函数(penalty function)的非约束优化问题，但同时要注意罚函数值在约束边界处发生急剧变化可能会引发问题。具体应用中，适应度函数的设计要结合求解问题本身的要求而定。3.2函数优化问题的描述函数优化问题是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。对于一些非线性、多模型、多目标的函数优化问题，用其他方法较难求解，而用遗传算法却可以方便地得到较好的结果。通常，目标函数优化问题可以描述为：

37、 （3.1） 或： （3.2）其中S称为搜索空间，。称为目标函数。(3.1)式描述的优化问题称为极大化问题，(3.2)式描述的称为极小化阃题。当把看成是一序列的函数时，上述的问题就转变为多目标优化问题。广义地讲，所有的搜索、优化都是对目标函数的“函数”优化，这罩所指的函数主要是强调函数的数学特征，如函数的连续性、凹凸性、多峰性、多维性等。在遗传算法的研究工作中，函数优化问题受到了较大的重视。在遗传算法产生的早期，就有一批学者(如Hollstien、De Jong等)在研究这个问题，直到如今，仍有不少人在不断探索求解函数优化问题性能更好的遗传算法，在前人的成果积累上，通过深层次的理论分析和大量的

38、各类实验，极大地推动了。之所以如此，主要有下面两条原因：首先，对很多实际问题进行数学建模后，可将其抽象为一个函数优化问题。由于问题种类繁多，影响因素复杂，这些数学函数会呈现不同的数学特征或这些不同数学特征的组合，因此寻求能处理各种不同的复杂函数又具有良好性能的方法是很困难的。其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。主要是由于闯恶种类繁多，影响因素复杂，若对各种情况都加以考虑并试算，其工作量势必太大。虽然人们提出了一些评价指标，如De Jong的两个用于定量分析的指标：即在线性能指标和离线性能指标，分别测量遗传算法的动态性能和收敛性，但这只是反映了算法在某一方面的性能，不

39、足以完全反暖算法在各种实际应用中的效果。另外，函数优化问题不包含有某一具体应用领域的专门知识，便于不同应甩领域的研究人员进行相互理解和交流，并能较好地反映算法本身所具有的本质特征和实际应用能力。所以入们专门设计了一些具有复杂数学特征的纯数学函数，通过遗传算法对这些函数的优化计算来测试各种算法的性能。函数优化问题是一个复杂的优化问题，特别是不可微或者多峰的函数，往往不能有效地求解。而遗传算法作为一种高度并行、随机、自适应的全局优化概率搜索算法，它将每个可能的问题表示为“染色体”，从而得到一个由染色体组成的“群体”，然后按遗传学规律进行选择、交叉、变异操作，直到满足终止条件为止。对很多实际问题进行

40、数学建模后，可将其抽象为一个数学函数的优化问题，出于问题种类的繁多、影响因素的复杂，这些数学函数会呈现出不同的数学特征，比如连续的、离散的、凸的、凹的、单峰值的、多峰值的函数等等，经常遇到的函数还有这些不同数学特征的组合，除了在函数是连续、可求导、低阶的简单情况下可解析地求出其最优解以外，大部分情况需要通过数值计算方法来进行近似优化计算，尽管人们对这个问题研究了很多年，但至今仍无一种既能处理各种不同的复杂函数、又具有良好求解结果的数值计算方法，特别是当问题的规模比较大时，优化计算时的搜索空间急剧扩大，人们认识到要严格地求出其最优解不可能、也不太现实，所以需要研究出一种能够在可接受的时间和可接受

41、的精度范围内求出数值函数近似最优解的方法或通用算法。遗传算法提供了求解复杂系统优化问题的通用框架，函数优化正是其最成熟的应用领域。在对各种复杂形式的测试函数的计算中，由于遗传算法直接以目标函数值作为搜索信息，同时使用多个搜索点进行搜索，且这种概率搜索始终遍及整个解空间，都能找到几乎全局最优解。对于一些非线性、多模型、多目标的函数优化问题，在其他优化方法较难求解时，遗传算法也能方便地得到较好的结果。实践表明，遗传算法求解函数优化问题的计算效率比较高、适用范围相当广。与传统的优化方法相比，遗传算法具有如下特点：具有简单通用、鲁棒性强、适于并行处理以及高效、实用等显著优点。1975年De Jong发

42、表了题为“An Analysis ofthe Behavior of a Class of GeneticAdaptive System”的学位论文，主要论述了遗传算法应用于函数最优化的研究，并根据其相关特性精心挑选了五种函数最优化的测试例子，且在计算机上经过大量的计算实践，得到了一些在遗传算法的发展和应用过程中具有重要指导意义的结论，其研究方式已成为遗传算法研究和发展的典范。3.3求解函数优化问题的最优交叉、变异率组合的研究遗传算法能较好地解决函数优化问题，但研究者发现，参数环境对遗传算法的性能和结果的质量至关重要，参数环境能改变算法的函数优化能力，这是遗传算法领域的一个重要研究课题，应该引

43、起人们的高度重视。如WolpcrtDH等人通过详细分析说明了在实际应用中算法中参数之闯的协作的重要性。孙艳丰等在大量资料的基础上也声明了参数环境对遗传算法在函数优化中的性能和结果的至关重要性。但在大量理论和实际应用当中，通常人们对交叉和变异率的选择是盲目的，极易出现早熟现象。而且受众多因素影响，要选择一个满意的操作和最优的参数楚很困难的，人们基本上都是根据理论分析中各参数的大致范围来选择参数，或根据经验来确定解决某个实际问题的最优参数组合，但通常要找到最优组合并不容易，往往会花费大量的时间，因此，科学、有效地对遗传算法中的参数特别是交叉和变异概率选择是十分必要的。如巩敦卫基于模式定理的推广形式

44、，探讨了交叉和变异率的上限。陈长征、A.L.Tuson就对其作用机理进行了深入分析并提出了改进措施，采用新的交叉和变异概率选择方法，著显示了其优越性能。利用遗传算法进行函数优化计算时，若精度不是太高，自变量不是太多时，可以采用二进制编码来表示个体。遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子，遗传算法通过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。本文在传统的二进制编码的基础上，采用动态调整交叉概率、变异概率的疗法，在程序运行过程中记录每一种不同组合参数下最佳个体所在世代数、适应度、最优解的值，通过它们与出现最优

45、值时进化世代数之间的关系图和统计分析，直观而又轻松地找到了解决某一类型函数优化问题各参数的最优组合(程序运行过程如图3.1所示)，实例验证这是非常有效的，给人们在实际应用遗传算法时盲目选择参数的问题提供了一条新的解决思路，具有一定的现实意义。图3.1 对于函数，（在x=1.850547时有最大值3.850274）（如图3.1所示），在染色体长度lchrom=25，种群大小确定（popsize=80）的情况下，通过模拟实验，、分别在0.70-0.90,0.001-0.100的范围内，遗传算法能按人们所熟知的理论具有极强的自适应能力，找到问题的最优解。如=0.82，=0.045时，在第40代收到最

46、佳值3.850274（最大值max，最小值min、平均值avg和进化世代数gen的关系如图3.2所示）；但=0.79，=0.002时，却在第3代局部收敛到非最佳值3.324148，并且误差大，不能满足精度要求；这说明在应用遗传算法解决实际中的函数优化问题时，注意各参数的取值是必须的。图3.2 max、min、avg和gen的关系图(=O82，=O045)采用本文所述方法，在程序运行过程中动态调整遗传算法的，值，发现不同的参数组合其性能省察极大（、的不同组合与最佳收敛世代关系如图3.3所示）。图3.3 的动态、与收敛世代数说明在实际应用中只有恰当选择各参数的值才有可能获得良好的性能。但分析发现，

47、实验数据中收敛值小于3.85022的组合中有92%为变异率小于0.005，其中最差的6个组合中交叉率为0.001的占50%，而在变异率的组合中，99.7%收敛到全局最优值（误差在级），说明过小的变异率使算法的局部搜索能力下降，从而出现局部收敛的概率明显增加。而变异率大于0.05时，有34.6%不能收敛到全局优化值，说明过大的变异率对好的可行解造成了破坏而使求解结果偏离了全局最优解，通过数据结果的统计分析的知最佳组合主要集中在=0.79-0.83，=0.034-0.048。本文提出寻找求解某一类型函数优化问题的最优组合参数的方法，虽然只是对有限的函数进行测试，但通过实例验证对解决盲目选择参数的问

48、题是行之有效的，对提高和充分挖掘遗传算法在实际应用中的良好性能也有一定的参考价值。3.4一种求解函数优化问题的自适应遗传算法通过以上章节分析，我们知道遗传算法的性能评价是一个复杂的过程，要选择恰当的参数并不容易，针对不同的实际问题，其方法和结论也有区别，然而在实际应用中，自适应的方法却往往能取得令人满意的效果。如A.L.Tuson等采用自适应的调整方法对生产调度问题进行了测试，收到了可靠的性能，陈长征等提出了交叉和变异概率的自适应改进措施，对其作用机理进行了深入分析，并用一个复杂的数学函数进行测试，克服了传统遗传算法难以解决的局部收敛问题。最有代表性的是Sfinivas M等提出的根据适应度值来调节个体的交叉和变异率的方法。该自适应交叉、变异概率按下式进行调节： （3.3） （3.4）式中。表示交叉率，为变异率，表示种群最大适应度值，表示种群平均适应度值，表示在要交叉的两个个体中较大的适应度值，表示要变异的个体适应度值。这里，是在0和l之间取值的常数，和较大。