基于区间参数多目标优化问题的遗传算法的研究外文翻译资料

 2021-11-24 10:11

英语原文共 16 页

1.介绍

本文的目的是使用遗传算法(GA)的多目标优化方法的概述和教程。对于多目标问题,目标通常是相互冲突的,阻止了每个目标的同时优化。许多甚至大多数真正的工程问题实际上都有多个目标,即最小化成本,最大化性能,最大化可靠性等。这些都是困难但现实的问题。GA是一种流行的元启发式算法,特别适合这类问题。通过使用专门的健身功能和引入促进解决方案多样性的方法,传统GA可以定制以适应多目标问题。

多目标优化有两种通用方法。一种是将各个目标函数组合成单个复合函数,或者将除了一个目标之外的所有目标移动到约束集。在前一种情况下,可以使用效用理论,加权和方法等方法确定单个目标,但问题在于正确选择权重或效用函数来表征决策者的偏好。实际上,即使是熟悉问题领域的人,也很难精确准确地选择这些权重。使这一缺点更加复杂的是,需要在目标之间进行缩放,并且权重中的小扰动有时会导致完全不同的解决方案。在后一种情况下,问题是将目标移动到约束集,必须为这些以前的目标中的每一个建立约束值。这可能相当武断。在这两种情况下,优化方法都会返回单个解决方案,而不是一组可以检查以进行权衡的解决方案。出于这个原因,决策者通常更喜欢考虑多个目标的一套好的解决方案。

第二种通用​​方法是确定整个帕累托最优解集或代表子集。帕累托最优集是一组相互之间非支配的解。在从一个Pareto解决方案转移到另一个Pareto解决方案时,在一个目标中始终存在一定量的牺牲以在其他目标中实现一定量的增益。帕累托最优解决方案通常优于单一解决方案,因为在考虑现实问题时它们是实用的,因为决策者的最终解决方案总是需要权衡。帕累托最优集可以具有不同的大小,但是帕累托集的大小通常随着目标数量的增加而增加。

2.多目标优化配方

考虑一个决策者,他希望优化K目标,使目标不可比较,决策者没有明确偏好目标相对于彼此。在不失一般性的情况下,所有目标都是最小化类型 - 最小化类型目标可以通过乘以负数来转换为最大化类型。具有K个目标的最小化多目标决策问题定义如下:给定解空间X中的n维决策变量向量x = { x 1,...,x n } ,找到最小化给定集合的向量x *的ķ目标函数zx*)= { z 1(x *),... ,z K(x *)}。解空间X通常受到一系列约束的限制,例如g j(x *)= b j forĴ=1,...,m和决策变量的界限。

在许多现实问题中,正在考虑的目标相互冲突。因此,相对于单个目标优化x经常导致关于其他目标的不可接受的结果。因此,几乎不可能实现同时优化每个目标函数的完美多目标解决方案。对多目标问题的合理解决方案是研究一组解决方案,每个解决方案在可接受的水平上满足目标而不受任何其他解决方案的支配。

如果所有目标函数都用于最小化,则可行解x被称为支配另一个可行解y(xgt;y),当且仅当Z(x)⩽Z(y),用于i=1,...,K和z(x)lt;z(y)至少一个目标函数j。如果解决方案空间中没有任何其他解决方案支配,则称解决方案是帕累托最优解。在不恶化至少一个其他目标的情况下,不能针对任何目标改进帕累托最优解。X中所有可行的非支配解的集合称为帕累托最优集对于给定的帕累托最优集,目标空间中的相应目标函数值称为帕累托前沿。对于许多问题,帕累托最优解的数量是巨大的(可能是无限的)。

多目标优化算法的最终目标是识别帕累托最优集中的解。然而,对于许多多目标问题而言,识别整个帕累托最优集合实际上是不可能的,因为它的大小。此外,对于许多问题,特别是对于组合优化问题,解决方案最优性的证明在计算上是不可行的。因此,多目标优化的一种实用方法是研究一组代表帕累托最优集合的解决方案(最着名的帕累托集合)。考虑到这些问题,多目标优化方法应该实现以下三个相互冲突的目标[1]

1.最着名的帕累托前线应该尽可能接近真正的帕累托前线。理想情况下,最着名的帕累托集应该是帕累托最优集的子集。

2.最着名的帕累托集合中的解决方案应该在帕累托前沿上均匀分布和多样化,以便为决策者提供权衡的真实图景。

3.最着名的帕累托前线应该捕捉帕累托前线的整个范围。这需要在目标函数空间的最末端研究解决方案。

对于给定的计算时间限制,通过聚焦(加强)对帕累托前沿的特定区域的搜索来最好地服务于第一目标。相反,第二个目标要求搜索工作在帕累托前沿上均匀分布。第三个目标旨在扩大两端的帕累托前沿,探索新的极端解决方案。

本文介绍了多目标遗传算法在解决多目标优化问题时实现这三个冲突目标的常用方法。

