[發明專利]基于遺傳算法的調度方法及裝置

有效

• 申請號: 201710068910.7
• 申請日: 2017-02-08
• 公開（公告）號: CN108399455B
• 公開（公告）日: 2021-05-25
• 發明（設計）人: 郎元輝;韓寧;朱恒斌
• 申請（專利權）人: 西安京迅遞供應鏈科技有限公司
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/08
• 代理公司: 中國貿促會專利商標事務所有限公司 11038
• 代理人: 許蓓

1.一種基于遺傳算法的倉儲調度方法，其特征在于，包括：

隨機產生種群，所述種群中的個體代表各個調度集合中非空元素之間的一一映射關系，所述個體的基因為調度集合中的元素，所述調度集合包括小車集合、托盤集合以及工位集合；

用二維數組對所述個體進行編碼，二維數組的第二維度表示不同調度集合的非空元素之間的一一映射關系，二維數組的第一維度表示調度集合中的元素；

計算種群中每個個體的適應度，包括：根據個體所代表各個調度集合中非空元素之間的一一映射關系中，各個調度集合的非空元素之間是否存在匹配關系，以及各個調度集合的非空元素之間的匹配成本，計算種群中每個個體的調度成本；根據種群中每個個體的調度成本的倒數計算種群中每個個體的適應度；

選取種群中滿足預設適應度條件的個體作為父本和母本進行交叉運算，在所述交叉運算過程中，將父本和母本第一維度相同且第二維度相鄰的基因作為子代個體的部分基因，并由每個調度集合中除所述第一維度相同且第二維度相鄰的基因之外的元素隨機組成子代個體中該調度集合的其余基因；

迭代地進行交叉運算以產生子代個體，直至種群滿足預設條件。

2.如權利要求1所述的倉儲調度方法，其特征在于，所述倉儲調度方法還包括：

選取種群中的部分個體進行變異，在所述變異過程中，將變異個體屬于同一調度集合的多個元素所對應的基因進行隨機交換；

迭代地進行變異運算以產生新的個體，直至種群滿足預設條件。

3.如權利要求2所述的倉儲調度方法，其特征在于，選取種群中0.5％至1％的個體進行變異，在所述變異過程中，將變異個體30％至60％的基因進行隨機交換。

4.如權利要求1所述的倉儲調度方法，其特征在于，所述選取種群中滿足預設適應度條件的個體作為父本和母本進行交叉運算包括：

選取種群中適應度高于預設值的個體，并計算所述適應度高于預設值的個體所對應的總適應度；

以所述適應度高于預設值的個體的適應度與所述總適應度的比值為概率，選擇所述適應度高于預設值的個體作為父本和母本進行交叉運算。

5.如權利要求1或2所述的倉儲調度方法，其特征在于，所述種群滿足預設條件包括以下條件中的至少一種：

(1)交叉運算的迭代次數高于預設值；

(2)變異的迭代次數高于預設值；

(3)種群中存在適應度函數值大于預設值的個體。

6.一種基于遺傳算法的倉儲調度裝置，其特征在于，包括：

種群產生模塊，用于隨機產生種群，所述種群中的個體代表各個調度集合之間的一一映射關系，所述個體的基因為調度集合中的元素，所述調度集合包括小車集合、托盤集合以及工位集合；

個體編碼模塊，用于用二維數組對所述個體進行編碼，二維數組的第二維度表示不同調度集合的非空元素之間的一一映射關系，二維數組的第一維度表示調度集合中的元素；

適應度計算模塊，用于計算種群中每個個體的適應度，包括：調度成本計算單元，用于根據個體所代表各個調度集合之間非空元素的一一映射關系中，各個調度集合的非空元素之間是否存在匹配關系，以及各個調度集合的非空元素之間的匹配成本，計算種群中每個個體的調度成本；適應度計算單元，用于根據種群中每個個體的調度成本的倒數計算種群中每個個體的適應度；

交叉運算模塊，用于選取種群中滿足預設適應度條件的個體作為父本和母本進行交叉運算，在所述交叉運算過程中，將父本和母本第一維度相同且第二維度相鄰的基因作為子代個體的部分基因，并由每個調度集合中除所述第一維度相同且第二維度相鄰的基因之外的元素隨機組成子代個體中該調度集合的其余基因；

第一迭代運算模塊，用于迭代地進行交叉運算以產生子代個體，直至種群滿足預設條件。

7.如權利要求6所述的倉儲調度裝置，其特征在于，所述倉儲調度裝置還包括：

變異模塊，用于選取種群中的部分個體進行變異，在所述變異過程中，將變異個體屬于同一調度集合的多個元素所對應的基因進行隨機交換；

第二迭代運算模塊，用于迭代地進行變異運算以產生新的個體，直至種群滿足預設條件。