下载文档原格式
多目标差分进化算法
多目标差分进化算法（Multi-Objective Differential Evolution，MODE）是一种用于解决多目标优化问题的进化算法。
与单目标差分进化算法类似，MODE也是一种基于群体的全局优化方法，它可以在不使用任何显式约束的情况下解决复杂的多目标问题。
MODE是由Kalyanmoy Deb和Amrit Pratap等人于2002年提出的。
这种方法通过维护一组个体来进行多目标优化，并使用不同的权重向量（或目标向量）来评估每个个体的适应度。
在MODE中，每个权重向量都被视为一个目标问题的不同实例，个体的适应度被定义为它们在所有目标问题中的表现。
采用差分进化算法的操作方式，MODE在每一代中对群体进行进化。
具体来说，对于每个个体，MODE将选择三个不同的个体作为参考点（也称为候选个体）。
然后，通过与参考个体进行差分操作，生成一个试探个体。
试探个体的适应度被评估，并与当前个体进行比较。
如果试探个体的适应度更优，则将其保留到下一代中，并用其替换当前个体。
在MODE中，采用了一种精英策略来维护较好的解。
具体来说，在每一代中，由于同一权重向量的多个个体可能收敛到同一解决方案，MODE将更新每一个权重向量中最优的个体，并将其保留到下一代中。
因此，这种策略可以确保每个权重向量都有一个最优解，进而使模型达到更好的全局优化效果。
总之，多目标差分进化算法是一种有效的全局优化方法，能够高效地解决多目标优化问题。
在实践中，MODE已被广泛应用于各种领域中，如机器学习、工程设计、经济学和环境管理等。
多目标多约束优化问题算法多目标多约束优化问题是一类复杂的问题，需要使用特殊设计的算法来解决。
以下是一些常用于解决这类问题的算法：1. 多目标遗传算法（Multi-Objective Genetic Algorithm, MOGA）：-原理：使用遗传算法的思想，通过进化的方式寻找最优解。
针对多目标问题，采用Pareto 前沿的概念来评价解的优劣。
-特点：能够同时优化多个目标函数，通过维护一组非支配解来表示可能的最优解。
2. 多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization, MOPSO）：-原理：基于群体智能的思想，通过模拟鸟群或鱼群的行为，粒子在解空间中搜索最优解。
-特点：能够在解空间中较好地探索多个目标函数的Pareto 前沿。
3. 多目标差分进化算法（Multi-Objective Differential Evolution, MODE）：-原理：差分进化算法的变种，通过引入差分向量来生成新的解，并利用Pareto 前沿来指导搜索过程。
-特点：对于高维、非线性、非凸优化问题有较好的性能。
4. 多目标蚁群算法（Multi-Objective Ant Colony Optimization, MOACO）：-原理：基于蚁群算法，模拟蚂蚁在搜索食物时的行为，通过信息素的传递来实现全局搜索和局部搜索。
-特点：在处理多目标问题时，采用Pareto 前沿来评估解的质量。
5. 多目标模拟退火算法（Multi-Objective Simulated Annealing, MOSA）：-原理：模拟退火算法的变种，通过模拟金属退火的过程，在解空间中逐渐减小温度来搜索最优解。
-特点：能够在搜索过程中以一定的概率接受比当前解更差的解，避免陷入局部最优解。
这些算法在解决多目标多约束优化问题时具有一定的优势，但选择合适的算法还取决于具体问题的性质和约束条件。
基于多策略融合和约束处理技术的差分进化算法
宋尔萍
【期刊名称】《微电子学与计算机》
【年(卷),期】2024(41)6
【摘要】当约束优化问题的目标函数结构比较复杂,约束条件较为严格时,差分进化算法(Differential Evolution,DE)的收敛性能表现较差。
为发挥基于群智能搜索算法的优势,本文提出了一个基于等级划分、状态转移和不可行解处理的多策略融合差分进化算法(Multi-Strategy fusion Differential Evolution,MSDE)。
首先,根据目标函数值和约束违反度值对父代群体进行等级划分,并根据等级特征将子群体划分为3个层次;然后,利用不同等级和层次的特征设计有效的进化操作,提高差分进化算法的勘探和挖掘能力;进一步,根据不可行解的分布特征将群体进行状态转移,使转移后的个体在决策空间具有较好的分布;接着,利用转移后个体的分布特征设计了约束处理技术,提高个体向可行域收敛的概率,使不可行解以较高的概率转移到可行域中;最后,与4个最新的进化算法做了仿真实验,结果表明,本文提出的相关策略改进了DE算法的性能。
【总页数】8页(P20-27)
【作者】宋尔萍
【作者单位】青海大学数理学院
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.结合机械设计约束处理的差分进化算法
2.混合多约束处理技术的并行约束差分进化算法
3.基于混合差分进化和alpha约束支配处理的多目标优化算法
4.结合机械设计约束处理的差分进化算法
5.基于多策略自适应差分进化算法的污水处理过程多目标优化控制
因版权原因，仅展示原文概要，查看原文内容请购买。
基于差分进化算法的自动化约束优化问题在当今科技飞速发展的时代，自动化技术在各个领域的应用日益广泛，而其中的约束优化问题更是备受关注。
约束优化问题是指在满足一系列约束条件的前提下，寻找最优的解决方案。
这些约束条件可能涉及资源限制、技术要求、法律法规等多个方面，使得问题的求解变得复杂而具有挑战性。
差分进化算法作为一种强大的优化算法，为解决自动化约束优化问题提供了有效的途径。
那么，什么是差分进化算法呢？简单来说，它是一种基于群体的随机搜索算法，通过模拟生物进化过程中的变异、交叉和选择操作，来不断优化解的质量。
与传统的优化算法相比，差分进化算法具有许多独特的优势。
首先，它对问题的初始解不敏感，这意味着即使初始解的质量较差，算法也能够通过不断的迭代逐步找到更好的解。
其次，差分进化算法具有较强的全局搜索能力，能够避免陷入局部最优解，从而提高获得最优解的可能性。
此外，它的参数设置相对简单，易于实现和应用。
在自动化约束优化问题中，我们常常面临各种各样的约束条件。
例如，在生产制造领域，可能需要在有限的时间、材料和人力等资源约束下，最大化生产效率或产品质量；在物流配送中，需要在满足车辆载重、行驶时间和路线限制等条件下，最小化运输成本；在工程设计中，要在满足结构强度、尺寸限制和性能要求等约束的同时，优化设计方案的成本和性能。
为了有效地应用差分进化算法解决这些约束优化问题，我们需要对算法进行适当的改进和调整。
一种常见的方法是引入惩罚函数，将约束违反的情况转化为目标函数的惩罚项。
这样，在算法的迭代过程中，违反约束的解会受到相应的惩罚，从而引导搜索朝着满足约束的方向进行。
另一种方法是采用约束处理技术，如可行性规则和修复策略。
可行性规则通过判断解是否满足约束条件，只允许可行解参与后续的进化操作。
而修复策略则是对不可行解进行修正，使其满足约束条件。
除了上述方法，还可以结合其他优化算法或技术，形成混合算法，以提高求解自动化约束优化问题的性能。
差分进化算法介绍1．差分进化算法背景差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。
差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。
近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。
差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。
它的全局寻优能力和易于实施使其在诸多应用中取得成功。
2.差分进化算法简介差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。
DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。
与进化策略(Es)采用Gauss或Cauchy 分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE 的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。
3.差分进化算法适用情况差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。
它可以对非线性不可微连续空间的函数进行最小化。
目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。
4.基本DE算法差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。
面向多目标优化的进化算法和遗传算法研究随着科技的不断进步，人们在工业、农业、商业等领域中对高效优化问题的需求越来越大。
多目标优化问题是其中的一类重要问题。
与单目标问题相比，多目标问题涉及到多个目标函数，这些目标函数之间相互影响，难以直接比较。
多目标优化问题的解决方案被认为是最优的，当它们满足所有目标函数时。
面向多目标优化问题，进化算法和遗传算法是两种有效的优化方法，其优点在于具有较好的全局搜索能力，并且适用于各种类型的问题。
本文将介绍进化算法和遗传算法在面对多目标优化问题时的研究。
一、进化算法在多目标优化问题中的应用进化算法是一种基于自然选择和适应性等有生命的生物体生存策略和规律的计算思想的一类优化算法。
它与传统的优化算法相比不需要对问题进行数学建模，同时还能够处理问题的不确定性和复杂性。
因此，进化算法是一种十分灵活的方法，其在多目标优化问题中表现良好。
（一）多目标进化算法多目标进化算法（Multi-Objective Evolutionary Algorithm, MOEA）是一类专门解决多目标优化问题的进化算法。
在MOEA中，每个个体都包含多个特征向量，每个向量表示该个体在不同目标下的得分。
同时，MOEA中也包含算法来处理收敛和多样性的问题。
在MOEA中，多样性和收敛性是非常重要的，因为这些因素会影响到解的质量和搜索速度。
（二）基于多目标进化算法的Pareto最优解Pareto最优解是指在多目标优化问题中，不能再优化一个目标的解集合。
这是一种非常常用的解决多目标优化问题的方法。
Pareto最优方法通过建立较小集合的非劣解来推动优化过程。
每个单独的非劣解都应该优于所有其他不可行解的任何一个水平。
因此，优化问题的解就变成找到Pareto最优解集。
这个问题可以通过多目标进化算法来解决。
（三）多目标粒子群优化算法多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization, MOPSO）是一种基于粒子群优化算法的多目标优化算法。
差分进化算法约束条件
差分进化算法（Differential Evolution, DE）是一种常用的
全局优化算法，通常用于解决连续优化问题。
在应用差分进化算法时，我们经常会遇到约束条件，也就是问题的解需要满足一定的限
制条件。
这些约束条件可能包括等式约束、不等式约束或者其他形
式的约束。
在差分进化算法中处理约束条件的方法有很多种，下面我将从
不同角度来解释：
1. 罚函数法，一种常见的处理约束条件的方法是使用罚函数法。
在罚函数法中，对于违反约束条件的解，通过增加一个罚项来惩罚
这些解，使得在优化过程中不满足约束条件的解变得不利于优化。
这样可以在一定程度上保证优化的解满足约束条件。
2. 转换方法，另一种常见的处理约束条件的方法是通过一定的
变换将约束优化问题转换为无约束优化问题。
这种方法包括线性变换、非线性变换等，通过变换使得原始的约束优化问题转化为一个
无约束优化问题，然后再利用差分进化算法进行求解。
3. 修复法，修复法是指在每一代种群中，对不满足约束条件的
个体进行修复，使其满足约束条件。
这种方法的优点是可以保证每
一代种群中的解都满足约束条件，但缺点是可能会增加计算的复杂度。
4. 多目标优化，有时候约束条件可以被看作是另一个优化目标，可以将约束条件转化为多目标优化问题进行求解。
总的来说，处理约束条件是差分进化算法在实际应用中需要考
虑的一个重要问题，不同的方法适用于不同的情况。
在应用差分进
化算法时，需要根据具体的问题特点选择合适的处理约束条件的方法，以求得较好的优化效果。
进化算法优化多目标优化问题进化算法（Evolutionary Algorithm, EA）是一种基于群体智能的搜索算法，用于解决优化问题。
这种算法模仿自然界的进化、选择和适应性机制，在搜索空间中寻找最优解。
进化算法具有广泛的应用，尤其在多目标优化领域有较好的表现。
本文将介绍进化算法在多目标优化问题中的应用及其优化策略。
一、多目标优化问题多目标优化问题（Multi-Objective Optimization, MOO）指在某一约束条件下最小化或最大化多个指标。
例如，设计一辆汽车时需要考虑速度、安全性、燃油效率、驾驶舒适性等多个因素，这些因素之间通常存在相互制约，需要在多个目标之间取得平衡和权衡。
多目标优化问题具有以下特点：1. 目标多样性。
多目标问题中可能存在不同种类的目标，如最大化效益和最小化成本。
2. 可行性约束。
不同目标之间通常存在冲突，需要在满足一定的限制条件下达成平衡。
3. 操作复杂性。
多目标问题通常包含多个变量参数，需要重复进行计算和优化，存在计算复杂度高和时间成本大的问题。
二、基本的进化算法进化算法的基本流程如下：1. 初始化种群。
根据问题的约束条件和初始值随机生成初始种群。
2. 评估适应度。
使用选择标准对种群个体进行评估，并确定优秀个体参与进化。
3. 进化操作。
通过交叉、变异等操作对优秀个体进行复制和变异，产生新个体并加入到种群中。
4. 判断终止条件。
根据预设的终止条件，判断是否需要结束进化。
5. 返回最优解。
找到最优解并返回。
三、进化算法优化多目标优化问题1. Pareto最优解在单目标优化问题中，最优解仅有一个，但在多目标问题中，最优解通常是由多个非支配解（Pareto Optimal Solution）组成的Pareto 最优解集合。
Pareto 最优解集合是指在约束条件下不可能找到更好解，同时不存在一种目标函数能优化所有目标的方案。
Pareto 最优解的求解过程也被称为 Pareto 最优化（Pareto Optimization）。
多目标优化的方法多目标优化是指在优化问题中存在多个相互独立的目标函数，而不是单一的目标函数。
由于不同的目标函数往往是相互冲突的，使得同时最小化或最大化多个目标函数是一个具有挑战性的问题。
在多目标优化中，我们追求的是找到一组解，这组解对于每个目标函数来说都是最优的，而这个解称为Pareto最优解。
在多目标优化中，使用传统的单目标优化方法是不适用的，因为它只能找到单个最优解。
因此，为了解决多目标优化问题，研究人员提出了许多有效的方法。
下面将介绍几种常见的多目标优化方法。
1. 加权求和法（Weighted Sum Method）加权求和法是最简单直观的一种方法。
它把多目标优化问题转化为单目标优化问题，通过给每个目标函数赋予不同的权重，将多个目标函数线性组合成一个单目标函数。
然后使用传统的单目标优化方法求解得到最优解。
这种方法的缺点是需要人工赋权，不同的权重分配可能得到不同的结果，且不能找到Pareto最优解。
2. 约束法（Constraint Method）约束法是通过约束目标函数的方式来解决多目标优化问题。
它将目标函数之间的关系转化为约束条件，并追求找到满足所有约束条件的最优解。
这种方法需要事先给出目标函数之间的约束条件，且难以找到满足所有约束条件的最优解。
3. 基于Evolutionary Algorithm的方法最常用的多目标优化方法是基于Evolutionary Algorithm（进化算法）的方法，如遗传算法（Genetic Algorithm, GA）和粒子群算法（Particle Swarm Optimization, PSO）。
这些算法通过模拟生物进化过程，使用种群的思想来搜索最优解。
它们通过不断演化改进解的质量，迭代地更新解的位置以逼近Pareto 最优解。
这些方法优势明显，能够找到Pareto最优解，但计算复杂度较高。
4. 多目标优化算法的性能评估方法为了评估多目标优化算法的性能，研究人员提出了一些评价指标。
基于双向协同进化的约束多目标优化问题研究在现代社会，咱们面临的事情可真是五花八门，尤其是在解决复杂问题时，尤其是那些优化问题，听着就让人觉得有点头疼。
但是别担心，今天我们要聊的就是一个有趣的话题——基于双向协同进化的约束多目标优化问题。
哎，这听起来有点高深，不过别害怕，咱们慢慢来，聊聊天，放松一下。
咱们得明白什么是多目标优化。
简单来说，就是当我们面对多个目标时，如何在这些目标之间找到一个平衡点。
想象一下，你在逛超市，既想买到便宜又想买到好东西，但这两者有时候就像水火不容，怎么也平衡不好。
这就是多目标优化的核心问题。
而约束条件就像那不成文的规则，让你不能随心所欲，得在这些规则里跳舞。
说白了，就是“有些事情可以做，有些事情却不行”，就像考试时只能选几个题目，想全选可没那么简单。
双向协同进化又是个啥呢？想象一下两个小伙伴一起合作，互相帮助，各自进步。
一个在前面引路，另一个在后面紧追，这样他们就能在不断的互动中一起变得更强。
在优化问题中，咱们也可以通过这种方式，运用不同的策略和方法，让算法之间互相学习，从而找到更好的解决方案。
就像打游戏一样，跟队友好好配合，总能战胜更强的敌人。
我们得说说这个研究到底有什么用。
应用范围广泛，简直无处不在。
比如，在工程设计中，设计师得在成本、性能和安全之间做出权衡，听着就觉得复杂，但有了双向协同进化，这些问题就能迎刃而解。
再比如，交通管理，想要让道路畅通无阻，得考虑车流量、环保、和成本等多个因素，这时候也是双向协同进化的好用武之地。
很多朋友可能会问，双向协同进化的具体做法是什么呢？其实就像做菜，得有材料、有火候。
第一步就是选定目标，然后设定一些约束条件，像是个指南针，让我们不会迷路。
采用不同的优化算法，让它们进行“对话”，互相学习。
这个过程就像朋友之间的相互鼓励，经过不断的调整和尝试，最终找出最优解，哇，听起来真是让人振奋。
不过，研究并不是一帆风顺，遇到的挑战也不少。
比如说，算法的复杂性，很多时候就像解谜游戏，越往后越难。
用于约束多目标优化问题的双群体差分进化算法孟红云1张小华2 刘三阳1(1.西安电子科技大学 应用数学系，西安，710071； 2.西安电子科技大学 智能信息处理研究所，西安，710071)摘 要：首先给出一种改进的差分进化算法，然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA 的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA 相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字： 差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP181 引言达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展，用进化算法求解优化问题已成为一个研究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结为求解一个带有约束条件的函数优化问题，因此研究基于进化算法求解约束优化问题是非常有必要的．不失一般性，以最小化问题为例，约束优化问题（Constrained Optimization Problem ，COP ）可定义如下：)(COP ()()()()qj x h pi x g t s x f x f x f x F j i k Rx n,,1,0)( ,,1,0)( ..,,,)(min 21ΛΛΛ===≤=∈ （1）其中)(x F 为目标函数，)(),(x h x g j i 称为约束条件，nn R x x x x ∈=),,,(21Λ称为n 维决策向量．将满足所有约束条件的解空间S 称为(1)的可行域．特别的，当1=k 时，(1)为单目标优化问题；当1>k 时，（1）为多目标优化问题．)(x g i 为第i 个不等式约束，)(x h j 是第j 个等式约束．另一方面，对于等式约束0)(=x h j 可通过容许误差（也称容忍度）0>δ将它转化为两个不等式约束：⎪⎩⎪⎨⎧≤--≤-0)(0)(δδx h x h jj （2） 故在以后讨论问题时，仅考虑带不等式约束的优化问题．进一步，如果x 使得不等式约束0)(=x g i ，则称约束()x g i 在x 处是积极的．在搜索空间S 中，满足约束条件的决策变量x 称为可行解，否则称为不可行解．定义1（全局最优解）()**2*1*,,,n x x x x Λ=是COP 的全局最优解，是指S x ∈*且)(*x F 不劣于可行域内任意解y 所对应的目标函数)(y F ，表示为)( )(*y F x F π． 对于单目标优化问题，)( )(*y F x F π等价为)()(*y F x F ≤，而对于多目标优化问题是指不存在y ，使得)(y F Pareto 优于)(*x F ．目前，进化算法用于无约束优化问题的文献居多，与之比较，对约束优化问题的研究相对较少[4-6]。
文[7]对当前基于进化算法的各种约束处理方法进行了较为详细的综述.对于约束优化问题的约束处理方法基本上分为两类：基于罚函数的约束处理技术和基于多目标优化技术的约束处理技术．由于罚函数法在使用中不需要约束函数和目标函数的解析性质，因此经常被应用于约束优化问题，但该类方法对罚因子有很强的依赖性，需要根据具体问题平衡罚函数与目标函数．为了避免复杂罚函数的构造，Verdegay 等[8]将进化算法中的竞争选择用于约束处理，并在比较两个解的性能时提出了三个准则,但他的第三个准则—可行解优于不可行解—这一准则合理性不强 .然而该文的这一准则却为进化算法求解约束优化问题提供了新思路，获得了良好效果.因为在现实中存在一大类约束优化问题，其最优解位于约束边界上或附近，对于这类问题，在最优解附近的不可行解的适应值很可能优于位于可行域内部的大部分可行解的适应值，因此无论从适应值本身还是从最优解的相对位置考虑，这样的不可行解对找到最优解都是很有帮助的，故如何有效利用搜索过程中的部分具有较好性质的不可行解是解决此类问题的难点之一．基于以上考虑，本文拟给出一种求解约束多目标优化问题的基于双群体机制的差分进化算法，并对文中算法的时间复杂度与NSGA-Ⅱ[9]和SPEA [10]进行比较，最后用实验仿真说明文中算法的可行性及有效性．2 用于约束优化的双群体差分进化算法差分进化算法差分进化算法是一类简单而有效的进化算法，已被成功应用于求解无约束单目标和多目标优化问题 [11-14]．该算法在整个运行过程中保持群体的规模不变，它也有类似于遗传算法的变异、交叉和选择等操作，其中变异操作定义如下：()321r r r P P F P C -⋅+= (3)其中1r P ,32,r r P P 为从进化群体中随机选取的互不相同的三个个体，F 为位于区间]1,5.0[中的参数．(3)式表示从种群中随机取出的两个个体32,r r P P 的差，经参数F 放大或缩小后被加到第三个个体1r P 上，以构成新的个体()n c c C ,,1Λ=．为了增加群体的多样性，交叉操作被引入差分进化算法，具体操作如下：针对父代个体),,(1n r x x P Λ=的每一分量i x ，产生位于区间]1,0[中的随机数i p ，根据i p 与参数CR 的大小关系确定是否用i c 替换i x ，以得到新的个体),,(1n r x x P ''='Λ， 其中 ,, ⎩⎨⎧='i i i x c x if if CR p CRp i i ≥<．如果新个体r P '优于父代个体r P ，则用r P '来替换r P ，否则保持不变．在差分进化算法中，选择操作采取的是贪婪策略，即只有当产生的子代个体优于父代个体时才被保留，否则，父代个体被保留至下一代．大量研究与实验发现差分进化算法在维护群体的多样性及搜索能力方面功能较强，但收敛速度相对较慢，因此本文拟给出一种改进的差分进化算法用于多目标优化问题，仿真实验表明，改进的差分进化算法在不破坏原有算法维护群体多样性的前提下，可改善差分进化算法的收敛速度．基于双群体的差分进化算法 2.2.1 基本概念以下仅讨论带不等式约束的多目标优化问题()()()()nj u x l x x x pi x g t s x f x f x F j j j n i k ,,1,,,, ,,1,0)( ..,,min )(min 11ΛΛΛΛ=≤≤==<= （4）定义 x 称为（4）的不可行解，是指至少存在一个p i ≤≤1，满足()0≥x g i ． 定义 x 违反约束的强度，即约束违反度函数定义为()()∑==pi ix g x P 1,0max )(σ，本文取2=σ．定义 x 违反约束的数目()()∑==pi i x g Num x N 1)(，其中()⎩⎨⎧≥<=0 , 10, 0x x x Num ．定义 不可行解x 优于不可行解y ，是指x 的约束向量()()()x N x P ,Pareto 优于y 的约束向量()()()y N y P ,． 2.2.2 基本思想由上一节分析可知，在搜索过程中遇到的不可行解不能简单丢掉．因此，在设计算法时不但要考虑算法的收敛速度，而且还必须保证群体中可行解的优势地位；另一方面，对于多目标优化问题，维持搜索群体的多样性与考虑群体的收敛速度是同等重要的．基于此考虑，本节采用基于双群体的差分进化算法求解约束多目标优化问题，其中群体f PoP 用来保存搜索过程中遇到的可行解，c PoP 用来保存搜索过程中遇到的占优不可行解，同时f PoP 具有较强的记忆功能，可记忆f PoP 中每一个体搜索到的最优可行解和整个群体f PoP 到目前为止搜索到的最优可行解，分别记为lbest 和gbest ，其中lbest 表示个体对自身的思考和认知，gbest 表示个体间的信息交流，这一点和PSO 算法类似．与此同时，我们还通过一种改进的差分进化算法产生新的群体，在产生新群体的过程中，群体c PoP 中的部分个体参与了个体再生，并通过新生成的个体更新f PoP 、c PoP 、lbest 和gbest ．为了避免性能较优的不可行解被删除，本文拟采用双群体搜索机制，其中群体{}1,,,21N f x x x PoP Λ=用于记录可行解，群体c PoP {}2,,,21N y y y Λ=记录不可行解，21,N N 分别为群体f PoP 与c PoP 的规模，满足21N N >，{}1,,,21N z z z lbest Λ=和{}3,,,21N g g g gbest Λ=分别为群体f PoP 中每一个个体i x 搜索到最优可行解i z 和群体f PoP 迄今为止搜索到最优可行解．2.2.3 改进的差分进化算法为了维护群体f PoP 的多样性和收敛性，同时有效的利用已搜索到的不可行解的某些优良特性，下面给出一种改进的差分进化算法，并通过以下两种方式产生新的个体．方法1：()()3422211r r r r r x g F x z F x C -+-+=其中f r r r PoP x x x ∈321,,，lbest z r ∈2，gbest g r ∈4．方法2：()()5423211r r r r r y g F y z F x C -+-+=其中f r PoP x ∈1，c r r PoP y y ∈53,，lbest z r ∈2，gbest g r ∈4．方法1的目的在于通过向最优个体学习，改善算法的收敛速度．方法2的主要目的在于和不可行个体进行信息交流，共享不可行解的一些优良特性，增加群体的多样性．在具体操作过程中，首先用改进的差分进化算法产生新的个体()n c c C ,,1Λ=，然后针对父代个体),,(1n r x x P Λ=的每一个分量i x ，产生位于区间]1,0[中的随机数i p ，根据i p 与参数CR 的大小关系确定是否用i c 来替换i x ，得到新的个体),,(1n r x x P ''='Λ． 如果r P '是可行解，而且f PoP 的规模小于给定规模1N ，则可直接将r P '插入f PoP ；如果插入后的群体的规模大于给定规模1N ，首先两两比较f PoP 中的个体，如果存在两个个体f j i PoP x x ∈,，满足)(i x F Pareto 优于)(j x F ，则将个体j x 删除，如果不存在，也就是说集合f PoP 中任意两个个体所对应的目标向量都不可比较，则计算f PoP 中任意两个个体间的距离，随机删除距离最小的两个个体中的一个．如果r P '是不可行解，而且c PoP 的规模小于给定规模2N ，则可直接将r P '插入群体c PoP 中；如果c PoP 等于给定规模阈值2N ，计算插入r P '后的群体c PoP 中任意两个个体的约束向量，如果存在两个个体f j i PoP y y ∈,，满足约束向量()()()i i y N y P ,Pareto 优于约束向量()()()j j y N y P ,，则删除j y ；如果不存在，则删除满足=)(i y P )(max y P cPoP y ∈的个体i y ．经过以上操作，群体f PoP 和c PoP 的规模不会大于给定规模阈值．最后利用新生成的群体f PoP 更新最优个体集合lbest 和gbest ，群体gbest 的更新方法和SPEA 算法中外部群体的更新方法相同，而lbest 的更新方法如下：如果新生成的可行解r P 'Pareto 优于对应的局部最优解i z ，则用r P '替换i z ，否则不予替换． 算法的基本流程综上所述，基于双群体的差分进化算法的约束处理技术的流程可表示如下：step1. 随机生成N ()21N N N +≥个个体，判断每一个体的可行性，然后根据个体可行 性将其插入到对应的群体f PoP 或c PoP 中；并初始化lbest 和gbest 及参数CR 和d P ． step2. 判断搜索是否结束，如果结束，转向step5，否则转向step3.step3. 生成随机数p ，如果d P p ≥，根据方法1，生成新的个体r P '；否则，根据方法2 生成新的个体r P '，如果r P '是可行解，将r P '插入到f PoP 中；否则r P '插入到c PoP 中，反复执行直到生成1N 个可行解．step4. 根据新生成的群体f PoP 更新最优个体集lbest 和gbest ，转向step2． step5. 输出最优解集gbest ．3 算法分析算法的性能衡量约束优化问题的算法性能的衡量可分为两部分，一部分为最终获得的最优解的性能的衡量，如通过GD [15]来度量最优群体的逼近性，SP [16]来衡量最优解的分布均匀性，或通过计算目标函数的次数衡量算法的复杂度和算法的收敛速度．另一部分是针对约束优化问题来衡量群体的多样性，Koziel & Michalewicz [17]给出一种多样性度量准则ρ，其定义如下：||||S F =ρ （5） 其中F 表示每一次搜索过程中生成的可行解的数目，S 为所生成的所有个体的数目．相应地，为了衡量群体中的不可行解违反约束的强度，可采用约束违反度函数的均值来度量：∑∈=cPoP y cavg PoPy P P /)( （6）其中c PoP 表示集合c PoP 所包含元素的数目．然而在实际问题中，决策者往往只对某一范围的最优解感兴趣，故下边只评价本文算法对标准测试函数最终获得的最优解集的逼近性与均匀性，并与NSGA-Ⅱ进行比较． 算法的时间复杂性分析我们仅考虑种群规模对算法时间复杂度的影响，设可行群体f PoP 的规模为1N ，不可行群体c PoP 的规模为2N ，群体lbest 的规模为1N ，群体gbest 的最大规模为3N ，则文中算法迭代一次的时间复杂度可计算如下：算法中重组和变异操作的时间复杂度为)(1N O ；判断进化群体中个体可行性所需时间复杂度为)(1N O ；更新群体f PoP 、c PoP 和lbest 的时间复杂度分别为)(1N O 、)(2N O 和)(1N O ；计算群体f PoP 和gbest 的适应度所需时间复杂度为)(31N N O +；用于更新最优群体gbest 的时间复杂度最差为))((231N N O +；保持最优群体gbest 和进化群体f PoP 多样性的时间复杂度最差为))log()())((3131331N N N N N N O ++++；则算法迭代一次所需的时间复杂度最差为)(1N O +)(1N O +)(1N O +)(2N O +)(1N O +)(31N N O ++))((231N N O +))log()(())((3131331N N N N O N N O ++++ （7）上述复杂度可简化为))log()(())(())((3131231331N N N N O N N O N N O ++++++ （8）设N 为所有种群的规模，令321N N N N ++=，则本文算法的时间复杂度))log()(())(())((3131231331N N N N O N N O N N O ++++++<)(3N O （9）NSGA-Ⅱ [9]和SPEA [10]是多目标进化算中两个最具有代表性的优秀算法，这两个算法的时间复杂度最差分别为)(2N O 和))((3N N O +，其中N N ,分别为进化种群规模和外部种群集的规模．因而，SPEA 和本文算法的时间复杂度最差为)(3N O ，这比NSGA-Ⅱ的时间复杂度稍高一些，但接下来的实验结果告诉我们，本文算法的均匀性及逼近性却明显优于NSGA-Ⅱ．事实上，SPEA 和本文算法的时间复杂度主要用于环境选择（Environmental selection ）上，如果文中对gbest 采取NSGA-Ⅱ中的多样性保持策略，则本文算法的复杂度将降至)(2N O ．4 实验结果与分析（1） 测试函数与参数设置为了验证本文给出算法的可行性，我们采用Deb [18]建议的用来测试约束多目标优化算法性能的四个常见的测试函数来检验本文算法的性能．可行解集合的规模1001=N ，不可行解集合的规模102=N ．初始化时，随机生成个体的数目200=N ，参数25.0=CR ，5.0=d p ．21,F F 为位于区间]0.1,5,0[中的一致随机数．Deb 给出的测试函数可用统一的解析表示，即()()()()()()[]()()()[]()⎪⎪⎩⎪⎪⎨⎧+-≥--=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧⎥⎦⎤⎢⎣⎡-=⎭⎬⎫⎩⎨⎧=dc x f e x f b a x f e x f x g x c x f x c x x f x f x F |})](cos )([sin sin{|sin )(cos )(1min min )(min 12121121θθπθθ其中()()[]∑=-+=5222cos 1041i i i x x x c π，.5,4,3,2,55,101=≤≤-≤≤i x x i测试函数选取不同的参数e d c b a ,,,,,θ时，所构造的测试函数性质不同，可行解和不可行解的分布也不同，最终导致全局Pareto 最优解集的不同．其中通过控制参数b 的大小，可以控制Pareto 前端不连续的段数，b 越大段数越多；而较小参数d 可以使得每一不连续Pareto 前端仅包含一个Pareto 点；参数a 调节连续可行域到Pareto 前端的点的距离，a 越大距离越远，其作用在于调节问题求解的难度；参数c 的作用在于改变分段Pareto 前端之间的分布特性，当c =1时，Pareto 前端为均匀分布；当1>c 时， Pareto 前端向1f 较大的方向移动；当1<c 时，则Pareto 前端向2f 较大的方向移动．基于以上分析我们选取不同的参数构造4个常用的测试函数检验本节算法的性能，这些测试函数的参数取值具体如下．图测试函数CTP1在目标空间示意图图测试函数CTP2在目标空间示意图图测试函数CTP3在目标空间示意图图测试函数CTP4在目标空间示意图测试函数CTP1：θ1.0π=d，2-=e．可行解、不可行解、全局=c，2=a，5.0==，40b，1Pareto前端分布如图所示．测试函数CTP2：πθ05=c，6==d，0e．可行解、不可行解、全局Pareto =，40.0-b，1=a，5=前端分布如图所示．测试函数CTP3：πθ2.0-=c，6=e．可行解、不可行解、全局d，1==，2.0=a，10b，1=Pareto前端分布如图所示．测试函数CTP4：πθ2.0-d，1==e．可行解、不可行解、全局c，5.0a，10=，1.0==b，1=Pareto前端分布如图所示．（2）实验结果与分析在相同的测试函数和目标函数计算次数下，将本文算法和经典的NSGA-II算法进行比较，并将各自算法独立运行30次，然后统计两种算法所得Pareto 最优解集的均匀性（Spacing ，SP ）与逼近性（Generational distance, GD ）的最好、最差、均值、方差和中间值，以此作为衡量算法性能的标准．由于真实Pareto 最优集是未知的，故我们将两种算法所得的60个近似Pareto 最优解集之并集的Pareto 滤集作为真实Pareto 最优解集的逼近，其中测试函数CTP1，CTP2，CTP3的函数值计算次数为10200，而CTP4的函数值计算次数为610014．这里，集合I 的Pareto 滤集)(I Pareto 定义为{})()(, ,|)(x F y F I y I x x I Pareto π∈∃/∈=. 图、、、为从30次运行中随机选择的一次运行结果，从实验曲线可以看到本文算法求出的Pareto Front 在逼近性方面要优于NSGA-II ．图测试函数CTP1的Pareto Front 图 测试函数CTP2的Pareto Front图测试函数CTP3的Pareto Front 图测试函数CTP4的Pareto Front为了进一步定量的评价两种算法的逼近性与均匀性，表，，，给出了两种算法对上述四个测试函数的SP ，GD 的统计结果，从表中数据容易看出，在解集的逼近性和均匀性方面本文算法对四个测试函数的标准方差都明显小于经典的NSGA-II 算法，这说表测试函数CTP1评价准则的统计结果表测试函数CTP4评价准则的统计结果明本文的算法性能更稳定．另一方面，上述定量的度量结果也表明在搜索过程中适当的运用性能较优的不可行解的信息不仅有助于保持群体的多样性，而且增强了算法的搜索功能，并在一定程度上起到了维持解集的均匀性的作用．5 结论本文借助粒子群算法的基本思想给出了一种改进的差分进化算法，在适当的利用部分优良不可行个体的基础上，提出了用于约束多目标优化问题的双群体差分进化算法．该算法中的两个群体分别用于记录进化过程中的可行解及部分性能较优的不可行解，其优点在于可以充分利用每次迭代产生的子代个体的信息．此外，还对文中算法的时间复杂度与NSGA-Ⅱ和SPEA进行比较.经典测试函数的数值仿真结果表明，本文算法无论在解集的逼近性及均匀性方面都优于NSGA-II算法，这表明文中提出的基于双群体的差分进化算法可用于求解带约束的多目标优化问题方面有一定的优势．正如“没有免费的午餐定理”[19]所指出的，任何一种算法不可能在所有的性能方面占尽优势，虽然本文算法在求解约束多目标优化问题方面具有一定的优势，但计算量要稍高于NSGA-II。
