将遺傳算法用于二維下料問題的一些結果

 最近做了這方面的事情。把自己的一些經驗跟大家分享一下。

遺傳算法是一種優化算法，是以可以應用在很多地方。尤其是對于比較複雜或者難于求出精确解的問題，該方法給出了比較好的解決方案。

二維下料問題是說，在固定寬度的闆材上切割下一些要求大小的目标物，使得消耗的闆材長度最小。

對于這個問題，可以把他抽象為這樣的數學模型：每一個目标物設定一個id号，這樣一組id号就構成了一個切割順序。顯然，在這樣的模型下，切割順序和切割方式對于最終的結果有比較大的影響。

略去切割方式，本文在一種切割方式下，集中對切割順序作一個小小的分析。

我選擇的切割方法是：将進入的目标物從下到上，從左到右地在闆材上找空閑位置，找到後将闆材上的該區域标記；重複上述過程直到沒有目标物進入為止。

在上述切割方式下，我的目标轉化為找到一個合适的序列使得切割後使用的闆材長度盡可能地小。

對于這個序列，我使用了遺傳算法。遺傳算法控制參數很多，尤其是初始種群的選取對于該算法有較大影響。我選擇了從大到小排列目标物，然後象擠牙膏那樣生成一組新的序列。用這樣的序列進行進化。基本上對于較小數目的目标物，很快能給出次優序列。從本人實驗的結果看，優化率（（直接切割所需長度－優化後所需長度）/直接切割所需長度）平均為11%，有時甚至高達28%。可見，優化和不優化還是有很大差别的。

最近就做了遺傳算法這方面的一點事情。希望對您能有用。