[发明专利]一种基于森林模型与改进遗传算法的船舶引航排班方法

摘要

本发明公开了一种基于森林模型与改进遗传算法的船舶引航排班方法。该方法根据引航任务衔接条件构建引航任务森林模型，采用改进广度优先搜索算法遍历引航任务森林获取初始引航任务组；根据初始引航任务组，采样改进遗传算法获取最优引航排班计划。本发明考虑了引航排班中各种成文的排班规则及不成文排班习惯，同时将引航排班问题所涉及的约束条件转化为费用模型，从可行性、公平性、效益三个角度出发，求解船舶引航排班方法。

主权项

一种基于森林模型与改进遗传算法的船舶引航排班方法，包括建立本地数据库，进行合同收池，其特征在于，该方法依次包括以下步骤：步骤(1a)：建立本地数据库，进行合同收池；步骤(1b)：从池中选出待引航排班船舶，根据引航任务衔接条件构建引航任务森林模型；步骤(1c)：采用改进广度优先搜索算法遍历引航任务森林获取初始引航任务组；步骤(1d)：根据初始引航任务组，采用改进遗传算法求解最优引航排班计划；步骤(1e)：根据确定的最优引航排班计划进行引航排班；对于所述步骤(1b)，构建引航任务森林模型的具体步骤如下：步骤(3a)：构建引航任务集合R；步骤(3b)：以引航任务为根节点，遍历引航任务集合R，根据引航任务衔接条件，为每个引航任务找出所有孩子节点，构造森林F；步骤(3c)：遍历森林F，若根据引航任务衔接条件，树中叶子节点存在孩子节点或孩子树，则通过将所有孩子节点与孩子树作为叶子节点的孩子更新当前树及森林F；步骤(3d)：若森林F中树的叶子节点存在孩子节点或孩子树，转步骤(3c)；步骤(3e)：输出引航任务的森林模型；对于所述步骤(1d)，改进遗传算法求解最优引航排班计划具体步骤如下：步骤(5a)：初始化参数；设置种群大小popsize，总运行代数gen，运行次数g＝1；交叉概率pc，变异概率pm，最优子群比λ；步骤(5b)：初始化种群；随机产生popsize个个体；步骤(5c)：计算适应度；根据适应度函数计算每个个体的适应度值；步骤(5d)：选择；将所有个体进行排序，以比率λ选择具有较优适应度值的个体构建最优个体子群；步骤(5e)：交叉；从最优个体子群中随机选择一个个体，当前个体以概率pc与随机选择的该个体交叉，得到子个体；步骤(5f)：变异；随机产生一(0,1)间实数rm，若rm<变异概率pm，则对当前个体执行变异操作；步骤(5g)：计算当前个体适应度值，如果该当前个体适应度值小于交叉变异前适应度值，更新当前个体；否则，个体不更新；步骤(5h)：如果当前运行次数g≤总运行代数gen，则运行次数g加1，转步骤(5c)；反之，进入步骤(5i)；步骤(5i)：输出最优解。