资源描述：
《应用遗传算法求解多目标0_1规划问题_孙艳丰.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第5卷第4期决策与决策支持系统Vol.5No.41995年JOURNALOFDECISIONMAKINGANDDECISIONSUPPORTSYSTEMS1995应用遗传算法求解多目标¹0一1规划问题叠孙艳丰王众托(北方交通大学运输模拟中心)(大连理工大学系统工程研究所)【摘要】遗传算法是求解大型优化问题非常有效的算法。本文提出一种多目标规,,划问题适应性值的定义方式利用遗传算法用于O一l规划问题的天然优越性。,首次尝试用遗传算法求解多目标0一1规划问题实验表明本文的算法有很好。已经集成到一个0。的计算效果这些算法一l规划
2、的软件包中,,关键词:遗传算法O一1规划多目标优化1引言,在系统工程与运筹学的优化问题中有相当一部分可以表示为多目标0一l规划问题,虽然目前已有一些求解这类问题的算法,但它们远远不能满足实际需要。从长远看,一,由于。1变量跨接了数值分析与逻辑分析两个领域川所以很可能成为解决复合型问题,,的得力工具因此探索多目标0一l规划的有效求解方法特别是大型问题的解法是很有意义。的目前,求解多目标规划问题的算法或求出问题的所有非劣解,决策人从中选择满意;。解或者在求解过程中根据决策人的意向按一定的策略逐渐找出一个满意解前者虽然求出了全部
3、非劣解,但却把困难推给了决策人,没有系统分析人员的帮助,从众多的非劣解中选择满意解也是很困难的,所以,更有效、实用的还是后者。基于这种思想,本文用遗,,传算法解多目标O一1规划问题时也试图通过决策人的参与求出令其满意的非劣解同时根据一1,,,0规划问题的特点设计了合理的编码及适应性值的定义方式实验表明这。,O。种方法具有很好的计算效果本文算法已编成软件集成到一个一1规划软件包中2遗传算法简单地说,遗传算法是以自然选择和遗传学原理为基础,将自然界生物进化过程中适工博士后基金资助项目。,,º孙艳丰:北方交通大学博士后通讯地址:
4、北方交通大学运输模拟中心邮政编码:100科,,。王众托:大连理工大学教授博士导师邮政编码116024第4期孙艳丰等:应用遗传算法求解多目标0一1规划问题103一一者生存规划同随机计算相结合而形成的一种有目的的搜索算法,它在搜索之前先将变量按某种形式进行编码(编码后的变量称为染色体),不同的染色体构成一个群体,每个染色体则成为群体中的一个个体。对每个个体,将按某种方式评估出其适应性值。新一代群体的产生是按下面两个步骤完成的。首先,根据个体的适应性值选择被保留的个体以及相应的;然后对被选择的个体进行重组、,。复制次数变异产生新
5、的个体遗传算法的基本执行过:程是随机选择N个初始点(称为一个群体,每个点称为一个个体),,x,(0)x;⋯J并将,k。这N个点进行编码一O(l)计算每个个体的适应性值f(x;),⋯,f(x穿)。,,’,,‘,(2)选择(seleetion):从x⋯x中选择X⋯X且每个X(‘;穿;穿关二1,2,一,N)被选中的概率为丫f(x;)/叉厂(x;)‘,,,重组(Recombination):从x⋯X’中以相同概率随机选出两个个体这两(3):艺个个体之间以事先给定的概率值执行重组运算,产生两个新个体,重复这一过程,直至·,,x“。形
6、成新群体x;一之:(4)变异(Mutation)变异运算根据一定的变异率随机地对每个个体的每一位改变其,+,,,x,。编码值形成新一代群体x:⋯入,,,。(5)检验停机准则满足否如果满足停止运算;否则令k+1冷k转(l),,:作为一种搜索算法与传统的搜索算法相比遗传算法具有如下特点(l)搜索时不直接使用变量本身,而使用它的编码。(2)搜索过程从搜索空间中的一组点迭代到另一组点,这样就减少了陷人局部最优解的可能性。(3)搜索时只需计算适应性值,而不需要导数或其他辅助信息,因而具有广泛的适用性。4,因而能搜索有噪声的、()搜索
7、时使用的不是确定性规则而是概率规则指导搜索多峰的复杂空间。,,。关于遗传算法的更多细节参见文献〔23〕3多目标规划方案的排序法,文〔4〕提出一种多目标决策方案排序的相似优序值法其表述如下:,,,设某一多目标决策问题有p个目标‘、(k二1川权重分别为w、并设已有N一,,;‘,个决策方案A(i一l~一N),A在目标G、下的取值为。*(i=1“一N;k,,。,二l⋯川设各目标均为正向目标(指目标值越大越好)方案排序的目的是通过综合比较,明确各方案的优劣程度。一104—决策与决策支持系统1995年A+。,“.,A,一,,先选取一个
8、基准方案(亡一J)作为比较的基础将(i一的+,与A比较令‘、a,*ad一一-JGG·"。.工·气气,J.leses.0A一.L心叭...0.O⋯万ll⋯⋯⋯:⋯⋯:⋯、‘、+,。峨反映了方案A的目标G下偏离A的程度所以称D为偏离矩阵,,首先考虑在目标‘*(k一1川下对各方案进行单目标排序设一,,,,D*
