在大数据时代背景下,我们需要无时无刻地处理海量的数据,所要解决的问题规模也逐渐扩大。因此,大规模优化问题应运而生。在大规模优化问题中,搜索空间较为庞大且更为复杂,这使得传统优化算法无法在有限的时间内获得较为满意的解决方案。针对这些难题,本文从采用“分而治之”思想的协同进化和增强种群多样性的整体进化两个角度设计大规模优化算法。除理论研究外,本文还以供应链管理中的不确定性环境下大规模网络设计和大规模多目标网络配置为求解对象,对大规模优化算法进行应用研究。论文的主要创新点包括:(1)提出基于图论的再解耦技术,提高算法分解大规模优化问题的效率。现有的问题解耦技术无法有效地分解大规模重叠问题,且分组效率取决于变量相关性Interactions among Variables,Ia V)的评估准确率,从而限制了协同进化算法的优化效率。本文通过处理Ia V的计算误差,设计递归分解方法和分组调整策略,将问题变量分成大小适中的多个组,从而增强现有分组方法的容错性,提高分组效率。此外,为验证该方法的分组效率,本文设计了一个带有复杂Ia V信息的重叠问题生成器和两个新的评估指标。(2)设计自适应种群控制策略,增加种群多样性,提高传统差分进化算法(Differential Evolution,DE)求解大规模优化问题的效率。在DE算法的选择操作中,只有当新生成的解比原始解表现优异时,它才会被加入到下一代种群中,否则被直接淘汰,但是,这将浪费计算资源,不利于算法在有限的计算资源条件下寻找大规模问题的最优解。因此,本文设计了种群增长策略,增加新生成的解进入到下一代种群中的概率,充分利用个体进化信息,提高种群多样性。同时,为了防止种群不断膨胀,本文设计种群减少策略,淘汰表现较差且长时间未改进的解,将有限的计算资源分配给更有潜力的解,加快算法的收敛速度。(3)设计基于功能独立分解的协同粒子群优化算法和不可行解修复操作,有效求解带有复杂约束的不确定性环境下大规模供应链网络设计问题。首先,本文采用蒙特卡罗方法模拟不确定因素,辅助算法评估生成的解。其次,根据问题特征,本文提出了基于功能独立分解的协同粒子群优化算法,有效地将该大规模问题分解,并采用多个种群分别求解子问题,缩小每个种群的搜索空间,降低问题的求解难度。此外,本文设计了两种修复操作改进违反约束的不可行解,获得更多的可行解,从而提高种群多样性。(4)设计基于排名的局部搜索算法(Efficient Local Search based algorithm with rank,ELSrank),有效求解大规模多目标供应链配置问题。与求解多目标优化问题的传统群体智能算法不同,本文提出的局部搜索算法不需要借助种群的进化。首先,本文设计了供应链成员配置排名的计算方式,并依据配置排名提出了能够探索两个解间共同邻域的局部搜索算法,从而获得该邻域内的较优解。其次,本文通过贪心策略获得该多目标优化问题所对应的单目标最优解,并基于贪心解采用局部搜索策略求出最优解集,从而不断改进。这种局部搜索策略能够快速的获得最优解集,加快算法的收敛。(5)设计多蚁群系统算法,有效求解大规模多目标供应链配置问题。本文采用多种群多目标框架,使用两个蚁群分别求解该问题的两个优化目标。本文依据问题特征获得供应链节点的优先级,设计贪心的启发式策略,从而构造表现较优的解。其次,本文采用基于多种群的信息素局部和全局更新方式,有效地将个体进化信息反馈到信息素的更新中。此外,本文采用ELSrank改进当前的最优解,从而快速的找到更有潜力的解。综上所述,本文从算法设计和供应链网络应用两个角度研究了大规模优化算法。在算法设计方面,本文首先提出了基于图论的解耦技术,有效地将大规模问题分解,从而提高协同进化算法的优化效率。其次,本文提出了种群控制策略,增加整体进化中DE算法的种群多样性。在供应链网络应用方面,本文设计了基于功能独立分解的协同粒子群优化算法求解大规模供应链网络设计问题,并采用修复操作改进不可行解,增强解决方案的可行性。此外,本文设计了局部搜索算法和多蚁群系统算法,从不同角度有效地求解大规模多目标供应链配置问题。
暂无评论