摘要: 传统的旅行商问题都是静态的,但在现实中许多问题是动态的。该文提出动态旅行商问题,问题的规模随时间不断变化。实时问题对算法的求解效率要求很高,为此设计了基于模糊规则的在线遗传算法,可以根据求解问题的变化,在线精炼模糊控制规则来控制算法的参数。仿真实验验证了算法的有效性。
关键词:
动态旅行商问题,
遗传算法,
模糊
Abstract: The common Traveling Salesman Problem(TSP) is static, but in actual life, most optimal problems are dynamic. This paper proposes the dynamic TSP, the size of the candidate city and the distance between cities may vary from time to time, while within the sample time these variables remain unchanged. That is a real time optimal problems and it is necessary to design the fast optimal tool. The fuzzy based genetic algorithm is proposed. Fuzzy rules are online extracted in the running process of algorithm, and these rules are used to adapt the parameter of genetic algorithm. Simulation results confirm the efficiency of the algorithm.
Key words:
Dynamic TSP(DTSP),
Genetic Algorithm(GA),
fuzzy
中图分类号:
(上海交通大学工业工程与管理系;上海 000). 动态旅行商问题的研究[J]. 计算机工程, 2008, 34(10): 187-189.
(Department of Industrial Engineering and Management; Shanghai Jiaotong University; Shanghai 000). Research on Dynamic Traveling Salesman Problem[J]. Computer Engineering, 2008, 34(10): 187-189.