资源描述：
《基于遗传算法的多目标问题求解方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、水利学报2003年7月SHUILIXUEBAO第7期文章编号:055929350(2003)0720064206基于遗传算法的多目标问题求解方法122游进军,纪昌明,付湘(11中国水利水电科学研究院水资源研究所,北京100044;21武汉大学水利水电学院,湖北武汉430072)摘要:本文利用遗传算法进化过程中每代种群均生成大量可行解的特点,提出一种基于目标序列的排序矩阵评价个体适应度的多目标遗传算法,改进了遗传算法的参数确定方法,有效控制了非劣解集的替换选取过程,使得算法可以一次交互求得非劣解集。最后将该方法应用
2、于供水和发电的综合利用水库的多目标调度中,验证了其可行性。关键词:多目标规划;遗传算法;优化技术;水库调度中图分类号:TV697文献标识码:A寻求非劣解集是多目标决策的基本手段。已有成熟的非劣解生成技术本质上都是以标量优化的手段通过多次计算得到非劣解集。目前遗传算法在多目标问题中的应用方法多数是根据决策偏好信息,先将多目标问题标量化处理为单目标问题后再以遗传算法求解,仍然没有脱离传统的多目标问题分步解决的方式。在没有偏好信息条件下直接使用遗传算法推求多目标问题的非劣解集的研究尚不多见。遗传算法(GeneticAl
3、gorithm,GA)是一种以随机理论为基础的模仿生物进化的搜索方法。近年来,遗传算法在各个科学领域得到广泛运用,在求解一些复杂优化问题已显示出强大能力,具有广泛[1-3]的适应性。国内已经有学者在不同领域研究了遗传算法在多目标问题中的应用。[4-6]国内学者在水库优化调度领域应用遗传算法也取得了一些成果。对于水库多目标优化调度的[7]遗传算法求解也有学者作了尝试。本文根据遗传算法每代均产生大量可行解和隐含的并行性这一特点,设计了一种基于排序的表现矩阵测度可行解对所有目标总体表现好坏的向量比较方法,并通过在个体适
4、应度定标中引入该方法,控制优解替换和保持种群多样性,采用自适应变化的方式确定交叉和变异概率,设计了多目标遗传算法(Multi2ObjectiveGeneticAlgorithm,MOGA)。该算法通过一次计算就可以得到问题的非劣解集,简化了多目标问题的优化求解步骤。1多目标遗传算法的思路和步骤111设计思路多目标问题中在没有给出决策偏好信息的前提下,难以直接衡量解的优劣,这是遗传算法应用到多目标问题中的最大困难。根据遗传算法中每一代都有大量的可行解产生这一特点,我们考虑通过可行解之间相互比较淘汰劣解的办法来达到最
5、后对非劣解集的逼近。考虑一个n维的多目标规划问题,且均为目标函数最大化,其劣解可以定义为:3fi(x)≤fi(xt)i=1,2,⋯⋯,n(1)3[8]且式(1)至少对一个i取“<”。即至少劣于一个可行解的x必为劣解。收稿日期:2002206226基金项目:国家自然科学基金重大项目(50099624);湖北省自然科学基金项目(2001ABB042);国家自然科学青年基金项目(50209011)作者简介:游进军(1977-),男,四川成都人,博士研究生,从事水文学及水资源方面研究。—64—对于遗传算法中产生大量的可行
6、解,我们考虑对同一代中的个体基于目标函数相互比较,淘汰掉确定的劣解,并以生成的新解予以替换。经过数量足够大的种群一定次数的进化计算,可以得到一个接近非劣解集前沿面的解集,在一定精度要求下,可以近似的将其作为非劣解集。个体的适应度计算方法确定后,为保证能得到非劣解集,算法设计中必须处理好以下问题:(1)保持种群的多样性及进化方向的控制。算法需要求出的是一组不同的非劣解,所以计算中要防止种群收敛到某一个解。与一般遗传算法进化到后期时种群接近收敛不同,多目标遗传算法中要求都要保持解的多样性以适应对已得到的优解(也就是最
7、后非劣解集的备选集)能再进行更新。(2)优解的选择替换。算法必须能选出表现更好的解,并避免由于优解的替换不当使得解集收敛于同一个方向,并使得解集的分布具有一定程度的均匀性。从上述思路出发,本文在多目标遗传算法中使用了针对多目标的个体适应度确定方法,对交叉和变异概率依据种群和进化代数进行自适应调整,并控制种群个体并行向非劣解集前沿面逼近。112算法步骤表1基于目标函数的表现矩阵11211适应度确定个体适应度是通过个体间的相互排序目标表现序列12⋯⋯N比较得到,使综合表现优良的个体获得较大适应度。算→Obj(1)X1
8、1X12⋯⋯X1NX1法中个体采用实数编码,只需知道各目标函数的优劣衡→Obj(2)X21X22⋯⋯X2NX2量标准(越大越优,越小越优或中心最优)即可将个体⋯⋯⋯⋯⋯⋯⋯⋯→对目标表现优劣排序。将种群所有个体对各目标表现排Obj(n)Xn1Xn2⋯⋯XnNXn序就能得到表1列出的表现矩阵:表中,Obj(i)(i=1,⋯,n)为目标函数,n为目标个数;N为个体总数,即可行
