[發(fā)明專利]一種基于遺傳算法的板式家具智能打包方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202111351734.0
• 申請(qǐng)日: 2021-11-16
• 公開（公告）號(hào): CN114004167B
• 公開（公告）日: 2023-10-17
• 發(fā)明（設(shè)計(jì)）人: 趙詩奎;季晏慶
• 申請(qǐng)（專利權(quán)）人: 濟(jì)南大學(xué)
• 主分類號(hào): G06F30/27
• 分類號(hào): G06F30/27;G06N3/126;G06F111/04;G06F111/08;G06F111/16
• 代理公司: 濟(jì)南圣達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 37221
• 代理人: 李圣梅

1.一種基于遺傳算法的板式家具智能打包方法，其特征在于，包括以下步驟：

步驟1：讀取問題數(shù)據(jù)，初始化待打包家具尺寸數(shù)據(jù)集合、包裝紙參數(shù)數(shù)據(jù)集合、打包約束數(shù)據(jù)集合、種群數(shù)目、染色體基因維數(shù)、最大迭代次數(shù)；

步驟2：利用基于最低水平線搜索方法生成數(shù)量為種群規(guī)模一半的不同的打包初始方案；

步驟3：將初始方案與隨機(jī)產(chǎn)生的其它打包方案按照種群數(shù)量各占一半的方式共同組成遺傳算法的初始種群；

步驟4：利用最低水平線法解碼方法計(jì)算個(gè)體適應(yīng)度值，即打包所需包裹數(shù)量；

步驟5：采用基于概率的方式選擇進(jìn)行操作的個(gè)體，即先將適應(yīng)度值進(jìn)行歸一化處理，所用包裹數(shù)量越少，適應(yīng)度值越大，個(gè)體適應(yīng)度越大，則被選擇的機(jī)會(huì)也就越大，每一輪產(chǎn)生一個(gè)[0，1]內(nèi)的均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)與個(gè)體適應(yīng)度進(jìn)行比較，個(gè)體適應(yīng)度大于該隨機(jī)數(shù)時(shí)，保留此個(gè)體到交配池中；

步驟6：從交配池中隨機(jī)選擇一對(duì)個(gè)體，隨機(jī)選擇兩個(gè)交叉點(diǎn)位置，依次交換交叉點(diǎn)之間所選中的成對(duì)板式家具打包順序，以確定交叉后每個(gè)板式家具只打包一次；

步驟7：對(duì)選中的單個(gè)個(gè)體，隨機(jī)交換其一對(duì)板式家具的打包順序作為變異操作，產(chǎn)生新的個(gè)體；

步驟8：判斷是否達(dá)到最大迭代次數(shù)：若滿足，結(jié)束搜索過程，輸出最優(yōu)值；若不滿足，則繼續(xù)迭代優(yōu)化，轉(zhuǎn)入步驟4。

2.根據(jù)權(quán)利要求1所述的打包約束，其特征在于，每個(gè)包裹的第一層只能有一塊板，不同的包裹根據(jù)底板的不同和包裹重量的約束會(huì)有不同的打包層數(shù)約束。

3.根據(jù)權(quán)利要求1所述的遺傳算法中的染色體，其特征在于，染色體編碼為帶符號(hào)的十進(jìn)制編碼，帶負(fù)號(hào)的染色體基因表示對(duì)應(yīng)的板式家具打包時(shí)按照高度大于寬度的方式進(jìn)行打包，若對(duì)應(yīng)的板式家具被選擇為底板，需將該染色體基因修正為正數(shù)后再進(jìn)行打包操作。

4.根據(jù)權(quán)利要求1所述的優(yōu)化目標(biāo)為減少包裹數(shù)量。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述生成打包初始方案的基于最低水平線搜索方法包括以下步驟：

步驟1：讀取問題數(shù)據(jù)，初始化待打包家具尺寸數(shù)據(jù)集合、包裝紙參數(shù)數(shù)據(jù)集合、打包約束數(shù)據(jù)集合；

步驟2：對(duì)所有板式家具按照寬度和高度進(jìn)行處理：首先對(duì)高度大于寬度的板式家具進(jìn)行旋轉(zhuǎn)，計(jì)算所有板式家具的面積。按照面積降序排序，生成集合RectSize1{}。按照寬度降序排序，對(duì)于寬度相同的按照高度降序排序生成集合RectSize2{}。按照高度降序排序，對(duì)于高度相同的按照寬度降序排序生成集合RectSize3{}；

步驟3：從矩形集合RectSize1{}中選擇面積最大的未打包板式家具，根據(jù)其寬度和高度確定底板的尺寸，以此選擇合適的包裝紙，即包裝紙的寬度和高度均大于板式家具的寬度和高度，根據(jù)選取的包裝紙和底板確定包裹的層數(shù)約束。生成一個(gè)水平線集合，將與所選板式家具寬度對(duì)應(yīng)的底部水平線作為基準(zhǔn)排放水平線加入到所述水平線集合中。若矩形空間RectSize1{}中已經(jīng)沒有未打包板式家具，結(jié)束打包，導(dǎo)出初始打包方案Order{}，以作為遺傳算法的初始個(gè)體；

