[發(fā)明專利]一種基于基因庫解決堆垛機(jī)路徑規(guī)劃的蟻群遺傳混合算法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110652142.6
• 申請(qǐng)日: 2021-10-21
• 公開（公告）號(hào): CN113743608A
• 公開（公告）日: 2021-12-03
• 發(fā)明（設(shè)計(jì)）人: 李東東;王雷;耿賽;黃勝洲;王風(fēng)濤;馬康康;謝芳琳;劉明豪;顧瀚;王飛
• 申請(qǐng)（專利權(quán)）人: 安徽工程大學(xué)
• 主分類號(hào): G06N3/12
• 分類號(hào): G06N3/12;G06Q10/04
• 代理公司: 安徽省蚌埠博源專利商標(biāo)事務(wù)所(普通合伙) 34113
• 代理人: 楊晉弘

本發(fā)明涉及一種基于基因庫解決堆垛機(jī)路徑規(guī)劃的蟻群遺傳混合算法，首先，將創(chuàng)建一個(gè)基因庫，用來存放個(gè)體的基因片段，在生成個(gè)體時(shí)，通過蟻群算法從基因庫中挑選優(yōu)良的基因片段來嘗試構(gòu)建較為優(yōu)秀的個(gè)體，通過以上策略，能有效的避免不好的基因片段對(duì)遺傳算法造成的影響，從而加速遺傳算法的收斂，同時(shí)，由于蟻群算法對(duì)未知的基因片段也具有一定的選擇概率，因此，對(duì)克服陷入局部最優(yōu)解也具備一定的效果。大量的仿真結(jié)果表明，采取本文新型策略的蟻群?遺傳混合算法在解決堆垛機(jī)路徑規(guī)劃的效果明顯，相對(duì)比傳統(tǒng)遺傳算法，不僅收斂速度更快，而算法對(duì)最優(yōu)解的獲得也具有較好的穩(wěn)定性。

技術(shù)領(lǐng)域

本發(fā)明涉及堆垛機(jī)路徑規(guī)劃技術(shù)領(lǐng)域，具體是一種基于基因庫解決堆垛機(jī)路徑規(guī)劃的蟻群遺傳混合算法。

背景技術(shù)

經(jīng)濟(jì)高速發(fā)展的今天，物流的高效性越發(fā)顯得重要，傳統(tǒng)的人為管理模式不再滿足行業(yè)的需求，于是，自動(dòng)化倉儲(chǔ)系統(tǒng)(Automated Storage and Retrieval System, AS/RS)橫空出世。作為一種新型的倉儲(chǔ)技術(shù)，同時(shí)也作為現(xiàn)代物流系統(tǒng)的核心部分，AS/RS正越來越多地應(yīng)用于各個(gè)行業(yè)。考慮到倉庫的出入庫效率直接影響到整個(gè)物流系統(tǒng)的效率，因此提高整個(gè)物流系統(tǒng)效率的一個(gè)關(guān)鍵方向就是出入庫路徑的優(yōu)化。堆垛機(jī)，作為AS/RS中的運(yùn)輸和存取貨物的主要設(shè)備，其揀選出入庫貨物的時(shí)間往往占整個(gè)作業(yè)周期的50%左右，因此解決堆垛機(jī)行駛路徑優(yōu)化問題是提高自動(dòng)化倉庫效率的有效手段。

路徑規(guī)劃技術(shù)是堆垛機(jī)研究領(lǐng)域的一個(gè)重要組成部分，主要目的是在初始化有若干進(jìn)出貨物任務(wù)的環(huán)境中，根據(jù)一定的準(zhǔn)則(如路徑最短，用時(shí)最短等)，尋求一個(gè)從庫口依次存取貨物的最優(yōu)策略。路徑規(guī)劃技術(shù)的發(fā)展在一定程度上標(biāo)志著堆垛機(jī)智能水平的高低，而路徑規(guī)劃方法的優(yōu)劣直接影響路徑規(guī)劃效果。

目前，在該問題上，考慮到解空間往往過于龐大，多使用啟發(fā)式算法來解決問題，啟發(fā)式算法不必遍歷整個(gè)解空間，只需通過遍歷子空間即可獲得全局最優(yōu)解或者次優(yōu)解。常用于該問題的啟發(fā)式算法主要有遺傳算法、粒子群算法、人工魚群算法等。其中，遺傳算法以其編碼簡(jiǎn)單，邏輯過程清晰，易于實(shí)現(xiàn)等特點(diǎn)，使得其在堆垛機(jī)的路徑規(guī)劃問題上廣泛應(yīng)用。但遺傳算法的缺點(diǎn)也十分明顯，例如收斂速度較慢，易于陷入最優(yōu)解等。究其原因，遺傳算法是以整個(gè)個(gè)體為操作對(duì)象，主要包括選擇、交叉、變異這三類操作，但事實(shí)上一個(gè)個(gè)體是由若干個(gè)基因片段構(gòu)成，這就會(huì)使得某些不好的基因片段通過干擾所在個(gè)體的整體評(píng)價(jià)，從而干擾算法對(duì)個(gè)體所含的優(yōu)秀基因片段的挖掘。另外，變異操作通常是取隨機(jī)位置的基因片段進(jìn)行變異，由于是隨機(jī)的，可能會(huì)導(dǎo)致某些好的基因片段被變異成了壞的基因片段，這同樣會(huì)給算法的效率帶來負(fù)面影響。

基于此，本發(fā)明提出一種基于基因庫的蟻群-遺傳混合算法來解決路徑規(guī)劃問題。首先，提出一種基因庫模型來儲(chǔ)存基因片段，個(gè)體的生成依賴蟻群算法從基因庫中挑選合適的基因片段合成，并在這過程中輔以閾值進(jìn)行篩選出壞的基因片段，從而在迭代的過程中，逐漸剔除壞的基因片段的影響。

發(fā)明內(nèi)容

本發(fā)明的目的就是為了解決現(xiàn)有的遺傳算法收斂速度較慢、易于陷入最優(yōu)解的缺點(diǎn)，提供的一種基于基因庫的蟻群遺傳混合算法，來解決路徑規(guī)劃問題。

為了實(shí)現(xiàn)上述目的，本發(fā)明采用了如下技術(shù)方案：

一種基于基因庫解決堆垛機(jī)路徑規(guī)劃的蟻群遺傳混合算法，其特征在于包括以下步驟：

1）建立復(fù)合任務(wù)單元

假設(shè)問題模型初始為入庫任務(wù)I有m個(gè)，出庫任務(wù)O有n個(gè)，假定堆垛機(jī)的容量為1，那么總?cè)蝿?wù)的解的序列模型L為:

(1)