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

蟻拓最佳化技術是近年來所發展出來的一種啟發式演算法。目前已經廣泛地運用於求解各種組合最佳化問題。例如：旅行推銷員問題、零工式生產排程問題、裝箱問題等。為降低螞蟻數目及避免求解過程發生停滯現象，本文提出一種改良的蟻拓最佳化技術－名為優加劣減螞蟻擇段系統。此技術沿用 的手法定義出較佳界限及較差界限，將螞蟻區分出較佳及較差二群。費洛蒙只在較佳及較差的螞蟻所建構的解上變更。這些解上相關連的物件連結再以隨機模式區分成優段及劣段。費洛蒙更新法則是在優段上添加費洛蒙並在劣段上扣減費洛蒙。 本研究並以優加劣減螞蟻擇段系統求解旅行推銷員、裝箱及零工式生產排程問題。過程中並以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.目錄 誌謝 I 摘要 II Abstract III 目錄 IV 圖目錄 VII 表目錄 IX 名辭彙編 X 符號列表 XII 第一章 緒論 1 1.1 研究背景 1 1.2 研究動機 4 1.3 研究目的 5 1.4 研究範疇與架構 6 1.5 章節概要 7 第二章 文獻探討 8 2.1 蟻拓最佳化技術介紹 8 2.1.1螞蟻建構行為 10 2.1.2蟻拓最佳化技術演算步驟介紹 15 2.2蟻拓最佳化技術演進 16 2.2.1 螞蟻系統（Ant System, AS） 17 2.5.2 螞蟻屯拓系統（Ant Colony System, ACS） 20 2.2.3 排名螞蟻系統（Rank Based Version of Ant system） 23 2.2.4 快速螞蟻系統（Fast Ant System, FANT） 24 2.2.5 費洛蒙界限螞蟻系統（Max Min Ant System, MMAS） 26 2.2.6 分群排名螞蟻系統 28 2.3 蟻拓最佳化技術應用於組合最佳化問題 30 2.3.1 蟻拓最佳化技術應用於旅行推銷員問題 32 2.3.2 蟻拓最佳化技術應用於求解裝箱問題 36 2.3.3 蟻拓最佳化技術應用於零工式生產排程問題 41 2.4 文獻探討結語 48 第三章 優加劣減螞蟻擇段系統應用於組合問題 50 3.1 建構解與物件連結介紹 50 3.2 入圍策略對於費洛蒙影響的介紹 51 3.3 優加劣減螞蟻擇段系統 65 3.3.1較佳較差界限法 66 3.3.2優加劣減費洛蒙隨機更新法則 68 3.3.3 費洛蒙重置策略 74 3.3.4優加劣減螞蟻擇段系統演算流程 76 3.4 優加劣減螞蟻擇段系統應用於旅行推銷員問題 81 3.5 使用優加劣減螞蟻擇段系統求解裝箱問題 86 3.6 優加劣減螞蟻擇段系統應用於零工式生產排程問題 92 3.7 小結 109 第四章 實例驗證與結果分析 110 4.1優加劣減螞蟻擇段系統應用於旅行推銷員問題的測試結果 110 4.1.1 旅行推銷員問題參數設定 111 4.1.2 旅行推銷員問題實驗數據分析 113 4.2優加劣減螞蟻擇段系統應用於裝箱問題的測試結果 121 4.2.1 裝箱問題參數設定 121 4.2.2 裝箱問題實驗數據分析 123 4.3 優加劣減螞蟻擇段系統應用於零工式生產排程問題的測試結果 133 4.3.1 零工式生產排程問題參數設定 133 4.3.2 零工式生產排程問題實驗數據分析 135 4.4小結 142 第五章 結論與未來研究建議 143 5.1結論 143 5.2未來展望 144 參考文獻 146 附 錄 一 旅行推銷員問題求得最佳解示意圖 150 附 錄 二 零工式生產排程問題求得最佳解示意圖 15