利用混合單新遺傳算法求解二維裝箱問題.pdf

1、裝箱問題是指將一些給定的不同尺寸的物品按照要求擺放入有一定容積的容器中,以獲得某種最佳的效益。裝箱問題涉及多學(xué)科、多領(lǐng)域的知識,在生產(chǎn)實(shí)踐中被廣泛的應(yīng)用。二維裝箱問題在現(xiàn)實(shí)生活中隨處可見,與人們的生產(chǎn)生活密切相關(guān),找到二維裝箱問題的有效算法可以節(jié)省資源,提高生產(chǎn)效率,對人們的生產(chǎn)生活產(chǎn)生重大影響,從而對人類社會產(chǎn)生積極的推動作用。同時(shí)求解二維裝箱問題的各種算法也能應(yīng)用到求解三維裝箱問題中,因此研究二維裝箱問題有著重要的理論意義和應(yīng)用價(jià)值

2、。
　　 裝箱問題是一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問題,在理論上屬于NP-hard問題。其求解是極為困難的。從20世紀(jì)70年代初開始,裝箱問題就引起了人們的關(guān)注。到目前為止,世界上研究的比較多的是一維及二維裝箱問題,人們提出了大量的求解裝箱問題的算法,其中最主要的算法有啟發(fā)式算法和遺傳算法。
　　 本文首先對裝箱問題的種類及研究現(xiàn)狀進(jìn)行了綜述,總結(jié)了現(xiàn)有的關(guān)于裝箱問題的一些算法,包括啟發(fā)式算方法和遺傳算法。闡述了遺傳算法

3、的基本實(shí)現(xiàn)機(jī)理,并對單親遺傳算法進(jìn)行了概述,然后針對二維矩形裝箱問題,對現(xiàn)有的FFA算法及其改進(jìn)算法IFFA進(jìn)行了分析,并對IFFA算法進(jìn)一步加以改進(jìn),提出了一種IFFA2算法,在IFFA2算法中,考慮了碎片的利用,并通過舉例說明了碎片的產(chǎn)生及表示方法,最后嘗試把IFFA2算法與單親遺傳算法結(jié)合起來構(gòu)成混合單親遺傳算法來實(shí)現(xiàn)對二維裝箱問題的求解,并給出了算法實(shí)現(xiàn)的流程圖。在算法中,提出了同時(shí)考慮物品裝箱順序及物品放置方向的編碼方案,并設(shè)