[發明專利]基于三維移動模式序列與密母算法的三維裝箱方法

有效

• 申請號: 201410798189.3
• 申請日: 2014-12-19
• 公開（公告）號: CN104504468B
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 劉靜;焦李成;韓二麗;朱園;馬文萍;馬晶晶
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N3/12
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 王品華,王喜媛

1.一種基于三維移動模式序列與密母算法的三維裝箱方法，包括如下步驟：

(1)參數設定：

設N為遺傳算法中種群中的個體數，N為大于或等于2的整數，M為每個個體中箱子個數，M為大于或等于1的整數；用W、H、L分別表示裝箱容器的寬、高、長；Mgen表示進化的最大代數，pc0為箱子順序交叉概率，pc1為移動模式交叉概率，pc2為旋轉模式交叉概率，其中pc0、pc1、pc2為0到1之間的實數；pm為變異概率，取值為0到1之間的實數；w₁、h、l分別為箱子的寬、高、長，x、y、z為箱子放置坐標點的值，m為移動模式值，取值為0、1、2；r為旋轉模式值，旋轉模式包括6種，取值為0～5之間的整數；num為箱子的序號；TEM為爬山法的迭代次數；RX、RY、RZ分別表示最小立方體包絡的寬、高、長；gen為進化代數；結構體數組best[N]用于保存每一代中適應度最大的個體，結構體Best用于保存爬山法得到的適應度最大的個體；

(2)隨機產生初始種群，即隨機產生箱子序號0～M-1的排列，隨機產生旋轉模式0～5的排列，隨機產生移動模式0～2的排列，產生N個這樣的個體組成初始種群；計算每個個體的適應度值，設gen＝0；

(3)判斷是否滿足gen<Mgen，若是，執行步驟(4)，否則執行步驟(9)；

(4)根據種群中每個個體的適應度值，用二元錦標賽法從中選擇N個適應度值大的個體；

(5)隨機產生0到1之間的隨機數temp；隨機選擇兩個個體，若temp<pc0，則對這兩個個體的箱子順序進行交叉；若temp<pc1則對這兩個個體的移動模式進行交叉；若temp<pc2，則對這兩個個體的旋轉模式進行交叉，并重新計算這兩個個體的適應度值；

(6)隨機產生0到1之間的隨機數temp₁，若temp₁<pm，隨機選擇種群中的一個個體，隨機對該個體的箱子順序、移動模式、旋轉模式進行變異，并重新計算該個體的適應度值；

(7)對種群中的個體按適應度值從大到小進行排序，將當前代中適應度值最大的個體存放在結構體數組best[N]中；

(8)對gen自加1，返回步驟(4)；

(9)對結構體數組best[N]按個體適應度值從大到小進行排序，應用爬山法對結構體best[0]進行優化，將優化后得到的適應度值最大的個體存入Best中，輸出爬山法優化后適應度最大的個體Best，即為優化后裝箱結果，其中包括箱子序號num，箱子的寬w、高h、長l，箱子放置的坐標點x、y、z，箱子的旋轉模式r，移動模式m，適應度即體積利用率。