3.遗传算法

GA的概念是由Holland和他的同事在20世纪60年代和70年代开发的[2]。GA受到解释物种起源的进化论理论的启发。在自然界中,环境中脆弱和不适合的物种面临着自然选择的灭绝。强者有更大的机会通过繁殖将他们的基因传递给后代。从长远来看,携带基因正确组合的物种在其种群中占主导地位。有时,在进化缓慢的过程中,基因可能会发生随机变化。如果这些变化在生存挑战中提供了额外的优势,那么新物种就会从旧物种发展而来。自然选择消除了不成功的变化。

在GA术语中,一个解向量Xisin;X被称为个人或染色体。染色体由称为基因的离散单元组成。每个基因控制染色体的一个或多个特征。在Holland最初的GA实现中,假设基因是二进制数字。在后面的实施中,引入了更多变化的基因类型。通常,染色体对应于溶液空间中的唯一解x。这需要解空间和染色体之间的映射机制。此映射称为编码。事实上,GA的工作编码的问题,而不是问题本身。

GA运行着一组染色体,称为种群。人口通常是随机初始化的。随着搜索的发展,人口包括更健康和更​​健康的解决方案,并最终收敛,这意味着它由单一解决方案主导。荷兰还提出了一个收敛的证明(模式定理)到全局最优,其中染色体是二元向量。

GA使用两个运算符从现有运算符生成新的解决方案:交叉和变异。交叉算子是GA最重要的运算符。在交叉中,通常将两条染色体(称为亲本)组合在一起形成新的染色体,称为后代。父母是从群体中现有的染色体中选择的,并且偏好于适应性,因此预期后代会遗传使父母更健康的良好基因。通过迭代地应用交叉算子,预期良好染色体的基因在群体中更频繁地出现,最终导致收敛到整体良好的解决方案。

变异算子引入染色体特征的随机变化。突变通常应用于基因水平。在典型的GA实施方案中,突变率(改变基因特性的概率)非常小并且取决于染色体的长度。因此,突变产生的新染色体与原始染色体不会有很大差异。突变在GA中起着关键作用。如前所述,交叉通过使人口中的染色体相似而引导群体收敛。突变将遗传多样性重新引入群体,并帮助搜索逃离当地的最佳状态。

繁殖涉及为下一代选择染色体。在最一般的情况下,个体的适应性决定了其为下一代生存的可能性。根据健身值的使用方式,GA中有不同的选择程序。比例选择,排名和锦标赛选择是最受欢迎的选择程序。通用GA[3]的程序如下:

步骤1:设置Ť=1。随机生成N个解,形成第一个种群P1。评估P1中溶液的适应度。

步骤2:交叉:生成后代群体Q如下:

2.1:根据适应度值从P中选择两个解x和y。

2.2:使用交叉运算符生成后代并将其添加到Q。

步骤3:突变:突变每种溶液Xisin;Q吨与预定义的突变率。

步骤4:健身分配:评估并分配一个适应值到各溶液Xisin;Q吨根据它的目标函数值和不可行性。

步骤5:选择根据Qt的适应度从Qt中选择N个解,并将它们复制到Pt 1。

步骤6:如果满足停止标准,则终止搜索并返回当前填充,否则,设置t=t 1转到步骤2。

4.多目标GA

作为一种基于人口的方法,GA非常适合解决多目标优化问题。可以修改通用单目标GA以在单次运行中找到一组多个非支配解决方案。GA同时搜索解空间的不同区域的能力使得有可能找到针对非凸,不连续和多模解空间的难题的多种解决方案。GA的交叉运算符可以利用关于不同目标的良好解决方案的结构,以在帕累托前沿的未开发部分中创建新的非支配解决方案。此外,大多数多目标GA不要求用户对目标进行优先级排序,扩展或权衡。因此,GA一直是最受欢迎的多目标设计和优化问题的启发式方法。琼斯等人。[4]报道,90%的多目标优化方法旨在逼近潜在问题的真正帕累托前沿。其中大多数使用了元启发式技术,70%的元启发式方法都基于进化方法。

第一个多目标GA,称为矢量评估GA(或VEGA),由Schaffer[5]提出。之后,开发了多种多目标进化算法,包括多目标遗传算法(MOGA)[6],Niched Pareto遗传算法(NPGA)[7],基于权重的遗传算法(WBGA)[8],随机加权遗传算法。 (RWGA)[9],非指定分类遗传算法(NSGA)[10],强度帕累托进化算法(SPEA)[11],改进的SPEA(SPEA2)[12],Pareto-Archived Evolution Strategy(PAES)[13],基于帕累托包络的选择算法(PESA)[14],基于区域的进化多目标优化选择(PESA-II)[15],快速非支配排序遗传算法(NSGA-II)

原文和译文剩余内容已隐藏,您需要先支付 20元 才能查看原文和译文全部内容!立即支付

以上是毕业论文外文翻译,课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。