[發明專利]一種基于森林模型與改進遺傳算法的船舶引航排班方法

有效

• 申請號: 201410465020.6
• 申請日: 2014-09-12
• 公開（公告）號: CN104268639B
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 薛云燦;張海霞;李彬;楊啟文
• 申請（專利權）人: 河海大學常州校區
• 主分類號: G06Q10/04
• 分類號: G06Q10/04
• 代理公司: 南京縱橫知識產權代理有限公司32224
• 代理人: 董建林,汪慶朋

1.一種基于森林模型與改進遺傳算法的船舶引航排班方法，包括建立本地數據庫，進行合同收池，其特征在于，該方法依次包括以下步驟：

步驟(1a)：建立本地數據庫，進行合同收池；

步驟(1b)：從池中選出待引航排班船舶，根據引航任務銜接條件構建引航任務森林模型；

步驟(1c)：采用改進廣度優先搜索算法遍歷引航任務森林獲取初始引航任務組；

步驟(1d)：根據初始引航任務組，采用改進遺傳算法求解最優引航排班計劃；

步驟(1e)：根據確定的最優引航排班計劃進行引航排班；

對于所述步驟(1b)，構建引航任務森林模型的具體步驟如下：

步驟(3a)：構建引航任務集合R；

步驟(3b)：以引航任務為根節點，遍歷引航任務集合R，根據引航任務銜接條件，為每個引航任務找出所有孩子節點，構造森林F；

步驟(3c)：遍歷森林F，若根據引航任務銜接條件，樹中葉子節點存在孩子節點或孩子樹，則通過將所有孩子節點與孩子樹作為葉子節點的孩子更新當前樹及森林F；

步驟(3d)：若森林F中樹的葉子節點存在孩子節點或孩子樹，轉步驟(3c)；

步驟(3e)：輸出引航任務的森林模型；

對于所述步驟(1d)，改進遺傳算法求解最優引航排班計劃具體步驟如下：

步驟(5a)：初始化參數；設置種群大小popsize，總運行代數gen，運行次數g＝1；交叉概率p_c，變異概率p_m，最優子群比λ；

步驟(5b)：初始化種群；隨機產生popsize個個體；

步驟(5c)：計算適應度；根據適應度函數計算每個個體的適應度值；

步驟(5d)：選擇；將所有個體進行排序，以比率λ選擇具有較優適應度值的個體構建最優個體子群；

步驟(5e)：交叉；從最優個體子群中隨機選擇一個個體，當前個體以概率p_c與隨機選擇的該個體交叉，得到子個體；

步驟(5f)：變異；隨機產生一(0,1)間實數r_m，若r_m<變異概率p_m，則對當前個體執行變異操作；

步驟(5g)：計算當前個體適應度值，如果該當前個體適應度值小于交叉變異前適應度值，更新當前個體；否則，個體不更新；

步驟(5h)：如果當前運行次數g≤總運行代數gen，則運行次數g加1，轉步驟(5c)；反之，進入步驟(5i)；

步驟(5i)：輸出最優解。