资源描述：
《用改进遗传算法求解影片投递问题(FDP)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第23卷第1期计 算 技 术 与 自 动 化Vol123,No112004年3月ComputingTechnologyandAutomationMar12004文章编号:1003-6199(2004)01-0033-04用改进遗传算法求解影片投递问题(FDP)12王美华,杨德贵(1.华南农业大学信息学院,广东广州 510642;2.华南农业大学理学院,广东广州 510642)摘 要:影片投递问题是近十几年来研究相当活跃的旅行商问题(TSP)的拓展,是组合优化的新问题。FDP也是一个NP难问题,且一般比TSP要难解
2、得多。本文采用改良点编码方案,运用惩罚函数、禁止相同基因段交叉和重置变异参数的技术以避免非可行解的干扰,通过测试发现:标准遗传算法的选择机制和FDP问题求解的常用交叉和变异方法,两者之间的简单撮合很难实现求解。经多次试验数据证明,改进后的算法大大提高了全局收敛性性能。关键词:遗传算法;影片传递问题;全局收敛性中图分类号:TP301.6文献标识码:AImprovedGAAlgorithmforFilmDeliveryProblem12WANGMei2hua,YANGDe2gui(1.CollegeofInforma
3、tion,SouthChinaAgric.Univ.,Guangzhou,510642,China;2.CollegeofScience,SouthChinaAgric.Univ.,Guangzhou,510642,China)Abstract:FilmDeliveryProblem,anewproblemofoptimizationgrouping,istheextensionoftheTravel2ingSalesmanProblem(TSP)onwhichhasbeendoneresearchforover
4、tenyears.FDPisalsoaNPdifficultproblem,andgenerallyspeaking,ishardertosolvethanTSP.Makinguseofthesystemofimprovingdotcod2ingandpunishmentfunction,thethesisattemptstolimittheintersectionofthesamegenesandtoreplacethevariationparameterinordertoavoidtheinterferenc
5、eoftheunfeasiblesolution.Throughtesting,itcanbefoundthatthealternativesystemofthestandardgeneticalgorithmandtheintersectionandvariationusedbyFDPcannotmixtogetasolution.Basedonthenumeroustesting,itcanbeconcludedthattheimprovementofalgorithmpromptsthefunctionto
6、runwellintheaspectofgeneralastringent.Keywords:geneticalgorithm;FilmDeliveryProblem;generalastringent想;另外一种是FDP与TSP的转换,并用启发式算1 引言法进行求解。无论是已经研究多年的TSP还是较新的FDP,人们的讨论与研究重点主要在于以下三FDP是TSP的扩展,若每个电影院的播放次个方面:一、寻找合适的编码和遗传算子,提高编[2]数为1,问题便是经典的TSP问题,FDP已有两码、解码、运算的效率,以及处理有
7、可能产生的非可种解法,一种是在编码、交叉和变异设计上的思行解;二、提高算法的全局收敛性,包括收敛的速度收稿日期:2003-11-12基金项目:广东省教育厅自然研究项目,华南农业大学校长基金作者简介:王美华(1970—),女,江苏常州人,硕士,主要研究方向:人工智能及其应用。©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.34计算技术与自动化2004年3月与质量;三、与其他算法作对比,综合分析,旨在寻[3]回i应该满足4个条件:[2]找效
8、果更优的混和算法。本文着重对第二点,即(1)Pj∈{1,2,⋯,l},vij∈V;希望改进常用的遗传算法,以提高其在求解FDP(2)Pj∈{1,2,⋯,l},vij≠vik,其中k=(j问题上的全局收敛性。+1)modl或k=(j-1)modl;(3)因为主影院作为巡回的起点和终点;所2FDP模型以,vi1=vil=v1;n(4)巡回遍历的电影院数之和为:l=∑di,21
