[發(fā)明專(zhuān)利]基于遺傳算法的調(diào)度方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201710068910.7
• 申請(qǐng)日: 2017-02-08
• 公開(kāi)（公告）號(hào): CN108399455B
• 公開(kāi)（公告）日: 2021-05-25
• 發(fā)明（設(shè)計(jì)）人: 郎元輝;韓寧;朱恒斌
• 申請(qǐng)（專(zhuān)利權(quán)）人: 西安京迅遞供應(yīng)鏈科技有限公司
• 主分類(lèi)號(hào): G06N3/12
• 分類(lèi)號(hào): G06N3/12;G06Q10/08
• 代理公司: 中國(guó)貿(mào)促會(huì)專(zhuān)利商標(biāo)事務(wù)所有限公司 11038
• 代理人: 許蓓

本發(fā)明公開(kāi)了一種基于遺傳算法的調(diào)度方法及裝置，涉及智慧倉(cāng)儲(chǔ)技術(shù)領(lǐng)域。其中的方法包括：隨機(jī)產(chǎn)生種群，種群中的個(gè)體代表各個(gè)調(diào)度集合之間的一一映射關(guān)系，個(gè)體的基因?yàn)檎{(diào)度集合中的元素；用二維數(shù)組對(duì)個(gè)體編碼，二維數(shù)組的第二維度表示調(diào)度集合，二維數(shù)組的第一維度表示調(diào)度集合中的元素；計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度；選取種群中滿(mǎn)足預(yù)設(shè)適應(yīng)度條件的個(gè)體作為父本和母本進(jìn)行交叉運(yùn)算，將父本和母本第一維度相同且第二維度相鄰的基因作為子代個(gè)體的部分基因，并由每個(gè)調(diào)度集合中除第一維度相同且第二維度相鄰的基因之外的元素隨機(jī)組成子代個(gè)體中該調(diào)度集合的其余基因；迭代交叉運(yùn)算直至種群滿(mǎn)足預(yù)設(shè)條件。從而提升了調(diào)度效率，節(jié)省了調(diào)度成本。

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

本發(fā)明涉及智慧倉(cāng)儲(chǔ)技術(shù)領(lǐng)域，特別涉及一種基于遺傳算法的調(diào)度方法及裝置。

背景技術(shù)

智慧倉(cāng)儲(chǔ)是未來(lái)發(fā)展的大勢(shì)所趨。無(wú)人倉(cāng)具備處理大量訂單的能力，可以大幅提升訂單處理效率及準(zhǔn)確率，降低人工成本，從而實(shí)現(xiàn)企業(yè)運(yùn)營(yíng)效率、經(jīng)營(yíng)效益的優(yōu)化。在無(wú)人倉(cāng)中，不同小車(chē)指派至不同托盤(pán)所需的路徑成本不同，不同托盤(pán)運(yùn)送至不同工位所需的路徑成本也不同。調(diào)度方法能夠?qū)崿F(xiàn)將小車(chē)指派到合適的托盤(pán)，并將托盤(pán)搬運(yùn)至合適的工位進(jìn)行生產(chǎn)，從而節(jié)約調(diào)度成本。因此，在無(wú)人倉(cāng)技術(shù)的實(shí)現(xiàn)過(guò)程中，調(diào)度方法起到較為核心作用，

傳統(tǒng)的調(diào)度方法中，采用遍歷的方法比較每一種調(diào)度組合的調(diào)度成本，然后確定調(diào)度成本最小的調(diào)度組合。然而隨著調(diào)度集合中所含元素個(gè)數(shù)的增多，對(duì)于遍歷的方法而言時(shí)間復(fù)雜度急劇增加，在有限的時(shí)間內(nèi)很難求得最小調(diào)度成本。而在有限時(shí)間內(nèi)或者有限的遍歷次數(shù)內(nèi)，獲得一個(gè)相對(duì)較低成本的調(diào)度組合隨機(jī)性較大，通常無(wú)法獲得令人滿(mǎn)意的調(diào)度組合。

