关键词:
多目标优化
进化计算
约束处理技术
柔性作业车间调度
分布式生产调度
摘要:
现实世界中大多数问题本质上都属于多目标问题,求解这类问题通常需要同时优化多个目标(目标之间是相互冲突的)函数,因此算法一般都是通过找到一组折衷解来代表问题的最优解。基于生物进化思想的智能优化算法不需要问题的先验知识,利用随机搜索策略可以在单次运行中就能获得一组近似解,因而成为求解多目标问题的一种有效方法。多目标优化算法最终要达到:1)种群收敛到Pareto最优前沿上;2)种群个体沿Pareto前沿均匀分布。在过去的二十年里,研究者虽然提出了各种各样的多目标优化算法,但是在求解问题时,还是难以有效地平衡种群的多样性和收敛性。特别是随着问题越来越复杂,优化的目标和变量也逐渐增加,为算法有效求解带来了很大的挑战。比如在超多目标空间中,选择压力的退化使得种群个体难以收敛到Pareto前沿,同时在高维空间也难以保持种群的多样性。因此,本文围绕几类典型的多目标优化问题,通过分析和挖掘不同类型问题的特征,充分利用问题特性设计了一系列对应的优化算法。本文主要研究内容包括:(1)针对复杂Pareto前沿问题,提出了一种基于两阶段的多目标优化算法。当多目标问题具有复杂Pareto前沿时,现有的方法难以均匀收敛。为了解决这个问题,提出了一种基于两阶段优化的MOEA/D-TS算法。算法采用两阶段进化策略,第一阶段着重于加强算法的收敛能力,使种群解快速收敛到Pareto前沿附近;在第二阶段中,算法主要提高种群个体的多样性,使解个体能够均匀地分布在Pareto前沿。在第一阶段中,MOEA/D-TS主要采用基于MOEA/D算法的框架,同时采用了一种改进的权重向量生成机制来处理Pareto前沿的不规则。第二阶段中设计了一种局部搜索策略,用来调整解的分布。MOEA/D-TS的性能在ZDT、DTLZ和IMOP问题中进行了验证,实验结果表明,与其它主流多目标优化算法相比,MOEA/D-TS能够在大多数测试问题上获得较好的收敛性和多样性。(2)针对超多目标优化问题,提出了一种基于向量夹角的超多目标优化算法。由于维度灾难,超多目标空间中的解个体之间会变得互不支配,现有的进化算法在求解这类问题时,难以平衡解集的收敛性和多样性。为了解决这一问题,提出了一种有效的超多目标优化算法Ma OEA-ASS。在Ma OEA-ASS中,首先采用基于向量夹角的选择策略从种群中选取多样性较好的解个体。然后将基于移动的密度估计与目标和策略相结合,利用种群进化过程中的信息动态调整解个体的适应度值,从而获得性能较好的解。提出的Ma OEA-ASS在DTLZ和WFG两组测试问题上进行了验证,与八种最新主流的多目标优化算法进行了比较。实验结果表明,提出的Ma OEA-ASS在大多数超多目标问题上都具有较优的性能。(3)针对约束多目标问题,提出了一种基于双种群协同的约束多目标优化算法。约束多目标问题难以求解是因为它们不仅需要很好地平衡空间中解个体的收敛性和多样性,同时还需要考虑解的可行性。现有的约束多目标优化算法在求解具有复杂可行区域的约束多目标问题时容易陷入局部区域,难以获得好的结果。为了解决这个问题,本文提出了一种基于双种群的CMOEA-TCP算法。CMOEATCP利用两个协同种群,通过相互协同来使解个体收敛到约束的Pareto前沿。其中一个种群是采用基于Pareto的方法进化,主要用于加快种群的收敛。同时另一个种群是通过基于分解的方法进行进化,用于提高种群的多样性。然后通过约束处理技术,在合并后的种群中选择高质量的解。为验证CMOEA-TCP的性能,在三组多目标约束测试问题上进行了实验。实验结果表明,与其它六种最新的约束多目标优化算法相比,CMOEA-TCP在大多数多目标约束问题上有明显的优势。(4)针对约束超多目标问题,提出了一种基于动态权重向量的约束超多目标优化算法。约束超多目标优化问题由于目标多、约束多且复杂,因此变得难以求解。为了解决这个问题,本文提出了一种基于权重向量动态变化的约束超多目标优化算法CMa OEA-DR。在求解过程中,权重向量是随着迭代次数不断动态变化,从而能够很好地适应各类复杂Pareto前沿问题。同时为了更好地调整向量,算法构造了一个档案集,用于保存进化过程中产生的优秀解,这些性能较优的个体用于更新权重向量。CMa OEA-DR在三组约束超多目标测试集上进行了实验验证,通过与其它六种主流的算法进行对比,验证了CMa OEA-DR在求解约束超多目标问题上是有效的。(5)针对算法在实际生产中的应用,将基于两阶段的MOEAD-TS算法用于求解多目标分布式柔性作业车间调度问题。建立了以最小化最大完工时间和总能量消耗为目标的分布式柔性调度模型,同时采用合理有效的编码解码机制对工厂、机器和工序进行编码解码。在进化过程中通过交叉和变异操作产生新的工序序列、机器序列和工厂序列,同时