基于改进遗传算法的TSP问题研究.pdf

万方数据

旅行商问题(删是一个典型的组合优化问题。基于改进遗传算法的TSP问题研究select，删X凹啪oveLImproVedAlgod恤mI呷阿Ve吲i60nalopemt0璐．TsP岬TSPprop08ed'池chTheStudyofBasedGeneticunive坤峨】【i，柚710072，ch如)8tIldied，砧creteme幽，like鹪∞nverge肿e，vef扯坩鹄a糟舯wd周涛1·2关键词：搬行商问题，遗传算法，赢散睹转选择算于，EPMx交叉算子，D咖ta60n变异算子c岫puter并且是一个NP难题．其可能的路径总数与城市数目n是成指数型增长的．所以一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有遗传算法是美国Michi娜n大学的J．Holland教授于1975年首先提出ll】。遗传算法的核心思想为自然选择，适者生存。遗传算法作为一种模拟生物进的通用框架。它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性．具有自组织、自适应和自2遗传算于的改进2．1编码及适应度函数的构造编码问题是遗传算法应用中的首要问题，也是设计遗传算法时的一个关键步骤。基本的编码方法可以分为三大类：二进制编码、浮点数编码(实数编码)、符号编码。几种方法的具体介绍和相互比较可以参考文献f11。在解决1sP问题时．多采用了实数编码方式，具体实现方式是：用遍历城市的顺序作为编码方式。如：某染色体编码为1234567891．表示从城市1开始经过依次城市2，3，4⋯最后到城市1终止。城市与城市之间的路径长度用一个路径矩阵记录．如果是对称路径．则此矩阵是对称矩阵。此处讨论的是对称阵。第f个染色体的编码为：其中q表示第i个城市，唾≠q，哦E{1，2，⋯．I＼，1，0<i，j<?v．Ⅳ是城市数目。2．1．2适应度函数的构造在遗传算法进行搜索时只以适应度函数为依据．利用种群中每个个体的适应度值来进行搜索，一般而言．适应度函数是直接由目标函数变换而成的．有时也要根据问题的要求．对目标函数进行一定的适应度尺度变换(Fittness题而言．路径长度为：微电子学与计算机2006年第23卷第10期(1陕西理工学院数学系．陕西议中723000)(2西北工业大学计算机学院，陕西西安710072)摘要：通过对遗传算法和两P问题特研究，提出了离散赌轮选择算手EPMx交叉算子和Dmulation变异算子等．时遗传算法的各个算子进行了改进。利用改进的遗传算法有效的解凌了鸭P问题．实验验证其与传统的解班方onZHOU7ra010mparLm蛐tof胁Illl日，shaanxiuIlive穗-哆斫Technolo野，H蚰矗咖gscie眦e，No曲we虬emPoM即hnicAb打act：p印ebAl伊d吐皿孤d幅PDmu僦ion矾l忸d叫叩eratoreI五cien山uBillgbyelp棚m明tnmdi6仰alK町删Ⅱ由：_IsP'GA，Di日c陀temut靠明l引言重要的意义。化的一种算法．提供了一种求解复杂系统优化问题学习性。2．1．1编码基金项目：陕西理工学院基金项目(YJG0524)置；吼啦⋯cwmscali雌)。对于’rsP问104式相比有更好的收敛特性．解的准确性更好。中圈分娄号：TP3l文献标识码：A’文章蝈母：1000—7180(2006)10_0104-03(1723000，china)(2GeMncWheelselect叩e豫tohCr∞帅verM∞lved收稿日期：2006一04_28sch00l0fIlltlIi8BetEPMXoper鲥oLw盯ebthreetllisa190dthm．h8conLr8吕ted’酊t}lmethod．betwheelDmu诅tionwere

万方数据

丘Mss：百r————L．——一×工501册如7增地=乞如f(墙，％I)+幽t(蛳，嘶)艺如l(啦，时1)+如t(口Ⅳ，Ⅱ1)7891船142f离。一般来说．适应度是越高越好．而在码P问题度是越小越好．为了使两P问题的适应度与一般遗分基因．从而形成两个新的个体。针对髑P问题．由背了聪P问题中每个城市只走一遍的规定．引人非2006年第23卷第10期微电子学与计算机其中d缸(儡，崎)表示城市％和城市q之间的距中．如果适应度是所经过的路径长度之和．路径长传算法中的适应度一致．这里用路径长度的倒数表示适应度。但当路径非常大(例如：10000)。这样其适应度的最高数据位将在小数点后的第四位．这样不利于计算，为此要进行尺度变换。为确保适应度有两位整数．此处将适应度放大L倍(在本例中L=1000)。因此适应度函数的表达式为：2．2选择算子的改进策珞与实现一般选择算子设计使得个体被选中并遗传到下一代群体中的概率与该个体的适应度大小有关。适应度越大．被选