论文部分内容阅读
进化算法已经被证明是能够有效地解决多目标优化问题的随机搜索算法之一。实际应用中的多目标问题往往是复杂的,非线性的,甚至是不确定,多目标进化算法以其优越的搜索能力,常用来解决复杂的和非线性的问题,而在不确定环境下的多目标进化算法的性能研究以及应用均较少。由于算法的对抗干扰的能力决定了算法在工程领域的实用性,不确定性对优化算法的影响开始引起了研究者们的关注。车间调度是先进生产的要求,是生产资源最优化,生产成本最低化的有效保证,是生产自动化的一个重要方面,也是有效提高生产效率的重要方式,因此车间调度问题得到了决策者和研究者的广泛关注。流水车间调度问题因其理论上的复杂性和实际应用中的典型性十分具有研究价值。但是通常研究者们会忽略掉调度过程中的不确定性,将流水车间调度问题中的许多参数视为定值,但是实际生产生活的许多不确定因素是不能够忽视的,决策的改变,生产环境的变化,设备工作状态均有可能影响调度方案的有效性,所以对不确定流水车间问题的研究具有现实意义,是调度算法鲁棒性的一个体现。本文的主要工作如下:一、在不确定环境下多目标进化算法性能研究方面,选取近年来具有代表性的多目标进化算法(Multi-Objective EvolutionaryAlgorithms, MOEAs): NSGA-II,SPEA2,GDE3作为待研究的算法。采用UA, GD, IGD, HV四种评价参数,用实验的方法分析三种算法在噪声环境下的性能,测试了不同噪声规模下评价参数的有效性,同时研究了蒙特卡罗积分的方法进行显示平均的方法适用的噪声范围。二、为对求解流水车间调度问题打下基础,我们先对具有代表性的无等待流水车间调度问题(NWFS)进行了研究,提出了一种带有邻域搜索的分布估计算法求解NWFS问题。首先提出并证明NWFS相邻两工件必在某一车床的零间隙性,并根据此性质提出了一种快速计算总时间表长的算法。其次提出了一种基于图论的邻域搜索算法,将寻找使总时间表长减少最多的多重插入的邻域搜索过程转化为寻找权值最大零图的过程,能快速找到使加工周期减少最多的独立插入移动。三、针对加工时间不确定流水车间调度问题,采用多目标进化算法框架求解该问题,首先通过三角模糊数对不确定车间调度问题进行建模,除了将传统的总调度周期的代数值作为优化目标外,定义了总调度周期的模糊度函数,并将最小化模糊度做为另外一个目标,通过多目标进化算法框架,提出了基于Pareto最优的遗传算子,并采用基于聚集距离的修剪算子进行种群的分布性维护,通过在五个经典上的测试,得到了求解模糊流水调度问题的有效解集。