[發明專利]一種基于深度強化學習實現的裝箱方法

在審

• 申請號: 202010545595.4
• 申請日: 2020-06-16
• 公開（公告）號: CN111695700A
• 公開（公告）日: 2020-09-22
• 發明（設計）人: 呂長虹;張小銳;楊立光;王曉輝;來蕾
• 申請（專利權）人: 華東師范大學
• 主分類號: G06N20/00
• 分類號: G06N20/00;G06Q10/04;G06Q10/08
• 代理公司: 上海愉騰專利代理事務所(普通合伙) 31306
• 代理人: 唐海波

1.一種基于深度強化學習實現的裝箱方法，其特征在于，所述裝箱方法包括以下步驟：

獲取需要裝箱的區域和各矩形箱體信息；

根據區域和各矩形箱體信息通過深度強化學習返回裝箱策略；

根據返回的裝箱策略結合矩形帶排樣算法對各矩形箱體進行裝箱。

2.根據權利要求1所述的基于深度強化學習實現的裝箱方法，其特征在于，所述根據區域和各矩形箱體信息通過深度強化學習返回裝箱策略具體可包括：

選擇基于策略的強化學習方法作為強化學習算法；

使用深度神經網絡模型Pointer Networks作為強化學習算法的策略函數，隨機性策略作為策略函數的輸出；

累計獎勵的期望值作為目標函數；

策略函數Pointer Networks通過束搜索算法搜索裝箱策略，返回裝箱策略。

3.根據權利要求2所述的基于深度強化學習實現的裝箱方法，其特征在于，所述根據區域和各矩形箱體信息通過深度強化學習返回裝箱策略具體可包括：深度強化學習通過策略梯度算法計算目標函數的梯度值，并選擇Adam優化算法更新Pointer Networks的模型參數。

4.根據權利要求2所述的基于深度強化學習實現的裝箱方法，其特征在于，所述深度強化學習包括：將深度神經網絡模型作為強化學習算法的智能體，將區域作為環境，區域內矩形箱體的布局作為狀態，智能體持續地與環境交互，根據當前的狀態選擇行為，而環境會反饋給智能體新的狀態和獎勵。

5.根據權利要求4所述的基于深度強化學習實現的裝箱方法，其特征在于，作為智能體的深度神經網絡模型包括編碼器、解碼器和連接兩者的中間狀態向量，編碼器將輸入向量編碼成固定長度的中間狀態向量并傳給解碼器，解碼器對中間狀態向量進行分析解碼并輸出結果。

6.根據權利要求4所述的基于深度強化學習實現的裝箱方法，其特征在于，所述深度強化學習的獎勵函數可如下：

其中，假設矩形箱體數量為N，τ為智能體的決策過程對應的采樣軌跡，s為環境反饋的狀態，a為智能體對狀態做出的行為，θ表示Pointer Networks的模型參數，為在當前模型參數θ下生成采樣軌跡τ的總獎勵值的期望值，則有采樣軌跡τ的概率為，

7.根據權利要求6所述的基于深度強化學習實現的裝箱方法，其特征在于，采取策略梯度算法對Pointer Networks的模型參數進行優化。

8.根據權利要求7之所述的基于深度強化學習實現的裝箱方法，其特征在于，所述策略梯度算法的優化流程如下：

訓練數據集S，迭代次數T，一次迭代所選取的樣本數B；

初始化Pointer Networks模型參數θ，初始化偏移量b；

對于t＝1～N，從訓練數據集S中選取一次迭代所需樣本s_i，i∈{1，…，B}，通過p_θ(·|θ)為每一個樣本s_i，i∈{1，…，B}生成解決方案o_i；

計算

更新模型參數更新偏移量b。

9.根據權利要求1至8之一所述的基于深度強化學習實現的裝箱方法，其特征在于，所述矩形帶排樣算法為構造類啟發式Bottom-Left-Fill算法。

10.根據權利要求9所述的基于深度強化學習實現的裝箱方法，其特征在于，所述Bottom-Left-Fill算法按順序依次放置矩形箱體，每個矩形箱體在初始階段放置到區域的右上方，并使矩形箱體不斷交替地向下向左移動，直至矩形箱體在當前所處位置不能繼續移動。