（应用数学专业论文）一种新的多目标优化遗传算法.pdf

论文题目：一种新的多目标优化遗传算法 专 业：应用数学 硕 士 生：杜文晖 (签名) 指导教师：王雪峰 (签名) 摘 要 为了更好的解决实际生活中的多目标优化问题，综合已有的理论和算法，提出了一 种新的多目标优化遗传算法。 在原有遗传算法基础上改进了遗传操作算子， 并采用 pareto 秩的方法来确定个体的适应度，为了使秩越小的个体被选择的概率越大，文中定义了一 个与 pareto 秩成反比例的函数。根据轮盘赌方法来进行选择操作、采用算数交叉算子和 非均匀变异算子，并在运算过程增加了一个临时存储器，用来存放当前种群的 pareto 最 优解，将新加入的个体与当前临时存储器中的个体进行比较，将劣于新加入个体的解从 临时存储器中删掉，始终保持这个存储器中的群体是最优的。为了提高算法在局部的搜 索能力，在算法搜索过程中增加了一个黄金分割搜索，以提高算法的收敛速度，使其更 快的逼近全局最优解。黄金分割搜索算法是经典的一维搜索方法，为了利用其良好的搜 索能力，将其扩展到n维空间，并给出了具体算法步骤。通过对 3 个算例进行分析，检 验了算法的有效性；任何一种算法都不是万能的，都是有其使用范围的，通过一个反例 来说明给出的新的多目标遗传算法也不例外。最后通过 wolpert（沃伯特）和 macready （麦克雷）教授提出的无搜索和优化免费午餐定理（no free lunch 定理）对这种观点 加以说明，即算法在提高了对某类问题的解决速度的同时，必然降低了对另外一类问题 的解决速度。 关 键 词：遗传算法；多目标优化；存储器；黄金分割 论文类型：应用研究 subject : a new multi-objective optimization genetic algorithm specialty : applied mathematics name : du wenhui (signature) instructor : wang xuefeng (signature) abstract in order to solve multi-objective optimization problem in the real-life, according to the existing theory and algorithms, a new multi-objective genetic algorithms was presented. based on the original genetic algorithm, to improve genetic operators, pareto rank methods used to determine the individual fitness, the smaller the rank the greater the probability of the individual being selected, i define a function which is the inverse function of pareto rank. according to roulette selection method, using arithmetic crossover and non-uniform mutation operator, in the computing process, increased a memory to store the current population of pareto optimal solution, the new individuals was joined the temporary memory , compared with the current individual of memory, from the temporary memory, the individual which is worse than the new entrants individual will be deleted. in the temporary memory, the solution of the individual is always optimal. to improve the local search capability of the algorithm, the artist applies a golden section search in the search process of the algorithm to improve the convergence speed. golden section search is the classic one-dimensional search method, in order to use its good search capabilities; the artist extends it to the n-dimension of space, and gives the specific steps of the algorithm. according to the numerical examples, the artist tests the effectiveness of the algorithm; any of the algorithms are not omnipotent, which of all have the area, through a counter-example to illustrate the given new multi-objective genetic algorithm is no exception. professor wolpert and macready presented a free search and optimization of free lunch theorem (no free lunch theorem). according to the theorem , to support this view in the paper. the algorithm improved the speed of certain types of problem solving, while the other will inevitably reduce the settlement rate of a class of problems. key words: genetic algorithm multi-objective optimization memory golden section thesis : applied research 1 绪论 1 1 绪论 工程中经常会遇到在多准则或多目标下设计和决策的问题，如果这些目标是相背 的，需要找到满足这些目标的最佳设计方案。像这种含有多目标和多约束的优化问题， 我们称为多目标优化问题（multi-objective optimization problem，mop）1,3。 近几十年来多目标优化问题得到了飞速的发展，成为了一门新兴学科，它起源于实 际中许多系统规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森 林管理、水库管理、能量分配等等。基本上，在现实生活中解决每个重要的决策问题的 时候，不得不在考虑不同的约束条件的同时处理若干相互冲突的目标，这些问题涉及多 个目标的优化，这些目标并不是独立存在的，而是相互有关联的。通常解决多目标优化 问题的作法是根据某效用函数将多目标问题合成单一目标来进行优化。但是，在大多数 情况下，在优化之前这种效用函数是难以确定的。这样遗传算法作为求解多目标优化问 题的新方法受到了相当程度的关注，并得到了迅速的发展。 本章主要介绍多目标优化问题的研究发展历史， 多目标遗传算法的研究现状以及本 论文的研究目的、内容和安排。 1.1 多目标优化综述 多目标优化问题是从实际应用中产生的， 我们在这方面的研究非常有必要是因为它 不论在经济、军事还是高科技领域都有着重要的研究价值和意义。 在多目标优化问题中，各目标通常相互冲突且不可公度，对其中的某一个目标进行 优化就必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评 价多目标问题解的优劣性1。与单目标优化问题相比2，多目标优化问题的解并不是唯 一的，而是存在一个最优解集合，集合中元素称为 pareto 最优或非劣最优。其最优解往 往有无穷多个，那么，如何在最优解集合中求出一组分布均匀且数量充足的代表解供给 决策者进行选择就显得十分重要。 追求最优化目标是人类的理想，最优化（optimization）就是从众多可能方案中选择 最佳者，以达到最优目标。优化问题是一个古老的问题，同时也是一个困难的问题，它 吸引了不少学者的目光，经典的方法很好地解决了部分优化问题，但是有些问题，比如 多目标优化问题（multi-objective optimization problems：mops） ，却没有高效实用的解 决方法，然而现实世界中的许多优化问题都涉及多个目标的优化，而且这些目标并不是 独立存在的，它们往往是耦合在一起且处于相互竞争的状态，每个目标具有不同的意义 和量纲，它们的竞争与复杂度使得对其优化变得十分困难。一般地，多目标最优化问题 可以统一地表示为如下多目标极小化模型4,5： 西安科技大学硕士学位论文 2 12 min, 0,1,2, 0,1,2, . . t m i i f xfxfxfx gxil gxillk st （1.1） 当 1212 , nm xx xx ，,1,2, ii xim ，其中为候选解 空间。 在现实生活中， 人类改造自然的一切活动总体上反映了 “效益最大化， 成本最小化” 这一基本优化原则，即用最低的成本获取最大的收益。在合作对策问题中如何求解最优 策略以获得共赢目标，在非合作对策问题中如何使得自己的利益实现最大，对方的收益 最小，因为多目标优化问题在现实生活中随处可见，所以针对多目标优化问题的研究成 为一个引人注目的研究领域，具有一定的现实意义。 在单目标优化中问题的最优解已具有明确的定义6，但是，在多目标优化中这一概 念却不能得到推广，多目标优化的解不同于单目标优化问题的最优解概念，多目标优化 问题的最优解应是一组最优解的集合，称为非劣解集，也就是 pareto 最优解集，当对所 有的目标函数考虑时，在搜索空间中再也不存在比这些解更优的解，我们称这样的解是 最优的，这一观点最早是由法国经济学家 v.pareto（1848-1923）在 1896 年提出的，但 是传统数学规划原理的多目标优化方法在解决实际问题时表现出了一定的脆弱性，因 此，有必要研究解的高效多目标优化的算法及理论。 1.2 多目标遗传算法的起源 计算机的出现使人类的科学研究进程得到了飞速发展， 也使得有些困难的问题有了 新的解决方法，同时众多领域都因研究工具的进步而重现生机，同时也产生了众多的新 兴学科。尽管人们可以让计算机完成一些过去无法想象的任务，但仍有很多复杂问题得 不到很好的解决7,8,9，众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的 搜索空间中寻找最优解或准最优解。 像货郎担问题和规划问题等组合优化问题就是典型 的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索 的组合爆炸。因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识，并自适 应的控制搜索过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课 题。遗传算法就是这种特别有效的算法。它的主要特点是简单、通用，鲁棒性强，适用 于并行分布处理， 应用范围广。 自然界中丰富多彩的生物是自然选择和进化的直接结果， 现代分子生物学的发展也为这一学说提供了直接的证据， 进化使得生物能够更好的适应 自然环境，虽然进化的结果非常复杂，但进化的过程却很简单：繁殖、变异、竞争、选 择， 而遗传算法正是模拟生物的遗传与自然选择的进化机理而演变的一类智能群体算法 10。 1 绪论 3 正是在自然界的启示下， 一种模拟自然界的生物进化过程的学科进化算法产生 了。进化算法的研究起源于 20 世纪 50 年代末，成熟于 80 年代。进化算法具有有四大 分支：在 60 年代中期，holland 提出了遗传算法(genetics algorithm: ga） ，rosenberg 提 出了进化策略（evolutionary strategy） ，foguel 等人提出了进化规划(evolutionary programming） ，20 世纪 90 年代，koza 在遗传算法的基础上将遗传算法（ga）应用于 计算机程序及自动化生成，提出了遗传程序设计（genetics programming） ，虽然这几个 分支在算法实现方面有一些细微的差别和各自的特征，但它们具有一个共同的特点，即 都是借鉴生物进化的思想和机理来解决实际问题的。目前，进化算法己在自适应控制、 经济预测、规划设计、机器学习、工程优化、人工生命等领域得到了成功的应用，且在 众多领域掀起了进化计算的研究热潮11,12。现实世界中的很多优化问题都涉及多个目标 的优化，多目标优化问题与单目标优化问题不同，单目标优化问题的最优解往往只有一 个或少数几个，而多目标优化问题的最优解往往很多，甚至是无穷多个，而进化算法是 以种群进化为基础的，其进化的结果是一群解，利用它可在一次运行中求出问题的多个 解甚至全部解，因此，进化算法模型比较适合于多目标优化问题的求解，同时，进化算 法适用于并行分布处理、智能性及表现的自适应性和自组织性等特点，可以同时搜索到 问题解空间中的多个区域。因此，进化算法为多目标优化问题的解决提供了新的思路和 新的契机。另外，由于多目标问题的广泛存在性和其求解的困难性，该问题一直是富有 挑战性和吸引力的问题。从 90 年代开始流行的进化算法为求解多目标优化问题提供了 有力的理论工具，近年来，进化计算界相继提出了多种不同的多目标进化算法 （multi-objective evolutionary algorithm: moea） ， 它们的提出引起了众多研究机构的重 视，这一方向已成为学术界研究的热点，近几年来这一方面取得的引人瞩目的成就以及 它应用于实际工程中的巨大价值，使得一系列以遗传算法为主题的国际会议十分活跃。 1.3 多目标进化算法的研究现状 遗传算法研究的兴起是在 80 年代末和 90 年代初期，但它的历史起源可追溯到 60 年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主，早期遗传算法的研究 特点是侧重于对一些复杂的操作的研究。虽然其中向自动博弈、生物系统模拟、模式识 别和函数优化等给人以深刻的印象，但总的来说，这是一个无明确目标的发展时期，缺 乏带有指导性的理论和计算工具的开拓。这种现象直到 70 年代中期，由于 holland 和 dejong 的创造性研究成果的发表才得以改观。进入 80 年代，遗传算法迎来了兴盛发展 时期，无论是理论研究还是应用研究都成了十分热门的课题，尤其是遗传算法的应用研 究， 不但它的应用领域扩大， 而且利用遗传算法进行优化和规划学习的能力也显著提高， 同时产业应用方面的研究也在摸索之中， 此外一些新的理论和方法在应用研究中也得到 了迅速的发展13。目前应用的领域主要有控制、规划、设计、组合优化、图像处理、信 西安科技大学硕士学位论文 4 号处理、路径规划和人工生命10。 进化算法是 90 年代初为了促进不同的模拟生物进化之间的交流而提出的，现已成 为“智能”与“优化”两大主题的研究新热点，出现了进化计算的繁荣，目前进化计算 已和人工神经网络（ann: artificial neural networks） ，模糊逻辑（fl: fuzzy logic）相 结合，产生了一门新的综合性的计算技术学科计算智能（ci: computational intelligence） 。 internet 技术的发展给进化计算的研究带来了丰富的信息资源，使我们可以获得更 广泛、快捷的交流以及极大的获得有关进化计算的科研资料，同时可随时了解有关进化 计算研究与应用的最新进展。由于进化算法与传统优化技术相比具有许多优势，且在人 工智能中有着广泛诱人的应用前景。国内自 90 年代以来对进化计算也开展了广泛的研 究。特别将进化计算应用于不同的领域，取得了瞩目的成就，但与国外相比，国内对进 化计算的理论研究还不够深入。 特别是把进化算法应用于多目标优化问题的求解的理论 和应用还不足，因此，对这一问题的研究具有很大的价值。 目前国际上对遗传算法开始出现了较大的争议， 主要是由于遗传算法的搜索过程很 乱，而且局部搜索的速度太慢，所以单独使用遗传算法来解决优化问题也并不是一个有 效的算法。目前国际上的趋势是把遗传算法和一些确定性的优化算法，比如 bfgs，填 充函数法，隧道函数法等结合起来，以加快局部搜索的速度，从而能更快的找到全局最 优值。 1.3.1 研究历史 mops 最早的出现，应追溯到 1772 年，当时 franklin 提出了多目标矛盾如何协调 的问题，但国际上一般认为 mops 最早是由法国经济学家 v.pareto 在 1896 年提出的， 他当时从政治经济学的角度出发，把很多难以比较的目标归纳成多目标优化问题。1951 年 t.c.koopmans 从生产分配活动中提出了多目标优化问题，并提出了 mops 的一个重 要概念pareto 最优解（非劣解） ，1968 年 z.johnsen 系统地提出了多目标决策问题的 研究报告，这是多目标优化这门学科开始大发展的转折点，多目标优化问题从 v.pareto 正式提出到 z.johnsen 对其系统总结，先后经历了六、七十年间的发展，但是，传统的 数学规划是以单点搜索为特征的串行算法难以利用 pareto 最优概念对问题求解， 尤其要 对一些复杂的问题求解时，传统优化方法显得难以处理，直到 1985 年 schaffer 提出了 第一个多目标遗传算法（moea） ，开创了用进化算法处理 mops 问题的先河，在此之 后相继出现了许多 moea。多数成功的 moea 的出现不仅很好地解决了古典运筹学所 能处理的连续型 mops，而且还具备进化算法处理问题的独有特征，例如对大多数不连 续，不可微，非凸，高度非线性问题的处理是非常有效的。因此目前进化多目标优化算 法作为一个优化工具己在解决工程技术、经济、管理、军事和系统工程等众多方面的问 1 绪论 5 题上越来越显示出它的强大生命力。 1.3.2 总体分类 目前对 moea 的研究成果可以说是层出不穷，但我们根据其某种特性可以将他们 进行分类14，下列讨论两种主要的分类：其一，若按决策者对目标主观偏重程度与非劣 解搜索过程之间的相互影响关系，可将多目标进化算法（moea）分为：（1）先验优 先权技术，（2）优先权演化技术，（3）后验优先权技术三大类，先验优先权技术是将 全体目标按权值合成一个标量效用函数，这样把多目标优化问题转化成单目标优化问 题；优先权演化技术是将优先权决策（决策器）与对非劣解的搜索过程（优化器）交替 使用，变化的优先权可产生变化的非劣最优解集，决策器从优化器的搜索过程中提取有 利于精练优先权的信息， 而优先权的设置则有利于优化器搜索到更为感兴趣的非劣最优 解域；后验优先权技术是对优化器进行最优解得搜索，而决策器是从搜索到非劣最优解 集中进行选择的过程。其二，若按进化群体内所有个体进行排序所使用的方法，可将 moea 分为基于 pareto 最优概念和不基于 pareto 最优概念的两大类，基于 pareto 最优 概念的优化技术采用 pareto 最优概念对多目标进行比较与排序， 并基于 pareto 排序进行 适应度赋值； 不基于 pareto 最优概念的多目标优化技术包括了直接和间接的目标加权和 方法。但从统计数据中发现，目前基于 pareto 最优概念的 moea 占据了主要地位。 1.3.3 主要方法 （1）并列选择法 schaffer 提出的“向量评估多目标遗传算法（vega） ”是一种非 pareto 方法，此方 法先将群体中全部个体按子目标函数的数目均等分成若干个子种群， 对各子群体分配一 个子目标函数， 各子目标函数在其相应子群体中独立进行选择操作后再组成一新的子种 群，将所有生成的子种群合并成完整群体再进行交叉和变异操作，如此循环执行“分割 并列选择合并”过程，最终求出问题的 pareto 最优解（非劣解） 。 （2）排序选择法14,15 fonseca等人提出了基于排序选择的 “多目标遗传算法 （ffga） ” 是一种典型的 pareto 方法，它根据“pareto 最优个体”的概念来对群体的所有个体进行排序，并依据排序次 序运用比例选择法，使得排在最前面的个体有更多的机会遗传到下一代，经过一定的代 数循环后，就可得到所需数目的 pareto 最优解。 （3）权重选择法16 hajela 和 lin 提出了“可变目标权重聚合法（hlga）”，此方法在适应度赋值时 使用加权和法，对每个目标赋一个权重，为了并行搜索多个解，权重本身并不固定，对 问题解和权重同时实施进化操作，为了保证收敛速度和遗传搜索的稳定性，该方法还使 西安科技大学硕士学位论文 6 用了配对约束。 （4）外部辅助选择法18-20 zitzler 和 thiele 提出了“强度进化算法（spea）”，将每代的非劣解储存在外部 的一个可更新的存储器中， 而群体中个体的适应度与外部存储器中优于该个体的数目有 关，利用 paerto 的关系保持群体多样性，使用聚类方法保证外部存储器中的非劣解数目 不超过规定范围且又不破坏其特征。 （5）粒子群选择法21 kennedy 和 eberhart 于 1995 年提出了一种优化方法粒子群算法 （particle swarm optimization，pso），由于其算法容易理解，易于实现，在许多优化领域得到了成功的 应用，近几年来，人们把它己用在多目标优化问题求解上，取得了很好的效果，例如： coello 和 lechuga 在非劣最优概念的基础上应用了一个“容器”来记录已经找到的非支 配向量解，并用这些解来指导其它粒子飞行的 pso 算法，parsopoulos 和 vrahtis 应用了 权重聚合的 pso 算法， hu 和 eberhart 则用动态临近的 pso 算法来求解多目标优化算法。 （6）序和密度选择法3 haimnig lu 和 gary g 提出了“序和密度遗传算法（rdga）”，该算法对多目标 优化问题的目标空间进行了分割并引入了格子的序和格子的密度， 把一个多目标优化问 题转化成了基于目标空间中格子的序和格子的密度的双目标优化问题， 其中格子的序是 用来控制整个目标空间中解的质量， 格子的密度是用来控制整个目标空间中解的均匀性 分布， 对它们的同时优化来引导目标空间中 pareto 最优解向 pareto 前沿曲面移动并保持 求得目标空间中非支配解的均匀性分布。 （7）非劣分层选择法22,23 srinivas and deb 提出了“非劣分层多目标遗传算法（nsga） ，k.deb，s.agrawal， a pratab 对方法 nsga 进行了改进， 提出了 nsga-ii 这两种算法的主要思想是对种群中 的个体按 pareto 进行排序，首先将种群中的所有非劣解被赋予 front=1，然后从种群中 忽略它们， 这时把种群中的新的非劣解又被赋予 front=2， 依次类推， 最后由个体的 front 值来决定个体的适应度值和选择与否。 1.4 本文内容及安排 本文一共分为五章，第一章绪论为总述，提出多目标优化的模型和要解决的问题， 并介绍了遗传算法以及多目标遗传算法的发展状况。 第二章的主要内容是介绍遗传算法 以及多目标遗传算法的基本概念，并对一些遗传算法的步骤作一介绍。第三章提出了新 多目标遗传算法，将“优胜劣汰”应用到遗传算法中，增加一个新的存储算子保存当前 的最优个体，并且阐述算法的个体的适应度分配、选择机制等，并在其中增加了黄金分 割搜索操作，对算法步骤做出了具体描述。第四章对本文提出的多目标遗传算法进行数 1 绪论 7 值试验，首先通过 3 个测试函数验证了本算法的有效性；其次，给出了不适用于本算法 的算例，通过这个算例来说明任何一个算法都是有使用范围的，本文给出的多目标遗传 算法也不例外；最后，通过 wolpert（沃伯特）和 macready（麦克雷）教授提出了无搜 索和优化免费午餐定理（no free lunch 定理）对上述观点加以说明。最后一章为本论 文的总结部分，得出本文的主要结论和对以后要进一步研究的问题做出总结。 西安科技大学硕士学位论文 8 2 基本概念与基本理论 在实际科学计算中， 进化算法实质上是一种优化处理过程， 但与传统优化方法不同， 传统优化方法都是用代价函数来衡量动作的行为， 从而选择一个好的动作使操作的对象 达到优化， 而大多数典型的优化方法是通过计算代价函数的梯度或高阶统计值来进行优 化的，通过此类方法只能得到局部极优值，且易受随机干扰的影响。进化计算是一种通 过问题的求解方法、进化方法及符合达尔文“适者生存”和随机信息交换思想，消除解 中不适应因素，同时利用原有解的知识，最终获得全局最优解。 2.1 遗传算法的基本原理 作为进化算法的一个重要分支遗传算法，它是把“遗传”与“算法”很好的结 合起来，使其相互渗透，相互融合，并借鉴了生物进化的思想，通过计算机模拟物种繁 殖过程中父代遗传基因的重新组合与“优胜劣汰”的自然选择机制的联合作用，来解决 科学与工程中的复杂问题11。 用遗传算法解决问题时，首先要对解决问题的模型结构和参数进行编码，一般用字 符串表示，这个过程就是要将问题符号化、离散化，或在连续空间中直接对其定义，通 常一个简单遗传算法（simple genetic algorithm: sga）按如下步骤进行10： （1）随机产生初始种群 12 0, n xx xx； （2）对解决的问题进行编码； （3）对当前群体 x t中每个个体 i x计算其适应度 i f x，适应度表示该个体的性 能好坏； （4）用选择算子产生中间种群 xt ； （5）对 xt 应用其它算子，产生新一代群体，这些算子的目的在于扩展有限个体 的覆盖面，体现全局搜索的思想； （6）令1tt ，如果不满足终止条件继续步骤 3。 下面给出遗传算法（ga）的一般流程图（图 2.1） ： 2 基本概念与基本理论 9 图 2.1 ga 流程图 sga 中常用的算子有如下几种10-11： 选择算子（selection/reproduction） ：又称再生算子，选择的目的是把优化的个体直 接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。 选择操作是建立在群体 中个体的适应度评估的基础上的。 目前常用的选择算子方法有： 适应度比例选择 （fitness proportionate selection） 、 最佳个体保存选择 （elitist selection） 、 期望值方法选择 （expected 复制 交换 变异 问题的初始解 编码成染色体 确定种群 p(t) 计算适应度 通过遗传运算存优去劣 种群 p(t+1) 种群 p(t) 种群 p(t+1) 种群满足预定指标 解码染色体 问题解答空间 西安科技大学硕士学位论文 10 value selection） 、排序选择（rank selection） 、联赛选择（tournament selection）和排挤 方法（crowding selection）等。为了防止由于选择误差，或者交叉和变异的破坏作用而 导致当前群体的最佳个体在下一代的丢失，de jong 提出了精英选择（elitist selection） 策略。以上每种方法对于遗传算法的影响各不相同。在具体使用时，应根据问题求解特 点采用较合适的方法或者混合使用。 交叉算子（crossover） ：交叉算子在遗传算法中起核心作用的遗传操作。它将被选 中的两个个体的基因链按交叉概率 c p进行交叉， 生成两个新的个体， 交叉位置是随机的， 通常使用的方法有：一点交叉（one-point crossover） ，两点交叉（tow-point crossover） ， 多点交叉（multi-point crossover） ，一致交叉（uniform crossover，又叫均匀交叉）等。 变异算子（mutation） ：变异算子是将新个体的各位按变异概率 m p进行变异，在遗 传算法中，通常使用的方法有：基本变异算子、逆转算子和自适应变异算子等。 目前， 实现上述各种算子的方法是多种多样的， 而且正在不断的提出许多新的算子， 以达到改进 ga 的性能， 且系统参数 （种群个数， 基因长度， 编码方式等） ， 交叉概率 c p， 以及变异概率 m p的改变等对算法的收敛性以及收敛速度都有很大的影响， 应根据具体求 解问题而定。 与自然进化类似，将候选解称为个体，则候选解集称为群体，每个个体代表一个可 行解，即待处理问题的一个决策向量，但个体并不就是决策向量，因为它是基于适当结 构的编码形式，所有可行向量构成个体空间i。 在选择过程中， 从群体中删除低质量的个体， 高质量的个体有更多的机会得到复制， 使的群体的平均适应度得以提高，而个体的质量是与目标函数和约束条件相关，在计算 个体适应度时须先对个体进行解码。 个体空间， 决策空间和目标空间之间的关系如图 2.2 所示，其中假设某个体ii，映射函数m的编码算法使i变为决策向量 xm i，x的目 标向量输出函数f对应个体i的适应度赋值。 图 2.2 个体空间、决策空间和目标空间之间的关系 个体 i 决策向量 x 目标向量 y 个体空间 i 决策空间 x 目标空间 y 映射函数 :m xm i 函数 :fyf x 2 基本概念与基本理论 11 遗传算法具有如下特点： （1）遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此操 作使得遗传算法可直接对结构对象进行操作。 （2）许多传统搜索算法都是单点搜索算法，容易陷入局部的最优解。遗传算法同 时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解 的风险，同时算法本身易于实现并行化。 （3）遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值 来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其 定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。 （4）种群是从旧种群开始，经历突变、自然选择和隔离等过程的再次分化得到， 种群的延续不是完全连续的。遗传算法不是采用确定性规则，而是采用概率的变迁规则 来指导他的搜索方向。 （5）具有自组织、自适应和自学习性（智能性） 。遗传算法利用进化过程获得的信 息自行组织搜索，适应度大的个体具有较高的生存概率，具有更适应环境的基因结构。 在遗传算法中，群体搜索策略和群体中个体之间的信息交换是遗传算法的两大特 点。它们的优越性主要体现在：遗传算法在搜索过程中不容易陷入局部最优，即使所定 义的适应度函数是不连续的、非规则的；由于他们固有的并行性，遗传算法非常适合于 巨量的并行机；遗传算法采用自然进化机制来表现复杂的现象，能很快可靠地解决非常 困难的问题；由于他们容易介入到已有的模型中且具有可扩展性，以及易与其它技术相 结合等特点，遗传算法目前已在函数优化，机器学习和并行处理等领域得到了越来越广 泛的应用。 2.2 多目标进化算法概述 2.2.1 多目标优化问题数学描述 一般的多目标优化问题（mops）由一组目标函数和相关的一些约束组成，可作如 下数学描述24,25： 12 min/max, .0,1,2, t m n i f xfxfxfx xdr stgxip （2.1） 其中 , 12 t xx xxn是 n r空间的n维向量，称x所在的空间d为问题的决策空 间， ,1,2,fxjm j 为问题的子目标函数，m维向量 12 , m fxfxfx所在 西安科技大学硕士学位论文 12 的空间称为问题的目标空间（objective space） ， gx i 1,2,ip为约束函数，mops 有时也称为向量优化问题（vector optimization problems：vops） 。 最小化和最大化可以相互转化，如果没有作特别说明，本文都以最小化目标问题为 研究对象。 定义 2.1（决策空间上的可行集） 集 |0,1,2, n dx gxxrip i 称为 mops 在决策空间上的可行集 （feasible set in decision space） 。 定义 2.2（目标空间上的可行集） 集 12 ,1,2, m mii ffffrffxim xd称为 mops 在目标空间上 的可行集（feasible set in objective space） 。 将向量函数 12 , m f xfxfxfx看作是映射: nm frdr，则目标空 间f上的可行集是决策空间d上的可行集在映射f下的像（image） 。如图 2.3 所示： 图 2.3 决策空间与目标空间上的可行集的关系 定义 2.3（优劣性，dominance/inferiority） 设目标向量解 12 , n xx xx和 12 , n yy yy，如果x部分小于y，即： 1, 2,in ，有 ii xy且1,2, ii inxy ，则称向量解 12 , n xx xx优于 12 , n yy yy；反过来，称目标向量解 12 , n yy yy劣于 12 , n xx xx。 12 , n x xx 12 , n fff 决策空间d 目标空间f 映射函数 :fff x 2 基本概念与基本理论 13 定义 2.4（非劣解，non-inferior solution） 若xd，且不存在另一个可行点xd，使得 ii fxf x ，1,2,im成 立，且其中至少有一个严格不等式成立，则称 x 是 mops 的一个非劣解（non-inferior solution） 。 定义 2.5（非劣解前沿面，pareto front） 由所有非劣解组成的集合称为多目标优化问题（mops）的最优解集（非劣解集， non-inferior set） ，也称为可接受解集或有效解集，一般记为 ture p；相应所有非劣最优解 的目标向量称为目标空间中的非劣解集 （非劣解前沿面， pareto front） ， 一般记为 ture pf。 ture p与 ture pf由具体的多目标优化问题中的各目标函数所决定，是一个确定的集合， 由优化算法所发现的非劣最优解组成的集合记为 known p与 known pf。使用进化算法求解多 目标优化问题时，隐含下列假设之一在某些赋范函数（如欧式空间）中成立： knowntrue pp， knowntrue pp或, knowntruetrue pfpfpf。 2.2.2 多目标进化算法 本节将介绍四种多目标遗传算法，随机权重方法、spea、nsga 以及 nsga-ii 的 详细做法26-28。基本上，多目标遗传算法与单一目标基因演算的方法是差不多的，都是 经由评价、选择、交配与变异等几个操作的交互作用，而达到求最优解的目的。下面对 此四种多目标遗传算法的重要机制与流程逐一说明。 （1）随机权重法（random-weight approach）29 假设需要最小化n个目标函数。权重和目标（weighted-sum objective）如下所示： 1 n kk k yw fx （2.2） 随机权重 k w由下式确定： 1 k k n j j r w r ，1,2,kn （2.3） 其中 j r是随机非负随机数。 在选出进行杂交的个体对之前，由式（2.3）生成一组新的随机权重，根据式（2.2） 计算每个个体的适应值。第i个个体的被选择概率 i p由下面的线性比例变换函数定义： min _ min 1 () i i popsize k k yy p yy （2.4） 西安科技大学硕士学位论文 14 其中 min y是当前种群中最差个体的适应值。 每一代临时存储一组 pareto 最优解并按代更新。对于含有n个目标函数的问题，最 优解中存在n个极限点，每一个最小化一个目标。采用精华保存策略将m个解（包括极 限点与一些随机选择的 pareto 解）直接存入下一代种群。算法的框架如下所示： step1：初始化（initialization）随机产生初始种群； step2：评价（evaluation）对于每个个体计算n个目标函数值，更新临时 pareto 解 集合； step3：选择（selection）用式（2.3）指定随机权重，用式（2.2）计算适应度值， 根据式（2.4）计算被选择概率，为杂交操作选出父代个体，重复这步选出（ popelite nn） 对父代； step4：杂交（crossover）对于产生的每一对个体，执行杂交操作产生后代； step5：变异（mutation）对杂交操作产生的每个个体执行杂交操作； step6：最优性策略（elitist strategy）从临时 pareto 解集中随机选出 elite n个个体，添 加到前面产生的（ popelite nn）个个体中； step7：终止准则（termination test）如果满足事先给出的停止条件，则算法终止， 否则返回 step2。 （2）spea20 spea（strength pareto evolutionary algorithm）包含以下几个特点：1.适应度函数值 的决定方式，取决于在外部种群中的非支配解数量与被它支配的成员的个数；2.每一次 都将非支配解存储在外部的种群中，不断更新这个存储器中的种群；3.使用聚类的方式 来删除多余的非支配解。 1）spea 的算法框架如下： step1：初始化随机产生一个初始种群p以及构造一个空的外部非支配解集q； step2：将p中的非支配个体复制到外部非支配解集q； step3：删除外部非支配解集q中被其它个体支配的个体； step4：如果所得到的外部非支配解集q的个体数目超过一个最大值 * n，则使用聚 类的方式来删除外部非支配解集q中的解； step5：计算每一个p及q中的个体适应度函数值； step6：从p及q中选出个体放入配对池中，充满为止； step7：交叉和变异； step8：若达到了指定欲执行的最大代数，则停止计算；否则转到 step2。 2）适应度函数：spea 中的适应度函数是通过以下两步决定的。首先，对外部非支 配解集中的个体先进行排序；其次，再对种群中的每个个体进行评价。 3）聚类：过多的非支配解可能会降低选择的压力，并且减慢搜索的速度。所以， 2 基本概念与基本理论 15 当非支配解的数目超过最大值 * n时， 就需要删掉一部分。 spea 使用聚类的方法做删减， 其具体作法如下： step1：初始化一个聚类集合c。不同的外部非支配点iq组成不同的聚类： i ic； step2：如果 * cn，则转到 step5；否则，执行 step3； step3：计算所有聚类中可能数对的距离。其中，两个聚类的距离用下列算式表示： 11, 12 1 11 12 icjc dij cc （2.5） 其中1cc且2cc； step4：找出最小距离 min d的两个聚类1c和2c，将这两个聚类合并成一个大的聚类， 然后转到 step2； step5：从每个聚类选出代表性的个体，组成新的非支配集合。 （3）nsga23 nsga（non-dominated sorting genetic algorithm）是一种基于 pareto 最优概念的多 目标进化算法，1995 年由 deb 提出。ngsa 与 sga 的主要区别在于选择算子的不同， 而交叉算子和变异算子不变。 在选择之前， 先对种群按照个体的非劣性进行排序。 首先， 找出当前种群中的非劣最优解，将这些非劣解组成第一个非劣最优解层，赋一个大的虚 拟适应值。将个体原来的适应值除以与其周围的个体数目成比例的一个数，根据这个降 低后的适应值执行选择操作以实现共享。 这样使得多个最优点共存于种群中。 共享之后， 暂时不考虑这部分非劣最优解，以同样的方法对种群中剩下的个体进行分类，找出第二 层非劣最优解，给这些点赋一个新的虚拟适应值，该值要小于上一层中最小的共享虚拟 适应值，重复同样的操作，直至整个种群划分完毕。 在 nsga 中对每个局部的 pareto 曲面上的所有个体分别采用适应度共享策略，