以基因演算法求解單原片方形物件排列問題

Solving Two-Dimensional Packing Problems by Using a Genetic Algorithm

工業界莫不亟思要如何精減人力以提昇效率、全面降低生產成本。然而尚有部分產業仍利用人工方式來處理原物料切割∕排列等相關作業。此類複雜之「物件切割」問題需要有合適之演算法來迅速求得原物料切割計畫。過去文獻中，不乏因為使用遺傳基因演算法（genetic algorithm, GA）而獲致不錯演算績效之研究，因此本研究採用GA 之演算架構，但繼續加強在上述文獻中尚未被著墨之「菁英策略」，並使用不同之「編碼」設計，以期超越文獻之GA 演算結果。在例題測試階段，我們首先以部分例題對所提出之GA 演算法之參數進行實驗，以獲取參數組合建議。接著經由建議之參數組合，對38 題國際文獻演算例題進行測試，再與國際文獻演算結果進行比較。結果顯示本研究所提出之GA 演算法，在中、小題型之單原片方形物件排列問題中幾乎皆優於國際文獻最佳結果，某些例題甚至超越文獻結果將近10% 之使用率，演算績效可謂非常傑出。