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

Solving Two-Dimensional Packing Problems by Using a Genetic Algorithm

吳泰熙(Tai-Hsi Wu) ； 吳奕樺(Yi-Hua Wu) ； 張欽智(Chin-Ju Chang)

《科學與工程技術期刊》 2卷3期 (2006/09) Pp. 75-83

https://doi.org/10.7117/JSET.200609.0075

摘要

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

關鍵字

方形物件排列問題 ； 基因演算法

並列摘要

In this study, a genetic-based algorithm (GA) is proposed for nesting two-dimensional rectangular parts in a material plate. In the literature GA has been adopted for solving the same problem, fairly good results having been obtained. A new method for designing the coding of the chromosomes, accompanied by a proposal for an elitism strategy, is presented in this research, aiming at further extending the problem-solving capability of the traditional GA. Promising computational results are obtained and reported by running examples from the literature.

並列關鍵字

two-dimensional packing problem ； genetic algorithm ； elitism strategy