资源描述：
《利用多群体dna遗传算法求解线性规划问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、利用多群体DNA遗传算法求解线性规划问题崔志华曾建潮太原重型机械学院系统仿真与计算机应用研究所030024摘要针对经典遗传算法存在的问题提出了多群体DNA遗传算法该方法在经典遗传算法的基础上通过借鉴生物学及社会学引入了多群体及DNA片断等概念并提出迁移与自适应变异算子可以提高遗传算法的有效性与收敛性为了验证算法的有效性将该算法应用于线性规划问题的求解在求解过程中首先利用熵障碍对偶方法对原问题进行转换然后使用多群体DNA遗传算法对转换后的目标函数进行求解仿真结果表明该方法具有良好的全局搜索能力和较快的收敛速度以上工作为解决大规模线性规划问题的求解提供了全新的思路和方法对遗传算法应用的发展具
2、有重要意义主题词DNA遗传算法多群体线性规划熵障碍对偶法UsingDNAGeneticAlgorithmwithMulti-PopulationtoSolveLPCuiZhihuaZengJianchao(Divisionofsystemsimulationandcomputerapplication,TaiyuanHeavyMachineryInstitute,030024)Abstract:DNAgeneticalgorithmwithmulti-populationispresentedforovercomingtheslowandprematureconvergenceofthe
3、classicgeneticalgorithm.Inordertoenhancethevalidityandconvergenceofthegeneticalgorithm,theconceptssuchasmulti-population,DNAfractionareintroducedbylearningfrombiologyandsociology.andthemigrationandmutationoperatorsarealsointroduced.Toprovethevalidity,thealgorithmisusedtosolvingthelinearprogrammin
4、gquestion.Atfirst,thequestionistranslatedbyusingentropicperturbation,thenDNAgeneticalgorithmwithmulti-populationisusedtosolvetheabovequestion,sotheresultiscalculated.Theoptimizationcomputingofsomeexamplesismadetoshowthatthenewgeneticalgorithmhasbetterglobalsearchcapacityandrapidconvergencerate.Th
5、eaboveworkprovidesanewideaandmethodforsolvinglarge-scopelinearprogrammingquestionandcontributesmuchtodevelopmentoftheapplicationofgeneticalgorithm.Keywords:DNAGeneticAlgorithmMulti-PopulationLinearProgramming(LP)EntropicPerturbation1.引言[1][2]单纯形法是解线性规划问题的最常用方法,可它不是一种多项式算法.椭圆算法的提出,使人们认识到线性规划问题存在多项
6、式方法.但椭圆算法本身在实际中的应用却并不成[3]功.内点法是新的一类多项式算法,尽管它在求解大规模线性规划问题方面显示了相当的潜力,其算法的精度和软件的开发都有待完善和发展.常规遗传算法是从生命的遗传机理开发得到的,它是解决复杂问题的全局优化算法,虽然遗传算法有优良的全局搜索能力,但由于它是基于0-1编码模型的遗传操作,局部搜索解空间不是很有效,且个体的多样性有时减少很快.常规遗传算法用于处理实际问题,尤其是处理复杂的混淆的和多任务问题时不够灵活,计算速度慢.且常规遗传算法模型不可能表达丰富的遗传信息,也不可能反映遗传信息对生物体生长,发育的调控作用.从DNA计算角度看,在所有基于进化
7、机理的方法中,遗传算法最适合采用DNA来实现.这是由于在遗传算法中,问题最优解的搜索是通过对染色体的位串结构的个体采用交叉和变异操作,不断的产生个体而获取的.[4]但是文仅仅利用DNA遗传算法来实现,收敛速度较慢,同时变异算子作为遗传算法的主要算[4]子,在文也过于简单故本文利用多群体来进行遗传.以提高搜索速度和效率,同时对变异算子使用自适应的方式,以提高精度.[5]本文讨论了熵障碍对偶方法的目标函数,利用多群体DNA遗传算法,对线
