物件排序與分群優化問題之仿電磁吸斥優化演算法

Abstract

本研究提出仿電磁吸斥離散優化演算法，求解物件排序優化問題及物件分群優化問題。求解問題包括旅行銷售員問題、裝箱重量均等問題、及節點著色問題。本研究針對物件排序優化問題本研究提出「虛擬映射」和「真實映射」兩種粒子移動模式及四種連續座標值映射成離散值的「離散映射作業」法。至於物件分群優化問題，本研究以區間指派法求解裝箱重量均等問題。針對有容量限制的裝箱重量均等問題提出懲罰函數及嘗試修補機制求解。求解節點著色問題是應用群合併法將節線限制問題轉成物件著色群合併作業的排序問題，最後並以求解物件排序優化法求解。本研究成功地擴展仿電磁吸斥優化演算法的應用範圍，使能求解組合優化問題。研究並測試甚多標竿問題的測試顯示效能甚佳。

This thesis proposes a new heuristic based on Electromagnetic-like mechanism （EM）. The method can be used in object sequencing problem and object grouping problem. It still contains an attraction-repulsion mechanism to move the particles towards the global optimality together. The object sequencing problem includes Traveling Salesman Problem（TSP）. The object grouping problem contains Bin Packing Balance Problem and Vertex Coloring Problem（VCP）. In solving object sequencing problem, the thesis proposes two scenario：Keep Continued and Keep Discritied, and also proposes four methods about Discritied Mapping Operation. In solving object grouping problem, the thesis uses Interval Assignment method to solve Bin Packing Balance Problem. The thesis uses Penalty Function and Repair Method to solve Bin Packing Balance Problem with Limited Capacity. In solving Vertex Coloring Problem, the thesis uses Merge Method（Juhos）and solving object sequencing problem methods. Some test results about Benchmark problem of these problems are included. The method extends successfully to discrete problems. We hope the thesis introduces EM to more researchers. More researches can be attracted to EM, more problem can be solved by EM.