论文部分内容阅读
传统的多目标优化算法在解决多目标问题时,容易陷入局部收敛,且解集性能较差。因此,本文针对不同情况下基于分解的多目标进化算法(Multi-objective Evolutionary Algorithm based on Decomposition,MOEA/D)表现出的缺陷进行改进,从而提高算法能力,改善解集性能。主要研究内容如下:为了提高MOEA/D求解Pareto前沿连续问题的能力,本文提出了基于变异算子和邻域值自适应的MOEA/D算法。针对MOEA/D预设控制参数,导致种群质量及算法性能下降的问题,该算法首先根据种群中个体适应度值的集中程度自适应地调整变异算子,提高算法搜索能力;其次,利用种群适应度值信息和进化阶段信息自适应调整邻域值;最后,根据新产生的个体在邻域内的被支配数是否超过设定阈值,算法将考虑是否引入Pareto支配关系作为个体性能判断准则。为了提高MOEA/D求解Pareto前沿不连续问题的能力,本文提出了基于自适应权重向量和匹配策略的MOEA/D算法。针对MOEA/D预设权重向量并采用随机匹配策略造成种群多样性降低等问题,该算法首先判定并更新位于不连续区域的无效子问题,降低其对种群进化的误导;其次,根据个体与子问题之间的聚合函数值及距离值,建立权向量匹配机制,加强个体与子问题之间的联系;最后,保存替换操作中表现优良的个体并建立外部档案集,提高邻域多样性。为了提高MOEA/D求解复杂Pareto解集问题的能力,本文提出了基于双空间邻居模型和双差分进化的MOEA/D算法。针对MOEA/D遗传操作随机性较大、替换操作失效及个体与其邻居解不匹配等问题,该算法首先通过决策空间中个体之间的距离来划分邻居集,并通过对应目标空间子问题建立邻域,定期更新,从而提高个体的邻居质量;其次,将局部线性嵌入(Locally Linear Embedding,LLE)用于高维决策空间距离计算的过程;最后,算法通过改变差分步长以及利用单次遗传操作中第一次差分进化的信息构造第二次差分进化的操作,在解决替换操作失效问题的同时有效的控制了遗传操作的随机性对进化过程的影响。将上述得到的三种进化算法应用于流水车间调度问题(Flow-shop Scheduling Problem,FSP)及柔性作业车间调度问题(Flexible Job Shop Scheduling Problem,FJSP)中。本文将前两种改进算法用于解决FSP问题。由于实际工程中无法提前获知Pareto前沿形状,因此算法引入判断机制。该机制通过判断进化过程中无效子问题的数量,及时为下一阶段进化切换所需的解决不同Pareto形状问题的算法。FJSP的加工过程并不具有流水线特点,其Pareto解集相较于FSP的Pareto解集具有一定的复杂性。因此,本文利用第三种改进算法,同时结合双层整数编码方法来解决该问题。实验结果验证了算法的有效性。