優加劣減螞蟻擇段系統應用於組合問題

Added to the superior segments and subtracted from inferior segments Ant System for Combinatorial Optimization Problems

林典翰(Tei-Han Lin)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00728

摘要

蟻拓最佳化技術是近年來所發展出來的一種啟發式演算法。目前已經廣泛地運用於求解各種組合最佳化問題。例如：旅行推銷員問題、零工式生產排程問題、裝箱問題等。為降低螞蟻數目及避免求解過程發生停滯現象，本文提出一種改良的蟻拓最佳化技術－名為優加劣減螞蟻擇段系統。此技術沿用 的手法定義出較佳界限及較差界限，將螞蟻區分出較佳及較差二群。費洛蒙只在較佳及較差的螞蟻所建構的解上變更。這些解上相關連的物件連結再以隨機模式區分成優段及劣段。費洛蒙更新法則是在優段上添加費洛蒙並在劣段上扣減費洛蒙。
本研究並以優加劣減螞蟻擇段系統求解旅行推銷員、裝箱及零工式生產排程問題。過程中並以TSPLIB、ORLIB提供的三種不同類型的標竿問題進行效率測試。測試結果顯示優加劣減螞蟻擇段系統是一個具有穩健性的蟻拓最佳化技術，能在使用較少的蟻次(即每代次所派出的人工螞蟻數目×求得該題目最佳解時所需的總代次(iteration))，得到與其它蟻拓最佳化技術一致或更接近目前己知的最佳解。

關鍵字

停滯現象 ； 優加劣減螞蟻擇段系統 ； 蟻拓最佳化技術 ； 旅行推銷員問題 ； 零工式生產排程問題 ； 裝箱問題

並列摘要

Ant colony optimization (ACO) is a new kind of heuristic algorithms in recent years. There are successful implementations of applying ACO to a number of different combinational optimization problems such as traveling salesman problem (TSP), bin packing problem (BPP), job shop problem (JSP), and so on. An improved ACO method, called added to the superior segments and subtracted for inferior segments ant system (ASDSAS) is presented.This method is to avoid stagnation and decrease tour constructions. At first, the ants are classified into two groups- superior and inferior using groups the grouping rule. Only the routing segments traversed by the superior and inferior ants are considered for pheromone updating. Moreover these segments traversed by the superior and inferior ants can be further classified into superior and inferior segments. Pheromone is added to the superior segments and subtracted from the inferior segments. Stochastic factor is adapted in pheromone updating.
ASDSAS is applied to solve TSP, BPP, and JSP. Several TSPLIB and ORLIB are tested and results are compared with other ACO Systems. Results show that ASDSAD can achieve the same solution, some even better, but use lesser computer resources.

並列關鍵字

Added to the superior segments and subtracted for ； Bin packing problem ； Stagnation ； Ant colony optimization ； Traveling salesman problem ； Job shop problem

參考文獻

Blum, C. and Sampels, M., 2002, “When Model Bias is Stronger than Selection Pressure,” In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature.

Dorigo, M. and Caro, G.., 1999, “The Ant Colony Optimization Meta-Heuristic,” New Ideas in Optimization, McGraw-Hill, pp. 11-32.

Dorigo, M. and Gambardella, L. M., 1996, “Solving symmetric and asymmetric TSPs by ant colonies,” Proceedings of the 1996 Congress on Evolutionary Computation, pp. 622 - 627

Dorigo, M. and Gambardella, L. M., 1997, “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66.

Dorigo, M. and Stützle, T., 2001, “The ant colony optimization metaheuristic: Algorithms, applications, and advances,” Handbook of Metaheuristics, F. Glover and G. Kochenberger. pp. 15.