论文研究-基于改进NSGA-II算法的港口堆位分配问题研究.pdf

所需积分/C币:7 2019-09-07 22:32:07 568KB .PDF

散杂货港口堆位分配问题是一个典型的组合优化问题。在对此问题分析和建模的基础上,采用NSGA-II算法进行求解。针对问题搜索空间大、约束条件复杂等特点,对传统NSGA-II算法进行了改进,以提高算法的处理效率、收敛性和多样性。应用Java编程语言,融合JESS推理机,进行了改进NSGA-II算法的仿真研究。
36 2012,48(33) Computer Engineering and Applications计算机工程与应用 法,很好避免了父代中优秀个体的丢失 货物编号123 5 6 7 NSGA-I算法应用与改进 梁色体X1X2X3X4X5X6X7X8 散杂货港口堆位分配问题与普通的多目标调度 图1染色体编码 问题相比,主要存在以下两方面特点。 束,即各基因互不相同。 (1)搜索空问更为庞大:普通多目标调度问题 (2)约東条件处理 般涉及的决策元素较少,如车间调度问题,只涉及几 在多目标优化模型中往往都含有线性或非线性 台机器和十几个零件之间的组合分配。而对于堆约束,在应用遗传算法对问题求解时,必须对约束条 位分配问题,则由于考虑的对象划分更为细致,往往件进行适当处理,目前应用较多的方法为罚函数 需要涉及几十票货物和上百个堆位。问题域增大会法。该方法的主要思想是对于解空间中无对应可行 导致问题求解效率降低,计算复杂度变人。 解的个体,在计算适应度值时除以一个较大罚函数 (2)约東条件更为复杂:港口堆位分配问题的约从而降低该个体被遗传到下一代群体中的儿率。但 束条件主要表现在两个方面:一方面表现在货物和是使用该方法会使得种群在生成交叉利变异时由 堆位之间的约東,如货类约東、疏运方式约東等;另于间题个体的出现,导致种群屮可选个体变少,降低 一方面还表现在分配后堆位之间的约束,即每个堆算法效率,并且容易由于个别基因的错误,导致优秀 位只允许被安排一次。约束条件的增多会使得种群个体丢失。特别是对于散杂货港口堆位分配这种限 中无效个体增加,导致求解效率降低,收敛变慢,并制条件众多且相对复杂的多目标优化问题,使用罚 容易由于个别基因的错误,导致优秀个体丢失。 函数法无法满足算法收敛性和多样性的要求,因此 因此本文在利用NSGAⅡ算法进行堆位分配问本文提出采用约束限制矩阵和随机修复算子对约束 题求解时,为解决搜索空间大、约束条件复杂等难条件进行处理 点,采用了多种改进策略,以提高算法的收敛效率, ①约束限制矩阵 4避免优秀个体丢失,保持种群屮个体的多样性。 本文在随机生成初始种群前,根据如表1所示的4 (1)编码设计 散杂货港口货物和堆位约束关系,应用JESS推理机 目前编码方式主要有两种,分别为二进制编码生成来港卸船货物和港口堆位之间的约束关系矩阵 和实数编码。二进制编码是遗传算法最早采用的编RES(/) 码形式,其优点在于编码解码揀作简单,交叉、变异 在生成初始种群时,通过约束限制矩阵对问题 等遗传操作便于实现。但是二进制编码在处理求解的搜索空间进行限制,使得约束后的搜索空间中的 精度高和决策变量个数多的问题时,会导致染色体每个个体与解空间中的一个可行解对应,这样做不 长度过长,遗传操作计算复杂度增高,效率变低。另但可以反映问题的约東条件,保证种群中个体的有 外,二进制编码不能直接反映所求解问题的特定知效性,提高算法效率,而且通过搜索空间的缩小,也 识,因此不便于开发针对特定问题的遗传算子,也不可降低算法复杂度。此外,使用此方法生成初始种 便于处理复杂的约東条件。而采用实数编码则可以群后,在进行交叉操作时也可以保证交叉后的个体均 很好地解决以上问题,适合较大空间的遗传搜索,其满足货物和堆位限制条件。在进行变异操作时,同样 个体的编码长度等于其决策变量的个数。考虑到堆使用限制矩阵RES(/对变异范围进行控制。 位分配问题搜索空间大、约束条件复杂等特点,本文 ②随机修复算子 采用实数编码方式,如图1所示,每个基因表示货物 使用上述约束限制矩阵RES(可以较好地处 计划分配的堆位编码,在编码时不但需要考虑货物理货物和堆位约束条件,但对于散杂货港口每个堆 与堆位的约束条件,而且还需要考虑自身互异性约位只允许放置一票货物的限制,即种群中个体本身 表1货物和堆位约束限制条件 序号 限制条件 相关说明 1堆位存贮和装卸限制卸货的货物类型必须与堆位所能允许类型相匹配 堆位疏运方式限制卸货货物的计划疏运方式必须与堆位可实现的疏运方式相匹配 234 堆位容量限制 卸货货物重量不能大于堆位的容量 同一票货物限制已放置了某一票货物的堆位不允许放置其他货物 5 客户专堆限制客户专堆不允许存放其他客户货物 宋昕,黄磊:基于改进NSGA-∏算法的港口堆位分配问题研究 2012,48(33) 37 基因互异性的约束,使用约束限制矩阵的方法无法 (5)进化代数Ge加1。 实现。因此,本文设计了随机修复算子,对种群屮的 (6)将父代种群和子代种群合并生成合并种群, 个体进行基因重复性校验,并对问题个体进行随机规模为2P。 修复,以解决互异性约束的问题。随机修复算了流 (7)采用快速非支配排序算法和拥挤度比较算 程如图2所示。 子对合并种群中所有个体进行评价,根据结果从中 始神 选择优秀个体作为木次迭代的父代种群,以实现精 英保护 选取某一个体江 (8使用快速非支配排序算子和拥挤度比较算 (初始i=1) i=i+l 子对新生成的父代种群进行适应度评价 (9)根据评价结果,通过选择、交叉和变异等遗 重复性校验」 不重复 传揀作生成本次迭代的子代种群,在进行交叉、变异 重复 是 时同样应用自适应参数的方法。 随机选取某一重复 输出修复后种群 (10)使用随机修复算子对生成的子代种群进行 基因进行单点变异 互异性校验,并对问题个体进行随机修复。 图2随机修复算子流程 (11)判断是否满足算法终止条件,如果满足则直 (3)交叉和变异 接输出最优解集,即第一非支配最优集,如果不满足 交叉概率P和变异概率Pm直接影响遗传算法则将进化代数Gem加1,并返回步骤(6)。 的搜索效率和收敛性,参数过小则会由于搜索效率 低导致收敛速度变慢,过大则会由于个体波动过大5实验结果与分析 导致算法无法收敛。本文在充分考虑遗传算法特 根据上文提出的散杂货港口堆位分配模型,以 点的基础上,结合NSGAⅡ算法中的精英策略提出及改进NSGAⅢ算法流程,采用广州港集团实际生产 了按照进化代数变化的自适应交叉、变异概率如下业务数据,进行堆位分配仿真以验证本文提出的堆4 式所示。当进化代数较小时,交叉、变异概率取值较位分配模型和求解算法的性能。堆位分配模拟数据 小以保证种群中个体稳步进化,而当进化代数较大共涉及6艘船舶,16票货物,2个堆位 时,交叉、变异概率取值变大使得种群更容易跳岀局 表2为计划天数内计划到港卸货的船舶信息,其 部最优解,增加种群中个体的多样性,并由于精英策取自广州港集团生产业务管理系统中数据,主要包 略的存在,也不会由于参数变大而引起最优解丢失。 括船名、贸易类型、装卸类型、计划到港吋间等数据 c max p)×i Pci=pcmin 项。其中包含两艘外贸船舶,四艘内贸船舶。 Gen Pmax- p)× 表2船舶信息 n mll 序号船名贸易类型计划停靠泊位全船吨数船型 基于以上分析,本文给出了基于改进NSGA-Ⅲ的1安妮格力外贸 1泊位 8000散货船 散杂货港口堆位分配算法的总体流程: 2海上诚信外贸 3泊位 40000班轮 (1)应用JES推理引擎对计划天数内所有来港3振东329内贸 2泊位30000散货船 卸货货物和港口堆位进行模式匹配推理,获得货物 4广驳运555内贸 1泊位 2000散货船 江门130内贸 4泊位 2600散货船 堆位约東限制矩阵RES()。 6穗一508贸5泊位34000散货船 (2)根据生成的约束限制矩阵,随机生成初始种 群,设种群规模为P。 表3为计划天数内到港船舶所装载的货物信息 (3)使用随机修复算子,对种群中不满足堆位互主要包括货物名称、货类、计划疏运方式、货物重量 异性约束的个体进行修复。 等数据项。其中涉及粮食、饲料、钢材、煤炭和矿石 4使用快速非攴配排序算子和拥挤度比较算五类散杂货港口主要货类,汽车、驳船、火车和皮带 子对父代适应度进行评价,并根据结果进行选择、交机四种主要疏运方式 叉和变异等遗传操作生成第一代子代种群,在进行 表4为散杂货港口部分堆位信息,为降低处理复 交叉、变异时应用上文提岀的自适应参数的方法。杂度,采用如图3所示的散杂货港口通用模拟图对应 生成子代种群后,应用随杋修复算亍对种群进行校的模拟薮教捃,共涉及η个堆位,主要包括堆位名称 验和修复 所属场、可堆存货类、可支持疏运方式、堆位容量等 382012,48(33) Computer Engineering and Applications计算机工程与应用 闸 闸 二区 四区〓 五区 七区 八区 驳船治位皮带机九区 十区 铁路 驳船泊位 二泊位 三泊位 四泊位 五泊位 图3散杂货港口通用模拟图 表3货物信息 10堆场区域为第二作业线,4、8、11堆场区域为第 序号货物名称货类疏运方式所在船货物重量作业线 大豆粮食驳船安妮格力 20000 除了以上数据外,散杂货港口堆场调度问题还 木薯粉饲料火车安妮格力 8000 涉及港口疏运方式基础信息、客户基础信息、作业方 铁矿石矿石火车海上诚信 15000 式基础信息等,这里不再赘述。 4铁矿石矿石火车海上诚信 15000 表5为应用普通NSGA算法和改进NSGA-Il 567 铁矿石矿石火车海上诚信10000 烟台煤煤炭汽车振东329 12000 算法求解堆位分配问题时的比对结果,种群规模均 烟台煤煤炭汽车振东329 8000 为20,最大进化代数为500。可以看出改进 NSGA-II 烟台煤煤炭汽车振东32910000 算法更适合处理搜索空间大、约東条件复杂的多目 9螺纹钢钢材汽车广驳运55512000 标优化问题,在计算效率、收敛性和多样性上都优于 玉米粮食皮带机广驳运55510000 11冷轧卷钢钢材汽车 工门130 普通NSGA-Ⅱ算法。 12000 玉米粮食驳船 工门130 6000 表5两种算法比较 玉米粮食皮带机江门130 8000 14 块煤煤炭火车穗 12000 算法 最大值 最大值最大解个数耗时 第一目标第二目标第三目标 块煤煤炭汽车穗一50812000 NSGA-II 12.94 38.46 24.52 1270 16块煤煤炭驳船穗一50810000改进 NSGA-D1342100003846 800 表4堆位信息 为说明改进的NSGA-Ⅱ算法处理散杂货港口堆 序号堆位名称堆存货类作业线堆位类型堆位容量位分配多目标优化问题的优势,下文以一次具体计 11区1位 煤炭 露天 15000 21区2位 煤炭 露天 算过程为例,对结果进行分析,种群规模为20。经过 500 31区3位 矿石 露天15000 500次迭代计算,最终得到9组 Pareto最优解,其中比 41区4位煤炭矿石钢材1 露天 15000 较有代表性的五组解如表6所示,各组解优化目标值 51区5位煤炭矿石钢材 露天 15000 如表7所示。 61区6位煤炭矿石钢材1 露天 15000 如表6、7所示,各组解均满足货物堆位的约束条 件和堆位互异性的约束条件,前三组解分别为某一 6711区1位粮食饲料 仓库 10000 6811区2位粮食饲料 仓库 15000 优化目标达到最优,而其余一到两个优化目标表现 6911区3位粮食饲料 仓库 15000 不佳。第四、五组解三项日标函数均未能达到种群 7011区4位煤炭矿石钢材3 露天 15000 内最优,但三项目标值均较高,平衡性优丁前三组 7111×位煤炭矿钢材3露大15000解。通过此次求解过程可以看出,基于改进 NSGA-II 7211区6位煤炭矿石钢材3露天 15000 的散杂货港口堆位分配问题求解貝有以下3个主要 数据项。其中涉及露天堆场、仓库、圆筒仓等多种堆特点 场类型。考虑到港口作业车辆行驶路线和堆场布局 (1)算法处理效率高:改进NSGA-算法应用基 特点,设第1、2、5、6、9堆场区城为第一作业线,3、7、丁Rete高效算法的JESS推理机进行推理,得到货物 宋昕,黄磊:基于改进NSGA-∏算法的港口堆位分配问题研究 2012,48(33) 39 表6五组 Pareto解 到布置有皮带机疏运设各的堆场,可知该目标也已 序号解 解二 解匹解五 达到理论最大值。 16区4位9区1位9区1位9区1位9区1位 (3)种群多样性好:经过500次迭代,共得到9组 22区8位11区3位4区6位2区8位7区4位 33区3位3区3位3区3位3区3位3区3位 Pareto最优解,通过对每组解进行比对发现,其中大 472位7K6位7区2位7区2位7区2位 部分货物的堆存地点已固定,只是个别货物的堆存 510区6位10区6位8区1位10区6位10区6位地点选择时难以兼顾各项优化目标。如第四组解和 63区1位3区1位3区1位3区1位3区1位第五组解之间只有两票货物的堆场地点选择存在差 79区3位3区4位3区4位3区4位3区4位 异,导致第二个和第三个日标值各有优劣。港口调 6区3位2区6位6区3位6区3位6区3位 99区5位9区5位2区2位2区2位2区2位 度人员可以根据码头当班次的实际情况或个人偏好 102区7位6区4位6区4位9区4位9区4位 从多个推荐方案中进行选择。 l111区4位4区7位4区7位4区7位4区7位 121区1位1区1位1区1位3区8位1区1位6结束语 132区9位2区9位2区9位2区9位2区9位 木文在对多目标优化问题求解方法充分研究的 148区2位4区8位4区8位8区2位8区2位 158区5位8区5位8区5位8区5位8区5位 基础上,针对散杂货港口堆位分配问题特点,以提高 161区6位11区6位5区2位11区6位11区6位 算法收敛效率和多样性为日标,结合JSS推理引擎 提出了基于改进NSGAⅢ算法的多目标优化方法。 表7五组 Pareto解对应目标函数值 通过堆位分配求解实例,证明该方法可以有效解决 序号目标函数1目标函数2目标函数3 解一1.3452380938461 散杂货港口堆场多目标优化调度问题。 解二12200 100.000 17241 解 13.420 33.333 8.475 参考文献: 解四 12.823 26.315 31.2≤0 [1 Knowles J D, Corne D Approximating the non-dominated 解五 12.856 38.461 29.411 front using the Pareto archived evolution strategy[J]. Evo 和堆位的约束矩阵,并针对求解模型搜索空间大、约 lutionary Computation Journal, 2000, 8(2): 149-172 朿条件复杂等特点,采用约束限制矩阵随机修复算2]梦红云多目标进化算法及其应用研究[D]西安:西安电子 子和自适应参数等优化方法,加快了算法处理速度 科技大学,2005:34-62 和收敛效率。进化代数为500时可以得到十分理想3谢涛,陈火旺,康立山多目标优化的演化算法门计算机学 报,2003,26(8):997-1003 的收敛效果,平均耗时约为800ms,其中JESS推理耗 [4 Deb K, Agrawal S, Pratap A. A fast elitist non-dominated 时仅为5ms,种群初始化耗时约为45ms,迭代100次 sorting genetic algorithm for multi-objective optimization 耗时约为150ms NSGA-II[C]/Proceedings of Parallel Problem Solving (2)算法收敛性好:种群经过500次迭代后,三个 from Nature VI Conference, Paris, 2000: 849-858 优化目标最大值分别为13.42、100和38.46,根据22[5]雷德明,吴智铭基于个体密集距离的多目标进化算法[J 节给出的目标方程式(1.1)至式(1.3)进行分析,可知 计算机学报,2005,28(8):1320-1325 结果分令人满意。第一目标值(最大化货物总的6杨敬松,夏秀峰,徘才混合遗传算法在分布式车间作业 堆位匹配度)为13.42,即每票货物平均匹配度为 调度中的应用[J计算机工程与应用,2005,41(19):213-215 0.84,匹配度较高;第二日标值(最小化各作业线作业 [7 Hill FJess in action-rule-based systems in Java[M.Green ich: Manning, 2004 量失衡度)为最大值100,说明该目标已达到最优,即 [8] Nebro A J, Coello C A, Luna F,et aL. A comparative study 各作业线作业量完全平衡;第三目标值(最小化货物 of the effect of parameter sealability in multi-objective 水平运输总距离)为3846,考虑到第13票货物的疏 metaheuristics[C]IEEE Congress on Evolutionary Com 运要求和港口堆场布局限制,其必须从四泊位运送 puting,2008:1893-1900

...展开详情
试读 6P 论文研究-基于改进NSGA-II算法的港口堆位分配问题研究.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-基于改进NSGA-II算法的港口堆位分配问题研究.pdf 7积分/C币 立即下载
    1/6
    论文研究-基于改进NSGA-II算法的港口堆位分配问题研究.pdf第1页
    论文研究-基于改进NSGA-II算法的港口堆位分配问题研究.pdf第2页

    试读已结束,剩余4页未读...

    7积分/C币 立即下载 >