英语原文共 17 页，剩余内容已隐藏，支付完成后下载完整资料

利用精英保留策略和拥挤熵多样性方法的多目标自适应差分进化算法研究

Yao-nan Wang,Liang-Hong Wu,Xiao-Fang Yuan

摘要：现今已提出一种包含了Pareto支配性的自适应差分进化算法来解决多目标优化问题。这种方法采用了外部精英保留策略以保留在进化过程中的非支配解集。为保留Pareto最优解的多样性引入了拥挤熵策略。该策略能够更准确地衡量解的拥挤度，然后用十八个标准测试函数来进行实验。实验结果表明，本文所提出的MOSADE方法和其他三个多目标最优进化算法相比得到的最优边界具有更好的均匀性和收敛性，保留了Pareto最优解集的多样性。

关键字：多目标进化；差分进化；精英保留；拥挤熵

1 引言

有两个或多个目标的最优化问题被称为多目标优化问题。多目标优化问题在工程和其他领域中很普遍。这种问题非常难解决，因为各目标之间相互制约。通常，多目标优化问题的解不是单一解，而是一组解的集合（更常被称为Pareto最优解集）。运用传统方法找Pareto最优解集时需要运行很多次，希望在每次运行时找到不同的解决方案（Coello 2006）。

在过去十年中，多目标进化算法的研究倍受瞩目，期间相继提出了许多多目标进化算法（Coello 2006;Schaffer 1985; Fonseca and Fleming 1995, 1998; Van Veldhuizen and Lamont 1998; Zitzler and Thiele 1999;Zitzle等2000, 2001; Knowles and Corne 2000; Ray等2001; Deb等2002; Coello等2004; Nebro等2007）。最主要的原因是这些算法是基于种群的，且这些算法具有可以在单次运行中找到Pareto最优解集的能力。此外，进化算法不易受Pareto最优边界的形状和连续性的影响，可以轻易解决不连续或凹形的Pareto最优边界（Coello 2006; Van Veldhuizen and Lamont 1998; Zitzler等2000。）

Rainer Storn和Kenneth Prince于1995年提出的差分进化（DE）算法（Storn and Price 1997）是最流行的进化算法之一。DE原理易懂、规则精简，却展示了很强的优化能力，成功地应用于许多单目标优化问题中（Price 1997）。最近，人们尝试将DE拓展应用到多目标问题中。Abass等人（2001）介绍了一种结合了Pareto优势的Pareto最优边界差分进化算法（PDE）用于解决多目标优化问题。PDE同时拓展了自适应、交叉、变异操作。Madavan（2002）发展了DE，结合了NSGA-II的非劣排序和等级选择过程来解决多目标优化问题。Babu（2003）结合罚函数和权值系数法，发展了进化算法来求解多目标优化问题。Xue（2003）研究基于Pareto进化的差分算法以解决于多目标决策问题，且已应用于双目标的企业计划问题上。Parsopoulos等（2004）受VEGA（Schaffer 1985）的启发，针对多目标优化问题提出了一种并行多种群差分进化算法。Iorio和Li（2004）运用DE解决螺旋多目标优化问题。它对NSGA-II进行了简单修正，将变异、交叉算子替换成了DE体系的算子。 Kukkonen和Lampinen（2004）提出了一种广义差分进化算法（GDE），该算法拓展了基本差分进化算法的选择算子，得以能够处理约束多目标优化问题。另外，在GDE基础上的优化版本GDE3也由（Kukkonen和Lampinen 2005）提出。GDE3是对DE算法在目标和约束数量上全局优化的延伸。Robicˇ和Filipicˇ，以及T. Robicˇ等人（2005）提出了一种多目标差分进化算法（DEMO），这是一种基于DE算法的新方法。DEMO结合了DE算法的许多优点，如基于Pareto 的等级机制、拥挤距离排序，并使用了最先进的多目标进化算法。针对差分进化和粗糙集的多目标优化理论被Alfredo于2006年提出。该方法采用了外部存档的方法保留非支配解集，包含了ɛ支配的概念以得到一个分布均匀的解集。J.Zhang等人在Zhang和Sanderson的论文中介绍了一种自适应多目标差分进化算法，其趋势由已存档的劣解来提供。和目前的MOEA算法中所用的存储当前最优非支配解的档案不同，该方法用一个外部档案保留最近找到的劣解，这些劣解与当前种群的不同表明了Pareto最优边界的方向。

本文采用了外部精英档案策略，拓展了求解多目标优化问题的差分进化算法。为了保留最优解的多样性，将采用拥挤熵这种更精确的方法。原始进化算法的性能依赖于控制参数的设置，并且可能需要大量运算时间找到某一问题的最合适的参数。因此，本文介绍了一种可以在进化中自动调整参数的自适应差分进化算法，该求解多目标优化问题的算法叫做MOSADE。

本文剩余部分结构如下。章节2介绍了多目标优化问题的基本概念。章节3详述了自适应差分进化算法。章节4介绍了精英保留策略和拥挤熵策略。章节5 详细介绍了利用精英保留策略和拥挤熵多样化的多目标自适应差分进化算法。章节6 展示了用十八个标准测试函数进行测试的实验。最后的章节7进行了总结。

2 多目标优化问题的基本概念

　　多目标优化问题的数学描述为：

(1)

s.t. (2)

(3)

(4)

其中是待最优化的目标向量，是目标函数的个数。是不等式约束条件，是等式约束条件。和分别是不等式约束条件和等式约束条件的个数。我们将叫做决策空间向量，为可行域。多目标优化问题就是寻求特定一组，满足约束条件（2），（3）的同时使目标函数达到最优。

定义1（强支配 strong dominance）若，则称向量强支配（记为）。

定义2（支配 dominance）当且仅当，则称向量支配（记为）。

