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

摘要

多目标优化是学术界和工业界研究的热点和难点问题，无论在科学研究还是在工程应用中都会遇到大量的优化问题需要同时考虑多方面的因素或目标，这些因素或目标之间通常具有相互冲突的特征。与单目标优化问题不同的是，多目标优化问题不存在唯一的全局最优解，而是存在一个最优解集合，称为Pareto最优解集，这个解集中的解互为非支配关系。由于决策者对于多目标优化问题通常要求快速、准确地获得多个Pareto最优解，这给多目标优化问题的求解带来了难度。作为一种基于群体智能的优化算法，进化算法(Evolutionary algorithm，EA)通过潜在解组成的种群的不断迭代完成对解空间的全局搜索，可以在一次运行时获得多个解，非常适合于求解多目标优化问题。近年来，国内外的专家和学者对多目标进化算法进行了广泛和深入的研究。多目标进化算法的目标是获得一个具有很好逼近性和分布性的非支配解集，从而能够为决策者提供有效和丰富的决策方案。 本文在总结和分析现有多目标进化算法和多目标生产调度问题研究现状的基础上，首先提出了以自适应多种群策略为核心思想的新型的多目标进化算法，在此基础上进而对多目标生产调度问题展开深入研究，具体工作可以概括如下: (1)为了使算法能够快速准确地获得一组非支配解，提出了一种自适应多种群策略，设计了一种基于这种自适应多种群策略的多目标遗传算法。该算法在每次迭代时，根据种群在目标空间和解空间的分布情况自适应为多个子问题并行构造子种群，通过子种群的进化运算实现对多个非支配解的并行搜索。通过选择经典的多目标进化算法及采用多种群策略的算法作为比较算法，并对标准的测试函数进行仿真实验，验证了所提出算法的能够快速准确地获得一组非支配解。 (2)为了提高算法所获得非支配解集的准确性和分布性，进一步改善了自适应多种群策略，提出了多优化策略集成的方法，设计了一种基于上述策略的混合多目标优化算法，通过选择一系列标准测试函数进行仿真实验，选择经典的、主流的及采用类似策略的多目标进化算法作为比较算法，实验结果表明所提出算法的有效性。 (3)针对具有恶化特性的单机调度问题，建立了以最小化最迟完成时间和总延迟时间的0-1整数规划多目标数学模型。针对问题特点，提出了基于支配规则的局部搜索策略，并设计了一种混合多目标进化算法进行求解。通过随机生成测试算例，并选择经典的多目标进化算法作为比较算法，实验结果表明所提出的算法能够有效地解决具有恶化特性的单机多目标调度问题。 (4)针对一般的多目标流水车间调度问题，建立了最小化最迟完成时间和总延迟时间的多目标数学模型，并设计了基于多种群策略的多目标遗传算法进行求解。为验证所提出算法的性能，采用标准的测试算例生成方法产生不同规模的算例，并选择解决该类问题的经典的、近期的及采用类似策略的多目标进化算法作为比较算法，实验结果表明所提出的算法在解决该问题上具有很好的效果。 (5)针对具有恶化特性的流水车间调度问题，建立了最小化最迟完成时间和总延迟时间的多目标数学模型，并设计了基于自适应多种群策略的多目标遗传算法进行求解。该算法采用了子问题分阶段引入方法和外部档案的进化策略。通过随机生成测试算例进行仿真实验，并选择经典的多目标进化算法作为比较算法，实验结果验证了所提出的算法在解决该问题上的有效性。 (6)针对一种新型的多目标混合并行机调度问题，建立了最小化总流水时间和总延迟工件个数为目标的多目标数学模型，并设计了改进的非支配排序遗传算法进行求解。结合问题特点，提出了启发式种群初始化策略和局部搜索策略。通过随机生成测试算例进行仿真实验，并选择经典的多目标进化算法作为比较算法，实验结果表明所提出的算法在解决该问题上具有很好的效果。

目录

声明

摘要

第一章绪论

1．1研究背景

1．2研究目的及意义

1．3本文的研究思路

1．4本文的主要工作和组织结构

1．5本章小结

第二章相关理论综述

2．1经典多目标优化理论

2．1．1多目标优化问题的定义

2．1．2传统的多目标优化方法

2．2多目标进化算法的研究现状

2．3多目标生产调度问题的研究现状

2．4多目标优化的测试问题和性能指标

2．4．1多目标优化的测试问题

2．4．2多目标优化算法的测试指标

2．5进化算法简介

2．5．1遗传算法

2．5．2粒子群优化算法

2．5．3差分进化算法

2．6本章小结

第三章基于自适应多种群策略的多目标遗传算法

3．1引言

3．2算法设计

3．2．1算法思想

3．2．2多种群的构造方法

3．2．3遗传算子的设计

3．2．4局部搜索策略的设计

3．3仿真实验与分析

3．3．1测试算例及比较算法

3．3．2参数设置

3．3．3实验结果与分析

3．4本章小结

第四章基于自适应多种群策略的混合多目标优化算法

4．1引言

4．2算法设计

4．2．1算法思想

4．2．2内部种群的进化方法

4．2．3外部档案的进化方法

4．3仿真实验与分析

4．3．1测试算例及比较算法

4．3．2参数设置

4．3．3实验结果与分析

4．4本章小结

第五章具有恶化特性的单机多目标调度问题及其算法研究

5．1引言

5．2问题描述

5．3问题的支配性质

5．4算法设计

5．4．1算法思想

5．4．2多种群的构造方法

5．4．3局部搜索策略的设计

5．4．4遗传算子的设计

5．5仿真实验与分析

5．5．1测试算例及比较算法

5．5．2参数设置

5．5．3实验结果与分析

5．6本章小结

第六章多目标流水车间调度问题及其算法研究

6．1引言

6．2问题描述

6．3算法设计

6．3．1算法思想

6．3．2多种群的构造方法

6．3．3遗传算子的设计

6．4仿真实验与分析

6．4．1测试算例及比较算法

6．4．2参数设置

6．4．3实验结果与分析

6．5本章小结

第七章具有恶化特性的多目标流水车间调度问题及其算法研究

7．1引言

7．2问题描述

7．3算法设计

7．3．1算法思想

7．3．2子问题的引入方法

7．3．3多种群的构造方法

7．3．4遗传算子的设计

7．4仿真实验与分析

7．4．1测试算例及比较算法

7．4．2参数设置

7．4．3实验结果与分析

7．5本章小结

第八章多目标混合并行机调度问题及其算法研究

8．1引言

8．2问题描述

8．3算法设计

8．3．1算法思想

8．3．2初始种群的生成

8．3．3遗传算子的设计

8．3．4局部搜索策略的设计

8．4仿真实验与分析

8．4．1测试算例及比较算法

8．4．2参数设置

8．4．3实验结果与分析

8．5本章小结

第九章总结与展望

参考文献

致谢

攻读学位期间撰写的论文

个人简历