遺傳算法是一種啟發(fā)式算法。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，可以不用依賴(lài)于問(wèn)題的具體領(lǐng)域，對(duì)解決問(wèn)題的種類(lèi)有很強(qiáng)的魯棒性，應(yīng)用廣泛。遺傳算法借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)，這些現(xiàn)象包括遺傳、交叉、變異等等。在遺傳算法的每次迭代運(yùn)算中都保留一組候選解，并按適應(yīng)度指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用交叉、變異等遺傳算子對(duì)這些個(gè)體不斷進(jìn)行組合產(chǎn)生新的子代，直到滿(mǎn)足某種收斂指標(biāo)為止。然而，在解決具有一一映射關(guān)系的小車(chē)集合、托盤(pán)集合以及工位集合之間的調(diào)度問(wèn)題時(shí)，為了能夠求得符合預(yù)設(shè)條件的調(diào)度組合，使用遺傳算法進(jìn)行求解并不能明顯提高調(diào)度效率，節(jié)省的調(diào)度成本也相對(duì)有限。

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

本發(fā)明解決的一個(gè)技術(shù)問(wèn)題是，在調(diào)度集合之間存在一一映射關(guān)系的前提下，如何快速高效的求得符合預(yù)設(shè)條件的調(diào)度組合，從而提高調(diào)度效率，節(jié)省調(diào)度成本。

根據(jù)本發(fā)明實(shí)施例的一個(gè)方面，提供了一種基于遺傳算法的調(diào)度方法，其特征在于，包括：隨機(jī)產(chǎn)生種群，種群中的個(gè)體代表各個(gè)調(diào)度集合之間的一一映射關(guān)系，個(gè)體的基因?yàn)檎{(diào)度集合中的元素；用二維數(shù)組對(duì)個(gè)體進(jìn)行編碼，二維數(shù)組的第二維度表示調(diào)度集合，二維數(shù)組的第一維度表示調(diào)度集合中的元素；計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度；選取種群中滿(mǎn)足預(yù)設(shè)適應(yīng)度條件的個(gè)體作為父本和母本進(jìn)行交叉運(yùn)算，在交叉運(yùn)算過(guò)程中，將父本和母本第一維度相同且第二維度相鄰的基因作為子代個(gè)體的部分基因，并由每個(gè)調(diào)度集合中除第一維度相同且第二維度相鄰的基因之外的元素隨機(jī)組成子代個(gè)體中該調(diào)度集合的其余基因；迭代地進(jìn)行交叉運(yùn)算以產(chǎn)生子代個(gè)體，直至種群滿(mǎn)足預(yù)設(shè)條件。

在一些實(shí)施例中，該方法還包括：選取種群中的部分個(gè)體進(jìn)行變異，在變異過(guò)程中，將變異個(gè)體屬于同一調(diào)度集合的多個(gè)元素所對(duì)應(yīng)的基因進(jìn)行隨機(jī)交換；迭代地進(jìn)行變異運(yùn)算以產(chǎn)生新的個(gè)體，直至種群滿(mǎn)足預(yù)設(shè)條件。

在一些實(shí)施例中，選取種群中0.5％至1％的個(gè)體進(jìn)行變異，在變異過(guò)程中，將變異個(gè)體30％至60％的基因進(jìn)行隨機(jī)交換。

在一些實(shí)施例中，計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度包括：根據(jù)個(gè)體所代表各個(gè)調(diào)度集合之間的一一映射關(guān)系中，各個(gè)調(diào)度集合的元素之間是否存在匹配關(guān)系，以及各個(gè)調(diào)度集合的元素之間的匹配成本，計(jì)算種群中每個(gè)個(gè)體的調(diào)度成本；根據(jù)種群中每個(gè)個(gè)體的調(diào)度成本的倒數(shù)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度。