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

遗传算法在函数优化中的应用 目录目录 1.绪论 1 1.1 概述.1 1.2 遗传算法的发展历史与研究进展.2 2.遗传算法流程与应用举例 4 2.1 遗传算法中各重要因素分析.4 2.2 重要参数设置.6 2.3 简单的遗传算法运算示例.6 3.遗传算法在函数优化应用中的性能研究 .10 3.1 遗传算法在实际应用中的性能影响因素10 3.2 函数优化问题的描述12 3.3 求解函数优化问题的最优交叉、变异率组合的研究14 3.4 一种求解函数优化问题的自适应遗传算法17 3.5 小结19 结束语 .19 参考文献 .20 致谢 .21 潍坊学院本科毕业论文 2 1.1.绪论绪论 1.11.1 概述概述 遗传算法(genetic algorithms 简称 ga)由美国密歇根大学的 john hholland 教授等 创立的一类仿生型的优化算法。它是以达尔文的生物进化论和孟德尔的遗传变异理论 为基础、模拟生物进化过程、自适应启发式全局优化的搜索算法。由于遗传算法无需 过多地考虑问题的动力学信息，如连续、可微等，该算法结构简单，并且具有全局搜 索能力、信息处理的隐并行性、鲁棒性和可规模化等优点，它在思路上突破原有的最 优化方法的框架，尤其适用于处理传统搜索方法难以解决的复杂和非线性问题，现己 被广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，并且在 经济和决策方面也有很好的应用，是 21 世纪有关智能计算中的关键技术之一。 遗传算法的处理对象不是参数本身，而是对参数进行了编码的个体，因此不仅可 以对传统的目标函数优化求解，而且可以处理诸如矩阵、树和图等结构形式的对象， 用适应度函数同时对搜索空间的多个解进行评估，它将每个可能的问题表示为“染色 体” ，然后按遗传学规律进行选择、交叉和变异操作，直到满足终止条件为止。隐含并 行性和全局搜索性是遗传算法的两大特点，前者可使遗传算法只需检测少量的结构就 能反映搜索空间的大量区域，后者则使遗传算法具有良好的稳健性。 在遗传算法的诸多应用中，函数优化是最显而易见的应用，也是经典的应用。函 数优化问题是许多领域中普遍存在的问题，也一直是人们探索的若干重要问题之一。 很多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以转化为函数优化 问题来求解。函数优化的本质就是从所有可能的方案中选择出最合理、达到最优目标 的方案。它通常可归结为求最小值问题，对于最大值问题可以通过对函数取反，将其 转化为最小值问题。对于函数优化问题，传统的求解方法有最速下降法、牛顿法、拉 格朗日乘数法、罚函数法等等。对于这些确定的搜索优化方法来说，函数可微通常是 求解问题的前提，而且随着函数维数的增长，求解的难度大幅度增长。因此传统的优 化方法并不适合于求解不可微函数以及高维函数的优化问题。一种模仿生物自然进化 过程的、被称作为演化算法的随机优化技术在解这类优化难题中显示出了优于传统优 化算法的性能。自 70 年代 holland 正式提出遗传算法以来，非经典的随机搜索优化方 法如演化策略、演化规划、基因表达式程序设计等层出不穷。遗传算法就是其中一种 具有代表性的随机算法，与传统的优化算法相比，遗传算法不是从单个点，而是从点 的群体开始搜索，对初始点集的要求不高；遗传算法不是直接在参变量集上实施，而 是利用参变量集的某种编码；遗传算法利用适应值信息，无需导数或其他辅助信息， 这就使得它在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续 潍坊学院本科毕业论文 2 的、非规则的或有噪声的情况下，它也能以较大的概率找到整体最优解。 1 2 遗传算法优化求解过程与梯度信息无关，只需要目标函数是可计算的，对于复杂 的优化问题只需选择、杂交、变异三种遗传运算就能得到优化解，基于这些显著的优 点，ga 已引起人们的广泛应用和研究。 1.21.2 遗传算法的发展历史与研究进展遗传算法的发展历史与研究进展 1.2.11.2.1 遗传算法的发展历史遗传算法的发展历史 遗传算法的发展历史始于二十世纪 60 年代。jhholland 教授认识到生物的遗 传和自然进化现象与人工自适应系统的相似关系，提出在研究和设计人工自适应系统 时，可以借鉴生物的遗传机制，以群体的方式进行自适应搜索。1967 年，holland 的学 生 bagley 在他的博士论文中首次提出了“遗传算法”这一术语，提出选择、交叉和变 异，与目前遗传算法中相应的算法十分接近，引入适应度定标(scaling)的概念。同时， 他也首次提出了遗传算法自我调整的概念。 第一个把遗传算法用于函数优化的是 hollstien，1971 年他在论文计算机控制系 统中的人工遗传自适应方法(artificial genetic adaptation in computer controlsystems) 中阐述了遗传算法用于数学反馈控制的方法，主要讨论了二变量函数的优化问题。 1975 年，holland 出版了第一部著名的专著自然系统和人工系统的适配 (adaptation in natural and artificial systems) ，该书系统地阐述遗传算法的基本理论和 方法，并提出了遗传算法的基本定理模式定理(schema theorem)，奠定了遗传算法 的理论基础。同年，美国 de jong 博士在其论文遗传自适应系统的行为分析中结 合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，将 选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟(generationgap)等 新的遗传操作技术，建立了著名的 de jong 五函数测试平台。 80 年代，holland 教授实现了第一个基于遗传算法的机器学习系统分类系统 (classifier system)，开创了基于遗传算法的机器学习的新概念，为分类器在构造上提出 了一个完整的框架。1987 年，davis 出版了genetic algorithm and simulatedannealing一书，以论文集形式用大量的实例介绍了遗传算法的应用技术。 1989 年，goldberg 出版了专著遗传算法在搜索优化和机器学习中的应用(genetic algorithms in search，optimization and machine learning) ，该书系统总结了遗传算法 的主要成果，对 ga 的基本原理及应用做了比较详细、全面的论述，奠定了现代遗传 算法的科学基础。该书至今仍是遗传算法研究中广泛适用的经典之作。此后，许多学 者对原来的遗传算法(或称基本遗传算法)进行了大量改进和发展，提出了许多成功的遗 传算法模型，从而使遗传算法应用于更广泛的领域。进入 90 年代后，遗传算法作为一 种实用、高效、鲁棒性强的优化技术，发展极为迅速，在各种不同领域如机器学习、 模式识别、神经网络、控制系统优化及社会科学等中得到广泛应用，引起了许多学者 1 3 的关注。1991 年，lawrence davis 出版了遗传算法手册(handbook ofgeneticalgorithm)一书，对有效地应用遗传算法具有重要的指导意义。国外出现了 一些著名学者，如 holland，goldberg，davis 等，其经典著作也鲜为人知，国内也有 一些有关的书籍相继出版，一系列以遗传算法为主题的国际会议变得十分活跃。从 1985 年开始，国际遗传算法会议，即 icga(internationalconference on genetic algorithm)每两年举行一次；在欧洲，从 1990 年开始也每隔一年举办一次类似的会议， 即 ppsn(parallel problem salving from nature)会议；目前与 ga 有关的学术会议有：世 界计算智能大会，它是 ieee 主办的综合性学术大会，有 icnn、fuzzy ieee 和 icec 三个学术会议联合组成，每四年召开一次；此外，还有 ann&ga、ep、gp、ep、seal 等和 internet 上专门的遗传算法站点更是推动着遗传 算法实质性的进展。 进入 21 世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学已成为一个 研究热点。遗传算法因能有效地求解 np 难问题以及非线性、多峰函数优化和多目标优 化问题，得到了众多学科的高度重视，同时也极大地推动了遗传算法理论研究和实际 应用的不断深入与发展，目前已在世界范围内掀起关于 ga 的研究与应用热潮，可以 预测随着进化论、遗传学、分子生物学、计算机科学的进展，ga 也将在理论与应用中 得到发展和完善。 1.2.21.2.2 遗传算法的常见应用遗传算法的常见应用 (1)函数优化 函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。 对于解变量是实数型的优化问题，为提高 ga 的搜索效率，可采用动态编码和实数编 码。对于带约束的优化问题，引入罚函数，把约束条件结合到且标函数定义中。樊重 俊用特定的杂交、变异算子在一定程度上解决了线性等式优化问题；对于多峰函数优 化问题，1987 年 goldberg 和 richardson 用共享和限制交配机制结合的方法成功实现了 多峰的搜索；袁丽华等利用小生境技术，成功实现多峰的搜索；2000 年刘洪杰等 m 利 用多种算子混合的方法来搜索多极值点，该算法对等高等距、不等高等距和不等高不 等距情况都有好的结果。对于多目标函数的优化问题，多数情况下，最优解是不存在 的，一般找到其 pareto 最优解或非劣解，这仍是个值得研究的新课题，也是当前管理 科学、决策理论、系统工程、运筹学等学科研究中十分重要的内容。 (2)组合优化组合优化问题，通常带有大量的局部极值点，往往是不可微的、不连 续的、多维的、有约束条件的、高度非线性的 np 完全问题，很难求出最优解。实践表 明遗传算法求解组合优化问题非常有效。如 ga 在求解巡回旅行商问题、装箱问题、 背包问题、图形划分问题等方面得到成功地应用；唐立新、张毅、曾三友等学者在各 1 4 自的研究领域已取得一定的成果。 (3)遗传编程与学习 koza 成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等 方面。kinnear 提出了基于遗传算法的移动机器人路径的新方法；基于 ga 的机器学习 特别是分类器系统已被用于学习模糊控制规则、人工神经网络的连接权和结构优化等 领域，也是目前遗传算法研究中一个十分活跃的领域。 (4) 自动控制 遗传算法已在自动控制领域得到了初步应用，并取得良好的效果。如基于 ga 的 模糊控制器的优化设计，用 ga 进行航空控制系统的优化；20 世纪 80 年代，goldberg 用 ga 学会控制天然气输气管道系统；机器人控制等等唧。此外，遗传算法也在生产 调度问题、图像与信号处理、设计、人工生命等方面获得了广泛的运用。这里就不一 一赘述了。总之，随着研究的深入，算法不断地被改进，遗传算法的应用领域将会越 来越广，效果也越来越好。 2.2.遗传算法流程与应用举例遗传算法流程与应用举例 2.12.1 遗传算法中各重要因素分析遗传算法中各重要因素分析 2.1.12.1.1 编码理论编码理论 遗传算法需要采用某种编码方式将解空间映射到编码空间（可以是位串、实数、 有序串） 。类似于生物染色体结构，这样容易用生物遗传理论解释，各种遗传操作也易 于实现。编码理论是遗传算法效率的重要决定因素之一。二进制编码是最常用的编码 方式，算子处理的模式较多也较易于实现。但是，在具体问题中，根据问题的不同， 采用适合解空间的形式的方式进行编码，可以有效地直接在解的表现型上进行遗传操 作，从而更易于引入相关启发式信息，往往可以取得比二进制编码更高的效率。 2.1.22.1.2 染色体染色体 每个编码串对应问题的一个具体的解，称为染色体或个体。一个染色体可以通过 选用的编码理论与问题的一个具体的解相对应，一组固定数量的染色体则构成一代群 体。群体中染色体可重复。 2.1.32.1.3 随机初始化随机初始化 随机或者有规律（如从一个已知离解较近的单点，或者等间隔分布地生成可行解） 生成第一代群体。一次遗传算法中有目的采用多次初始化群体会使算法拥有更强的搜 索全局最有解的能力。 2.1.42.1.4 适应度适应度 1 5 一个染色体的适应度是对一个染色体生存能力的评价，它决定了该染色体在抽取 操作中被抽取到的概率。估价函数是评价染色体适应度的标准，常见的估价函数有： 直接以解的权值（如 01 背包问题以该方案装进背包物品的价值作为其适应度） ，累计 二进制串中 1/0 的个数（针对以二进制串为编码理论的遗传算法） ，累加该染色体在各 个目标上的得分。 2.1.52.1.5 遗传算子遗传算子 遗传算子作为遗传算法的核心部分，其直接作用于现有的一代群体，以生成下一 代群体，因此遗传算子的选择搭配，各个算子所占的比例直接影响遗传算法的效率。 一个遗传算法中一般包括多种遗传算子，每种算子都是独立运行，遗传算法本身只指 定每种算子在生成下一代过程中作用的比例。算子运行时从当前这代群体中抽取相应 数量的染色体，经过加工，得到一个新的染色体进入下一代群体。 下面列出几种常见的遗传算子： 保持算子：抽取 1 个染色体，直接进入下一代。该算子使算法能够收敛。 交配算子：抽取 2 个染色体，交换其中的某些片段，选择适应度高的（或者都选） ， 进入下一代群体。该算子使得遗传算法能够利用现有的解寻求更优的解。 变异算子：抽取 1 个染色体，对其进行随机的改变，进入下一代群体。该算子使 得算法可以跳出局部最优解，拥有更强搜索全局最有解的能力，防止陷入局部搜索， 该算子的概率不可过高，否则将引起解的发散，使得算法无法收敛。 2.1.62.1.6 抽取抽取 抽取操作是遗传算法中一个重要基本操作，作用是按照“优胜劣汰”的原则根据 各个染色体的适应度从当前这代群体中挑选用于遗传算子的染色体。通常采用的手段 是偏置转盘： 设算法中群体数量为，首先计算当代群体的各染色体适应度之和 population 。将 1内的整数划分成个区间段，每个染色体所占的 population i i xfts 1 )()( )(ts population 区间段的长度既是它的适应度。这样，随机产生一个 1的整数，抽取该点所属区 )(ts 间段相对应的染色体，就可以保证任意一个染色体 xi 在抽取操作中被抽取到的概率为 。 )()(tsxf i 2.1.72.1.7 终止条件终止条件 遗传算法的终止条件用于防止遗传算法无止境的迭代下去，一般限制条件可以 1 6 设为达到指定的迭代次数后终止，或当解的收敛速度低于一定值时自动终止。当遗 传算法达到终止条件时，遗传算法结束，并按照要求返回中途最优的一个染色体。 2.22.2 重要参数设置重要参数设置 在应用遗传算法解决问题的时候，往往需要根据实际情况的不同，对不同问题使 用不同的遗传参数。在大规模的问题上，一次遗传算法的不同时期也可以设置不同的 遗传参数。对遗传算法效率影响较大的参数如下： 群体大小：一代群体中染色体的数量，群体大小越大所能容纳的染色体品种也越 多，越有利于搜索全局最有解，但是会下降收敛的速度，所需的时间也更多。 迭代次数：最多更新群体的次数，迭代次数的增加可以使得解收敛更精确但是所 需的时间也越多，如果时间允许，采用多次初始化群体的操作要比设置很大的迭代次 数来得更高效些。 保持率：保持算子所占的比例，通常不超过 70% 交配率：交配算子所占的比例，通常不超过 50% 变异率：变异算子所占的比例，通常不超过 1% 2.32.3 简单的遗传算法运算示例简单的遗传算法运算示例 在这一节，我们将运用猫和老鼠的例子详细说明遗传算法每一组成部分。假设我 们希望通过遗传算法得到最优秀的猫。 2.3.12.3.1 染色体的表达：染色体的表达： 我们把猫的染色体简单分成两部分，一部分表示奔跑速度，另一部分表示智力水 平。每一项属性用一个四位的二进制数进行编码，数字越大代表该属性越好。如图 2.1 所示。 10100101 00111101 速度智力 猫1(染色体） 猫2（染色体） 图 2.1 染色体编码 猫 1 的染色体为（10100101） ，我们可以从染色体看出它的奔跑速度高，但是比较 笨。相反的，猫 2（00111101）速度慢，但是智力水平高。 除了二进制以外，遗传算法还有很多编码方法，比如格雷码、浮点数编码和字母 编码等。在这一节，我们均用二进制的编码方式来介绍遗传算法。 2.3.22.3.2 评估函数评估函数 1 7 评估函数用以评价种群中每个染色体的适应值，又称为适应值函数（fitness function） 。在遗传算法中，适应值函数起着一个环境的作用，它给与种群一个生存的 环境，并决定了哪些个体容易存活。在这个例子当中，猫跑得越快越聪明就越容易捉 到老鼠，也就越适应环境。我们简单构造一个用以评价猫的适应值函数： 适应值=速度+智力 则对于猫 1，我们首先把它的染色体的二进制编码转换为十进制，然后再把它的两 个属性相加得到它的适应值为 10+5=15。同样的，猫 2 的适应值为 3+13=16，如图 2.2 所示。 10100101 猫1 染色体： 适应值：10+5=15 00111101 猫2 染色体： 适应值：3+13=16 图 2.2 适应值的计算 2.3.32.3.3 选择算子选择算子 运用适应值函数对种群中的每个染色体进行评价以后，每个染色体都被赋予一个 适应值。选择算子模仿自然的选择过程，从种群中选择出适于生存的个体，并复制到 下一代。适应值越高的个体更容易被选择从而复制到下一代中，而适应值低的个体则 往往不被选择。假设一代种群中有 4 只猫，它们的染色体分别为：（01001000） ， （11001010） ， （00100010） ， （10000100） 。我们根据预先定义的适应值函数计算出它们 的适应值分别为：12，24，4，12。选择往往是基于适应值概率分布的一个随机选择过 程，有轮盘赌选择（roulette wheel selection） 、锦标赛选择（tournament selection）和比 例选择（proportionate selection）等一系列不同的选择方法。我们以最常用的轮盘赌选 择为例，首先构造一个轮盘，并将其分成 4 份，每一份的大小和其中一只猫的适应值 相对应，如图 2.3 所示。 1 8 12 24 12 4 选择 随机转动 图 2.3 轮盘赌示意图 随机转动轮盘，每次就会选择出一个染色体并复制到下一代。我们可以看出，适 应值越大的染色体在轮盘中被选中的概率越高，随机转动轮盘 4 次就可以复制出新的 一代种群。这一过程可以用简单的概率计算来表达，如表 2.1 所示。 表 2.1 各个染色体的选择概率分布 0 1 0 0 1 0 0 01 1 0 0 1 0 1 00 0 1 0 0 0 1 01 0 0 0 0 1 0 0 染色体： 适应值：1224412 被选择的 概率： 12/5224/524/5212/52 首先将种群中所有染色体的适应值相加得到一个总的适应值，然后将每个个体的 适应值除于总适应值，就可以得到每个个体被选择的概率。根据这一概率分布进行选 择就可以得到下一代的种群。这种基于轮盘的选择称为轮盘赌选择。 2.3.42.3.4 交叉算子交叉算子 交叉算子用以模仿自然界群体遗传过程中发生的交配，对新一代的种群进行遗传 上的改变。按照不同的交叉方法，交叉算子分为单点交叉（single point crossover） 、两 点交叉（two point crossover）和均匀交叉（uniform crossover）等等。以单点交叉为例， 首先对种群进行两两配对，并从中选出一对染色体，假设为（01001000）和 （10000100） 。如图 2.4 所示。 1 9 01001000 10000100 交叉点 染色体1 染色体2 01000100 10001000 染色体3 染色体4 交叉 适应值 12 12 8 16 图 2.4 交叉过程示意图 随机选取一个交叉点，并相互交换位于交叉点右边的所有位，产生出两个新的个 体（01000100） ， （10001000） 。我们可以看出，交叉产生出了适应值比父母体都要高的 进化染色体，这是因为这个染色体通过交叉分别继承了父母的优良特性。虽然一些较 差的染色体也会产生，但是它们在以后的选择过程中往往会被淘汰，从而不会对整个 过程产生大的影响。 2.3.52.3.5 变异算子变异算子 变异以较小概率对个体编码串上的某个或某些位值进行改变，它可以分为均匀变 异（uniform mutation）和非均匀变异（non-uniform mutation）等等。对于一个选定的 染色体执行变异操作，就是随机改变其中的一或几位的基因，将它们从 1 变为 0，或者 从 0 变为 1，如图 2.5 所示。变异在染色体中随机引入新的信息，使得进化过程趋于多 样化。 10001000染色体 1 变异 10001100新染色体 适应值 16 20 图 2.5 变异过程示意图 2.3.62.3.6 流程图流程图 经过上述选择，交叉和变异算子的作用，新的一代种群就产生了。我们不断反复 这一过程，将这一群体一代又一代地演化下去，直到满足一定条件为止。算法的基本 1 10 流程图如图 2.6 所示。在若干代后，遗传算法就可以在种群中进化出一只跑得最快而且 最聪明的猫（11111111） 。 开始 初始化 满足终止条件？ 选择 评估 交配 变异 结束 否 是 选择算子可以有轮盘赌选 择、锦标赛选择、比例选 择等不同的设计方案 交配算子常用的有单点交 配、两点交配、均匀交配 等设计方案 变异算子可以采用均匀变 异或者非均匀变异等适合 不同问题的设计方案 图 2.6 遗传算法流程图 3.3.遗传算法在函数优化应用中的性能研究遗传算法在函数优化应用中的性能研究 遗传算法的性能问题一直是该领域的重要内容，研究其性能不仅具有理论上的意 义，尤其对实际应用特别是计算机程序更为重要。近几年来，遗传算法在这方面取得 了突破性进展。如goldberg等首先分析了简化遗传算法的性能，eiben、guo guanqi等 提出了一种pls算子，有机结合实数编码与gaussian适应性交异，以提高求解多峰函数 优化问题时的收敛速度和可靠性，杨世达通过多方改进，使遗传算法在优化计算过程 中性能明显改善。 然而，遗传算法的性能研究至今仍然是一个悬而未决的问题。本章对遗传算法在 函数优化应用中的性能影响因素进行了分析，根据人们选择参数的经验主义和盲目性， 提出了一种寻找求解函数优化问题的最优交叉、变异率组合的新方法，并通过了实例 验证。同时，提出了一种自适应的遗传算法，其效率高，性能好，并具有一定的通用 性。 3.13.1 遗传算法在实际应用中的性能影响因素遗传算法在实际应用中的性能影响因素 在实际应用中，遗传算法的性能影响因素很多，但主要是由编码方法、操作算子 和适应度函数决定。 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。 编码方法决定了个体的染色体排列形式和解码方法，也影响到交叉、变异等遗传算子 的运算方法。rudolph 和 qi 等分别对二进制和浮点数编码的遗传算法进行了全局收敛 性分析，为遗传算法的应用提供了重要参考依据。 传统的遗传算法通常采用有限长的二进制编码，这有利于数学模型的建立，便于 1 11 人们对模式定理、收敛性分析、欺骗问题等理论分析和计算机的处理，但不利于人们 的习惯表达。dc jong 曾提出了两条操作性较强的编码原则：有意义积木块编码原则和 最小字符集编码原则，但至今仍没有完整的理论对其进行指导。因而人们提出了多种 不同的编码方法，从具体实现的角度可以分为三大类，即二进制编码方法、实数(浮点) 编码方法和符号编码方法。 实数(浮点)编码在 90 年代以来得到越来越多的重视和发展。实数编码是连续参数 优化问题直接的自然描述，相对于二进制编码有许多优势：它适合在遗传算法中表示 范围较大的数，可以提高解的精度和运算速度，便于在较大空间的遗传搜索，避免了 编码中带来的附加问露，便于和其它方法的结合等。符号编码方法是指个体染色体编 码串中的基因值取自一个无数值含义、而只有代码含义的符号集。 符号编码的主要优点是：（1）符合有意义积木块编码规则：（2）便于在遗传算 法中利用所求解问题的专门知识；（3）便于遗传算法与相关近似算法之间的混合使用。 遗传算法的性能与其操作算子息息相关，近年来，研究者对操作算子做了大量的分析 和研究，并提出一些方法和策略以提高算法的性能。 （1）选择算子 选择算子的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。常见的 有适应度比例、最佳个体保留、期望值、排序选择、联赛选择、排挤方法等，其中适 应度比例方法是遗传算法最基本也是最常用的选择方法，也叫赌轮或蒙特卡罗选择。 最优保留策略可视为选择操作的一部分，它是遗传算法收敛的一个重要保证条件，可 以使算法最终能收敛到全局最优值。 不同的选择方法对于遗传算法的在线和离线性能的影响均不相同。在实际应用中， 应根据问题求解特点采用较合适的方法或者结合使用。 （2）交叉算子 交叉算子是遗传算法区别于其它优化算法的本质特征，在遗传算法中起关键作用， 是产生新个体的最主要方法，它决定了遗传算法的全局搜索能力。它直接影响着算法 的最终实现和性能，在一定程度上决定着遗传算法的发展前景。 经典的观点强调交叉的作用，其理论基础是著名的积木块假设，这一观点与生物 学中的实际观察最相符合。但交叉操作正受到理论与实践两方面的严峻考验与挑战， 如钟国坤等啤 l 提出了一种单亲遗传算法，抛开交叉算子，而代之以隐含序号编码的遗 传算法、交叉算子功能的基因换位等遗传算子，算法效率高，并且不要求初始群体的 多样性，也不存在“早熟”问题。 交叉概率以的大小也直接影响着遗传算法的性能，较大的。可增强开辟新的搜 c p 索区域的能力，但高性能的模式遭到破坏的可能性增大，若，太小，搜索可能陷入 c p 迟钝状态，因而合适的交叉概率是算法获得良好性能的条件之一。 1 12 实际应用中，研究者们设计了各种新的交叉策略，并收到了良好的性能。 bianrunqiang 等提出了一种新的改进交叉策略，有效克服了近亲繁殖引起的早熟现象， a.l.tuson 等采用自适应的调整方法对生产调度问题进行了测试，收到了可靠的性能， 金聪等提出了一种每个基因位交叉概率自适应变化的新的交叉操作，算法性能远高于 sga，钟国坤等用异位交叉算子极大地提高了算法的收敛速度，而且不易陷入局部最 优解，张铃等则对交叉操作进行了重新设计，提出了佳点集遗传算法，速度和精度都 得到了改善，并有效地避免了早熟现象。 （3）变异算子 变异是传统遗传算法中一个必不可少的步骤，因其局部搜索能力而作为辅助算子， 能维持群体多样性，防止出现早熟现象。在实际应用中，交叉和变异算子相互合作， 共同完成对全局和局部的搜索，以获得良好的收敛性能。大量应用实例可以看到遗传 算法有这样一个特点，即在早期可以迅速达到次优解接近最优解，但此后搜索到最优 解的速度就慢下来了。究其原因是因为应用中往往采用固定的较大的。和较小的。 c p m p 并且在整个搜索过程中保持不变，所以算法可以迅速接近最优解，但在最优解附近由 于较小的变异率而缺乏较强的局部搜索能力以致很难找到最优解。针对这种情况，可 采用动态参数自适应调整方法，即在算法开始时采用较大的和较小的，算法搜索 c p m p 速度放慢时动态调整参数大小，使适当减少而适当增大。但同时也要考虑 de c p m p jong 在经过仔细分析和计算后所得出的其中一个重要结论：虽然的增大会增加群体 m p 的多样性，但它却降低了算法的在线性能和离线性能，并且随着的增大，算法性能 m p 越来越接近于随机搜索算法的性能。因而，它们之问如何有效地协同也是目前遗传算 法的一个重要研究内容。 遗传算法使用个体的适应度函数对解的质量进行评价，适应值越高，解的质量就 越好，该个体被选择的概率就越大，因而，适应度函数直接影响着算法的性能。针对 应用中的各种不同现象，对适应度函数须进行适当调整，即适应度定标(fitnessscaling)， 以提高遗传算法的优化搜索性能。目前常见定标方式有三种，即线性定标、baff 幂函数定标和指数定标。 k ff )exp( ff 适应度函数评价是选择操作的依据，一般以发现最大值或准最优解作为遗传算法 迭代停止条件，但在许多优化问题中适应度最大值并不清楚，因而众多的实际应用中， 若发现群体个钵的进化已趋于稳定状态，则终止算法迭代。另外，由于遗传算法仅靠 适应度来评价和引导搜索，所以求解问题所固有的约束条件不能明确表示出来，而实 际应用中许多问题都是有约柬条件的，作为一种解决方法。可将问题转换为一个带罚 函数(penalty function)的非约束优化问题，但同时要注意罚函数值在约束边界处发生急 剧变化可能会引发问题。具体应用中，适应度函数的设计要结合求解问题本身的要求 而定。 1 13 3.23.2 函数优化问题的描述函数优化问题的描述 函数优化问题是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用 算例。对于一些非线性、多模型、多目标的函数优化问题，用其他方法较难求解，而 用遗传算法却可以方便地得到较好的结果。 通常，目标函数优化问题可以描述为： （3.1）sxxf)(max 或： （3.2）sxxf)(min 其中 s 称为搜索空间，。称为目标函数。(3.1)式描述的优化问题称为rsxf: )( 极大化问题，(3.2)式描述的称为极小化阃题。当把看成是一序列的函数时，上述)(xf 的问题就转变为多目标优化问题。 广义地讲，所有的搜索、优化都是对目标函数的“函数”优化，这罩所指的函数 主要是强调函数的数学特征，如函数的连续性、凹凸性、多峰性、多维性等。在遗传 算法的研究工作中，函数优化问题受到了较大的重视。在遗传算法产生的早期，就有 一批学者(如 hollstien、de jong 等)在研究这个问题，直到如今，仍有不少人在不断探 索求解函数优化问题性能更好的遗传算法，在前人的成果积累上，通过深层次的理论 分析和大量的各类实验，极大地推动了。之所以如此，主要有下面两条原因： 首先，对很多实际问题进行数学建模后，可将其抽象为一个函数优化问题。由于 问题种类繁多，影响因素复杂，这些数学函数会呈现不同的数学特征或这些不同数学 特征的组合，因此寻求能处理各种不同的复杂函数又具有良好性能的方法是很困难的。 其次，如何评价一个遗传算法的性能优劣程度一直是一个比较难的问题。主要是 由于闯恶种类繁多，影响因素复杂，若对各种情况都加以考虑并试算，其工作量势必 太大。虽然人们提出了一些评价指标，如 de jong 的两个用于定量分析的指标：即在 线性能指标和离线性能指标，分别测量遗传算法 t t et tf t sx 1 )( 1 )( t t et tf t sx 1 )( 1 )( 的动态性能和收敛性，但这只是反映了算法在某一方面的性能，不足以完全反暖算法 在各种实际应用中的效果。另外，函数优化问题不包含有某一具体应用领域的专门知 识，便于不同应甩领域的研究人员进行相互理解和交流，并能较好地反映算法本身所 具有的本质特征和实际应用能力。所以入们专门设计了一些具有复杂数学特征的纯数 学函数，通过遗传算法对这些函数的优化计算来测试各种算法的性能。 函数优化问题是一个复杂的优化问题，特别是不可微或者多峰的函数，往往不能 有效地求解。而遗传算法作为一种高度并行、随机、自适应的全局优化概率搜索算法， 它将每个可能的问题表示为“染色体” ，从而得到一个由染色体组成的“群体” ，然后 1 14 按遗传学规律进行选择、交叉、变异操作，直到满足终止条件为止。 对很多实际问题进行数学建模后，可将其抽象为一个数学函数的优化问题，出于 问题种类的繁多、影响因素的复杂，这些数学函数会呈现出不同的数学特征，比如连 续的、离散的、凸的、凹的、单峰值的、多峰值的函数等等，经常遇到的函数还有这 些不同数学特征的组合，除了在函数是连续、可求导、低阶的简单情况下可解析地求 出其最优解以外，大部分情况需要通过数值计算方法来进行近似优化计算，尽管人们 对这个问题研究了很多年，但至今仍无一种既能处理各种不同的复杂函数、又具有良 好求解结果的数值计算方法，特别是当问题的规模比较大时，优化计算时的搜索空间 急剧扩大，人们认识到要严格地求出其最优解不可能、也不太现实，所以需要研究出 一种能够在可接受的时间和可接受的精度范围内求出数值函数近似最优解的方法或通 用算法。 遗传算法提供了求解复杂系统优化问题的通用框架，函数优化正是其最成熟的应 用领域。在对各种复杂形式的测试函数的计算中，由于遗传算法直接以目标函数值作 为搜索信息，同时使用多个搜索点进行搜索，且这种概率搜索始终遍及整个解空间， 都能找到几乎全局最优解。对于一些非线性、多模型、多目标的函数优化问题，在其 他优化方法较难求解时，遗传算法也能方便地得到较好的结果。 实践表明，遗传算法求解函数优化问题的计算效率比较高、适用范围相当广。与 传统的优化方法相比，遗传算法具有如下特点：具有简单通用、鲁棒性强、适于并 行处理以及高效、实用等显著优点。 1975 年 de jong 发表了题为“an analysis ofthe behavior of a class of geneticadaptive system”的学位论文，主要论述了遗传算法应用于函数最优化的研究， 并根据其相关特性精心挑选了五种函数最优化的测试例子，且在计算机上经过大量的 计算实践，得到了一些在遗传算法的发展和应用过程中具有重要指导意义的结论，其 研究方式已成为遗传算法研究和发展的典范。 3.33.3 求解函数优化问题的最优交叉、变异率组合的研究求解函数优化问题的最优交叉、变异率组合的研究 遗传算法能较好地解决函数优化问题，但研究者发现，参数环境对遗传算法的性 能和结果的质量至关重要，参数环境能改变算法的函数优化能力，这是遗传算法领域 的一个重要研究课题，应该引起人们的高度重视。如 wolpcrtdh 等人通过详细分析说 明了在实际应用中算法中参数之闯的协作的重要性。孙艳丰等在大量资料的基础上也 声明了参数环境对遗传算法在函数优化中的性能和结果的至关重要性。 但在大量理论和实际应用当中，通常人们对交叉和变异率的选择是盲目的，极易 出现早熟现象。而且受众多因素影响，要选择一个满意的操作和最优的参数楚很困难 的，人们基本上都是根据理论分析中各参数的大致范围来选择参数，或根据经验来确 1 15 定解决某个实际问题的最优参数组合，但通常要找到最优组合并不容易，往往会花费 大量的时间，因此，科学、有效地对遗传算法中的参数特别是交叉和变异概率选择是 十分必要的。如巩敦卫基于模式定理的推广形式，探讨了交叉和变异率的上限。陈长 征、a.l.tuson 就对其作用机理进行了深入分析并提出了改进措施，采用新的交叉和变 异概率选择方法，著显示了其优越性能。 利用遗传算法进行函数优化计算时，若精度不是太高，自变量不是太多时，可以 采用二进制编码来表示个体。遗传算法中，交叉算子因其全局搜索能力而作为主要算 子，变异算子因其局部搜索能力而作为辅助算子，遗传算法通过交叉和变异这一对相 互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。本文在传统的 二进制编码的基础上，采用动态调整交叉概率、变异概率的疗法，在程序运行过 c p m p 程中记录每一种不同组合参数下最佳个体所在世代数、适应度、最优解的值，通过它 们与出现最优值时进化世代数之间的关系图和统计分析，直观而又轻松地找到了解决 某一类型函数优化问题各参数的最优组合(程序运行过程如图 3.1 所示)，实例验证这是 非常有效的，给人们在实际应用遗传算法时盲目选择参数的问题提供了一条新的解决 思路，具有一定的现实意义。 图 3.1 0 . 2)10sin()(xxxf 对于函数，（在 x=1.850547 时有最大值0 . 2)10sin()(xxxf21，x 3.850274） （如图 3.1 所示） ，在染色体长度 lchrom=25，种群大小确定（popsize=80）的 情况下，通过模拟实验，、分别在 0.70-0.90,0.001-0.100 的范围内，遗传算法能按 c p m p 人们所熟知的理论具有极强的自适应能力，找到问题的最优解。如=0.82，=0.045 c p m p 时，在第 40 代收到最佳值 3.850274（最大值 max，最小值 min、平均值 avg 和进化世 代数 gen 的关系如图 3.2 所示） ；但=0.79，=0.002 时，却在第 3 代局部收敛到非 c p m p 最佳值 3.324148，并且误差大，不能满足精度要求；这说明在应用遗传算法解决实际 中的函数优化问题时，注意各参数的取值是必须的。 1 16 图 3.2 max、min、avg 和 gen 的关系图(=o82，=o045) c p m p 采用本文所述方法，在程序运行过程中动态调整遗传算法的，值，发现不同 c p m p 的参数组合其性能省察极大（、的不同组合与最佳收敛世代关系如图 3.3 所示） 。 c p m p 图 3.3 的动态、与收敛世代数)( 21 xxf， c p m p 1 17 说明在实际应用中只有恰当选择各参数的值才有可能获得良好的性能。但分析发 现，实验数据中收敛值小于 3.85022 的组合中有 92%为变异率小于 0.005，其中最差的 6 个组合中交叉率为 0.001 的占 50%，而在变异率的组合中，99.7%100 . 0 005 . 0 ， m p 收敛到全局最优值（误差在级） ，说明过小的变异率使算法的局部搜索能力下降， 6 10 从而出现局部收敛的概率明显增加。而变异率大于 0.05 时，有 34.6%不能收敛到全局 优化值，说明过大的变异率对好的可行解造成了破坏而使求解结果偏离了全局最优解， 通过数据结果的统计分析的知最佳组合主要集中在=0.79-0.83，=0.034-0.048。 c p m p 本文提出寻找求解某一类型函数优化问题的最优组合参数的方法，虽然只是对有 限的函数进行测试，但通过实例验证对解决盲目选择参数的问题是行之有效的，对提 高和充分挖掘遗传算法在实际应用中的良好性能也有一定的参考价值。 3.43.4 一种求解函数优化问题的自适应遗传算法一种求解函数优化问题的自适应遗传算法 通过以上章节分析，我们知道遗传算法的性能评价是一个复杂的过程，要选择恰 当的参数并不容易，针对不同的实际问题，其方法和结论也有区别，然而在实际应用 中，自适应的方法却往往能取得令人满意的效果。如 a.l.tuson 等采用自适应的调整 方法对生产调度问题进行了测试，收到了可靠的性能，陈长征等提出了交叉和变异概 率的自适应改进措施，对其作用机理进行了深入分析，并用一个复杂的数学函数进行 测试，克服了传统遗传算法难以解决的局部收敛问题。 最有代表性的是 sfinivas m 等提出的根据适应度值来调节个体的交叉和变异率的 方法。该自适应交叉、变异概率按下式进行调节： （3.3） avg avgavg c ff ff k ffffk p 3 max max1 )()( ， ， （3.4） avg avg avg ff ff k ffffk p 4 max max2 m )()( ， ， 式中。表示交叉率，为变异率，表示种群最大适应度值，表示种群 c p m p max f avg f 平均适应度值，表示在要交叉的两个个体中较大的适应度值，表示要变异的个体 ff 适应度值。这里，是在 0 和 l 之间取值的常数，和较大。 1 k 2 k 3 k 4 k 3 k 4 k 从公式(3.3)、(3.4)中可以看出，如果个体较差（其适应度值小于平均适应度值） ， 对其就给予较大的交叉率和变异率和，如果个体较优良（其适应度值大于平均适 3 k 4 k 应度值） ，则依据其优良程度线性她赋予此个体相应的交叉率和变异率一一适应度值越 接近最大适应度值，个体交叉率和变异率就越小，当等于最大适应度时交叉率和变异 率就为零。 虽然这种交叉调节方法有助于保护优良个体的有效模式，便于找到分布在局部优 点周围的全局最优点，适合于多峰函数的求解，但是这种方法在进化初期阻碍了进化 1 18 效率。因为优良个体交叉率很小，处在不与“外界交往”的环境中，所以其带有的有 效模式也不能进行传播，影响了进化速度，而且最优个体一真不发生变化，有可能很 快占据整个种群，产生“早熟”现象。 遗传算法的性能影响因素多而复杂，为突出重点而不失一般性，本算法采用二进 制编码，只对交叉概率和变异概率进行自适应调节，和的总趋势是由大变小 c p m p c p m p 并趋于稳定。进化前期，为维护群体的多样性，采用相对较大的和算法运行过程 c p m p 中，根据适应值大小自适应地对和进行调节，进化后期。由于群体趋予收敛，相 c p m p 对较小和稳定的和使优秀的个体得到保留，有利于增加收敛的稳定性。 c p m p 算法的执行步骤如下： 1.initialize population ； t p 2.caleelate fitness ； t f 3.select two chromosomes from according to ； t p t f 4.crossover with probability and mutation with ，form offspring； c p m p 1t p 5.calculate if，then 1t fkff tt 1 )10( ) 10() 10( tgenntgenm nrandomppmrandompp mmcc 、 ， 6.go to step 2 umil termination criteria are meet 实验初始化参数取值： (精度大于)，对251 . 09 . 0popsizepp mc ， 6 10 和 de jong 函数 f2，gen 分别为 150 和 1000，实验结果如表 3.1 和表 3.2 所示。)(xf 其中，sga 的和大小根据上节所提出的方法选择最优组合。 c p m p 表 3.1 自适性 ga 性能 测试函数0 . 2)10sin()(