定义3（弱支配 weak dominance）若，则称向量弱支配（记为）。

定义4（Pareto最优解 Pareto optimal solution）当不存在满足 时，称点为最优解。

定义5（Pareto最优集 Pareto optimal set）对于给定的MOP，其对应最优解集（）定义为。

定义6（Pareto最优边界 Pareto front）对于给定的MOP和Pareto最优解集，Pareto最优边界定义为。

通常情况下，很难找到包含了这些线或者曲面的最优解点的解析表达式（Coello等人 2004）。而生成Pareto最优边界的通常方法是计算可行点和对应。

3 自适应差分进化算法

差分进化（DE）算法是一种简单却强大的基于种群随机查找解决全局优化的技术（Price 1997;Vesterstrom and Thomsen 2004）。下面简要介绍这个经典的差分进化算法。

3.1 基本的差分进化

设为问题的搜索空间。差分进化算法将种群大小为的n维空间向量作为算法每代的种群。为约束条件数目，代表某一代。初始种群是随机生成的且应当覆盖整个空间。将变异和交叉这两个控制参数作用于每代种群中的每个个体，可得到目标向量对应的决策向量。然后对决策向量进行筛选，决定其是否进入下一代种群中。

对于DE有若干种变异（Storn and Price 1997）。变形的方案有多种，这里采用了DE/rand/1/bin策略的方案。采用这种方案有两个原因：（1）在实践中最常采用这种方案（Price 1997; Vesterstrom和Thomsen 2004）；（2）没有必要选出每一代最好的个体，实际上，在多目标问题中很难决定哪个是最好的，因为最优解往往是一组解而不是一个。

根据DE/rand/1/bin的变异算子，每个独立目标，其变异向量产生如下：

（8）

其中实参变异常数；控制偏差变量具有放大作用，可以避免搜寻停止。Storn和Price（Storn 和Price 1997）指出，取值(0，2]。为随机从选择的序号，且互不相同，同时应当与目标向量序号不同，所以须满足。

除了进行变异操作，种群也进行交叉操作。对于每个变异向量，其对应实验向量产生公式如下：

（9）

产生第个[0,1]之间随机数，其中。为交叉算子，取值范围为[0,1]，由用户事先决定。是一个随机序列数，用它来确保至少从获得一个参数。不然，不产生新个体，种群不能进化。

要决定实验向量是否进入下一代，DE按照贪婪准则将实验向量与当前种群中的目标向量进行比较。选择的方程为

（10）

3.2 参数自适应策略

　　基本DE的参数控制在进化过程中一直在修正，而这些参数极大地决定了所获解的质量和查询的效率。通常，合适的参数值需要依据具体问题来选择，并且会用到用户的经验（Zhang和Sanderson 2008; Vesterstrom和Thomsen 2004; Nobakhti和Wang 2006; Qin和Suganthan 2005; Brest等人2006）。DE对于控制参数的敏感性体现在两个方面。其一，很多研究已表明，收敛概率和收敛速度极大程度上取决于参数和。其二，由于DE特殊的变异机制，如果出于某些原因（和CR选择不当）DE种群失去了多样性，搜索会完全终止，变异趋于零。这两个原因突出强调了拥有自适应DE的优势。一些DE的自适应算法在许多文献中（Zhan和Sanderson 2008; Vesterstrom和Thomsen 2004; Nobakhti和Wang 2006; Qin和Suganthan 2005; Brest等人 2006）提出。本文提出了一种新的控制DE参数自适应的策略。

在基本DE中，种群中的全部个体共享控制参数和，且参数在进化过程中是固定的。本实验将给每个个体分配控制参数，每个个体有其各自的和。这些变量各不相同。

这些变量值在值域内随机取值。在种群进化过程中，如果一个个体连续在代（本文中用5代）没有生成一个更优的实验向量（子向量），说明当前的控制参数不合适，应当适应性地更换。在每连续的代中，如果一个个体产生了一个或多个更优的后代，那么该个体当前的控制参数是合适的，应当保留给后代。新的控制参数和更新方法为：

（11）

（12）

其中和都是均匀分布在[0，1]的随机值。和分别 为变异常数的下限和上限。和分别是交叉概率常数的下限和上限。在我们的实验中，，，，。所以新的和分别在[0.1，0.9]和[0，0.5]中随机取值。新生成的和在变异前更新，并且影响着变异、交叉和子代的选择。

自适应控制参数和的生成规则很简单，且和基本DE算法相比时间复杂度并没有增加。但是采用这种算法后，DE的稳健性极大地提升了，并且用户也不用去猜测因具体问题而不同的和的最佳值。

4 精英保留和多样性保护

4.1 外部精英保留

自从1999年Eckart Zitzler正式地介绍了基于精英保留机制的Pareto进化算法(Zitzler和Thiele 1999)之后，许多研究人员在实验中采用了相似的精英保留概念。这种机制产生的最主要的原因是：当前种群的一个非支配解未必是演化算法产生的所有种群的非支配解。因此，我们需要找到一种方法，保证使得我们反馈给用户的解不能够被算法生成的每一个个体支配（Coello 2006）。所以，最直观的解决方法是将找到的所有非支配解在一个档案中存储起来。相反地，如果一个解能支配所有档案中记录的解，被支配的解应当都删除。

本文同样采用了精英保留策略。在进化过程中用一个外部档案来存储当前找到的Pareto最优解。随着进化的进行，每一代没有被相应目标向量支配的实验向量一个个与当前档案比较，较好的解就存入档案。当非支配实验个体与当前档案相比有三种情况：（1）当实验个体被档案中的一个（几个）个体支配时，实验个体不能加入

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[29650]，资料为PDF文档或Word文档，PDF文档可免费转换为Word