以瀰集演算法求解流線型製造單元排程

Abstract

瀰集演算法是一種廣泛被使用拿來求解複雜空間搜尋問題的巨集啟發式演算法。對於各種問題，過去的研究往往著重在對於演算法進化部分的改善，本研究不同於以往的思維去嘗試一種新的研究議題，採用新的染色體表達法來改變瀰集演算法的績效。 本研究對於求解具有固定序列的流線型製造單元排程問題利用瀰集演算法搭配兩種不同的染色體表達法去進行比較；這兩種瀰集演算法具有相同的演算流程，但具有不同的染色體表達方式，一個是過去研究所使用的，本研究稱之為舊染色體表達法(Sold)；另一個則是使用Wu et al. (2011)所發明的，本研究將其稱為新染色體表達法(Snew)。經由大量的數據分析後發現本研究所使用的瀰集演算法搭配新染色體表達法(Memetic-Snew)大部分都優於瀰集演算法搭配舊染色體表達法(Memetic-Sold)。此結果顯示一個新的重要研究方向，利用巨集啟發式演算法於不同空間求解問題時，新的染色體表達法可以改善空間求解問題的績效。

The memetic algorithm, a type of meta-heuristic algorithms, has been widely used in solving complex space-search problems. Most prior research focused on how to apply or enhance the search mechanism to various problems. Aside from the traditional track, this research examines a new research issue—Can the adoption of a new solution representation scheme improve the performance of the memetic algorithm? A flowshop manufacturing cell scheduling problem with permutation is used as the problem context, and two memetic algorithms are compared. The two algorithms, essentially the same in algorithmic flow, are distinct in using two different solution representation schemes (respectively called Sold and Snew). Noticeably, Sold was developed by prior studies and Snew is by Wu et al. (2011); the two algorithms are named Memetic-Sold and Memetic-Snew accordingly. Extensive numerical experiments reveal that Memetic-Snew mostly outperforms Memetic-Sold. This finding highlights an important new research track—exploring new solution representation schemes while applying meta-heuristic algorithms to various space-search problems.