论文部分内容阅读
现实世界中的工业生产、金融投资和资源调度等优化问题通常包含混合类型的决策变量,即连续变量和离散变量。这类包含混合变量的优化问题被称为混合变量优化问题(Mixed-Variable Optimization Problems,MVOPs)。进化算法(Evolutionary Algorithms,EAs)因其简单高效的特点被广泛地用来求解各种优化问题。然而,目前的进化算法并不能高效地求解混合变量优化问题,一方面,混合变量优化问题中的混合类型的变量提高了问题空间的复杂度,增加了算法搜索的难度;另一方面,算法采用的性能较差的重组算子或多个重组算子间性能的不协调可能会降低算法效率。粒子群优化算法(Particle Swarm Optimization,PSO)是被广泛研究和应用的进化算法。然而,基于PSO求解混合变量优化问题的算法却鲜有被研究。协同进化策略(Co-evolution Strategy,CES)是目前广泛应用在进化算法设计中的策略,基于协同进化策略设计出的竞争或合作算子能够提高算法的搜索效率,提升算法的整体性能。因此,为了更加高效地求解混合变量优化问题,本文引入协同进化策略,研究求解混合变量优化问题的粒子群优化算法。具体的研究工作包括如下三点。1)本文提出了基于竞争式协同进化的混合变量粒子群优化算法(Competitive Coevolution based Particle Swarm Optimization,CCPSO)以解决PSO过早收敛的问题。CCPSO基于松弛方法处理混合变量,并采用连续变量重组算子生成粒子。为了提高种群多样性,CCPSO采用基于竞争式的学习对象生成策略为每一个粒子生成特殊的学习对象;同时提出基于竞争学习的预测策略为粒子选择合适的学习对象,充分挖掘了学习对象的进化潜力,以在保证种群多样性的同时提高算法的收敛速度。为了平衡多样性和收敛性,CCPSO提出基于容忍度的搜索方向调整机制,在充分利用学习对象进化潜力的同时避免粒子群陷入局部最优。2)由于基于松弛方法的算法并不适合求解所有的混合变量优化问题。当离散变量无序时,这类算法的性能会明显下降。本文进一步提出了基于合作式协同进化的混合变量粒子群优化算法PSOmv,以更加高效地解决混合变量优化问题。PSOmv采用混合变量编码方式并基于合作式协同进化框架将变量分组。PSOmv分别采用了连续变量重组算子PSO-c和离散变量重组算子PSO-d处理混合变量。PSO-c采用了种群排序的机制为每个粒子随机地选择学习对象,该机制在保证粒子收敛速度的同时提高了粒子群的多样性。PSO-d则基于统计方法生成粒子,在更新每个离散变量的分配概率时将充分地考虑粒子群的历史搜索信息和当前信息。PSO-c和PSO-d生成的不同子种群的粒子通过合作即可得到原问题的解。PSOmv采用了基于随机采样的个体评估机制选择合作粒子,该机制可大幅提高粒子间的合作效率,实现在评估准确性和评估效率之间的有效平衡。3)为了进一步扩展基于协同进化的混合变量粒子群优化算法的应用场景,本文结合无人机协同多任务调度这一实际问题进行研究,提出了考虑多种约束条件和多个优化目标的无人机协同多任务分配问题模型(Multiple Constraints and Objectives Cooperative Multiple Task Allocation Problem,M-CMTAP)并采用基于协同进化的混合变量粒子群优化算法求解。M-CMTAP模型考虑了多种约束条件和优化目标,决策变量包含连续变量和离散变量。为了求解该模型,本文提出了基于协同进化的混合变量多目标粒子群优化算法(Coevolution based Multi-objective Optimization Particle Swarm Optimization,C-MOPSO)。C-MOPSO采用基于任务分配和路径规划的编码方法表示无人机的任务分配结果和路径规划结果;并基于约束处理的可行解初始化方法高效地生成可行粒子;同时提出基于结构学习的重组方法对粒子进行更新,以提高种群的多样性和收敛性。为了进一步加快算法的搜索效率,算法引入协同进化的思想在两个子种群之间进行合作进化。为了验证本文所提出的多个算法的性能,本文基于主流的测试函数和实例做了实验。实验结果表明,本文提出的算法具有良好的性能,也验证了本文提出的基于协同进化的策略在求解混合变量优化问题时的有效性。