1、附录 4 附录 4 一种基于树结构的快速多目标遗传算法 介绍： 一般来讲，解决多目标的科学和工程问题，是一个非常困难的任务。在这些多目标优化问题 (MOPS)中，这些目标往往在一个高维的问题空间发生冲突，而且多目标优化也需要更多的计算资源。一些经典的优化方法表明将多目标优化转化成为单目标优化问题，其中许多运行被要求找到多个解决方案。这使得一种算法返回一组候选解，这比只返回一个基于目标的权重解的算法更好。由于这个原因，在过去 20 年中，人们越来越感兴趣把进化算法(EAs)应用到多目标优化中。 许多多目标进化算法 (MOEAs)已经被提出，这些多目标进化算法使用Pareto 占优的概念来引导搜索
2、，并返回一组非支配解作为结果。与在单目标优化中找到最优解作为最终的解不同，在多目标优化中有二个目标：（ 1）收敛到 Pareto 最优解集（ 2）在 Pareto 最优解集中保持解的多样性。为了解决在多目标优化中这两个有时候会冲突的任务，许多策略和方法被提出。这些方法的一个共同的问题是，它们往往是错综复杂的。对于这两项任务，为了得到更优秀的解，一些复杂的策略通常被使用，并且许多参数需要依据经验和已经得到的问题信息进行调整。另外，许多多目标进化算法有高达 2GMNO 的计算复杂度或者需要更多的处理时间（ G 是代数， M 是目标函数的数量， N 是种群大小。这些符号在下文也保持相同的含义）。 在
3、这篇文章中，我们提出了一种基于树结构的快速多目标遗传算法。 (这个数据结构是一个二进制树，它保存了在多目标优化中解的三值支配关系（ 例如，正在支配、被支配和非支配 ） ，因此，我们命名它为支配树 (DT)。由于一些独特的性能，使支配树能够含蓄地包含种群个体的密度信息，并且很明显地减少了种群个体之间的比较。计算复杂度实验也表明，支配树是一种处理种群有效的工具。 基于支配树的进化算法 (DTEA)统一了在支配树中的收敛性和多样性策略，即多目标进化算法中的两个目标，并且由于只有几个参数，这种算法很容易操作。另外，基于支配树的进化算法 (DTEA)使用附录 4 了一种特别设计的基于支配树 (DT)的消
4、除策略。这种策略不仅维护自然种群的多样性，但也意识到精英主义没有额外的消耗。六个基准测试函数和三个著名的 MOEAs（ 如 NSGA-II， SPEA2，和 Jensen 的改进版本的 NSGA-II）被用来检验 DTEA 算法的效率和效果。程序运行时间实验表明， DTEA 算法总是远远快于基准算法，尤其是在人 口规模很大的时候。另一方面，通过检测三个评价解质量的标准，我们发现，整体上对于收敛到真正 Pareto 最优前沿和维护种群多样性来讲， DTEA 算法的解决方案质量并不比 NSGA-II 和SPEA2 差，但是 DTEA 算法的计算所时间要短得多。本文的其余部分安排如下。论文第二节简要
5、回顾了先进的 MOEAs，第三节详细描述 DTEA，第四部分给出并讨论了实验结果，最后，第五节总结本文。 概述 MOEAs 本节简要调查当代 MOEA 研究。第一部分将给出在本文中使用的一些概念。第二部分将简要分析当前最先进的多目标进化算法。 2.1 在多 目标优化中的定义 许多研究人员都给出了类似的定义。我们在这介绍两个重要概念的定义。为了不是一般性，我们在本文中只考虑最小化问题，它很容易将一个最大化问题转换成一个最小化问题。 定义 1：一般的多目标优化：一般来说，最小化一组多目标优化函数)() , . . ,()( 1 xfxfxF m ，约束函数 xkixg i , . .1,0 （ 是
6、决策变量空间）一个多目标优化的解可以使 m 维的目标向量 )(xF 的一部分达到最小，其中 nxxx .,1是空间 的 n 维决策变量向量。 定义 2： Pareto 占优：一个向量 muuu ,.,1 是占优向量 mvvv ,.,1 （记作 vu ），当且仅当 u 部分小于 v ，即 mi ,.,1 ii vu ，并且 mi ,.,1ii vu 。 当前，大多数多目标优化的研究都是基于 Pareto 占优。（在一些文献中，Pareto 占优也被定义为严格的 ，这里我们并不讨论他们的区别。）一个决策变量向量 x 被称作 Pareto 最优解，当且仅当不存在 y ，使得 yFxF 。所有 Pareto 最优决策向量被称为 Pareto 最优解集。相应的目标向量解集被称作非支配集，或者 Pateto 前沿。根据 Pareto 占优的定义，我们可以发现在 MOPs 和 SOPs 的解之间的关系中一个截然不同的差异。 SOPs
