基于案例检索的集装箱码头箱区优化研究

2016-07-30 09:00大连东软信息学院商务管理系李浩渊孙冬石
中国商论 2016年17期
关键词:遗传算法

大连东软信息学院商务管理系 李浩渊 孙冬石

基于案例检索的集装箱码头箱区优化研究

大连东软信息学院商务管理系 李浩渊 孙冬石

摘 要:本文面对集装箱码头的进出口箱区规划问题,采用仿真模型与智能优化算法相结合的仿真优化方法进行分析求解。底层仿真模型覆盖集装箱码头全作业过程,并充分考虑了作业中的随机因素;顶层优化采用了遗传算法与案例检索相结合的一种创新方法,有效解决了仿真优化运算时间过长的问题。

关键词:仿真优化 箱区规划 遗传算法 案例检索

近年来伴随着集装箱码头吞吐量的不断增长,堆场资源变得越来越紧张。如何在有限的空间约束前提下,通过合理的规划和管理来提升作业效率,已经成为码头管理者关注的重点问题。

由于码头生产作业中包含诸多随机因素,数学模型往往很难描述[1],而仿真与优化相结合成为解决该问题的一种有效手段。因此,本文采用仿真优化方法对进出口箱区规划问题进行求解。

针对仿真优化方法中存在的运算时间过长问题,在Lee[2]和Bachelet[3]研究基础上,提出了一种改进的案例检索方法,较好地解决了运算代价过大的问题。

1  仿真模型

1.1 仿真对象

以国内某集装箱码头实际布局为背景,开展仿真模型构建仿真对象中,包含4个泊位,36个堆区,6排码头进出闸口通道,每个泊位分配若干岸桥,每台岸桥配备10台内部集卡,每个堆区配备一台龙门吊,码头内会随机产生若干外部集卡开展作业。

1.2 模型特点

(1)仿真模型能够实现多船作业模拟,对过程的描述能够细化到每台机械的运行过程。

(2)仿真过程以秒为单位,实现细粒度仿真推进。

(3)为节省仿真运行时间,本模型采用数学仿真方式。

2  仿真优化算法设计

2.1 算法原理

仿真优化是一种将仿真模型与优化算法结合使用的一种组合算法,其与传统优化的主要区别在于,仿真程序取代数学公式成为目标评价的方式,主要优点在于仿真程序相对数学模型能够更为充分地考虑到系统中随机因素的干扰,从而更为准确地对不同方案的表现进行评估。优化算法负责将性能参数输入仿真模型,仿真模型负责输出评价指标给优化算法,优化算法再根据评价结果开展进化搜索,并将更优参数再次回馈仿真模型,不断重复评价—优化过程,直至满足终止条件。

2.2 遗传算法设计

(1)编码方案

决策向量采用0~1编码方式:

其中,

(2)适值计算

综合考虑作业效率和岸桥利用率两个因素,分别进行归一化处理,形成评价适值

(3)遗传算子

选择策略:正比选择。

交叉策略:单切点方式,交叉概率0.9。

变异策略:位值方式,变异概率0.05。

(4)停止准则

最大进化代数100,运算停止。

3  基于案例检索的改进方法

3.1 案例检索原理

针对仿真优化方法运算时间过长的问题,可以从两个方面进行努力,一是避免重复仿真,二是通过预测减少表现不好的解的仿真次数。因此,本文设计了一种考虑近似匹配程度的案例检索方法。

3.2 几个基础定义

定义2:完全匹配案例

定义3:近似匹配案例

3.3 案例检索流程

步骤1:在案例库中,是否存在该解的完全匹配案例,如存在,跳转至步骤8。如不存在,跳转至步骤2。

步骤2:在不存在该解的完全匹配案例的情况下,再次检测是否存在该解的近似匹配案例,如存在,跳转至步骤3。如不存在,转步骤9。

