多目标优化算法 ——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 强度，非支配集中个体的适应度定义为其所支配的个体总数在群体中所占的比
进化计算综述 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 . 目前,进化算法用于无约束优化问题的文献居多，与之比较,对约束优化问题的研究相对
浅析多目标优化问题 【摘要】本文介绍了多目标优化问题的问题定义。通过对多目标优化算法、评估方法和测试用例的研究，分析了多目标优化问题所面临的挑战和困难。 【关键词】多目标优化问题；多目标优化算法；评估方法；测试用例 多目标优化问题MOPs （Multiobjective Optimization Problems）是工程实践和科学研究中的主要问题形式之一，广泛存在于优化控制、机械设计、数据挖掘、移动网络规划和逻辑电路设计等问题中。MOPs有多个目标，且各目标相互冲突。对于MOPs，通常存在一个折衷的解集（即Pareto最优解集），解集中的各个解在多目标之间进行权衡。获取具有良好收敛性及分布性的解集是求解MOPs的关键。 1 问题定义 最小化MOPs的一般描述如下： 2 多目标优化算法 目前，大量算法用于求解MOPs。通常，可以将求解MOPs的算法分为两类。 第一类算法，将MOPs转化为单目标优化问题。算法为每个目标设置权值，通过加权的方式将多目标转化为单目标。经过改变权值大小，多次求解MOPs 可以得到多个最优解，构成非支配解集[1]。 第二类算法，直接求解MOPs。这类算法主要依靠进化算法。进化算法这种面向种群的全局搜索法，对于直接得到非支配解集是非常有效的。基于进化算法的多目标优化算法被称为多目标进化算法。根据其特性，多目标进化算法可以划分为两代[2]。 （1）第一代算法：以适应度共享机制为分布性策略，并利用Pareto支配关系设计适应度函数。代表算法如下。VEGA将种群划分为若干子种群，每个子种群相对于一个目标进行优化，最终将子种群合并。MOGA根据解的支配关系，为每个解分配等级，算法按照等级为解设置适应度函数。NSGA采用非支配排序的思想为每个解分配虚拟适应度值，在进化过程中，算法根据虚拟适应度值采用比例选择法选择下一代。NPGA根据支配关系采用锦标赛选择法，当解的支配关系相同时，算法使用小生境技术选择最优的解进入下一代。 （2）第二代算法：以精英解保留机制为特征，并提出了多种较好的分布性策略。代表算法如下。NSGA-II降低了非支配排序的复杂度，并提出了基于拥挤距离的分布性策略。SPEA2提出了新的适应度分配策略和基于环境选择的分布性策略。PESA-II根据网络超格选择个体并使用了基于拥挤系数的分布性策略。
多目标优化方法 基本概述 几个概念 优化方法 一、多目标优化基本概述 现今,多目标优化问题应用越来越广,涉及诸多领域。在日常生活与工程中,经常要求不只一项指标达到最优,往往要求多项指标同时达到最优,大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如:在机械加工时,在进给切削中,为选择合适的切削速度与进给量,提出目标:1)机械加工成本最低2)生产率低3)刀具寿命最长;同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为: X=[x1,x2,…,x n ]T----------n维向量 min F(X)=[f1(X),f2(X),…,f n(X)]T----------向量形式的目标函数s、t、g i(X)≤0,(i=1,2,…,m) h j(X)=0,(j=1,2,…,k)--------设计变量应满足的约束条件多目标优化问题就是一个比较复杂的问题,相比于单目标优化问题,在多目标优化问题中,约束要求就是各自独立的,所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念:最优解,劣解,非劣解。 最优解X*:就就是在X*所在的区间D中其函数值比其她任何点的函数
值要小即f(X*)≤f(X),则X*为优化问题的最优解。 劣解X*:在D中存在X使其函数值小于解的函数值,即f(x)≤f(X*), 即存在比解更优的点。 非劣解X*:在区间D中不存在X使f(X)全部小于解的函数值f(X*)、 如图:在[0,1]中 X*=1为最优解 在[0,2]中 X*=a为劣解 在[1,2]中 X*=b为非劣解 多目标优化 问题中绝对最优 解存在可能性一般很小,而劣解没有意义,所以通常去求其非劣解来解决问题。 三、多目标优化方法 多目标优化方法主要有两大类: 1)直接法:直接求出非劣解,然后再选择较好的解 将多目标优化问题转化为单目标优化问题。 2)间接法如:主要目标法、统一目标法、功效系数法等。 将多目标优化问题转化为一系列单目标优化问题。 如:分层系列法等。
基于分解的多目标进化算法
摘要：在传统的多目标优化问题上常常使用分解策略。但是，这项策略还没有被广泛的 应用到多目标进化优化中。本文提出了一种基于分解的多目标进化算法。该算法将一个多目 标优化问题分解为一组？？？单目标优化问题并对它们同时优化。通过利用与每一个子问题 相邻的子问题的优化信息来优化它本身，这是的该算法比 MOGLS 和非支配排序遗传算法 NSGA-Ⅱ相比有更低的计算复杂度。实验结果证明：在 0-1 背包问题和连续的多目标优化问 题上，利用一些简单的分解方法本算法就可以比 MOGLS 和 NSGA-Ⅱ表现的更加出色或者 表现相近。实验也表明目标正态化的 MOEA/D 算法可以解决规模围相异的多目标问题，同 时使用一个先进分解方法的 MOEA/D 可以产生一组分别非常均匀的解对于有 3 个目标问题 的测试样例。最后，MOEA/D 在较小种群数量是的性能，还有可扩展性和敏感性都在本篇 论文过实验经行了相应的研究。
I. 介绍
多目标优化问题可以用下面式子表示：
其中 Ω 是决策空间， 以得到的目标集合成为
，包含了 m 个实值目标方法， 被称为目标区间。对于可 。
如果
，并且所有的目标函数都是连续的，那么 Ω 则可以用
其中 hj 是连续的函数，我们可以称(1)为一个连续的多目标优化问题。 如果目标函数互斥，那么同时对所有目标函数求最优解往往是无意义的。有意义的是获
得一个能维持他们之间平衡的解。这些在目标之间获得最佳平衡的以租借被定义 Pareto 最 优。
令 u, v∈Rm，如果
对于任意的 i，并且至少存在一个
，那
么 u 支配 v。如果在决策空间中，没有一个点 F(y)能够支配 F(x)点，那么 x 就是 Pareto 最优， F(x)则被称为 Pareto 最优向量。换句话说，对于 Pareto 最优点在某一个目标函数上的提高， 都会造成至少一个其余目标函数的退化。所有 Pareto 最优解的集合称为 Pareto 集合，所有 最优向量的集合被称为 Pareto 前沿。
在许多多目标优化的实际应用中，通过选择器选择一个接近 Pareto 最优前沿的解作为 最后的解。大多数多目标优化问题都有许多甚至是无穷个 Pareto 最优向量，如果想要获得 一个完整的最优前沿，将是一件非常耗时的事情。另一方面，选择器可能不会专注于获得一 个过于庞大的最优解向量集合来解决问题，因为信息的溢出。因此，许多多目标优化算法往 往是获得一个均匀分布在 Pareto 最优前沿周围的最优解向量，这样就具有更好的代表性。 许多研究人员也致力于使用数学模型来获得一个近似的最优前沿。
一般来说，在温和控制下多目标优化问题的 Pareto 最优解，可以看做是一个标量优化 问题的最优解(其中目标函数是 fi 的集合)。因此，Pareto 最优前沿的近似求解可以被分解为
NSGA-II 算法实例 目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。 一、 数值例子 多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1． 适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2． 调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations', 200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200， 适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)
粒子群算法程序 tic D=10;%粒子群中粒子的个数 %w=0.729;%w为惯性因子 wmin=1.2; wmax=1.4; c1=1.49445;%正常数，成为加速因子 c2=1.49445;%正常数，成为加速因子 Loop_max=50;%最大迭代次数 %初始化粒子群 for i=1:D X(i)=rand(1)*(-5-7)+7; V(i)=1; f1(i)=X(i)^2; f2(i)=(X(i)-2)^2; end Loop=1;%迭代计数器 while Loop<=Loop_max%循环终止条件 %对粒子群中的每个粒子进行评价 for i=1:D k1=find(1==Xv(i,:));%找出第一辆车配送的城市编号 nb1=size(k1,2);%计算第一辆车配送城市的个数 if nb1>0%判断第一辆车配送城市个数是否大于0，如果大于0则 a1=[Xr(i,k1(:))];%找出第一辆车配送城市顺序号 b1=sort(a1);%对找出第一辆车的顺序号进行排序 G1(i)=0;%初始化第一辆车的配送量 k51=[]; am=[]; for j1=1:nb1 am=find(b1(j1)==Xr(i,:)); k51(j1)=intersect(k1,am);%计算第一辆车配送城市的顺序号 G1(i)=G1(i)+g(k51(j1)+1);%计算第一辆车的配送量 end k61=[]; k61=[0,k51,0];%定义第一辆车的配送路径 L1(i)=0;%初始化第一辆车的配送路径长度 for k11=1:nb1+1 L1(i)=L1(i)+Distance(k61(k11)+1,k61(k11+1)+1);%计算第一辆车的配送路径长度end else%如果第一辆车配送的城市个数不大于0则 G1(i)=0;%第一辆车的配送量设为0 L1(i)=0;%第一辆车的配送路径长度设为0 end
用于约束多目标优化问题的双群体差分进化算 法精编 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] 对当前基于进化算法的各种约束处理方法进行了较为详细的综述. 对于约束优化问题的约束处理方法基本上分为两类：基于 罚函数的约束处理技术和基于多目标优化技术的约束处理
多目标优化算法与求解策略 2多目标优化综述 2.1多目标优化的基本概念 多目标优化问题(Multi-objective Optimization Problem，MOP)起源于许多实际复杂系统的设计、建模和规划问题，这些系统所在的领域包括工业制造、城市运输、资本预算、森林管理、水库管理、新城市的布局和美化、能量分配等等。几乎每个重要的现实生活中的决策问题都要在考虑不同的约束的同时处理若干相互冲突的目标，这些问题都涉及多个目标的优化，这些目标并不是独立存在的，它们往往是祸合在一起的互相竞争的目标，每个目标具有不同的物理意义和量纲。它们的竞争性和复杂性使得对其优化变得困难。 多目标最优化是近20多年来迅速发展起来的应用数学的一门新兴学科。它研究向量目标函数满足一定约束条件时在某种意义下的最优化问题。由于现实世界的大量问题，都可归结为含有多个目标的最优化问题，自70年代以来，对于多目标最优化的研究，在国内和国际上都引起了人们极大的关注和重视。特别是近10多年来，理论探索不断深入，应用范围日益广泛，研究队伍迅速壮大，显示出勃勃生机。同时，随着对社会经济和工程设计中大型复杂系统研究的深入，多目标最优化的理论和方法也不断地受到严峻挑战并得到快速发展。近几年来，将遗传算法(Genetic Algorithm，GA)应用于多目标优化问题成为研究热点，这种算法通常称作多目标优化进化算法或多目标优化遗传算法。由于遗传算法的基本特点是多方向和全局搜索，这使得带有潜在解的种群能够一代一代地维持下来。从种群到种群的方法对于搜索Pareto解来说是十分有益的。 一般说来，科学研究与工程实践中许多优化问题大都是多目标优化问题。多目标优化问题中各目标之间通过决策变量相互制约，对其中一个目标优化必须以其它目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。与单目标优化问题的本质区别在于，多目标优化问题的解不是唯一的，而是存在一个最优解集合，集合中
龙源期刊网 https://www.doczj.com/doc/e68363753.html, 多目标优化进化算法比较综述 作者：刘玲源 来源：《决策与信息·下旬刊》2013年第07期 摘要多目标优化是最优化领域的一个重要研究方向，本文简要介绍了多目标优化的模型和几种多目标优化的进化算法，并对算法进行了简要比较。 关键词多目标优化粒子群遗传算法蚁群算法人工免疫系统 中图分类号：TP391 文献标识码：A 一、背景 多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。 二、不同算法介绍 （一）多目标遗传算法。 假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。 （二）人工免疫系统。 人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。 （三）多目标PSO约束算法。
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 选择共享适应度较大的个体进入下一代 优点：能够快速找到一些好的非支配最优解域 能够维持一个较长的种群更新期 缺点：需要设臵共享参数 需要选择一个适当的锦标赛机制 限制了该算法的实际应用效果
多目标优化的求解方法 多目标优化(MOP)就是数学规划的一个重要分支,就是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下: 多目标优化方法本质就是将多目标优化中的各分目标函数,经处理或数学变换,转变成一个单目标函数,然后采用单目标优化技术求解。目前主要有以下方法: （1）评价函数法。常用的方法有:线性加权与法、极大极小法、理想点法。评价函数法的实质就是通过构造评价函数式把多目标转化为单目标。 (2)交互规划法。不直接使用评价函数的表达式,而就是使决策者参与到求解过程,控制优化的进行过程,使分析与决策交替进行,这种方法称为交互规划法。常用的方法有:逐步宽容法、权衡比替代法,逐次线性加权与法等。 (3)分层求解法。按目标函数的重要程度进行排序,然后按这个排序依次进行单目标的优化求解,以最终得到的解作为多目标优化的最优解。 而这些主要就是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法与蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都就是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其她若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少与总的运输费用最低, 这就是含有两个目标的优化问题。利用首次适配递减算法与标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合
多目标优化方法 基本概述几个概念优化方法 一、多目标优化基本概述 现今，多目标优化问题应用越来越广，涉及诸多领域。在日常生活和工程中，经常要求不只一项指标达到最优，往往要求多项指标同时达到最优，大量的问题都可以归结为一类在某种约束条件下使多个目标同时达到最优的多目标优化问题。例如：在机械加工时，在进给切削中，为选择合适的切削速度和进给量，提出目标：1)机械加工 成本最低2)生产率低3)刀具寿命最长；同时还要满足进给量小于加工余量、刀具强度等约束条件。 多目标优化的数学模型可以表示为： X=[x i,x 2,…,x n ] T ---------------------------------- n 维向量 min F(X)=[f i(X),f 2(X),…,f n(X)] T- --------- 向量形式的目标 函数 s.t. g i(X) < 0,(i=1,2,…,m) h j (X)=0,(j=1,2,…,k) ------ 设计变量应满足的约 束条件 多目标优化问题是一个比较复杂的问题，相比于单目标优化问题，在 多目标优化问题中，约束要求是各自独立的，所以无法直接比较任意两个解的优劣。 二、多目标优化中几个概念：最优解，劣解，非劣解。 最优解X*:就是在乂所在的区间D中其函数值比其他任何点的函数值要小即f(X *) 如图：在［0,1］ 中 X*=1为最优解 在［0,2］ 中X*=a为劣解 在［1,2］ 中X*=b为非劣解 多目标优化问 题中绝对最优解存 在可能性一般很 小，而劣解没有 意义，所以通常去 求其非劣解来解决 问题。 三、多目标优化方法 多目标优化方法主要有两大类： 1)直接法：直接求出非劣解，然后再选择较好的解 将多目标优化问题转化为单目标优化问题。 2)间接法女口：主要目标法、统一目标法、功效系数法等。 将多目标优化问题转化为一系列单目标优化问题。女口：分层系列法等。 1、主要目标法 求解时从多目标中选择一个目标作为主要目标，而其他目标只需满足一定要求即可，因此可将这些目标转化成约束条件，也就是用约束条件的形式保证其他目标不致太差，这样就变成单目标处理方法。 例如：多目标函数f 1(X),f 2(X),.?…,f n(X)中选择f k(X)作为主 要目标，这时问题变为求min f k(x) D={x|f min < f i(X)< f ma》,D为解所对应的其他目标函数应满足上下限。 2、统一目标法 通过某种方法将原来多目标函数构造成一个新的目标函数，从而将多目标函数转变为单目标函数求解。 ①线性加权和法 根据各目标函数的重要程度给予相应的权数，然后各目标函数与 多目标优化的求解方法 多目标优化（MOP）是数学规划的一个重要分支，是多于一个的数值目标函数在给定区域上的最优化问题。 多目标优化问题的数学形式可以描述为如下： 多目标优化方法本质是将多目标优化中的各分目标函数，经处理或数学变换，转变成一个单目标函数，然后采用单目标优化技术求解。目前主要有以下方法： （1）评价函数法。常用的方法有:线性加权和法、极大极小法、理想点法。评价函数法的实质是通过构造评价函数式把多目标转化为单目标。 （2）交互规划法。不直接使用评价函数的表达式，而是使决策者参与到求解过程，控制优化的进行过程，使分析和决策交替进行，这种方法称为交互规划法。常用的方法有：逐步宽容法、权衡比替代法，逐次线性加权和法等。 （3）分层求解法。按目标函数的重要程度进行排序，然后按这个排序依次进行单目标的优化求解，以最终得到的解作为多目标优化的最优解。 而这些主要是通过算法来实现的, 一直以来很多专家学者采用不同算法解决多目标优化问题, 如多目标进化算法、多目标粒子群算法和蚁群算法、模拟退火算法及人工免疫系统等。 在工程应用、生产管理以及国防建设等实际问题中很多优化问题都是多目标优化问题, 它的应用很广泛。 1)物资调运车辆路径问题 某部门要将几个仓库里的物资调拨到其他若干个销售点去, 在制定调拨计划时一般就要考虑两个目标, 即在运输过程中所要走的公里数最少和总的运输费用最低, 这是含有两个目标的优化问题。利用首次适配递减算法和标准蚁群算法对救灾物资运输问题求解, 求得完成运输任务的最少时间, 将所得结果进行了比较。 2)设计 如工厂在设计某种新产品的生产工艺过程时, 通常都要求产量高、质量好、成本低、消耗少及利润高等, 这就是一个含有五个目标的最优化问题; 国防部门在设计导弹时, 要考虑导弹的射程要远、精度要最高、重量要最轻以及消耗燃料要最省等,这就是一个含有四个目标的最优化问题。Jo等人将遗传算法与有限元模拟软件结合应用于汽车零件多工序冷挤压工艺的优化。Chung等人也成功应用遗传算法对锻件工艺进行了优化。 3)投资 假设某决策部门有一笔资金要分配给若干个建设项目, 在确定投资方案时, 决策者总希望做到投资少收益大。Branke等人采用基于信封的多目标进化算法成功地解决了计划投资地选择问题。 4)模拟移动床过程优化与控制 一个工业化模拟移动床正常运行时, 一般有七股物料进、出吸附塔, 其中起关键作用的物料口将作为决策量引起目标值的变化。根据实际生产要求通常包括生产率、产品纯度、吸附剂消耗量等多个目标。模拟移动床分离过程由于其过程操作变量的强耦合性、工艺机理的复杂性及分离性能的影响因素繁多性, 需要众多学者对其操作优化和过程控制进行深入的研究。Huang等人利用TPS 算法解决了模拟移动床多个冲突目标的最大最小的问题, 并与NSGA2 算法的结果进行了比较。吴献东等人运用粒子群算法开发出一种非线性模拟移动床( SMB )色谱分离过程的优化策略。 5)生产调度 在离散制造生产系统中, 一个工件一般经过一系列的工序加工完成, 每道工序需要特定机器和其他资源共同完成, 各工件在各机器上的加工顺序(称技术约束条件)通常是事先给定的。车间调度的作用 第六章最优化数学模型 §1 最优化问题 1．1 最优化问题概念 1．2 最优化问题分类 1．3 最优化问题数学模型 §2 经典最优化方法 2．1 无约束条件极值 2．2 等式约束条件极值2．3 不等式约束条件极值 §3 线性规划 3．1 线性规划 3．2 整数规划 §4 最优化问题数值算法4．1 直接搜索法 4．2 梯度法 4．3 罚函数法 §5 多目标优化问题 5．1 多目标优化问题 5．2 单目标化解法 5．3 多重优化解法 5．4 目标关联函数解法5．5 投资收益风险问题 第六章 最优化问题数学模型 §1 最优化问题 1．1 最优化问题概念 （1）最优化问题 在工业、农业、交通运输、商业、国防、建筑、通信、政府机关等各部门各领域的实际工作中，我们经常会遇到求函数的极值或最大值最小值问题，这一类问题我们称之为最优化问题。而求解最优化问题的数学方法被称为最优化方法。它主要解决最优生产计划、最优分配、最佳设计、最优决策、最优管理等求函数最大值最小值问题。 最优化问题的目的有两个：①求出满足一定条件下，函数的极值或最大值最小值；②求出取得极值时变量的取值。 最优化问题所涉及的内容种类繁多，有的十分复杂，但是它们都有共同的关键因素：变量，约束条件和目标函数。 （2）变量 变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量。一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联。 设问题中涉及的变量为n x x x ,,,21 ；我们常常也用),,,(21n x x x X =表示。 （3）约束条件 在最优化问题中，求目标函数的极值时，变量必须满足的限制称为约束条件。 例如，许多实际问题变量要求必须非负，这是一种限制；在研究电路优化设计问题时，变量必须服从电路基本定律，这也是一种限制等等。在研究问题时，这些限制我们必须用数学表达式准确地描述它们。 用数学语言描述约束条件一般来说有两种： 等式约束条件 m i X g i ,,2,1,0)( == 不等式约束条件 r i X h i ,,2,1, 0)( =≥ 或 r i X h i ,,2,1, 0)( =≤ 注：在最优化问题研究中，由于解的存在性十分复杂，一般来说，我们不考虑不等式约束条件0)(>X h 或0)( 第七章多目标优化问题的求解 优化问题按照目标函数的数量，可以分为单目标优化问题和多目标优化问题，前面我们讲过的线性优化就是一个单目标优化问题，对单目标优化问题进一步突破，将目标函数扩展为向量函数后，问题就转化为多目标优化问题。本节将简要介绍多目标最优化问题的建模与求解方法。 1、多目标优化模型 多目标优化问题一般表示为 ..()min () s t J ≤= x G x 0 x F 其中121()[(),(),,()]T f f f =F x x x x ，下面将通过例子演示多目标优化问题的建模。 例1 设某商店有123,,A A A 三种糖果，单价分别为4,2.8和2.4元/kg ，现在 要举办一次茶话会，要求买糖果的钱不超过20元，但糖果的总重量不少于6kg ， 1A 和2A 两种糖果的总重量不低于3kg ，应该如何确定最好的买糖方案。 分析：首先应该确定目标函数如何选择的问题，本例中，好的方案意味着少花钱多办事，这应该是对应两个目标函数，一个是花钱最少，一个是买的糖果最重，其他的可以认为是约束条件。当然，这两个目标函数有些矛盾，下面考虑如何将这个问题用数学描述。 设123,,A A A 三种糖果的购买重量分别为123,,x x x kg ，这时两个目标函数分别为花钱：1123min ()4 2.8 2.4f x x x =++x ，糖果总重量：2123max ()f x x x =++x ，如果统一用最小值问题表示，则有约束的多目标优化问题可以表示为 123123123123121234 2.8 2.4min -4 2.8 2.4206.. +3,,0 x x x x x x x x x x x x s t x x x x x ++?? ??++??++≤??++≥?? ≥??≥?（）模型建立以后，可以考虑用后面的方法进行求解。多目标优化的求解方法
多目标最优化数学模型
多目标优化问题(over)
相关主题
文本预览