步驟4：找出最低水平線，在矩形集合RectSize2{}中尋找寬度小于等于所述最低水平線的寬度，且排入后該矩形的頂部水平線不高于底板高度的待排板式家具，為了保持遺傳算法種群的多樣性，在搜索到的前三個(gè)板式家具中任選一個(gè)記錄其寬度，搜索不到則記為0。在矩形集合RectSize3{}中尋找高度小于等于所述最低水平線的寬度，且旋轉(zhuǎn)排入后該矩形的頂部水平線不高于底板高度的待排板式家具，為了保持遺傳算法種群的多樣性，在搜索到的前三個(gè)板式家具中任選一個(gè)記錄其高度，搜索不到則記為0；

步驟5：判斷記錄的板式家具的寬度或高度是否大于0，如果記錄的數(shù)據(jù)大于0，則說明存在待排板式家具可以被打包放置，取板式家具的寬度和高度中較大的，若所取板式家具的寬度大于高度，將選取的板式家具寬度對(duì)應(yīng)矩形集合RectSize2{}中的矩形靠左排放在所述最低水平線上，并記錄該板式家具的序號(hào)到集合Order{}，轉(zhuǎn)入步驟6，若所取板式家具的高度大于寬度，將選取的板式家具高度對(duì)應(yīng)矩形集合RectSize3{}中的矩形旋轉(zhuǎn)后靠左排放在所述最低水平線上，并記錄帶負(fù)號(hào)的該板式家具的序號(hào)到集合Order{}，轉(zhuǎn)入步驟6。如果記錄的板式家具的寬度和高度均等于0，說明沒有任何待排板式家具可以被排放到該位置，則該空間視為浪費(fèi)，此時(shí)需要將最低水平線位置的高度提升為左鄰居和右鄰居中高度最小的一個(gè)高度，轉(zhuǎn)入步驟4，若只有一條最低水平線且不能放置任何板式家具，轉(zhuǎn)入步驟7；

步驟6：更新最低水平線集合，將放置矩形位置對(duì)應(yīng)的最低水平線替換為矩形對(duì)應(yīng)的頂部水平線集合。刪除矩形集合RectSize1{}、RectSize2{}、RectSize3{}中該板式家具的尺寸以及面積信息，轉(zhuǎn)入步驟4。若矩形空間RectSize1{}中已經(jīng)沒有未打包板式家具，結(jié)束打包，導(dǎo)出初始打包方案Order{}，以作為遺傳算法的初始個(gè)體；

步驟7：判斷該包裹是否裝滿，未裝滿則需要重新生成一個(gè)尺寸大小與底板相同的最低水平線集合轉(zhuǎn)入步驟4繼續(xù)排放未打包板件，若該包裹已經(jīng)裝滿，轉(zhuǎn)入步驟3。

6.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述遺傳算法解碼方法為最低水平線法包括以下步驟：

步驟1：讀取問題數(shù)據(jù)，初始化待打包家具尺寸數(shù)據(jù)集合、板式家具對(duì)應(yīng)的矩形集合、包裝紙參數(shù)數(shù)據(jù)集合、打包約束數(shù)據(jù)集合、當(dāng)前染色體對(duì)應(yīng)的打包順序集合Order{}；

步驟2：從打包順序集合Order{}中按順序從矩形集合中選擇未打包板式家具，根據(jù)其寬度和高度確定底板的尺寸，以此選擇合適的包裝紙，即包裝紙的寬度和高度均大于板式家具的寬度和高度，根據(jù)選取的包裝紙和底板確定包裹的層數(shù)約束。生成一個(gè)水平線集合，將與所選板式家具寬度對(duì)應(yīng)的底部水平線作為基準(zhǔn)排放水平線加入到所述水平線集合中。若已經(jīng)沒有未打包板式家具，結(jié)束打包，導(dǎo)出包裹數(shù)量為適應(yīng)度值；

步驟3：找出最低水平線，從打包順序集合Order{}中按順序從矩形集合中選擇未打包板式家具，判斷當(dāng)前板式家具是否能擺放在該水平線上，即該板式家具寬度小于等于所述最低水平線的寬度，且排入后該矩形的頂部水平線不高于底板高度，對(duì)應(yīng)的染色體基因?yàn)樨?fù)數(shù)時(shí)，判斷條件為該板式家具高度小于等于所述最低水平線的寬度，且旋轉(zhuǎn)排入后該矩形的頂部水平線不高于底板高度：如果滿足條件，轉(zhuǎn)入步驟4；若不滿足條件，轉(zhuǎn)入步驟5；

步驟4：更新最低水平線集合，將放置矩形位置對(duì)應(yīng)的最低水平線替換為矩形對(duì)應(yīng)的頂部水平線集合。刪除打包順序集合Order{}中板式家具對(duì)應(yīng)的打包順序，轉(zhuǎn)入步驟3。若已經(jīng)沒有未打包板式家具，結(jié)束打包，導(dǎo)出包裹數(shù)量為適應(yīng)度值；

步驟5：沒有任何板式家具可以放到該位置，則該空間視為浪費(fèi)，判斷是否可以提升最低水平線：如果可以，此時(shí)需要將最低水平線位置的高度提升為左鄰居和右鄰居中高度最小的一個(gè)高度，轉(zhuǎn)入步驟3；如果不可以，轉(zhuǎn)入步驟6；

步驟6：判斷該包裹是否裝滿，即該層是否為包裹的頂層：如果不是，需要重新生成一個(gè)尺寸大小與底板相同的最低水平線集合，轉(zhuǎn)入步驟3繼續(xù)排放未打包板件；若該包裹已經(jīng)裝滿，轉(zhuǎn)入步驟2。