差分进化算法研究及在港口物流调度中的应用.doc

差分进化算法研究及在港口物流调度中的应用制造及物流系统中广泛存在着设备及资源优化问题,优化的质量和效果直接关系到系统的运行成本及生产效率,因此如何设计高效的优化算法已成为学术界和工业界共同关注的热点问题。优化问题根据变量的取值可分为连续最优化问题和离散最优化问题,本文针对这两类不同的典型优化问题,对差分进化算法进行了系统性的基础研究和应用研究。本文针对以非线性规划为代表的连续最优化问题和以资源约束项目调度为代表的离散最优化问题,研究了分别求解连续和离散最优化问题的两种差分进化算法。针对非线性规划问题,提出了新的基于个体依赖机制的差分进化算法,并以集装箱船舶配载计划问题为背景,进行了应用研究；针对资源约束项目调度问题,提出了新的离散差分进化算法,并以集装箱港口泊位和岸桥集成调度问题为背景,进行了应用研究；以实际集装箱港口为背景开发了一套物流优化决策支持系统。本文主要工作概括如下：1)针对以非线性规划为代表的连续最优化问题,提出了一种新的基于个体依赖机制的差分进化算法(IDE)。与常规差分进化算法不同,提出了依据适应值的差异调和个体参数的方法,设计了多样化的变异策略,并在变异策略中引入了随机干扰元素避免陷入局部最优,从而提高算法的全局搜索能力。经过国际标准函数集测试表明,IDE是目前国际上求解此类问题最好的差分进化算法。2)以集装箱船舶配载计划问题为背景,进行了IDE算法的应用研究。该问题的任务是在对集装箱船舶装载区域分段的基础上,决策出港集装箱在每个区域内的堆放顺序,目标是最大化船舶稳定性。针对此问题,设计了用于确定每个集装箱堆放优先级的分段连续编码,并提出了基于IDE的两阶段混合算法。基于实际数据的实验结果表明,算法可以在短时间内求得问题的近优解。3)针对以资源约束项目调度为代表的离散最优化问题,提出了一种新的离散差分进化算法(PDDE)。针对离散最优化问题,设计了排序编码,定义了新的离散变异操作和交叉操作算子,以保证算法在可行域内迭代。通过观测迭代过程产生的资源约束项目调度问题的解,发现了不同的优秀解中首任务(或尾任务)间具有相似性的规律(伪定理),并依此设计了一种保持相似性的任务不变、进化非相似性任务的降维搜索机制。基于迭代后期获得的解,通过学习发现多数解的任务之间具有关联特征的共性规律,提出了保持任务关联性的局部搜索策略。基于资源约束项目调度问题的标准测试数据的实验结果表明,所提算法优于目前求解此类问题的主流算法。4)以集装箱港口的泊位和岸桥集成调度问题为背景,进行了PDDE算法的应用研究。该问题的任务是在满足泊位及岸桥资源量约束以及船舶间优先级关系约束的条件下,决策每艘船舶的靠港作业开始时间,目标是最小化计划期内所有船舶的总服务完成时间。将问题归结为资源约束项目调度问题,设计了用于确定船舶作业开始时间的排序离散编码,并使用PDDE进行求解。基于实际数据和模拟数据的实验结果表明,PDDE是快速有效的。5)以国内某大型集装箱码头为背景,基于上述提出的连续和离散差分进化算法,开发了用于优化集装箱港口物流调度问题的决策支持系统。系统包括泊位岸桥分配、集装箱堆存计划、集装箱倒垛优化、集装箱船舶配载计划等功能模块。通过实际数据测试,验证了提出的算法在求解实际集装箱港口物流调度优化问题的有效性。