1、 I遗 传 算 法 用 于 优 化 计 算 问 题 的 研 究摘 要摘 要 遗 传 算 法 是 基 于 “适 者 生 存 ”的 一 种 高 度 并 行 、 随 机 和 自 适 应 的 全局 搜 索 优 化 算 法 ， 它 将 问 题 的 求 解 表 示 成 个 体 的 适 者 生 存 过 程 ， 通 过 种群 的 一 代 代 不 断 进 化 ， 包 括 复 制 、 交 叉 和 变 异 等 操 作 ， 最 终 收 敛 到 “最 适应 环 境 ”的 个 体 ， 从 而 求 得 问 题 的 最 优 解 或 满 意 解 。 遗 传 算 法 被 成 功 地 用于 各 种 不 同 领 域 ，如 组 合 优
2、 化 ，图 像 处 理 ，模 式 识 别 ，智 能 控 制 ，机 器 学 习 ，数 据 挖 掘 等 多 个 领 域 ，而 优 化 计 算 问 题 是 对 遗 传 算 法 进 行 性 能 评 价 的 常 用 算例 。 本 文 将 系 统 地 论 述 了 遗 传 算 法 在 优 化 计 算 问 题 中 的 应 用 ， 采 用 基 于 遗 传算 法 的 函 数 优 化 问 题 的 通 用 框 架 ， 用 遗 传 算 法 求 解 函 数 优 化 问 题 为 研 究 对 象 ，通 过 对 连 续 函 数 以 及 0-1 背 包 、 TSP 等 离 散 问 题 的 实 例 分 析 及 计 算 ， 得 出较
3、 为 理 想 的 结 果 。关键词：遗传算法 ，优化计算 ，0-1 背包问题 ， TSP 问题IIAbstractGenetic Algorithm (GA) is a highly parallel, random and adaptive optimization search algorithm based on the mechanics of survival of fittest.It makes problem solving as individual survival of the fittest process, evolving populations from gene
4、ration to generation, including selection, crossover and mutation operations, and eventually converge to the “best adapted to the environment“ individuals, in order to obtain the optimal solution of the problemor satisfactory solution.The genetic algorithm was successfully used in various fields, su
5、ch as combinatorial optimization, image processing, pattern recognition, intelligent control, machine learning, data mining, and other fields.,but function optimization is a common example of genetic algorithm.The paper systematically discuss the research work of applying genetic algorithm to solve
6、mathematical function optimization problems.General framework and procedures to solve function optimization problem using genetic algorithm is proposed.through extensive analysis and calculation examples,such as continuous function,the Knapsack Problem and the Traveling Salesman Problem,effective re
7、sults have been obtained.Key Words: Genetic Algorithm , Optimization, Knapsack Problem ,Traveling Salesman Problem摘 要 .IAbstract.II第一章 引言 .11.1 概述 .11.2 遗传算法的发展历史及研究进展 .21.3 本课题研究的目的和意义 .4第二章 遗传算法的基本理论 .52.1 数学基础 .52.1.1 模式定理 .52.1.2 隐含并行性 .62.2 遗传算法的运算流程 .62.3 遗传操作 .82.3.1 编码 .82.3.2 适应度函数 .82.3.3
8、遗传算子 .9第三章 优化计算 .123.1 连续函数优化 .123.1.1 编码和产生初始化种群 .133.1.2 解码 .133.1.3 计算适应度 .143.1.4 优化计算结果 .173.1.5 MATLAB 遗传算法工具箱 .183.2 离散问题优化 .213.2 .1 0-1 背包问题 .213.2.2 遗传算法求解 TSP 问题 .23结 论 .30参考文献 .32致 谢 .331第一章 引言1.1 概述遗传算法是基于“ 适者生存 ”的一种高度并行、随机和自适应的全局搜索优化算法，它将问题的求解表示成个体的适者生存过程，通过种群的一代代不断进化，包括复制、交叉和变异等操作，最终收
9、敛到“最适应环境” 的个体，从而求得问题的最优解或满意解。因为遗传算法不需要过多地考虑问题具体的信息，如是否可导、是否连续等，且遗传算法框架结构比较简单，能够应用于许多问题的全局优化，具有隐含并行性、鲁棒性和大规模计算等优点。遗传算法突破了以往的全局优化方法的基本框架，在处理传统的优化搜索方法难以解决的复杂的组合优化问题，如背包问题、TSP 问题等，能够取得比较好的结果。遗传算法不以参数本身为处理对象，而对参数进行编码，然后对编码后的个体进行优化搜索。遗传算法不仅能够对连续函数进行优化计算，而且能够对离散问题，如 0-1 背包、TSP 问题等，进行优化计算。每个编码后的个体代表问题域的一个可行
10、解，遗传算法根据适应度函数对问题域的每个可行解进行评价，然后根据遗传算法的基本框架进行选择、交叉和变异操作，当满足最优化条件时，输出问题的最优解。优化计算问题是存在于众多研究领域，吸引了来自各行各业的研究人员采用不同的方法来解决它。对于许多复杂的问题，如神经网络的训练、系统模型参数的辨识等，可以转化为优化计算问题来求解。优化计算的本质上是从问题域的所有可行解中选择出能够达到最优目标的解，一般可以分为最大值问题和最小值问题。对于优化计算问题，使用传统的求解方法，如枚举法、启发式算法、搜索算法等，随着问题的种类的不同和问题规模的扩大，传统的求解方法将很难得到最优解，而遗传算法为我们提供了一种求解优
11、化问题的通用框架，2通过对种群施加的迭代进化过程，不断地将当前代种群中适应度较高的个体遗传到下一代群体中，并且不断地淘汰适应度较低的个体，从而能够找出适应度最大的个体。这个适应度最大的个体经解码处理之后所对应的个体表现型就是这个实际应用问题的最优解或近似最优解。1.2 遗传算法的发展历史及研究进展20 世纪 60 年代末 70 年代初，美国 Michigan 大学的 John Holland 及其同事、学生们形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。1967 年，Holland 的学生 Bagley 在他的博士论文中首次提
12、出了“遗传算法”这一术语，提出选择、交叉和变异，与目前遗传算法中相应的算法十分接近，引入适应度定标(Scaling)的概念。同时，他也首次提出了遗传算法自我调整的概念。Hollstien 首次将遗传算法用于函数优化计算，1971 年在他的论文“ Artificial Genetic Adaptation in Computer Control Systems”中系统的阐述了将遗传算法用于数学反馈控制的方法，主要讨论了二变量函数的优化问题。1975 年， Holland 出版了开创性著作“Adaptation in Natural and Artificial Systems”，以后 Holla
13、nd 等人将该算法加以推广，应用到优化和机器学习等问题中并正式定名为遗传算法。该书系统地阐述了遗传算法的基本理论和方法，并提出了遗传算法的基本定理模式定理(Schema Theorem)，奠定了遗传算法的理论基础。同年，美国 De Jong 博士在其论文遗传自适应系统的行为分析中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟(generationgap)等新的遗传操作技术，建立了著名的 De Jong 五函数测试平台。3对遗传算法影响力最大的专著，要属于 1989 年美国伊利诺大学的Goldberg 所著
14、的“Genetic Algorithm in Search，Optimsization，and Machine Learning”。这本书对于遗传算法的理论及其多领域的应用展开了较为全面的分析和例证。1992 年，Michalewicz 出版了另一部很有影响力的著作“Genetic Algorithm+Data Structure=Evolution Programs”对遗传算法应用于最优化问题起到了推波助澜的作用。以遗传算法、进化计算为主题的多个国际会议在世界各地定期的召开。1985 年，在美国卡内基梅隆大学召开了第一届国际遗传算法 ICGA85，以后该会议每隔一年举行一次。1997 年夏季
15、在美国密西根大学召开了 ICGA97。现在与之平行的国际会议很多，其中 International Conference on Evolutionary Programming 和 IEEE Conference on Evolutionary Computation 每隔 2 年和 4 年召开一次。在欧洲，从 1990 年开始每隔一年举办一次 Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。在国内，有关遗传算法的研究，自本世纪以来一直处于不断上升的时期，特别近年来
16、，遗传算法的应用在许多领域取得了令人瞩目的成果，该类研究获得不同渠道的经费资助比例也在逐年上升。其中较突出的研究成果有：2002 年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题；2004 年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法 Parallel GA，BCPGA） ；2005 年，江雷等针对并行遗传算法求解 TSP 问题，探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收
17、敛的障碍，向全局最优解方向进化。41.3 本课题研究的目的和意义从上面的介绍可以看出遗传算法已经成为一个研究的热点课题，国内外都非常重视遗传算法理论和应用的研究，并取得了令人瞩目的进展，遗传算法的应用成果已渗入到许多领域，如组合优化、机器学习、自适应控制、规划设计和人工生命等领域。遗传算法为解决复杂优化计算问题提供了一个崭新而有效的思路，良好的搜索能力和较强的健壮性。遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类具有很强的鲁棒性，广泛应用于很多学科。本文主要介绍遗传算法的优化计算方法和计算流程。对于连续函数，在Matlab 上运用遗传算法工具箱实现了一
18、个单变量的连续函数和两个多变量的连续函数的优化计算，并在 c+上实现单变量的连续函数优化计算，都能够取得问题的最优解。对于离散问题的优化计算，着重对 0-1 背包问题和 TSP 问题等离散问题的经典案例进行系统论述，并针对不同问题提出不同的解决方案。在程序设计中采用多种算子相互结合的方式提高收敛速率，如针对背包问题采用轮盘赌选择与精英保留策略，针对 TSP 的是实值编码，采用逆转变异，优化计算结果表明，遗传算法得到的结果较为理想。第二章 遗传算法基本理论5第二章 遗传算法的基本理论2.1 数学基础2.1.1 模式定理模式 ：模式可以表示基因串中具有某些特征位置相同的结构，我们把模式描述成为一个
19、串的子集，在一个以二进制编码的串中，模式包括三个字符集的字符串，其中符号*代表任意字符，为 0 或 1。对于一个二进制编码串，(0,1)当串长为 时，共有 个不同的模式，遗传算法中串的运算实际上是模式的运l3l算。模式阶：模式 中确定位置的个数称为模式 的模式阶，记作 ，如HH()OH。模式阶用来反映不同模式之间的确定性差异，模式阶数越低，(1*0)5O模式的确定性越低，所匹配的样本个数就越多。定义距： 模式 H 中第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作 。如 。()(10*)4在遗传操作中，即使模式具有相同的阶数也会有表现出不同的性质，而定义距恰好就反映了这种性质的
20、差异。模式定理：在遗传算法选择、交叉、变异算子的作用下，具有低阶、短定义距以及平均适应度值高于种群品均适应度值的模式在子代中成指数增长。模式定理的数学表表达式为： _()()(,1),.1cmfHmHttpoHpl式中， -表示在 t+1 代种群中存在模式 H 的个体数目；(,)t第二章 遗传算法基本理论6-表示在 t 代种群中存在模式 H 的个体数目；(,)mHt-表示在 t 代种群中包含模式 H 的个体平均适应度；f-表示在 t 代种群中所有个体的平均适应度；f-表示个体的长度；l-表示交叉概率；cp-表示变异概率。m模式定理作为遗传算法的基本理论，保证了较优的模式，即遗传算法的较优解的数
21、目呈指数增长，为解释遗传算法的机理提供了一种数学工具。2.1.2 隐含并行性假设种群中有 n 个个体，染色体长度为 的编码串中隐含着的 个不l 2lln:同的模式。随着种群世代进化过程的进行，不是所有的模式都能够以很高概率被处理，一些定义距较长的模式将遭到破坏。关于遗传算法中能够以指数规律处理的模式数量，Holland 和 Goldberg 经过分析提出了遗传算法有效处理的模式个数有效模式总数约与种群规模的立方成正比为 O（ ） ，这一性质被称为3n隐含并行性。隐含并行性是遗传算法的一个重要特点，通过这种隐含并行性，我们可以快速地搜索出一些较优的模式。2.2 遗传算法的运算流程遗传算法简单、易
22、懂，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。其数学模型可表示为：，式中： 0(,T)GACEPN第二章 遗传算法基本理论7C -个体的编码方法；E -个体的适应度评价函数；-初始种群；0PN-种群大小；-选择算子；-交叉算子；-变异算子；T -遗传运算终止条件。对一个需要进行优化计算的具体问题，我们可以通过以下步骤来构造求最优解的遗传算法:(1) 根据不同的问题确定变量及各种约束条件，确定出个体的表现型与问题的解空间；(2) 确定出目标函数的类型(最大值或最小值优化) 和数学表达形式或量化方法；(3) 确定问题可行解的染色体编码方法，使每个个体的基因型对应遗传算法搜索空间的一个可行解；(4) 确定解码方法，编码串到参数变量的转化，即由个体基因型到个体表现型的对应关系；(5) 确定个体的评价方法，按照具体的问题选定适应度函数，确定出由目标函数到个体适应度的转换规则；(6) 设计遗传算子，即根据具体问题确定出选择、交叉、变异等算子的具体操作方法；(7) 确定遗传算法的有关运行参数，即确定出遗传算法的 、N、Pm、T 等参0P数。
