基于自组织优化算法的多旅行商问题的求解与应用

论文摘要

自组织优化算法是基于极值动力学提出的一种新的启发式智能优化算法,是极值优化算法的一种改进形式。自组织优化算法具有统计物理中远离平衡态的动力学特征,它总是选择当前解中适应度差的变量和相互关联的变量进行变异。自组织优化算法具有收敛速度快、局部搜索能力强、设计简单、容易实现的优点,并且增加了解的邻域操作与邻域解的概率选择,使得算法具有更大概率的广度搜索和深度搜索能力,是一种更为合理的动态优化过程。该算法提出后在求解组合优化问题上得到了一定的应用,如旅行商问题和热轧单元调度问题等。本文把自组织优化算法的应用推广到了约束条件更强的组合优化问题,通过模型处理和局部适值的定义,把约束条件统一转化到目标函数进行处理,取得了显著的优化效果。具体的,本文对以下问题做了应用研究:基于自组织优化算法的多旅行商问题的求解。本文通过引入虚拟城市把多旅行商问题转化为单旅行商问题,虚拟城市不仅仅用于区分不同旅行商的路径,而且其局部适值的定义有效的处理了问题的约束。对于传统多旅行商问题本文直接应用自组织优化算法进行求解;对于要求最长路径最短的多旅行商问题和每个旅行商允许经过的城市数有上限的多旅行商问题,分别通过虚拟城市局部适值的不同定义,将约束转化为目标函数的一部分,有效的处理了问题的特殊约束。针对标准算例进行的仿真结果表明自组织优化算法可以有效的求解这几类多旅行商问题。此外,对于多旅行商问题的一个广泛应用实例——车辆路径规划问题,本文也应用自组织优化算法进行了求解,针对每辆车的容量有限制而且要求总的路径最短的车辆路径规划问题,本文给出了仿真结果,表明自组织优化算法可以有效求解每辆车的容量带约束的车辆路径规划问题。基于自组织优化算法的热轧批次调度。热轧单元调度中的板卷排序是一个典型的约束组合优化问题,热轧批次调度需要运用并行策略,按工作订单和约束条件,同时形成多个轧制单元的轧制顺序。论文首先基于多旅行商问题模型,建立热轧批次调度的带约束优化的数学模型;然后应用自组织优化算法进行求解;本文提出的基于自组织优化算法的并行优化算法,可以有效地求解多个轧制单元的并行调度问题。通过虚拟板卷局部适值函数的定义有效地解决了组合优化中的约束问题,达到了对多个轧制单元进行并行调度的目的,确保在一个轧制批次中,每个轧制单元性能分布的均匀性。基于实际工业数据的仿真结果表明自组织优化算法能够有效地解决工业规模的热轧批次调度问题。

论文目录

• 致谢
• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 引言
• 1.2 组合优化问题实例
• 1.2.1 组合优化问题数学模型
• 1.2.2 旅行商问题
• 1.3 几种智能优化算法
• 1.3.1 遗传算法
• 1.3.2 蚁群算法
• 1.3.3 极值优化算法
• 1.4 本文主要研究内容
• 第2章 自组织优化算法简介
• 2.1 自组织临界性理论
• 2.2 自组织临界性的应用
• 2.2.1 极值优化算法
• 2.2.2 自组织优化算法
• 2.2.3 自组织优化算法与其它算法的比较
• 2.3 2-opt邻域操作
• 第3章 基于自组织优化算法的多旅行商问题的求解
• 3.1 多旅行商问题概述
• 3.2 多旅行商问题描述
• 3.2.1 总的路径最短
• 3.2.2 最长路径最短
• 3.2.3 旅行商的能力带约束
• 3.3 应用自组织优化算法求解多旅行商问题
• 3.3.1 总的路径最短
• 3.3.2 旅行商的能力带约束
• 3.3.3 最长路径最短
• 3.4 多旅行商问题应用──车辆路径规划问题
• 3.4.1 车辆路径规划问题概述
• 3.4.2 车辆路径规划问题数学模型
• 3.4.3 求解车辆路径规划问题的自组织优化算法
• 3.5 小结
• 第4章 基于自组织优化算法的热轧批次问题研究
• 4.1 引言
• 4.2 热轧生产过程
• 4.3 数学描述
• 4.3.1 变量定义
• 4.3.2 问题建模
• 4.4 求解热轧批次调度的自组织优化算法
• 4.4.1 局部适值函数的定义
• 4.4.2 求解轧制批次调度的自组织优化算法流程
• 4.4.3 仿真结果
• 4.5 小结
• 总结与展望
• 参考文献
• 硕士期间完成论文
• 作者简介