以協力演化遺傳演算法求解容器堆疊問題

Solving Container Loading Problem Using Cooperative Coevolutionary Genetic Algorithm

在貨品運送過程或工廠的生產部門中，棧板(pallet)或方形容器（container）往往是堆疊零件、半成品與成品之工具。而物體堆疊方式是否能有效利用容器空間，關係到各項作業成本是否能有效降低。本研究發展協力演化遺傳演算法，首先設計一「下後左」之啟發式堆疊法則為核心模組，但在外部控制機制上則導入「協力演化」之觀念，數個遺傳演算法同時進行演化，各自搜尋不同之解答空間（solution space），但卻週期性地交換各母體間之演化資訊，以提昇搜尋之品質及效率。演算法測試時，先以部分例題對所提出之協力演化遺傳演算法之參數進行實驗，以獲取參數組合建議。接著經由建議之參數組合，對國際文獻演算例題進行測試，再與國際文獻演算結果進行比較。結果顯示本研究所提出之協力演化遺傳演算法，只要子群體之數目足夠，其演算結果可超越國際文獻最佳結果。

In this study, a cooperative coevolutionary genetic algorithm (CCGA) is proposed for solving the container loading problem. A heuristic rule, ”bottom-back-left (BBL)”, for loading objects into a container is developed as the core, while CCGA controls the improving process at the outer level. The introduction of CCGA aims at bringing in different species to the same environment, where the interactions among them affect the genetic composition of all the constituents, so that better solutions can be obtained. Intensive testing is implemented to search for proper CCGA parameter combinations. Promising computational results are obtained and reported by running examples from the literature.