多目标进化算法研究及其在生产排序中的应用

论文摘要

生产计划中的多目标排序问题是一类典型的组合优化难题,对其求解过程是在多个冲突的优化目标及高度复杂的搜索空间进行寻优,因此传统优化算法往往难以有效求解这类问题。本文在分析总结现有进化算法及多目标排序研究基础上,提出一种基于递进进化结构的多目标进化算法,并针对排序问题的特点,将现有启发式算法引入进化算法的局部搜索中,提高了算法的求解效率。本文主要工作内容如下:1.简要回顾了多目标进化算法及多目标排序问题的发展历史。在分析现有多目标遗传算法特点的基础上,归纳总结了现有多目标遗传算法研究存在的不足,指出其应用于多目标排序问题存在的困难。2.针对现有多目标进化算法存在的不足,提出一种基于递进进化结构的混合多目标进化算法。通过在进化算法中引入递进进化结构,改善了群体多样性,又隐式地实现了不同进化层之间的非劣解集信息传递;通过采用改进的精英选择策略,实现了不须计算适应值而仅通过规则指导即可实现精英个体的保留;同时,在递进进化过程中引入非劣解局部搜索策略,提高了进化算法的局部搜索性能。采用改进算法对7个典型的多目标连续函数优化算例进行求解,将所得结果与两种现有代表性多目标遗传算法的优化结果进行对比,研究结果表明,新算法具有更好的优化性能,在相似进化条件下,较参照算法获得了更好的非劣解集。3.提出一种求解flow shop排序问题的混合多目标进化算法。提出一种结合flow shop启发式算法与可变邻域搜索的启发式局部搜索策略,并将该策略应用于算法递进过程中的非劣解局部搜索,极大改善了算法寻优能力。采用改进的混合多目标进化算法（HEMEA）与NSGA-II、MOGLS等方法对31个标准双目标flow shop算例及一个典型三目标flow shop优化算例进行求解,优化结果表明,本文提出的混合算法较现有代表性算法具有更强的求解性能。4.提出一种求解job shop排序问题的混合多目标进化算法。根据job shop排序问题的特点,提出一种基于时间进度表原理的启发式算法,可以在解码过程中通过一次解码求出一个排序的所有目标值,提高了现有基于操作编码算法的解码效率;提出一种新的适应值计算方法,通过新的适应值评价方式,可以在一个评价公式中同时体现非劣解等级数与同一非劣解等级内个体稀疏状况对个体适应值的影响,降低了算法复杂性。采用改进算法（HEMEA）与NSGA-II、MOGLS对82个标准双目标job shop算例和5个三目标job shop算例进行求解,优化结果表明,本文提出的混合算法较两种验证算法取得了更好的优化结果,验证了算法的有效性。5.为解决某航天企业生产车间作业排序中出现的铣床瓶颈问题,本文建立了一种求解该问题的“分解-协调”混合生产作业优化模型,并提出一种基于操作编码的混合多目标进化算法对该优化模型进行求解。优化结果表明,混合多目标进化算法比实际生产排序人员能得出更好的排序结果,并且求解效率大为提高,从而验证了本论文改进算法的实用性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 多目标进化算法及多目标排序研究现状
• 1.2.1 多目标进化算法研究现状
• 1.2.2 多目标排序研究现状
• 1.3 论文研究内容
• 第二章 多目标优化与多目标遗传算法
• 2.1 多目标优化的基本概念
• 2.1.1 多目标优化问题描述
• 2.1.2 Pareto 最优性
• 2.2 多目标遗传算法设计的关键技术
• 2.2.1 适应值设计
• 2.2.2 维持群体多样性
• 2.2.3 精英保留策略
• 2.3 多目标遗传算法的性能评价
• 2.3.1 性能评价指标
• 2.3.2 测试函数及其设计
• 2.4 多目标遗传算法
• 2.4.1 代表性多目标遗传算法介绍
• 2.4.2 现有算法研究的不足
• 2.5 本章小结
• 第三章 递进多目标进化算法
• 3.1 递进多目标进化算法
• 3.1.1 基于Pareto 最优性的非劣解集筛选
• 3.1.2 改进的精英复制策略
• 3.1.3 递进进化结构
• 3.1.4 非劣解局部搜索策略
• 3.1.5 递进多目标进化算法流程
• 3.1.6 算法复杂性分析
• 3.2 函数优化算例分析
• 3.2.1 算例描述
• 3.2.2 进化编码及进化操作
• 3.2.3 进化参数设置
• 3.2.4 结果分析
• 3.3 本章小结
• 第四章 求解多目标FLOW SHOP 的混合递进多目标进化算法
• 4.1 多目标FLOW SHOP 问题描述
• 4.2 求解FLOW SHOP 排序问题的混合递进多目标进化算法
• 4.2.1 Flow shop 排序问题的进化编码
• 4.2.2 Flow shop 排序问题的进化操作
• 4.2.3 求解flow shop 排序问题的启发式算法
• 4.2.4 一种改进的启发式局部搜索策略
• 4.2.5 改进的启发式可变邻域搜索算法
• 4.2.6 求解目标值
• 4.2.7 求解flow shop 排序问题的混合递进多目标进化算法流程
• 4.2.8 算法复杂性分析
• 4.3 双目标FLOW SHOP 排序问题的优化求解
• 4.3.1 算例描述
• 4.3.2 进化参数设置
• 4.3.3 结果分析
• 4.4 三目标FLOW SHOP 排序问题的优化求解
• 4.4.1 算例描述
• 4.4.2 进化参数设置
• 4.4.3 结果分析
• 4.5 本章小结
• 第五章 求解多目标JOB SHOP 的混合递进多目标进化算法
• 5.1 多目标JOB SHOP 问题描述
• 5.2 求解JOB SHOP 排序问题的混合递进多目标进化算法
• 5.2.1 Job shop 排序问题的进化编码
• 5.2.2 Job shop 排序问题的进化操作
• 5.2.3 改进的适应值评价策略
• 5.2.4 基于时间进度表策略的目标值求解算法
• 5.2.5 求解job shop 排序问题的混合递进多目标进化算法流程
• 5.2.6 算法复杂性分析
• 5.3 双目标JOB SHOP 排序问题的优化求解
• 5.3.1 算例描述
• 5.3.2 进化参数设置
• 5.3.3 结果分析
• 5.4 三目标JOB SHOP 排序问题的优化求解
• 5.4.1 算例描述
• 5.4.2 进化参数设置
• 5.4.3 结果分析
• 5.5 本章小结
• 第六章 多目标生产排序的实证研究
• 6.1 实际调度过程描述
• 6.2 实例建模
• 6.2.1 实例数据
• 6.2.2 实例建模假设
• 6.2.3 实例优化模型
• 6.3 实例优化的递进多目标进化算法
• 6.3.1 基于操作的进化编码及进化操作
• 6.3.2 求解目标值
• 6.3.3 求解零件层子问题混合车间作业排序的多目标进化算法
• 6.3.4 算法复杂性分析
• 6.4 实例优化
• 6.4.1 实例子问题双目标优化的进化参数设置
• 6.4.2 实例的分解-协调优化过程
• 6.3.5 与实际方法的比较分析
• 6.4 本章小结
• 结论
• 本文研究总结
• 进一步研究展望
• 参考文献
• 附录A 双目标FLOW SHOP 优化算例的非劣解集
• 附录B 三目标FLOW SHOP 优化算例的非劣解集
• 附录C 双目标JOB SHOP 优化算例的非劣解集
• 附录D 三目标JOB SHOP 优化算例的非劣解集
• 攻读博士期间取得的研究成果
• 致谢
• 作者简介