估計機率分佈演算法(Estimation of Distribution Algorithms, EDAs)在最近已成為演化式演算法中重要領域之一，可用來解決困難之組合性最佳化問題，但本計畫主持人發現過去的研究僅有一個可求解群內最佳化問題之 EDAs，如 多旅行推銷員(Multiple Traveling Salesmen Problems, mTSP)或平行機台排程問題(Parallel Machine Scheduling Problems, PMSPs)，這些問題同時都包含了指派與順序之最佳化。基於過去少有 EDAs 演算法求解群內最佳化問題之相關 研究，本研究提出一個自指引基因演算法並結合最小負載指 派法則 (Minimum Loading Assignment rule, MLA rule)， 用此轉化的編碼方式 (Transform-Based Encoding)來切入 mTSP 這類型的問題，其求解間僅 n!，此結果與目前最佳之直 接編碼方式兩段式染色體編碼遺傳演算法(Two-Part Encoding Genetic Algorithm, TPGA) 比較，兩段式染色體 編碼求解間仍需 n!*C(n-1, m-1)，因此預期所提出方法會比TPGA 佳。所採用的三十三個測試例題從 TSPLIB 取得，目標函數包含了 極小化總移動距離與極小化最大移動距離，推銷員人數有 2、3、5、10 與 20 人，實驗的結果顯示本研究所提出的 SGGA 演算法結合 MLA 法則後，無論在極小化總移動距離與極小化最大移動距離，都能比目前最佳的直接編碼方式佳。且在極小化總移動距離的問題中，在使用三個至十個推銷員時，目標函數值並不會隨著人數增加而隨之成長，因此本研 究建議之後的 EDAs 研究，採用轉化的編碼方式會比直接編碼佳。 Estimation of Distribution Algorithms (EDAs) have recently been recognized as a prominent alternative to traditional evolutionary algorithms due to their increasing popularity. The core of EDAs is a probabilistic model which directly impacts performance of the algorithm. Previous applications of EDAs have used algorithms to solve many hard problems. However, this researcher found that there is one problem which EDAs does not discusses so far. It is the in-group optimization problems, such as the multiple traveling salesmen problem (mTSP) and parallel machine scheduling problem (PMSP) studied in this research. These problems include the assignment and sequencing procedures in the same time and to be shown in different forms. As a result, this research proposed an algorithm deal by using the Self-Guided GA together with the Minimum Loading Assignment rule (MLA) to tackle the mTSP. This strategy is called the transformed-based encoding approach instead of the direct encoding. The solution space of the proposed method would be only n!. We compare the proposed algorithm against the best direct encoding technique, two-part encoding genetic algorithm (TPGA) and its solution space is n!*C(n-1, m-1), in the experiment on the 33 instances drawn from the well-known TSPLIB. The experimental results show the proposed algorithm is better than the two-part encoding genetic algorithm in terms of minimization of the total traveling distance and the maximum traveling distance among the salesmen. An interesting result also presents the proposed algorithm would not cause longer traveling distance when we increase the number of salesmen from 3 to 10 persons under the objective of minimization of total traveling distance. Consequently, this research may suggest the EDAs researcher could employ the MLA rule instead of the direct encoding in their proposed algorithms.
