计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2014年
1期
191-194,198
,共5页
混合蛙跳%分段%旅行商问题%逆转变异算子%邻域搜索
混閤蛙跳%分段%旅行商問題%逆轉變異算子%鄰域搜索
혼합와도%분단%여행상문제%역전변이산자%린역수색
shuffled frog leaping%subsection%Traveling Saleman Problem(TSP)%in-over mutation operator%neighborhood search
针对旅行商问题(TSP)在搜索后期解的多样性和精度下降的问题，提出一种解决TSP问题的分段混合蛙跳算法(S-SFLA)。该算法在搜索初期利用逆转变异算子减少交叉路径，在搜索的后期引入邻域搜索(个体邻域，局部最优领域，全局最优邻域)增加种群多样性。在整个搜索过程中记忆全局历史最优解与局部历史最优解，进行全局更新和局部更新，避免迂回搜索。在局部更新中，每一个青蛙都有机会得到更新。实验结果表明，与遗传算法、蚁群算法、基本蛙跳算法相比，S-SFLA算法在求解中等规模的TSP问题上具有更快的搜索速度和更高的求解精度。
針對旅行商問題(TSP)在搜索後期解的多樣性和精度下降的問題，提齣一種解決TSP問題的分段混閤蛙跳算法(S-SFLA)。該算法在搜索初期利用逆轉變異算子減少交扠路徑，在搜索的後期引入鄰域搜索(箇體鄰域，跼部最優領域，全跼最優鄰域)增加種群多樣性。在整箇搜索過程中記憶全跼歷史最優解與跼部歷史最優解，進行全跼更新和跼部更新，避免迂迴搜索。在跼部更新中，每一箇青蛙都有機會得到更新。實驗結果錶明，與遺傳算法、蟻群算法、基本蛙跳算法相比，S-SFLA算法在求解中等規模的TSP問題上具有更快的搜索速度和更高的求解精度。
침대여행상문제(TSP)재수색후기해적다양성화정도하강적문제，제출일충해결TSP문제적분단혼합와도산법(S-SFLA)。해산법재수색초기이용역전변이산자감소교차로경，재수색적후기인입린역수색(개체린역，국부최우영역，전국최우린역)증가충군다양성。재정개수색과정중기억전국역사최우해여국부역사최우해，진행전국경신화국부경신，피면우회수색。재국부경신중，매일개청와도유궤회득도경신。실험결과표명，여유전산법、의군산법、기본와도산법상비，S-SFLA산법재구해중등규모적TSP문제상구유경쾌적수색속도화경고적구해정도。
Because reduction of the diversity of solution causes the reduction of search speed and accuracy at the same time in the later period of search according to Traveling Saleman Problem(TSP). A Subsection Shuffled Frog Leaping Algorithm(S-SFLA) is proposed. In the initial period of search, in-over operator is used to reduce cross paths. In the latter period, the neighborhood search(individual neighborhood, local optimal area, the global optimal neighborhood) is introduced to increase the diversity of population. In the whole search process, global optimal solution of history and the local optimal solution of history are remembered to avoid circuit search, and in the process of local update, every frog has the opportunity to be updated. Experimental results show that, compared with genetic algorithm, ant colony algorithm, basic leapfrog algorithm, S-SFLA algorithm has higher precision and search speed in solving TSP problem of medium scale.
