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

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

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

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