资源描述：
《用单亲遗传算法解决影片递送问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、用单亲遗传算法解决影片递送问题摘要姓名:王珍和专业:应用数学导师:行飞遗传算法(简称GA)是基于生物进化原理的普适性全局优化算法，是解决NP难问题的一种行之有效的方法。但是，序号编码的遗传算法不能在任意两条染色体的任意位置进行交叉，必须使用PMX,CX和OX等特殊的交叉算子，这些算子实施起来都很麻烦且效率不高。针对这一问题，采用单亲遗传算法，取消交又操作，强化变异作用。这样既简化了遗传操作，又克服了早熟现象。较成功的解决了影片递送问题，文中的算例表明，该算法是实际有效的。关键词:遗传算法;组合优化;单亲遗传算法;FD
2、P问题SOLVINGFILMDELIVERPROBLEMWITHAPARTHO一GENETICALGORITHMSABSTRACTGeneticAlgorithms(GA)aregeneralpurposeglobaloptimizationalgorithmsbasedonnaturalevolutionprinciple.But,geneticalgorithmsusingordinalstringsmustusespecialcrossoveroperatorssuchasPNX,OXandCX,instead
3、ofgeneralcrossoveroperatiors.ConsideringtheabovedeficiencyofGAusingordinalstrings,thispaperproposesamethod(PGA)thatusesordinalstringsandrepealscrossoveroperatorswhileinstroducessomeparticulargeneticoperatorssuchasgeneexchangeoperatorwhichhavethesamefunctionascr
4、ossoveroperators.ThereforegeneticoperationofPGAissimpleanditsinitialpopulationneednotbevariedandthereisnoimmatureconvergenceinPGA.CalcultingexamplesshowtheefficiencyofPGA.KEYWORD:geneticalgorithms，combinationoptimum,Filmdeliverproblem,exchangeoperator引言影片递送问题(简
5、称FDP)是组合优化的一个新问题，是由Cheng和Gen首先提出的‘”。描述如下:一盘影片拷贝要在n个影院放映，每个影院放映次数已定d;(i=1,2,⋯,n).问题是要为影片递送员找一个巡回，从主影院1开始，将影片送到第1家影院d;次(i=1,2,⋯,n)，最后回到主影院1，并极小化总的路程。当所有的d;为1时，FDP变化为经典的TSP.可见，FDP是TSP的扩展，并可推广到一大类路径与排序问题(机器顺序优化问题、资源分配问题、车辆路线问题和二次指派问题等)。己经提出T两种求解FDP的遗传算法，分别由Cheng和Ge
6、nE23,Zhang和Zheng"'提出。他们都在交叉操作方面作了很大的工作，但对收敛结果影响不大，相反地变异起了关键的作用，且变异概率对遗传算法的性能有明显的影响“，。本文在对GA研究的基础之上，针对问题的特点，采用了单亲遗传算法，加快了遗传操作。第一章、遗传算法的数学机理遗传算法是一种随机优化算法，由美国密执根大学的Holland教授发展起来的，是一种自适应启发式群体型、概率性迭代式算法。他将适者生存这一基本的达尔文进化理论引入串结构，并在串之间进行既有组织又随机的信息交换，伴随着算法的进行，优良的品质被逐渐保留
7、并加以组合，从而不断产生出更好的个体，而坏的特性被淘汰。新代个体中不仅包含着上代的大量信息，又不断地在总体特性上胜过上代，使整个群体向前进化发展.由于遗传算法仅需要知道目标函数的信息，而不需要其连续、可微等要求，因而具有广泛的实用性，同时他又是一种采用启发性知识的智能搜索算法，所以往往能在搜索空间高度复杂的问题上取得比以往算法(如梯度法)更好的效果151I.遗传算法的运行过程及其特征与传统的优化方法相比，GA使用参数的编码集，而不是参数本身进行操作，是在种群中而不是在单点上寻优，使用随机转化规则而不是确定性规则进行工
8、作。其基本步骤如下:stepl:选择问题的一个编码:在搜索空间中随机产生有N个染色体的初始群体pop(1)，t:=1;step2:对群体pop(t)中的每一个染色体pop。(t)计算它的适应函数值f二fitness(pop,(t));step3:若满足停止规则，则算法停止;否则计算各个体的选择概率p，一弄，，=了，;⋯，，Y-f,并以此概率分布
