基于遗传算法求解TSP问题的一种新思路.pdf

澎盘�!4丽咔居�基于遗传算法求解��籰��题的一种新思路�����钩渌惴�李晓仕李天牧��侵质�帜训挠呕�奈侍狻H绻�阎3鞘衛,��一问的距离和为本文提出一种基于遗传算法的求解��侍獾男滤悸罚�A思跎俅�硎奔浜腿〉萌�局最优值,,具有����J����⋯,对这种动态规则去求���的解,在城市数较少的情况下尚可计算。当城市数目增加,计算量就会增加到无发计算的地步,是一个�问题。实现时,它的计算速度非常快,但在计算机上模拟速度必然会有很大的下降。另外也可采用显丽易见在一定条件下求解��田问题,包含一个简单的就近原则。以六个城市为例,/为了方便观察,我们把城市间的距离看成直线。而且左边、右边各三个城市,三个城市间的距离为��冶叩娜�龀鞘杏胱蟊叩某鞘邢喽杂Γ�脚懦鞘屑涞木嗬胛�。�缤�、强��示�N颐强刹捎昧街致眯蟹绞骄��饬�龀鞘校灰恢质遣捎镁徒��颍涣硪恢质遣捎梅蔷�采用就近原则的图�傻玫絛��,而采用非就近原则可得到��,可见在特殊情况下就�航��颇洗笱�畔⒂肟蒲�担�ッ鳎������侍猓�刹捎肏����芰亢��辞蠼狻T诔鞘惺�∮��时,采用电路来遗传算法进行求解。遗传算法只是取一部分染色体作为父辈,然后沿着优化的方向繁殖后代,从而得到优化的结果。因此计算量可大为减少,而且速度也较快。本文在遗传算法的基础上加上了一个补充算法,这个补充算法用于提高父辈的性状。从遗传学的角度看,如果遗传能从性状较好的父辈开始,那么染色体进化到最优或次最优的时间必将大大缩短。因为子辈的性状是从父辈遗传过来的,父辈的性状好,予辈的性状也往往较好。近原则。从两种方法所得到的结果,我们就不难发现就近原则是求解��颂馑���摹[帷�原则。’云南省科委应用基础基金项目“����弊手�
糯�惴�P�墨至垫堡苎壁垒竺望�┍谒芏�谇敌钦���原则是得到��侍庾钣沤馑�匦敕�拥脑�颍�裨颍�ǖ贾侣肪兜闹馗春屠朔选6�谝话�求解的目标函数是����如��⋯十�保�馐歉銮髆�����狻�越小,,��侍庵校�蠖嗍�鞘辛=崴�匦敕�拥脑�颉R蛭T诿挥�做特殊假设韵基础上,也可以把所有城市看成多个城市组的组合,每个城市组由距离较近城市组成,显然在每个城市组内部,。如果在不同组闻往返,势必造成图�睦朔选�虽然就近原则是旅行者必须遵循的原则,但是得到最优路径的问题井未完全解决,因为我们还不知道旅行每组城市的最优起点和终点。就近原则只是在寻求最优路径的大多数情况下�热缢蹬醭�鸬愫椭盏愕那榭鱿�所应遵循的原则。本文用遗传算法解决这个问题,通过遗传算法不断修改就近原则下所获得的路径,就可获得比较理想的路径,而且所须的运算时间也较少。因为遗传算法不须对所有的城市位置进行修改,而是部分地修改城市位置。补充算法的算法如下:��愿�ǔ鞘形5谝怀鞘校��阉�栉5鼻俺鞘小���拥鼻俺鞘形恢贸龇⑴懦�鼻俺鞘校�矣氲鼻俺鞘芯嗬胱罱�某鞘小<亲〈顺鞘校��把它设为当前城市。��卸下眯惺欠窠崾��绻�挥性蚍祷氐絝�。��崾����砍跏蓟�把�龀鞘兴�械南嗷ゾ嗬