摘要
旅行商问题(T raveling Salesm an P rob lem,简称TSP)是一个典型的组合优化问题,而且是一个NP完全问题。遗传算法(G enetic A lgorithm,简称GA)是求解组合优化问题的行之有效的算法。但遗传算法并不是一个完美无缺的算法,它最突出的问题是早熟现象。在解决像旅行商这类组合优化中的NP完全问题,是极易陷入早熟收敛,城市规模越大越难求得最优解。如何缓和旅行商问题中的早熟现象,使问题的解尽可能接近最优解,这是本文研究的主要内容。本文在分形法的基础上提出了一种分形法与范例库推理相结合的改进方法用以求解TSP问题。首先建立范例库,选取其中优良的个体来指导城市规模大的旅行商问题进行合理的区域分割,由于优良个体与最优值的结构大体相同,相似度大,故可以有效地实施“分而治之”的策略。在寻优进化过程中,还要对范例库进行更新与维护。通过对TSPL IB测试库中的eil51、eil101、ch130和ch150问题的求解,说明该方法在求解TSP问题上是行之有效的。
The traveling .salesman problem （TSP） is one of the typical NP completeness problems in combinational optimization, and genetic algorithm （GA） is a more efficient and more effective for solving this kind of problem. However, GA is not a perfect algorithm, which distinct disadvantage is permutation convergence. GA easily traps in permutation for NP-hard problem such as TSP, especially when the city scale is large. It is the primary research work in this paper how to reduce permutation to .seek the answer closing as possible as optimization. A new algorithm, which uses fractals combined with case-base for TSP, is presented based on fractals. At first case-base is build, and the good individual is selected to instruct the .,searching space divided. For it is similar as optimum in structure, using the strategy of ＂dividing-and-ruling＂ geographical space, the searching space can he rationally divided. The case-base is refreshed and maintained in the searching proceed. Used the algorithm for TSP such as eil51, eil101, ch130 and ch150 problems in the TSPLIB, the results show it is efficient.
出处
《系统工程》
CSCD
北大核心
2006年第12期102-106,共5页
Systems Engineering
基金
国家自然科学基金资助项目(60475002)
关键词
旅行商问题
分形法
范例库推理
Traveling Salesman Problem （TSP）
Fractals
Case-base Reasoning
