计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2009年
6期
248-250
,共3页
马光志%卢炎生%宋恩民%汤海先
馬光誌%盧炎生%宋恩民%湯海先
마광지%로염생%송은민%탕해선
旅行商问题%基因簇%遗传算法
旅行商問題%基因簇%遺傳算法
여행상문제%기인족%유전산법
在用遗传算法求解TSP时,极易破坏已经发现的较短线路片段,从而使遗传算法的收敛变慢.为了保护较短的线路片段,遗传操作以基因和基因簇为单位进行,优良基因簇可完整地遗传到下一代.在获得第一个近似最优解后,粉碎已发现的基因簇并继续寻优,以期能够获得全局最优解.使用CHN144及TSPLIB中的数据进行试验,找到了CHN144问题的当前最优路径.通过对TSP225的实验获得了最短路径3859,优于目前已经公布的最短路径3916.实验表明,基于基因簇的算法具备3000个城市左右的寻优能力.
在用遺傳算法求解TSP時,極易破壞已經髮現的較短線路片段,從而使遺傳算法的收斂變慢.為瞭保護較短的線路片段,遺傳操作以基因和基因簇為單位進行,優良基因簇可完整地遺傳到下一代.在穫得第一箇近似最優解後,粉碎已髮現的基因簇併繼續尋優,以期能夠穫得全跼最優解.使用CHN144及TSPLIB中的數據進行試驗,找到瞭CHN144問題的噹前最優路徑.通過對TSP225的實驗穫得瞭最短路徑3859,優于目前已經公佈的最短路徑3916.實驗錶明,基于基因簇的算法具備3000箇城市左右的尋優能力.
재용유전산법구해TSP시,겁역파배이경발현적교단선로편단,종이사유전산법적수렴변만.위료보호교단적선로편단,유전조작이기인화기인족위단위진행,우량기인족가완정지유전도하일대.재획득제일개근사최우해후,분쇄이발현적기인족병계속심우,이기능구획득전국최우해.사용CHN144급TSPLIB중적수거진행시험,조도료CHN144문제적당전최우로경.통과대TSP225적실험획득료최단로경3859,우우목전이경공포적최단로경3916.실험표명,기우기인족적산법구비3000개성시좌우적심우능력.
