基於雲端具回饋機制之模組化混和型演化式演算法應用於TSP最佳化問題

Modular Cloud Hybrid Evolution Algorithm Based on Feedback Assistance for Optimal Data Solution in Traveling Salesman Problem

李寬瑋(Kuan-wei Lee)

指導教授 ： 簡銘伸

國立虎尾科技大學/電機資訊學院/資訊工程研究所/碩士(2014年)

摘要

本論文提供了一種基於雲端具回饋機制之模組化混和型演化式演算法。使用者可在雲端系統的虛擬機上建立各式各樣步驟和型態的演化式演算法來解決旅行銷售員問題。使用者只需要在使用者介面設定演算法參數，並上傳對應的染色體編碼，系統會將所有參數封裝成XML格式並傳送至伺服器，按照使用者設定執行演化式演算法，而不需要另外建置演化式演算法，達到節省建置成本之目的。提出的回饋控制演算法會將不同的交配方法進行交互作用，來提升染色體在下一次迭代的存活率。除此之外透過回饋控制方法，演化式演算法的收斂將更有效率。

關鍵字

雲端運算 ； 演化式演算法 ； 基因演算法 ； 旅行銷售員問題 ； 回饋控制 ； 混合 ； 模組化

並列摘要

This paper develops a modular cloud hybrid evolution algorithm based on feedback assistance for optimal data solution in traveling salesman problem. Different steps and types of the evolution algorithm can be established via individual thread procedures and various virtual machines in cloud. According to the proposed XML format, system users can upload only the coding of chromosomes without the evolution algorithm implementation. The proposed feedback assistance is based on the fitness evaluation result and survival ratio of different crossover methods. The Reduce the cost for establishing the evolution algorithm according to the proposed system can. The feedback assistance can interact with the different crossover methods and emphasize the method that can enhance more survival individuals for the next evolution generation. Furthermore, via using the feedback assistance, the convergence time of the optimal solution can be enhanced.

並列關鍵字

Cloud Computing ； Evolution Algorithm ； Genetic Algorithm ； Travel Salesman Problems ； Feedback Control ； Hybrid ； Modular

參考文獻

[3] P. Toth and D. Vigo, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, 2001.

[4] M. S. Jian, T. Y. Chou, K. S. Siw, and L. Y. Chung. “Adaptive life-cycle and viability based paramecium-imitated evolutionary algorithm”, WSEAS Transactions on Computers, Vol. 8, Issue 8, pp.1358-1367, 2009.

[6] Castro, J., “Solving difficult multicommodity problems with a specialized interior-point algorithm”, Annals of Operations Research, Vol.124, Issue 1-4, pp.35-48, 2003.

[7] Chiu, Y. and H. Zheng, “Real-time mobilization decisions for multi-priority emergency response resources and evacuation groups: Model formulation and solution”, Transportation Research Part E: Logistics and Transportation Review, Vol.43, Issue 6, pp.710-736, 2007.

[8] Haghani and S. Oh, “Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations”. Transportation Research Part A: Policy and Practice, Vol.30, Issue 3, pp.231-250, 1996.