降幂编码遗传算法及其在旅行商问题中的应用研究

《降幂编码遗传算法及其在旅行商问题中的应用研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉科技大学硕士学位论文第1页摘要旅行商问题是一个实用背景广泛，并且有着重要理论价值的组合优化难题，该问题的一个显著特点是描述简单，但很难得到最优解。因为旅行商问题在工程技术领域的应用十分广泛，所以具有很高的研究价值。由于旅行商问题的时间复杂度很大，精确算法只能求解规模很小的旅行商问题，所以当求解规模较大的旅行商问题时，常常采用近似算法，遗传算法是一种常见的求解旅行商问题的近似算法。因为字符编码在求解旅行商问题时，拥有信息表达简单、直观的特点，所以目前在解决旅行商问题时，一般使用的都是字符型编码的遗传算法。但是字符型编码由于其

2、自身的特点，在求解旅行商问题时存在会产生非法染色体、计算效率低的缺点，其效果并不是很理想。本研究提出了一种新的求解旅行商问题的遗传算法编码方式，将其与字符型编码进行比较，证明其在交叉的时候不会产生非法的染色体，并且实验结果表明其能更快的找到最优解，这两个优点足以证明这种新的编码方式更适合求解旅行商问题。关键词：旅行商问题遗传算法二进制编码字符编码降幂编码第1I页武汉科技大学硕士学位论文AbstractTSPiSusedin811extensivepracticalbackground．whichiSthecombination

3、aloptimizationproblemwimimportanttheoreticalvalue，theobviousfeatureisthedescriptionisverysimple，butdifficulttogetalloptimalsolution．ItishighresearchvalueasTSPusedintheapplicationofengineeringtechnologyextensively．AsthegreattimecomplexityofTSP,exactalgorithmscanonlys

4、olvesmall-scaleTSP,SOapproximationalgorithmisusedalottosolvelarge—scaleTSP,geneticalgorithmisacommonsolutionofapproximationalgorithmforTSEBecausetheinformationissimpleandintuitivewhenchoosethecharacterencodingforTSP,thegeneticalgorithmforcharacteristicsencodingisaco

5、mmonsolutionnowadays．Howeverasitsowncharacteristicsofcharacterencoding,itisnotthebesteffectasitmakesillegalchromosomeandalsocalculatewithlowefficiency．Thisresearchgivesanewcharacteristi鹪encodingofgeneticalgorithmforTSP,comparedwi廿1othercharacteristics，itisprovedthat

6、itdoesn’tproduceillegalchromosomeswhencrossed，alsotheexperimentalresultsshowthatitcanhelpyoutofindaoptimalsolutionmuchfaster,、)l，itllthesetwoadvantages，thisnewcodingmethodiSprovedthatitiSamoresuitablesoluti011forTSEKeyword：TSP／geneticalgorithm／binaryencoding／charact

7、erencoding／descendingencoding武汉科技大学硕士学位论文第1Ⅱ页摘要目录¨IAbstract．．．．．．．．．．．．．．．⋯⋯⋯⋯．．．．．．．．⋯．．．．．．⋯⋯⋯．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．⋯．．．．．．．．．．．．．．．．．．⋯．．．⋯⋯⋯．．⋯．．⋯⋯⋯．IIEj录⋯．．．．⋯⋯⋯⋯．．．．．．．．．．⋯⋯⋯．⋯⋯⋯．．⋯⋯⋯．．⋯．．．．．．⋯．⋯⋯⋯⋯．．．．．．．．．．．．．．．．．．．．⋯⋯⋯⋯．．．．．．．．．⋯⋯⋯⋯llI第一章绪论l1．1选题背景

8、及研究意义⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．2国内外研究现状⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯11．3遗传算法概述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯21．3．1遗传算法的基本原理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