用于约束多目标优化问题的双群体差分进化算法
用于约束多目标优化问题的双群体差分进化算法
孟红云１ 张小华２ 刘三阳1
(1.西安电子科技大学 应用数学系，西安，71007１;
2.西安电子科技大学 智能信息处理研究所，西安,7１0０７1）
摘 要:首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解.此外,将本文算法、N ＳGA-Ⅱ和SPEA 的时间复杂度进行比较表明，ＮS ＧA-Ⅱ最优,本文算法与SPE Ａ相当.对经典测试函数的仿真结果表明,与ＮＳGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字: 差分进化算法；约束优化问题；多目标优化问题；
中图分类号：TP18
1 引言
达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展,用进化算法求解优化问题已成为一个研究的热点[1-3].但目前研究最多的却是无约束优化问题.然而，在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性，以最小化问题为例,约束优化问题（Constrai ｎｅd Opti ｍｉｚａtio ｎ Prob ｌｅm ，COP )可定义如下：
)(COP ()()()()q
j x h p i x g t s x f x f x f x F j i k R
x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ (1) 其中)(x F 为目标函数,)(),(x h x g j i 称为约束条件,n n 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 j j
（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 Pa ｒe ｔo 优于)(*x F .
目前,进化算法用于无约束优化问题的文献居多，与之比较,对约束优化问题的研究相对
较少［４－6]。文[7]
对当前基于进化算法的各种约束处理方法进行了较为详细的综述.对于约束优化问题的约束处理方法基本上分为两类：基于罚函数的约束处理技术和基于多目标优化技术的约束处理技术.由于罚函数法在使用中不需要约束函数和目标函数的解析性质，因此经常被应用于约束优化问题,但该类方法对罚因子有很强的依赖性，需要根据具体问题平衡罚
函数与目标函数．为了避免复杂罚函数的构造,Ve ｒdegay 等[8]将进化算法中的竞争选择用于
约束处理，并在比较两个解的性能时提出了三个准则,但他的第三个准则—可行解优于不可行解—这一准则合理性不强 .然而该文的这一准则却为进化算法求解约束优化问题提供了新思路,获得了良好效果.
因为在现实中存在一大类约束优化问题,其最优解位于约束边界上或附近,对于这类问题，在最优解附近的不可行解的适应值很可能优于位于可行域内部的大部分可行解的适应值,因此无论从适应值本身还是从最优解的相对位置考虑，这样的不可行解对找到最优解都是很有帮助的，故如何有效利用搜索过程中的部分具有较好性质的不可行解是解决此类问题的难点之一．基于以上考虑,本文拟给出一种求解约束多目标优化问题的基于双群体机制的差分
进化算法，并对文中算法的时间复杂度与ＮSG Ａ－Ⅱ［9]和S ＰE Ａ[1０]进行比较，最后用实验
仿真说明文中算法的可行性及有效性． 2 用于约束优化的双群体差分进化算法
2．１ 差分进化算法
差分进化算法是一类简单而有效的进化算法,已被成功应用于求解无约束单目标和多目
标优化问题 [１1-１４]．该算法在整个运行过程中保持群体的规模不变，它也有类似于遗传算
法的变异、交叉和选择等操作,其中变异操作定义如下:
()
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 ，以得到新的个体),,(1
n r x x P ''=' , 其中 , , ???='i i i x c x if if CR
p CR p i i ≥<.如果新个体r P '优于父代个体r P ,则用r P '来替换r P ,否则保持不变.在差分进化算法中，选择操作采取的是贪婪策略，即只有当产生的子代个体优于父代个体时才被保留,否则,父代个体被保留至下一代．
大量研究与实验发现差分进化算法在维护群体的多样性及搜索能力方面功能较强，但收敛速度相对较慢，因此本文拟给出一种改进的差分进化算法用于多目标优化问题，仿真实验表明,改进的差分进化算法在不破坏原有算法维护群体多样性的前提下,可改善差分进化算法的收敛速度．
差分进化算法及应用研究
湖南大学 硕士学位论文 差分进化算法及应用研究 姓名：吴亮红 申请学位级别：硕士 专业：控制理论与控制工程指导教师：王耀南 20070310
硕士学位论文 摘要 论文首先介绍了智能优化算法的产生对现代优化技术的重要影响，阐述了智能优化算法的研究和发展对现代优化技术和工程实践应用的必要性，归纳总结了智能优化算法的主要特点，简要介绍了智能优化算法的主要研究内容及应用领域。 对差分进化算法的原理进行了详细的介绍，给出了差分进化算法的伪代码。针对混合整数非线性规划问题的特点，在差分进化算法的变异操作中加入取整运算，提出了一种适合于求解各种混合整数非线性规划问题的改进差分进化算法。同时，采用时变交叉概率因子的方法以提高算法的全局搜索能力和收敛速率。用四个典型测试函数进行了实验研究，实验结果表明，改进的差分进化算法用于求解混合整数非线性规划问题时收敛速度快，精度高，鲁棒性强。 采用非固定多段映射罚函数法处理问题的约束条件，提出了一种用改进差分进化算法求解非线性约束优化问题的新方法。结合差分进化算法两种不同变异方式的特点，引入模拟退火策略，使算法在搜索的初始阶段有较强的全局搜索能力，而在后阶段有较强的局部搜索能力，以提高算法的全局收敛性和收敛速率。用几个典型Benchmarks函数进行了测试，实验结果表明，该方法全局搜索能力强，鲁棒性好，精度高，收敛速度快，是一种求解非线性约束优化问题的有效方法。 为保持所求得的多目标优化问题Pareto最优解的多样性，提出了一种精英保留和根据目标函数值进行排序的多目标优化差分进化算法。对排序策略中目标函数的选择方式进行了分析和比较，并提出了一种确定进化过程中求得的精英解是否进入Pareto最优解集的阈值确定方法。用多个经典测试函数进行了实验分析，并与NSGA-Ⅱ算法进行了比较。实验结果表明，本文方法收敛到问题的Pareto前沿效果良好，获得解的散布范围广，能有效保持所求得的Pareto最优解的多样性。 提出了一种新的基于群体适应度方差自适应二次变异的差分进化算法。该算法在运行过程中根据群体适应度方差的大小，增加一种新的变异算子对最优个体和部分其它个体同时进行变异操作，以提高种群多样性，增强差分进化算法跳出局部最优解的能力。对几种典型Benchmarks函数进行了测试，实验结果表明，该方法能有效避免早熟收敛，显著提高算法的全局搜索能力。提出了将该改进算法用来整定不完全微分PID控制器最优或近似最优参数的新方法。为克服频域中常用的积分性能指标如IAE，ISE和ITSE的不足，提出了一种新的时域性能指标对控制器性能进行测试和评价。用三个典型的控制系统对提出的ASMDE-PID控制器进行了测试。实验结果表明，该方法实现容易，收敛性能稳定，计算效率高。与ZN，GA和ASA方法相比，DE在提高系统单位阶跃响应性能方面效率更高，鲁棒性更强。 为了提高差分进化算法的全局搜索能力和收敛速率，提出了一种双群体伪并行差分
1多目标优化
多目标优化算法 ——11级计算一班 20113745 陆慧玲 近年来,多目标优化问题求解已成为演化计算的一个重要研究方向,而基于Pareto 最优概念的多目标演化算法则是当前演化计算的研究热点。多目标演化算法的研究目标是使算法种群快速收敛并均匀分布于问题的非劣最优域。 最优化问题是工程实践和科学研究中主要的问题形式之一，其中，仅有一个目标函数的最优化问题称为单目标优化问题，目标函数超过一个并且需要同时处理的最优化问题称为多目标优化问题(multiobjectiveoptimizationprob- lems，简称MOPs)。对于多目标优化问题，一个解对于某个目标来说可能是较好的，而对于其他目标来讲可能是较差的，因此，存在一个折衷解的集合，称为Pareto 最优解集(Pareto optimal set)或非支配解集(nondominated set)。起初，多目标优化问题往往通过加权等方式转化为单目标问题，然后用数学规划的方法来求解，每次只能得到一种权值情况下的最优解。同时，由于多目标优化问题的目标函数和约束函数可能是非线性、不可微或不连续的，传统的数学规划方法往往效率较低，且它们对于权重值或目标给定的次序较敏感。进化算法通过在代与代之间维持由潜在解组成的种群来实现全局搜索，这种从种群到种群的方法对于搜索多目标优化问题的Pareto 最优解集是很有用的。 第一代进化多目标优化算法以Goldberg 的建议为萌芽。1989 年，Goldberg 建议用非支配排序和小生境技术来解决多目标优化问题。非支配排序的过程为：对当前种群中的非支配个体分配等级1，并将其从竞争中移去；然后从当前种群中选出非支配个体，并对其分配等级2，该过程持续到种群中所有个体都分配到次序后结束。小生境技术用来保持种群多样性，防止早熟。Goldberg 虽然没有把他的思想具体实施到进化多目标优化中，但是其思想对以后的学者来说，具有启发意义。随后，一些学者基于这种思想提出了MOGA，NSGA 和NPGA。 从20 世纪末期开始，进化多目标优化领域的研究趋势发生了巨大的变化，l999 年，Zitzler 等人提出了SPEA。该方法使精英保留机制在进化多目标优化领域流行起来。第二代进化多目标优化算法的诞生就是以精英保留策略的引入为标志。在进化多目标优化领域，精英保留策略指的是采用一个外部种群(相对于原来个体种群而言)来保留非支配个体。(1)SPEA 和SPEA2 SPEA 是Zitzler 和Thiele 在1999 年提出来的算法。在该算法中，个体的适应度又称为Pareto 强度，非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比
多目标进化算法总结
MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???>
当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数
多目标进化算法总结
MOGA i x 是第t 代种群中个体，其rank 值定义为： () (,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况：
1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法
NPGA 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j Pop m Sh d i j ∈= ????∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设置共享参数
进化计算综述
进化计算综述 1.什么是进化计算 在计算机科学领域，进化计算（Evolutionary Computation）是人工智能（Artificial Intelligence），进一步说是智能计算（Computational Intelligence）中涉及到组合优化问题的一个子域。其算法是受生物进化过程中“优胜劣汰”的自然选择机制和遗传信息的传递规律的影响，通过程序迭代模拟这一过程，把要解决的问题看作环境，在一些可能的解组成的种群中，通过自然演化寻求最优解。 2.进化计算的起源 运用达尔文理论解决问题的思想起源于20世纪50年代。 20世纪60年代，这一想法在三个地方分别被发展起来。美国的Lawrence J. Fogel提出了进化编程（Evolutionary programming），而来自美国Michigan 大学的John Henry Holland则借鉴了达尔文的生物进化论和孟德尔的遗传定律的基本思想，并将其进行提取、简化与抽象提出了遗传算法（Genetic algorithms）。在德国，Ingo Rechenberg 和Hans-Paul Schwefel提出了进化策略（Evolution strategies）。 这些理论大约独自发展了15年。在80年代之前，并没有引起人们太大的关注，因为它本身还不够成熟，而且受到了当时计算机容量小、运算速度慢的限制，并没有发展出实际的应用成果。
到了20世纪90年代初，遗传编程（Genetic programming）这一分支也被提出，进化计算作为一个学科开始正式出现。四个分支交流频繁，取长补短，并融合出了新的进化算法，促进了进化计算的巨大发展。 Nils Aall Barricelli在20世纪六十年代开始进行用进化算法和人工生命模拟进化的工作。Alex Fraser发表的一系列关于模拟人工选择的论文大大发展了这一工作。 [1]Ingo Rechenberg在上世纪60 年代和70 年代初用进化策略来解决复杂的工程问题的工作使人工进化成为广泛认可的优化方法。[2]特别是John Holland的作品让遗传算法变得流行起来。[3]随着学术研究兴趣的增长，计算机能力的急剧增加使包括自动演化的计算机程序等实际的应用程序成为现实。[4]比起人类设计的软件，进化算法可以更有效地解决多维的问题，优化系统的设计。[5] 3.进化计算的分支 进化计算的主要分支有：遗传算法GA ，遗传编程GP、进化策略ES、进化编程EP。下面将对这4个分支依次做简要的介绍。 1遗传算法（Genetic Algorithms）： 遗传算法是一类通过模拟生物界自然选择和自然遗传机制的随机化搜索算法，由美国John HenryHoland教授于1975年在他的专著《Adaptation in Natural and Artificial Systems》中首次提出。[6]它是利用某种编码技术作用于称为染色体的二进制数串，其基本思想是模拟由这些串组成的种群的进化过程，通过有组织地然而是随机地信息交换来重新组合那些适应性好的串。遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染
用于约束多目标优化问题的双群体差分进化算法
用于约束多目标优化问题的双群体差分进化算法 孟红云１ 张小华２ 刘三阳1 (1.西安电子科技大学 应用数学系，西安，71007１; 2.西安电子科技大学 智能信息处理研究所，西安,7１0０７1） 摘 要:首先给出一种改进的差分进化算法,然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解.此外,将本文算法、N ＳGA-Ⅱ和SPEA 的时间复杂度进行比较表明，ＮS ＧA-Ⅱ最优,本文算法与SPE Ａ相当.对经典测试函数的仿真结果表明,与ＮＳGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字: 差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算法的出现和发展,用进化算法求解优化问题已成为一个研究的热点[1-3].但目前研究最多的却是无约束优化问题.然而，在科学研究和工程实践中,许多实际问题最终都归结为求解一个带有约束条件的函数优化问题,因此研究基于进化算法求解约束优化问题是非常有必要的.不失一般性，以最小化问题为例,约束优化问题（Constrai ｎｅd Opti ｍｉｚａtio ｎ Prob ｌｅm ，COP )可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ (1) 其中)(x F 为目标函数,)(),(x h x g j i 称为约束条件,n n 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 j j （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 Pa ｒe ｔo 优于)(*x F . 目前,进化算法用于无约束优化问题的文献居多，与之比较,对约束优化问题的研究相对
基本差分进化算法
基本差分进化算法 基本模拟退火算法概述 DE 算法是一种基于群体进化的算法，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。由于DE 算法操作简单，寻优能力强，自提出以来引起了国内外学者的高度关注，目前已在电力系统优化调度、配网重构等领域得到了应用。 1、算法原理 DE 算法首先在N 维可行解空间随机生成初始种群P 0001[,,]N =X x x L ，其中000T 1[,,]i i iN x x =x L ，p N 为DE 种群规模。DE 算法的核心思想在于采取变异和交叉操 作生成试验种群，然后对试验种群进行适应度评估，再通过贪婪思想的选择机制，将原种群和试验种群进行一对一比较，择优进入下一代。 基本DE 算法主要包括变异、交叉和选择三个操作。首先，在种群中随机选取三个个体，进行变异操作： 1123()t t t t i r r r F +=+-v x x x 其中1t i +v 表示变异后得到的种群，t 表示种群代数，F 为缩放因子，一般取(0,2]，它的大小可以决定种群分布情况，使种群在全局范围内进行搜索；1t r x 、2t r x 、3t r x 为从种群中随机抽取的三个不同的个体。 然后，将变异种群和原种群进行交叉操作： 1,R 1 ,,R () or () () and ()t i j t i j t i j v rand j C j randn i u x rand j C j randn i ++?≤=?=?>≠?? 其中t 1,i j u +表示交叉后得到的种群，()rand j 为[0,1]之间的随机数，j 表示个体的第j 个分量，R C 为交叉概率，()randn i 为[1,,]N L 之间的随机量，用于保证新个体至少有一维分量由变异个体贡献。 最后，DE 算法通过贪婪选择模式，从原种群和试验种群中选择适应度更高的个体进入下一代： 11t 11 ()() ()()t t t i i i i t t t i i i f f f f ++++?<=?≥?u u x x x u x 1()t i f +u 、()t i f x 分别为1t i +u 和t i x 的适应度。当试验个体1t i +u 的适应度优于t i x 时，
用于约束多目标优化问题的双群体差分进化算法精编
用于约束多目标优化问题的双群体差分进化算 法精编 Document number：WTT-LKK-GBB-08921-EIGG-22986
用于约束多目标优化问题的双群体差分进化算法 孟红云 1 张小华2刘三阳1 (1.西安电子科技大学应用数学系，西安，710071； 2.西安电子科技大学智能信息处理研究所，西安，710071)摘要：首先给出一种改进的差分进化算法，然后提出一 种基于双群体搜索机制的求解约束多目标优化问题的差分 进化算法．该算法同时使用两个群体，其中一个用于保存 搜索过程中找到的可行解，另一个用于记录在搜索过程中 得到的部分具有某些优良特性的不可行解，避免了构造罚 函数和直接删除不可行解．此外，将本文算法、NSGA-Ⅱ和SPEA的时间复杂度进行比较表明，NSGA-Ⅱ最优，本文算法与SPEA相当.对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，本文算法在均匀性及逼近性方面均具有一定的优势. 关键字：差分进化算法；约束优化问题；多目标优化问题； 中图分类号：TP18 1 引言 达尔文的自然选择机理和个体的学习能力推动进化算 法的出现和发展，用进化算法求解优化问题已成为一个研 究的热点[1-3]．但目前研究最多的却是无约束优化问题．然而，在科学研究和工程实践中，许多实际问题最终都归结 为求解一个带有约束条件的函数优化问题，因此研究基于 进化算法求解约束优化问题是非常有必要的．不失一般
性，以最小化问题为例，约束优化问题（Constrained Optimization Problem ，COP ）可定义如下： )(COP ()()()()q j x h p i x g t s x f x f x f x F j i k R x n ,,1,0)( ,,1,0)( ..,,,)(min 21 ===≤=∈ （1） 其中)(x F 为目标函数，)(),(x h x g j i 称为约束条件， n n 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 j j （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] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类：基于 罚函数的约束处理技术和基于多目标优化技术的约束处理
约束优化设计
行域 φ 内，选择一个初始点 X 然后确定一个可行 得一个目标函数有所改善的可行的新点 X 即完成了 第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： s .t . min f (x ) g u (x ) ≤ 0 h v (x ) = 0 x ∈ R n u = 1, 2,..., m v = 1, 2,..., p < n 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于 这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由 m 个不等式约束条件 gu(x )≤0 所确定的可 0 搜索方向 S ，且以适当的步长沿 S 方向进行搜索，取 1 一次迭代。以新点为起始点重复上述搜索过程，每次 均按如下的基本迭代格式进行计算： X k+1=X k +α k S k (k=0,1,2,..) 逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算 不论何时终止，都可以获得比初始点好的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局 部最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集
φ(X,μ1,μ2)=F(X)+∑μ 1 G??g j X)??+∑μ2H??h k(X)?? a)可行域是凸集；b)可行域是非凸 集 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数 结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优 化问题。 m l j=1k=1 新目标函数 然后对新目标函数进行无约束极小化计算。 加权因子 间接法是结构优化设计中广泛使用的有效方法，其特点： 1）由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和数值计算的稳定性大有提高； 2）可以有效处理具有等式约束的约束优化问题； 3）目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精度，甚至导致计算失败。
差分进化算法介绍
1．差分进化算法背景 差分进化(Differential Evolution，DE)是启发式优化算法的一种，它是基于群体差异的启发式随机搜索算法，该算法是Raincr Stom和Kenneth Price为求解切比雪夫多项式而提出的。差分进化算法具有原理简单、受控参数少、鲁棒性强等特点。近年来，DE在约束优化计算、聚类优化计算、非线性优化控制、神经网络优化、滤波器设计、阵列天线方向图综合及其它方面得到了广泛的应用。 差分算法的研究一直相当活跃，基于优胜劣汰自然选择的思想和简单的差分操作使差分算法在一定程度上具有自组织、自适应、自学习等特征。它的全局寻优能力和易于实施使其在诸多应用中取得成功。 2.差分进化算法简介 差分进化算法采用实数编码方式，其算法原理同遗传算法相似刚，主要包括变异、交叉和选择三个基本进化步骤。DE算法中的选择策略通常为锦标赛选择，而交叉操作方式与遗传算法也大体相同，但在变异操作方面使用了差分策略，即：利用种群中个体间的差分向量对个体进行扰动，实现个体的变异。与进化策略(Es)采用Gauss或Cauchy分布作为扰动向量的概率密度函数不同，DE使用的差分策略可根据种群内个体的分布自动调节差分向量(扰动向量)的大小，自适应好；DE 的变异方式，有效地利用了群体分布特性，提高了算法的搜索能力，避免了遗传算法中变异方式的不足。 3.差分进化算法适用情况 差分进化算法是一种随机的并行直接搜索算法，最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。它可以对非线性不可微连续空间的函数进行最小化。目前，差分进化算法的应用和研究主要集中于连续、单目标、无约束的确定性优化问题，但是，差分进化算法在多目标、有约束、离散和噪声等复杂环境下的优化也得到了一些进展。 4.基本DE算法 差分进化算法把种群中两个成员之间的加权差向量加到第三个成员上以产生新的参数向量，这一操作称为“变异”。然后，变异向量的参数与另外事先确
最新高维多目标进化算法总结
高维多目标进化算法 二、文献选读内容分析及思考 （一）Borg算法 Borg算法是基于ε-MOEA算法（Deb，2003）的一种全新改进算法[32]，下面将从创新点、原理、算法流程和启发思考四方面进行阐述。 1.创新点 1）在ε支配关系的基础上提出ε盒支配的概念，具有能同时保证算法收敛性与多样性的特点。 2）提出了ε归档进程，能提高算法计算效率和防止早熟。 3）种群大小的自适应调整。 4）交叉算子的自适应选择。由于处理实际问题时，是不知道目标函数具有什么特性，前沿面如何，在具有多个交叉算子的池子里，根据进程反馈，选择不同的交叉算子，使产生的后代具有更好的特性针对要研究的问题。 2. Borg算法原理 1）ε盒支配：通过对目标空间向量的每一维除以一个较小的ε，然后取整后进行pareto支配比较。这样的支配关系达到的效果是把目标空间划分成以ε为边长的网格（2目标时），当点处于不同的网格时，按pareto支配关系比较；当处于同一网格时，比较哪个点距离中心点（网格最左下角）最近。这样一来，网格内都只有一个点。 2）ε归档进程 如图1所示，黑点表示已经归档的，想要添加到档案集的新解用×表示，阴影表示归档解支配的区域。当新解的性能提升量超过阈值ε才属于ε归档进程。比如解1、解2加入归档集属于ε归档进程，解3加入归档集就不属于ε归档进程。 图1 ε支配网格 在这个过程中设置了一个参数c，表示每一代中加入归档集解得个数，每隔一定迭代次数检测c有没有增加，如果没有增加表明算法停滞，重启机制启动。 3）重启 自适应种群大小：重启后的种群大小是根据归档集的大小设置。γ表示种群大小与归档集大小的比值，这个值也用于第二步中，如果γ值没超过1.25，重启机制也启动。启动后，γ人为设定为固定值，种群被清空，填充归档集的所有个体，不足的个体是随机选取归档集中个体变异所得。与之相匹配的锦标赛比较集大小是归档集大小乘以固定比值τ。 4）交叉算子的自适应选择 摒弃以往采用单一的交叉算子，采用包含各类交叉算子的池子，比如有K
差分进化算法-入门
基本差分进化算法 1基本差分进化算法的基本思想 DE 算法是一种基于实数编码的用于优化函数最小值的进化算法，是在求解有关切比雪夫多项式的问题时提出来的，是基于群体差异的进化计算方法。它的整体结构类似于遗传算法，一样都存在变异、交叉和选择操作，但是它又不同于遗传算法。与基本遗传算法的主要区别在于变异操作上，如： 1、传统的遗传算法采用二进制编码，而差分进化算法采用实数编码。 2、在遗传算法过两个父代个体的交叉产生两个子个体，而在差分进化算法过第两个或几个个体的差分矢量做扰动来产生新个体。 3、在传统的遗传算法中，子代个体以一定概率取代其父代个体，而在差分进化中新产生的个体只有当它比种群中的个体优良时才替换种群中的个体。 变异是DE 算法的主要操作，它是基于群体的差异向量来修正各个体的值，其基本原理是通过把种群中两个个体的向量差加权后，按一定的规划与第三个个体求和来产生新个体，然后将新个体与当代种群中某个预先决定的个体相比较，如果新个体的目标值优于与之相比较的个体的目标值，则在下一代中就用新个体取代，否则，旧个体仍保存下来。 差分进化算法其基本思想是：首先由父代个体间的变异操作构成变异个体；接着按一定的概率，父代个体与变异个体之间进行交叉操作，生成一试验个体；然后在父代个体与试验个体之间根据适应度的大小进行贪婪选择操作，保留较优者，实现种群的进化。 2 差分进化算法的基本操作 设当前进化代数为t ，群体规模为NP ，空间维数为D ，当前种群为 {}12(),, ,t t t NP X t x x x =，()12,, ,T t t t t i i i iD x x x x =为种群中的第i 个个体。在进化过程 中，对于每个个体t i x 依次进行下面三种操作。 2.1 变异操作 对于每个个体t i x 按下式产生变异个体12(,, ,)t t t t T i i i iD v v v v =，则 123() 1,2, ,D t t t t ij r j r j r j v x F x x j =+-= (1) 其中111112(,,,)t t t t T r r r r D x x x x =，222212(,,,)t t t t T r r r r D x x x x =和333312(,, ,)t t t t T r r r r D x x x x =是群 体中随机选择的三个个体，并且123r r r i ≠≠≠；1t r j x ，2t r j x 和3t r j x 分别为个体1r ，2r 和3r 的第j 维分量；F 为变异因子，一般取值于[0,2]。这样就得到了变异个体t i v 。
多目标进化算法总结
x 是第 t 代种群中个体，其 rank 值定义为： rank (x ,t ) =1+p (t ) p (t )为第t 代种群中所有支配x 的个体数目 适应值 (fitness value )分配算法： 1、 将所有个体依照 rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值(从 rank1 到 rank n * N )，一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一 rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制(ranking scheme )： 向量y a =(y a ,1,,y a ,q )和y b =(y b ,1,,y b ,q )比较 分为以下三种情况： k =1,,q -1; i =1,,k ; j =k +1,,q ; (y a ,i g i )(y a ,j g j ) i =1, ,q ; (y a ,i g i ) 当 y a 支配 y b 时，选择 y a 3、j =1, ,q ; (y a ,j g j ) 当 y b 支配 y a 时，选择 y b 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的 大小影响 理论上给出了参数share 的计算方法 goal vector ： g = (g 1, ,g q ) 1、 2、
基本思想： 1、初始化种群 Pop 2、锦标赛选择机制：随机选取两个个体 x 和 x 和一个 Pop 的 子集 CS(Comparison Set)做参照系。若 x 被 CS 中不少于一 个个体支配，而 x 没有被 CS 中任一个体支配，则选择 x 。 3、其他情况一律称为死结(Tie )，采用适应度共享机制选择。 个体适应度： f i 小生境计数(Niche Count )： m =j Pop Sh d (i , j ) 共享适应度(the shared fitness )： 选择共享适应度较大的个体进入下一代 优点：能够快速找到一 些好的非支配最优解域 能够维持一个较长的种群更新期 缺 点：需要设置共享参数 需要选择一个适当的锦标赛机制 限制 了该算法的实际应用效果 1- 共享函数： Sh (d ) = d share 0, d share d share
基于TSP的改进差分进化算法
龙源期刊网 https://www.wendangku.net/doc/1a18477328.html, 基于TSP的改进差分进化算法 作者：朱宇航伏楠 来源：《硅谷》2012年第17期 摘要: 针对TSP问题,提出一种改进的差分进化算法:利用贪心算法产生初始种群,定义特有的编码匹配函数进行变异操作,排序法修复变异个体,并采用顺序交叉,在变异操作之后,加入新的选择机制,防止交叉操作破坏变异出的优良个体,实验结果表明改进后的差分进化算法能够高效地解决TSP问题,体现良好的优化性能。 关键词: 差分进化算法;TSP;进化算法 0 引言 差分进化算法(DE:Differential Evolution)是一种模拟自然进化法则的仿生智能计算方法,在解决复杂的全局优化问题方面,DE的性能更加优秀,过程也更为简单,受控参数少[1],但由于DE 特有的差分操作的限制,DE被成功应用的领域多集中在连续优化领域,在离散优化领域的应用还相对较少[2]。 TSP(旅行商问题)作为典型的离散优化问题,是解决很多实际问题的最终转化形式,同时也是著名的NP难题,在短时间内求出其最优解非常困难,现有解法[3-4]在求解中都各有缺点.因此,研究将DE经过必要的改进后应用于TSP的求解具有重要意义。 1 改进DE算法 1.1 编码及匹配函数 适应度定义为:负的路径长度,使得路径长度越短,适应度值越大。 1.2 贪婪初始化 为提高初始种群的质量,采用贪婪的初始化方法.对于初始种群的每个个体,产生方法如下: step1:初始化待走城市列表List为包含所有城市的列表; step2:随机选择一个城市A作为起点,并将此点作为当前城市T,从List中移除; step3:从List中选择距离城市T最近的城市作为新的当前城市T,并将T从List中移除; step4:判断List是否为空,若是,则结束;若否,则转step3。
约束优化设计
第四章 约束优化设计 ● 概述 ● 约束坐标轮换法 ● 随机方向法 ● 罚函数法 概述 结构优化设计的问题，大多属于约束优化设计问题，其数学模型为： 根据求解方式的不同，可分为直接解法和间接解法两类。 直接解法是在仅满足不等式约束的可行设计区域内直接求出问题的约束最优解。属于这类方法的有：随机实验法、随机方向搜索法、复合形法、可行方向法等。其基本思路： 在由m 个不等式约束条件g u (x )≤0所确定的可行域φ内，选择一个初始点0 X 然后确定一个可行搜索方向S ，且以适当的步长沿S 方向进行搜索，取得一个目标函数有所改善的可行的新点1 X 即完成了一次迭代。以新点为起始点重复上述搜索过程，每次均按如下的基本迭代格式进行计算： k+1k k k =+S (k=0,1,2,..)X X α逐步趋向最优解， 直到满足终止准则才停止迭代。 直接解法的原理简单，方法实用，其特点是： 1） 由于整个过程在可行域内进行，因此，迭代计算不论何时终止，都可以获得比初始点好 的设计点。 2） 若目标函数为凸函数，可行域为凸集，则可获得全域最优解，否则，可能存在多个局部 最优解，当选择的初始点不同，而搜索到不同的局部最优解。 3） 要求可行域有界的非空集 1,2,...,1,2,...,u m v p n == 间接解法 间接解法是将约束优化问题转化为一系列无约束优化问题来解的一种方法。由于间接解法可以选用已研究比较成熟的无约束优化方法，并且容易处理同时具有不等式约束和等式约束的问题。因而在机械优化设计得到广泛的应用。 间接解法中具有代表性的是惩罚函数法。将约束函数进行特殊的加权处理后，和目标函数结合起来，构成一个新的目标函数，即将原约束优化问题转化为一个或一系列的无约束优化问题。 然后对新目标函数进行无约束极小化计算。 间接法是结构优化设计中广泛使用的有效方法，其特点： 1） 由于无约束优化方法的研究日趋成熟，为间接法提供可靠基础。这类算法的计算效率和 数值计算的稳定性大有提高； 2） 可以有效处理具有等式约束的约束优化问题； 3） 目前存在的主要问题，选取加权因子较为困难，选取不当，不仅影响收敛速度和计算精 度，甚至导致计算失败。 a) 可行域是凸集；b)可行域是非凸集 () ()()()121211 ,,m l j k j k X F X G g X H h X φμμμμ==??=++? ?????∑∑ 新目标函数 加权因子 摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目标优化问题分解为一组单目标优化问题并对它们同时优化。通过利用与每一个子问题相邻的子问题的优化信息来优化它本身，这是的该算法比MOGLS和非支配排序遗传算法NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在0-1背包问题和连续的多目标优化问题上，利用一些简单的分解方法本算法就可以比MOGLS和NSGA-Ⅱ表现的更加出色或者表现相近。实验也表明目标正态化的MOEA/D算法可以解决规模范围相异的多目标问题，同时使用一个先进分解方法的MOEA/D可以产生一组分别非常均匀的解对于有3个目标问题的测试样例。最后，MOEA/D在较小种群数量是的性能，还有可扩展性和敏感性都在本篇论文中通过实验经行了相应的研究。 I.介绍 多目标优化问题可以用下面式子表示： Maximize F(x)=((f1(f)…...f f(f))f subject to x∈Ω 其中Ω是决策空间，F：Ω→f f，包含了m个实值目标方法，f f被称为目标区间。对于 可以得到的目标集合成为{F(x)|x∈Ω}。 如果x∈R m，并且所有的目标函数都是连续的，那么Ω则可以用 Ω={x∈f f|h f(x)≤0,j=1……m} 其中hj是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义Pareto最优。 令u, v∈Rm，如果f f≥f f对于任意的i，并且至少存在一个f f≥f f(i,j∈{1…..m})，那么u支配v。如果在决策空间中，没有一个点F(y)能够支配F(x)点，那么x就是Pareto最优，F(x)则被称为Pareto最优向量。换句话说，对于Pareto最优点在某一个目标函数上的提高，都会造成至少一个其余目标函数的退化。所有Pareto最优解的集合称为Pareto集合，所有最优向量的集合被称为Pareto前沿。 在许多多目标优化的实际应用中，通过选择器选择一个接近Pareto最优前沿的解作为最后的解。大多数多目标优化问题都有许多甚至是无穷个Pareto最优向量，如果想要获得一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往往是获得一个均匀分布在Pareto最优前沿周围的最优解向量，这样就具有更好的代表性。许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。 一般来说，在温和控制下多目标优化问题的Pareto最优解，可以看做是一个标量优化问题的最优解(其中目标函数是fi的集合)。因此，Pareto最优前沿的近似求解可以被分解为一组标量目标优化子问题。这个想法是建立在许多传统的对最优前沿求近似解的数学编程方法上的。现在有许多的聚合方法，最流行的是切比雪夫法和加权法。最近，边界交叉方法也引起了许多的关注。 如今多目标进化算法并没有将分解这一概念引入当前的主要发展领域。这些算法将多目标优化问题看成一个整体。他们并没有通过任何特别的标量优化将每一个解相互联系在一起。在一个标量目标优化问题中，所有的解都可以通过他们的目标函数值进行对比，而挑战 i x 是第t 代种群中个体，其rank 值定义为： ()(,)1t i i rank x t p =+ ()t i p 为第t 代种群中所有支配i x 的个体数目 适应值（fitness value ）分配算法： 1、 将所有个体依照rank 值大小排序分类； 2、 利用插值函数给所有个体分配适应值（从rank1到 rank * n N ≤），一般采用线性函数 3、 适应值共享：rank 值相同的个体拥有相同的适应值， 保证后期选择时同一rank 值的个体概率相同 最后采用共享适应值随机选取的方法选择个体进入下一代 一种改进的排序机制（ranking scheme ）： 向量,1,(,,)a a a q y y y =???和,1,(,,)b b b q y y y =???比较 goal vector ：() 1,,q g g g =??? 分为以下三种情况： 1、 ()() ,,1,,1; 1,,; 1,,; a i i a j j k q i k j k q y g y g ?=???-?=????=+???>∧≤ 2、() ,1,,; a i i i q y g ?=???> 当a y 支配b y 时，选择a y 3、() ,1,,; a j j j q y g ?=???≤ 当b y 支配a y 时，选择b y 优点：算法思想容易，效率优良 缺点：算法容易受到小生境的大小影响 理论上给出了参数share σ的计算方法 基本思想： 1、初始化种群Pop 2、锦标赛选择机制：随机选取两个个体1x 和2x 和一个Pop 的 子集CS(Comparison Set)做参照系。若1x 被CS 中不少于一 个个体支配，而2x 没有被CS 中任一个体支配，则选择2x 。 3、其他情况一律称为死结（Tie ），采用适应度共享机制选择。 个体适应度：i f 小生境计数（Niche Count ）：(),i j P o p m S h dij ∈ = ??? ?∑ 共享函数：1-,()0,share share share d d Sh d d σσσ? ≤?=??>? 共享适应度（the shared fitness ）： i i f m 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果MOEAD(基于分解的多目标进化算法)
多目标进化算法总结