外文翻译---一种基于树结构的快速多目标遗传算法

1、附录4 附录4一种基于树结构的快速多目标遗传算法介绍：一般来讲，解决多目标的科学和工程问题，是一个非常困难的任务。在这些多目标优化问题(MOPS)中，这些目标往往在一个高维的问题空间发生冲突，而且多目标优化也需要更多的计算资源。一些经典的优化方法表明将多目标优化转化成为单目标优化问题，其中许多运行被要求找到多个解决方案。这使得一种算法返回一组候选解，这比只返回一个基于目标的权重解的算法更好。由于这个原因，在过去20年中，人们越来越感兴趣把进化算法(EAs)应用到多目标优化中。许多多目标进化算法(MOEAs)已经被提出，这些多目标进化算法使用Pareto占优的概念来引导搜索，并返回一组非支配解作

2、为结果。与在单目标优化中找到最优解作为最终的解不同，在多目标优化中有二个目标：（1）收敛到Pareto最优解集（2）在Pareto最优解集中保持解的多样性。为了解决在多目标优化中这两个有时候会冲突的任务，许多策略和方法被提出。这些方法的一个共同的问题是，它们往往是错综复杂的。对于这两项任务，为了得到更优秀的解，一些复杂的策略通常被使用，并且许多参数需要依据经验和已经得到的问题信息进行调整。另外，许多多目标进化算法有高达的计算复杂度或者需要更多的处理时间（G是代数，M是目标函数的数量，N是种群大小。这些符号在下文也保持相同的含义）。在这篇文章中，我们提出了一种基于树结构的快速多目标遗传算法。(这

3、个数据结构是一个二进制树，它保存了在多目标优化中解的三值支配关系 （例如，正在支配、被支配和非支配），因此，我们命名它为支配树(DT)。由于一些独特的性能，使支配树能够含蓄地包含种群个体的密度信息，并且很明显地减少了种群个体之间的比较。计算复杂度实验也表明，支配树是一种处理种群有效的工具。基于支配树的进化算法(DTEA)统一了在支配树中的收敛性和多样性策略，即多目标进化算法中的两个目标，并且由于只有几个参数，这种算法很容易操作。另外，基于支配树的进化算法(DTEA)使用了一种特别设计的基于支配树(DT)的消除策略。这种策略不仅维护自然种群的多样性，但也意识到精英主义没有额外的消耗。六个基准测试

4、函数和三个著名的MOEAs（如NSGA-II，SPEA2，和Jensen的改进版本的NSGA-II）被用来检验DTEA算法的效率和效果。程序运行时间实验表明，DTEA算法总是远远快于基准算法，尤其是在人口规模很大的时候。另一方面，通过检测三个评价解质量的标准，我们发现，整体上对于收敛到真正Pareto最优前沿和维护种群多样性来讲，DTEA算法的解决方案质量并不比NSGA-II和SPEA2差，但是DTEA算法的计算所时间要短得多。本文的其余部分安排如下。论文第二节简要回顾了先进的MOEAs，第三节详细描述DTEA，第四部分给出并讨论了实验结果，最后，第五节总结本文。概述MOEAs本节简要调查当代

5、MOEA研究。第一部分将给出在本文中使用的一些概念。第二部分将简要分析当前最先进的多目标进化算法。2.1在多目标优化中的定义许多研究人员都给出了类似的定义。我们在这介绍两个重要概念的定义。为了不是一般性，我们在本文中只考虑最小化问题，它很容易将一个最大化问题转换成一个最小化问题。定义1：一般的多目标优化：一般来说，最小化一组多目标优化函数，约束函数（是决策变量空间）一个多目标优化的解可以使m维的目标向量的一部分达到最小，其中是空间的n维决策变量向量。定义2：Pareto占优：一个向量是占优向量（记作），当且仅当部分小于，即 ，并且 。当前，大多数多目标优化的研究都是基于Pareto占优。（在一

6、些文献中，Pareto占优也被定义为严格的，这里我们并不讨论他们的区别。）一个决策变量向量被称作Pareto最优解，当且仅当不存在，使得。所有Pareto最优决策向量被称为Pareto最优解集。相应的目标向量解集被称作非支配集，或者Pateto前沿。根据Pareto占优的定义，我们可以发现在MOPs和SOPs的解之间的关系中一个截然不同的差异。SOPs的解在目标空间中是标量数字，并且它们的关系有两种可能性：小于和大于（包含等于，为了简单起见，经常称之为大于）。然而，MOPs的解是向量，并且它们之间的关系有三种可能：，和非支配。这些差异要求MOEAs要有更复杂的适应度评价规则。2.2先进的MOE

7、As一个良好的MOEA必须满足以下两个点：（1）得到的非支配集要收敛到真正的Pareto最优前沿；（2）一个均匀分布的解决方案是可取的。这两个目标往往是大多数MOEAs的性能指标。许多方法被设计用来满足这两个目标。为了解决第一个方面，一个基于Pareto的适应度评价方法通常被设计为指导朝向真正Pareto前沿进行搜索。其基本思想是根据它们的支配关系对解进行排序。Goldberg第一次提出了一个普遍的方法，解集按照不同的支配序分成不同的前沿。Fonseca和Fleming提出了一种方法，在这种方法中，一个解集的支配序被解的数量和当前支配它的种群赋值。另一个排序在SPEA2中被提出，在这种方法中，

8、每一个个体都被分配一个强度值。对于第二方面中，一些成功的多目标进化算法提供的密度估计方法以保存种群的多样性。Pareto小生境和适应度共享技术在许多多目标进化算法中得到广泛地使用，例如，在NSGA，NPGA和MOGA中。在SPEA2中，第k个最近邻密度估算方法被应用于获得每一个个体的密度指数，NSGA-II的定义了一个新的密度估计度量，它不需要任何用户定义的参数。另一种流行的策略是使用超网格把目标空间划分成单元格。此外，一个新的-eliminating多样性的方法也被提出。最近，一些新的进化范例成功应用于多目标优化，例如，粒子群优化，人工免疫系统，估计分配和分散搜索。张和李提出了一种新的基于分

9、解的多目标优化。这种方法将一个多目标雨花问题分解成为多个标量优化的子问题，并且在同一时间优化它们。此外，为了得到良好的解，一些有效的技术也被采用。目前的研究表明，目前的研究表明，精英主义可以显著地提高多目标进化算法的性能，它有助于防止优秀解个体的丢失。对于避免过早收敛和不必要的计算复杂性，一个动态的人口规模，在线自主调整人口折衷和密度分布信息的特性，已被认为是比恒定的人口规模更有效和效率更高的方法。此外，使用不受约束的精英归档可避免被估计的Pareto前沿收缩。虽然有很多的多目标进化算法在采用这些策略和技术的一些基准问题上取得了良好的表现，但是这些算法还是有一些不足。一方面，许多多目标进化算法

10、错综复杂。为了获得优秀的解，许多多目标进化算法的收敛性和多样性使用单独的技术，即使这两方面在大多数多目标进化算法中最终融入个人的适应度评价。此外，在多目标进化算法中，许多参数需要根据问题域的知识和经验进行调整。例如，在DMOEA中，使用6个策略和四个参数需要进行调整。另一方面，许多多目标进化算法耗时。由于与单目标优化相比，多目标有优化通常是一个难计算的问题（比如三值关系），所以，由于大多数发表的多目标进化算法有高计算的需求。还有一种解释是MOEA的研究往往忽略了问题的计算复杂性，幸运的是，许多研究人员已经开始注意到这个问题。Deb等人提出了一种快速非支配排序算法来减少计算复杂度，在NSGA-I

11、I算法中，非支配排序的计算复杂度从降到。Jensen系统地分析许多当代多目标进化算法的计算复杂度，并提出了一些有效的非支配排序算法。此外，为了减小难度，一些数据结构也被引入。四叉树被检验作为把精英个体存储到非支配解中，这个不可约的支配图(IDG)被提出以用来管理种群。为了促进带精英策略的非支配排序，引入被支配和非支配的树结构。这些新算法和数据结构在某些程度上加快了适应度评价的处理。然而，它仍然需要进一步调查这个重要问题并且设计简单而又有效的适应度评价方法。基于支配树的进化算法3.1支配树3.1.1支配树的结构正如我们所知道的，适用度评价是多目标进化算法的重要组成部分，它高度影响算法的性能；并且

12、它在处理时间上非常耗时。大多数基于Pareto的适应度评价要求每个解应该与其他大量的解进行比较，这使得大多数的MOEAs计算复杂度限制在。请注意因子意味着随着种群数量的增长，使得计算复杂度增加非常快。然而，在许多情况下，MOEAs使用种群规模非常大的，特别是当相互冲突的目标非常多的时候。因此，这种困难需要解决。通过分析一些常用的适应度评价处理过程，我们可以发现在这些过程中有很多不必要的比较。个体之间的占优关系可以在一个图中看出，每个节点代表一个个体并且每条边代表相邻节点之间的关系。例如，图1显示了五个节点之间的占优关系。我们我们直观地观察可能有一些冗余的关系在图1(b)。减少这些冗余的关系可能

13、是一个有效的策略来减少适应度评价的计算复杂度。因为Pareto占优关系是可传递的，一些关系可以基于现有的关系来推导。以图1为例，如果我们知道N4 Pareto占优N3，N3 Pareto占优N2，那么不用通过比较我们也可以得出N4 Pareto占优N2。因此，N4与N2之间的比较可以避免。我们也注意到了另一个现象，我们只需要获得种群中每一代的Pareto最优解集，即使那些占优的解仍然对于进化过程有用。这样的原因是决策者经常基于最优解做出决定，而不在其他解上花费更多的功夫。也正是由于这个原因，许多解之间的关系(例如，解之间的占优关系)是不必要的知道，因此这些关系可以去除。在图1（b）这个示例中，

14、很明显N1和N4构成Pareto最优解集。我们可以观察N4占优N3，N1占优N2。因此，我们并不对N2和N3之间的关系感兴趣并且这可能不值得花费时间来比较或推断它们。通过以上分析，我们能找到两个原则来减少不必要的计算时间： （1）避免冗余比较（例如依靠推理来推断这些关系）；（2）只保留必要的关系（即，忽略那些不是非常重要的关系）正如我们提到的，不同于SOPs的解之间的关系，MOPs的解有三值关系。它可以归纳成一个叫做的函数。定义3：的函数这个函数是一个三值函数。当的目标向量占优的目标向量，；当的目标向量占优的目标向量；当、互不占优时，。我们知道，对于排列标量数的二值关系来说，二进制排列树（BS

15、T）是一个非常有效的工具。在二进制排列树中，一个节点的左子树所连接的节点其值小于它本身，一个节点的右子树所连接的节点其值大于它本身。我们考虑多目标优化的三值的关系也可以被存储在一个扩展的二叉树中。接下来是作者早期在Ref工作时提出来的关于结构树的思想，为此目的，我们设计了一个特殊的二叉树。图2中的一个例子表明图1中节点之间的关系。在图中，Pareto最优解集是N1、N4，主要的关系被保留，许多不重要的关系（例如，被支配节点之间的关系）被忽略。作为一个新型的二叉树，我们称之为支配树。定义4：支配树(DT)。一个支配树是一种二叉树，定义如下。1)一个支配树一个外部节点或者一个内部节点，其连接到被称为左子树节点和右子树节点的一对支配树上。2)每个节点在支配树有中四个域：id、计数器、左连接和右连接。其中，个体节点代表id域表示所代表的哪个个体节点，计数器域表示左子树的大小（包括它自己），左连接域连接到其左子树，该节点占优它的左子树的根节点，右连接域连接到它的右子树，该节点不占优它的右子树的根节点。DT的定义与BST的定义相似，DT和BST也拥有近似的性能。例如，在DT和BST中，一个节点的子代是它左子树的根节点；相应地，这个节点是父代节点。DT也还有一些不同的特点。一个新术语“同级链”在D