步骤3:如果发现该解的近似匹配案例的表现较好时,即它的评价值与最好评价值非常接近,差值小于一个常数的话,则跳转至步骤5。否则,跳转至步骤4。

步骤4:如果发现该解的近似匹配案例的表现值不好时,即它的评价值与最好评价值相距较远,差值大于一个常数,则认为当前解仿真价值不大,但为了保证算法的探索能力,利用随机数则跳转至骤5。否则,跳转至步骤8。来决定是否继续仿真,若

步骤5:运行仿真程序,获得解的评价值。跳转至步骤6。

步骤6:对比该解在案例库中存储的评价值,若更优,更跳转至步骤7。否则,跳转至步骤10。

步骤7:更新评价值,跳转至步骤10。

步骤8:将案例库中存储的评价值直接赋予当前解,跳转至步骤10。

步骤9:通过运行仿真程序,获得解的评价值,并将其加入案例库。转步骤10。

步骤10:完成评价值获取后,继续优化算法运算。

3.4 案例检索特点

(1)实现了对已完成仿真结果的有效利用,避免重复仿真。

(2)只将局部最优案例加入案例库,并不是所有的新解均加入案例库,有效缩小了案例库的规模。

(3)通过评估预测,实现对好评价的获得可能性进行评估,从而大大减少了仿真次数。

(4)通过当前解与近似案例的对比,节省了大量仿真运算代价。

(5)通过当前解与最优解的对比,保证了算法的全局探索能力,确保了解的多样性。

4  实验与分析

4.1 仿真参数设计

在仿真运行的过程中,充分考虑码头作业的各项随机因素,采取数据统计和概率分布来进行随机描述,其中,岸桥、龙门吊的作业效率以及外部集卡在闸口处的作业时间,均服从正态分布,对应具体分布参数为和外部集卡的到达时间服从泊松分布,其具体分布参数设定为

4.2 案例检索效果分析

案例检索之所以能够实现运算代价的降低,主要源于两点:一是能找到完全匹配案例的解,不需要进行仿真;二是能找到近似匹配案例的解,通过进一步与最优案例的对比,也存在很大可能不通过仿真运算而直接完成赋值。

因此,在实验中,本文记录了算法运算各代中,检索到完全匹配案例的解的个数,检索到近似匹配案例的解的个数以及案例库的规模等数值,如表1所示。

表1 案例检索统计结果

从表1中可以看出,本文所设计的案例检索方法,有效减少了调用仿真程序的次数,从而大大降低了运算时长,而且很好地控制了案例库的整体规模,在问题得到求解的同时,运行时间的问题也得到了有效解决。

5  结语

本文面向集装箱码头箱区规划问题,运用仿真模型与优化算法相结合的仿真优化方法进行求解,并引入了考虑案例匹配的案例检索方法,有效地解决了运算代价的问题,获得了较好的解决方案。

参考文献

[1]于越,金淳,霍琳.基于仿真的集装堆场大门系统规划研究[J].系统仿真学报,2007(13).

[2]Lee L H,Chew E P Manikam P.A general framework on the simulation-based optimization under fixed computing budget[J].European Journal of Operational Research,2006(3).

[3]Bachelet B,Yon L.Model enhancement:improving theoretical optimization with simulation[J].Simulation Modelling Practice and Theory,2007(6).

中图分类号:F069

文献标识码:A

文章编号:2096-0298(2016)06(b)-162-02

猜你喜欢
遗传算法
基于遗传算法的高精度事故重建与损伤分析
基于改进遗传算法的多无人机协同侦察航迹规划
基于遗传算法的模糊控制在过热汽温控制系统优化中的应用
基于遗传算法的智能交通灯控制研究
基于遗传算法的教学楼智能照明控制系统设计
一种基于遗传算法的聚类分析方法在DNA序列比较中的应用
基于遗传算法的加速度计免转台标定方法
遗传算法在试题自动组卷中的应用
基于遗传算法的三体船快速性仿真分析
基于改进的遗传算法的模糊聚类算法