《多目标优化的一类模拟退火算法》由会员分享，可在线阅读，更多相关《多目标优化的一类模拟退火算法（5页珍藏版）》请在金锄头文库上搜索。
1、2002.8计算机工程与应用1引言大量工程优化问题往往涉及多个目标的同时优化， 但各目标间常存在冲突， 因此寻求多目标优化问题的Pareto最优解一直是运筹学中重要的研究课题1-4。 传统多目标优化技术主要是目标规划 （goai programming） ， 尽管它具有快速性， 但对目标函数有凸 （凹） 性、 连续性、 甚至线性等要求， 且难以给定各目标合适的权重， 从而限制了其应用领域。近年来， 借鉴生物学、 物理学、 人工智能思想发展起来的Meta-heuristic算法5，6， 如遗传算法、 模拟退火和禁忌搜索， 因其独特的优化机制及其通用性、 灵活性而在优化领域得到了广泛重视和深入研究
2、与应用， 但其在多目标优化领域的研究还处于起步阶段1-4。 文章通过对搜索操作和参数的合理设置， 提出了一类求解多目标Pareto最优解的高效模拟退火算法，在多次运行或并行实现条件下可得到Pareto边界 （Pareto-frontier） 上多个不同方向的Pareto最优解，数值仿真验证算法的有效性。2问题描述考虑带约束多目标优化问题， 如式 （1） ， 其中包括I个决策变量x1、 、xI，K个形式不限的不同优化目标f1、 、fK和M个形式不限的不同约束g1、 、gM。Minimize fi（x1， ，xI） ，i=1，2， ，K，Subject to g （x1， ，xI） ， =1，2，
3、 ，M!.（1）区别于单目标优化，多目标优化的各目标间往往存在冲突。对于解空间中任意两点X1、X2， 若对于任意i!1， ，K满足fi（X1）“fi（X2） 且至少存在一个 !1， ，K满足f （X1）random（0，l） 则仍用X替代X； 再否则保留X。（4） 判断当前温度下抽样准则是否满足， 若是则继续以下步骤， 否则返回步骤 （2） 。（5） 进行退温操作，tk+l:!tk， 并令k=k+l。（6） 判断算法终止准则是否满足， 若是则结束搜索并输出X*， 否则返回步骤 （2） 。上述算法流程保留了传统SA的特点， 用加权综合目标进行多目标优化的考核。由于权值的随机性， 多次运行或并行实
4、现该算法可得到Pareto边界上多个不同方向的Pareto最优解，从而可为决策者提供多个选择。需要强调的是：（l） 步骤 （l） 中初温由式t0:-（Fmax-Fmin）/In Pr确定， 其中Fmax、Fmin分别为初始L个解的最大、最小综合目标值，Pr!（0，l） 为初始控制接受概率。由于初态的随机性， 当数量L足够多时可一定程度上体现了整个解空间中状态的分布情况， 而通过定义pr来确定初温， 考虑了各状态的相对性能， 能赋予不同状态合适的突跳概率且一定程度上能避免初温选取的盲目性6，7。另外， 步骤 （5） 采用指数退温意在折衷优化度和效率6，7。（2）SA区别于传统规划算法的关键之一在
5、于邻域函数的设计， 作者在文献8详细讨论了函数优化问题的模拟退火算法状态发生器的设计，该文简单采用附加Gaussian分布扰动方式， 即x=x+“#，#!N（0，l） ，“为步长。为了避免优良解的遗失， 算法在步骤 （3） 概率接受的同时附加了保优操作。（3） 步骤 （4） 可采用传统SA的定步长法， 即连续Sl步抽样； 区别于传统SA对终止温度的设置， 该文采用最优解滞留步数检验策略，即若最优解在连续S2步退温期间均不变则认为收敛， 如此来避免过多无谓搜索和优化度的严重下降4数值仿真与分析上述模拟退火算法具有很强的通用性，对目标f和约束g没有任何限制， 可应用于任何形式的多目标优化问题， 在
6、此仅以两个典型算例来验证算法的有效性。其中， 式 （2）2是一个双目标线性规划问题， 线性规划软件包 （LP） 对fl进行单目标优化的结果为xl:4.25，x2:2.25，fl*:-2375，f2:-2l75， 对fl进行单目标优化的结果为xl:3.75，x2:2.75，fl:-2325，f2*:-2225， 其中带*数据为最优值； 式 （3）3非线性多目标优化问题， 传统方法难以求解。在此利用所提出的SA各进行l000次随机优化 （或l000个处理机的一次并行优化） ，取L:20、pr=0.l、!:0.9、“:0.l、Sl:50、S2:30， 以优化目标为座标的解分布如图l和图2所示， 表l
7、给出了典型的l5个Pareto最优解。Minimize fl=-400xl-300xn；f2=-300xl-400x2.Subject to 4xl“20；2xl+6x2“24；l2xl+4x2“603x2“l0.5；4xl+4x2“26；xl#0；x2#0!# “# $.；（2）Minimize fl=l/（x2l+x22+l） ；f2=x2l+3x2l+l. Subject to xl!-3，3；x2!-5，5%.（3）此外， 为了考察算法的优化度， 对式 （2） 的约束加以修改，如式 （4） 。此时理论上该问题以任何一个目标进行单目标优化或双目标得到的解均一样， 即xl*:4.995，x
8、2*:3.l3，fl*:-2937，f2*:-2750.5。Subject to 4xl“l9.98；2xl+6x2“28.78；l2xl+4x2“72.48；3x2“9.39；4xl+4x2“32.5；xl#0；x2#0%.（4）该文SA方法得到的解为xl:4.994803，x2:3.l29594，fl:-2936.799l4l，f2:-2750.278244，它与理论最优解的相对误差依次为0.00394%，0.0l3%，0.00684%，0.00806%。图lSA对式 （2） 多目标优化解分布图图2SA对式 （3） 多目标优化解分布图表lSA得到的多目标Pareto最优解由此可见， 该算法
9、具有以下优点：（l） 多解性。SA能较好地实现多目标优化， 并得到Pareto边界上多个不同方向的最优解 （图l和图2表明SA对两算例实现Pareto最优化的成功率均在95%以上） ，进而可为决策者提供多个选择。（2） 最优性。SA能够保证取得较好的优化质量， 对式 （4） 的优化表明了SA较高的优化精度。（3） 鲁棒性。尽管SA采用随机初始化， 但所得结果在Pareto最优意义下基本一致， 这说明了算法较好的初值鲁棒性。（4） 快速性。在PII366计算机上SA对各算例的平均优化时间小于0.08秒。（下转55页）算例式 （2）算例式 （3）xlx2flf2xlx2flf2l3.75022.7
10、495-2324.9297-2224.8627l.0002-0.00040.49992.000323.75582.7439-2325.49l0-2224.30l8l.46980.00730.3l643.l60633.75832.74l2-2325.66l2-2223.9520l.24690.00l00.39l42.554643.78952.7l05-2328.9352-222l.04l02.3203-0.00l50.l5676.383654.02752.47l9-2352.5868-2l97.02l82.02900.00290.l9545.ll7064.l96l2.3039-2369.6034
11、-2l80.383ll.03l90.00260.48432.064974.20622.2936-2370.5634-2l79.3038l.00230.06800.49772.0l8584.23832.26l4-2373.7466-2l76.0522l.675l0.00l80.26283.805994.24092.2588-2374.0l54-2l75.8003l.2938-0.00250.37402.6738l0 4.24342.2558-2374.0980-2l75.3403l.8405-0.003l0.22794.3873ll 4.24632.253l-2374.4490-2l75.l3l
12、l2.53330.00l60.l3487.4l74l2 4.24652.2533-2374.5462-2l75.25872.72780.00l00.ll858.4407l3 4.24832.25l5-2374.788l-2l75.l0332.l2960.00390.l8075.5350l4 4.24852.25l5-2374.8244-2l75.l268l.5293-0.00l50.29953.3387l5 4.24982.250l-2374.93ll-2l74.96l7l.0002-0.00350.49992.0005仿 真 次 数5计算机工程与应用2002.8（上接5页）因此， 该文提出的
13、SA算法是一类有效的多目标优化算法。5小结文章提出了一类求解多目标Pareto最优解的高效SA算法， 在多次运行或并行实现条件下可得到Pareto边界上多个不同方向的Pareto最优解， 数值仿真验证了算法的有效性。结合遗传算法、 进化规划等方法提出群体并行搜索Pareto最优解的算法是下一步的研究内容。 （收稿日期：2002年1月）参考文献1.Jones D F，Mirrazavi S K，Tamiz M.Muiti-objective meta-heuristics：an overview of the current state-of-the-artJ.European J of Ope
14、ra- tionai Research，2002；137：1-92.Zeieny M.Muitipie criteria decision making：eight concepts of opti-maiityJ.uman Systems Management，1998；17：97-1073.leung Y W，Wang Y.Muitiobjective programming using uniform de-sign and genetic aigorithmJ.IEEE Trans Systems，Man and Cyber-netics-C，2000；30（3） ：293-3044.
15、baykasogiu A，Owen S，Gindy .A taboo search based approach tofind the pareto optimai set in muitipie objective optimizationJ.Engi-neering optimization，1999；31（6） ：731-7485.王凌， 郑大钟.Meta-heuristic算法研究进展J.控制与决策，2000；15（3） ：257-2626.王凌.智能优化算法及其应用M.北京：清华大学出版社，20017.Wang l，Zheng D Z.An effective hybrid opti
16、mization strategy for jobshop scheduiing probiemsJ.Computers and Operations Research，2001；28（6） ：585-5968.王凌， 郑大钟.基于Cauchy和Gaussian分布状态发生器的模拟退火算法J.清华大学学报，2000；40（9） ：109-112输出软件工程与软件工程管理， 按照软件工程来规范开发方的开发过程， 参照CMM模型， 分析开发方在软件过程及其管理方面的薄弱环节， 帮助开发方根据自身的特点与条件， 制订本企业的软件过程和选择实行改进的部分。 从而促进开发方规范化、 工程化生产， 改进软件过程， 提高软件能力成熟度， 提高自身的竞争力。 4.2保证质量保证系统质量， 是信息项目监理最根本、 最核心的作用。 把好质量关、 技术关是监理方的天职， 从项目各阶段里程碑的设定、 质量检验、 文档交付到验收确认， 处处都要将项目实施置于一种规范化管理中， 从第三
