一种快速构造多目标Pareto非支配集的方法:选举法则

基于Pareto的多目标优化问题是进化算法的一个重要研究方向,而如何构造Pareto非支配集则是提高算法效率的关键所在。通过对选举现象的观察,同时针对多目标个体之间的特性,提出了一种快速求解多目标Pareto非支配集的方法:选举法则(election principle,EP),分析了其时间复杂度为O(rmN),并对其进行了正确性证明。因为种群中实际的非支配个体数m比进化群体规模N小,所以与同类方法相比,EP有更高的效率,并通过了实验验证。

用于多目标进化的归一化排序非支配集构造方法

本文基于归一化思想,通过计算进化群体中个体多目标值的归一化和,提出了个体之间排序意义上的大于、等于关系,建立了进化群体中所有个体从大到小的全排序,同时给出了相关理论和证明.在此基础上,提出了多目标进化算法的非支配集构造方法,该方法使个体之间的比较次数有较大幅度地减少,加速了非支配集的构造速度.实验结果已经验证了本文提出的用归一化排序构造非支配集的方法效率提高显著.

多目标优化非支配集构造方法的研究进展

多目标优化非支配集的构造是多目标进化算法研究领域的一个重要步骤,旨在研究用多目标进化算法解决多目标优化问题的效率。对多目标优化问题进行了描述并且给出了求解算法的一般框架,结合研究现状讨论了目前该领域几种主要的基于Pareto非支配集的构造算法,以及它们的计算时间复杂度;总结并展望了该领域未来的发展趋势。

非支配集下变异蜂群指导的智能交通控制方法

非支配集下的变异蜂群指导算法具有更加优越的自适应能力。传统的交通控制方法采用变时隙策略,无法将交通的动态信息实时的融合起来。提出了一种非支配集下基于变异蜂群指导的智能交通控制方法,采用变异蜂群指导算法,通过搜寻者不断搜寻最佳交通控制的逼近方案,通过检测者不断更新最佳交通控制的区域,通过观察者实时反馈交通调整控制信息,三者协同工作,提高了智能交通控制的效率。最后通过Sphere函数,Rastrigin函数和Rosenbrock函数分别进行测试,仿真结果显示,50种群和20种群下的蜂群指导算法均对交通具有很好的指导作用。

用擂台赛法则构造多目标Pareto最优解集的方法

针对多目标进化的特点,提出了用擂台赛法则(arena’s principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0<m/N<1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN2)和O(Nlog(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.

用伪二叉树法则构造多目标Pareto最优解集的方法

针对多目标进化算法中如何提高非支配集构造效率的问题,提出了一种用伪二叉树法则构造多目标Pareto最优解集的方法.根据多目标解的性质,将解的比较结果分为支配、被支配以及不相关3种类型,再根据解的比较结果生成排序伪二叉树.在每一轮比较中,从进化群体中选出一个个体,将该个体与当前非支配集中的个体进行比较,淘汰被支配的个体,而未被淘汰的个体将插入到非支配集中第一个被淘汰个体的位置.依次进行,直到进化群体中的个体比较完毕,从而生成排序的伪二叉树.同时,在理论上证明了采用该方法获取的非支配集为目标进化群体的最大非支配集,分析得知其在最差情况下的时间复杂度为O(rN2/2).实验结果表明,当目标数较大时(r≥5),在构造非支配集的效率上伪二叉树法要明显优于Deb、Jensen算法及擂台赛法则.

基于多目标演化优化的SVM对抗仿真测试算法

机器学习通常从数据中挖掘潜在的模式与规则,容易受到数据的影响而产生诸如过拟合、欠拟合等现象,进而影响学习模型的泛化与鲁棒性能。从对抗仿真测试的角度考察SVM可能存在的脆弱不稳定性,采用的对抗仿真策略是通过选择性地污染训练样本标签,模拟攻击SVM分类器使其性能退化,以测试其对训练样本的依赖性。为探究SVM分类器在不同样本组合攻击下的性能损失上限,设计了最小攻击代价-最大攻击成效这一对矛盾目标,构建了SVM仿真测试的多目标优化模型。该模型本质上是一种典型的多目标组合优化问题,可采用适当的多目标演化算法求解目标间的一组非支配解集,揭示分类器在不同样本组合攻击下的分类性能表现。在人工及真实数据集上的仿真对比实验结果表明:所提方法能够一次性生成不同攻击水平下的最优攻击样本组合,取得最大的分类性能损失,更能全面测试SVM分类器性能的稳定性。

基于ε支配擂台赛法则的多目标遗传算法

将ε支配引入擂台赛算法,得到一种快速确定Pareto非支配集的方法,并据此提出一种改进的多目标遗传算法。从理论上分析新算法的时间复杂度,并通过数值对比实验验证新算法的有效性。

一种基于聚集距离的多目标进化算法

在多目标进化算法的研究中,解群体的多样性和运行效率是最重要的两个指标。在进化算法中一般采用构造非支配集的方法来保持算法的运行效率和解集的分布性;采用聚类技术来计算和维持解群体的分布性和多样性。文章提出了用庄家法构造非支配集和基于个体距离的聚类方法的多目标进化算法。经试验证明,该算法能够趋近到Pareto最优解,并且能保证较好的分布度。

聚类差分进化算法求解多目标工艺规划与调度集成问题

针对多目标工艺规划与调度集成问题,以完工时间、交货总拖期和设备工作负荷为优化目标,建立了多目标非线性工艺规划集成模型,提出一种聚类差分进化算法。该算法设计了包含工艺、设备和加工顺序信息的3层编码结构,结合聚类算法、差分进化算法和遗传算法的相关操作,有效地优化工艺信息和调度方案,保持可行解的多样性,实现Pareto非支配解集快速更新。通过对Pareto非支配解集进行领域搜索,使其更加接近或到达Pareto最优解集。最后通过实例验证了算法的性能。

基于初集排序的Pareto非支配解集构造算法

针对具有大型解空间的多目标决策问题，为进一步提高多目标决策的效率，快速且有效的非支配解集构造方法值得探究．给出非支配关系性质、初始非支配解集（简称初集）及非支配解集构造的有关定义与定理．在此基础上，依据有序集理论与运算规则，提出基于初集排序方法的Pareto非支配解集构造算法．该算法应用集合排序的方法，对有序的可行解集与有序的非支配解集进行比较，获得多目标决策问题的最优解．构建不包含初始非支配解的有序可行解集，设计非支配解排序规则、查找规则与插入规则．分析提出的算法及常见的非支配排序方法的时间复杂度．通过ZDT1-ZDT3、DTLZ1与DTLZ3测试函数的非支配解集构造实验，与王芳等（2016）提出的NTCM等方法相比，证明提出的非支配解集构造算法是有效的，时间复杂度更低，非支配解集构造时间具有显著的优势．

基于灰狼算法的多目标车间调度优化

针对车间的调度问题,现有研究多集中于生产效率的单一优化,忽略了机器负载、能耗等方面的优化。为提高作业车间的生产效率,同时优化车间内多个核心指标,建立了包含最小化最大加工时间、机械负载、以及加工能耗等指标的车间调度模型。提出了混合交叉搜索策略的灰狼算法(MSS-GWO),通过引入选择系数提高了种群的多样性;并设计了一种非线性函数进行动态调整全局搜索和局部搜索以保持种群多样性的同时使算法快速收敛;对领导狼引入动态权重避免算法陷入局部最优解。通过MK数据集测试,验证了混合交叉搜索策略的有效性,并与其他文献的方法进行对比,验证了算法在多目标车间调度问题的优越性。

考虑环境效益的分布式电源多目标规划

分布式电源(distributed generation,DG)接入配电网,可以有效缓解传统发电方式带来的环境污染和能源枯竭问题。在考虑DG环境效益的基础上,针对多类型DG接入位置及容量问题,建立了综合污染气体排放量、配电网总费用和系统电压偏差的多目标模型,并提出了一种自适应多目标粒子群算法。该算法结合非线性变异算子保持种群多样性,采用动态自适应网格策略使得Pareto前端分布更加均匀,从而为最终决策提供良好的候选方案。针对获得的非支配集,采用分层模糊决策技术得到符合决策者侧重点的最终方案。算例分析结果表明,利用该方法得到的DG配置方案,可以有效地减少污染排放量,降低总费用,减小电压偏差,这验证了模型和算法的合理性和有效性。

求解多目标优化问题的改进布谷鸟搜索算法

针对求解多目标优化问题,提出一种改进的多目标布谷鸟搜索算法(IMOCS).相比于标准多目标布谷鸟搜索算法(MOCS),IMOCS在莱维飞行中使用动态自适应的步长控制量,并基于层级和拥挤度距离选择下一次莱维飞行的种群.为了验证算法的有效性,通过在测试实例(SCH,ZDT系列,LZ)计算所求Pareto前沿与真实Pareto前沿的广义距离和所求Pareto前沿的多样性来测试IMOCS的性能.结果表明,与MOCS,NSPSO,NSGA-II比较,IMOCS所求的广义距离更小,即由IMOCS所求Pareto前沿更加接近于真实Pareto前沿,同时IMOCS的Pareto前沿分布更加广泛和均匀,即多样性更好.

自适应多目标混合差分进化算法在联盟运输调度中的应用

传统的单目标算法运行一次只能得到一个解,而多目标算法运行一次可以得到一个解集。文中所提算法(DEASA)通过改进差分进化策略,设计重构,调整自适应参数,并采用擂台法则构建非支配集,将模拟退火策略融入到差分进化算法当中,进一步提高了算法的性能,降低了时间复杂度,增强避免陷入局部最优的能力。通过实验验证表明,该算法能有效地解决联盟运输调度问题。

一种基于快速排序的快速多目标遗传算法

多目标遗传算法的一个重要步骤就是构造非支配集,本文提出了一种基于快速排序的非支配集构造方法,提高了非支配集构造效率,并且在Deb提出的NSGAⅡ的基础上,改进了其种群构造策略,设计了一类新的多目标遗传算法。实验表明,这种方法比NSGAⅡ具有更快的收敛速度且保持了良好的分布性。

冷轧机组批量作业计划模型与算法

针对编制冷轧机组作业计划受到钢卷宽度跳跃、入口厚度跳跃和出口厚度跳跃等多个工艺约束的问题,把排产过程归纳为非对称双旅行商问题,建立了冷轧机组生产作业计划的Pareto多目标模型.提出了基于Pareto非支配集的自适应多目标蚁群算法,利用自适应蚁群算法和Pareto非支配集思想,综合考虑多个目标,自适应地提供蚂蚁路径搜索参数,并对得到的非支配解集对应路径更新信息素,引导蚂蚁向最优解集方向搜索,最终提供多个可行的批量作业计划,根据生产要求从中选择合适的最优排产结果.利用某冷轧薄板厂实际的生产数据进行仿真实验,表明模型与算法在冷轧机组批量作业计划编制过程中具有可行性.

基于MMAS的多目标优化算法研究

针对多目标优化问题求解过程中多个目标相互制约难以求解的特点,为了多目标的协调优化,提出了一种基于最大最小蚁群算法(MMAS)的多目标优化蚁群算法。将蚁群算法的离散搜索机制映射到连续空间,修改了离散蚁群算法的行进规则和信息素的存留策略,使蚁群算法能够应用于解决解空间连续的问题。最大最小蚂蚁系统信息素取值方式的引入,极大地改善了蚁群算法搜索过程中容易陷入停滞的问题,尤其改善了蚁群算法在解空间的全局搜索能力。通过对两组测试函数求解的结果与其它方法比较,仿真结果表明所获得的最优解更多,分布范围更广,所求得的最优解集更加逼近真实的最优前沿。

用基于快速排序的MOGA求解MOKP

0/1背包问题是一类典型的组合优化问题,且属于NP完全问题.多目标遗传算法通过一次运行可以搜索到多个解,同时具有比规范遗传算法更强的求解问题的能力.该文将基于快速排序的多目标遗传算法应用于多目标0/1背包问题中,可以快速、高效地找出多个最优解.实验表明该方法能够获得满意的效果.

多目标车辆路径的遗传算法

传统的单目标遗传算法运行一次只能得到一个解,而多目标遗传算法运行一次可以得到一个解集,多个解可以为决策者提供更多的选择余地,作出更好的决策。本算法通过设计新的改进遗传算子,进一步提高了算法的性能,并设计采用擂台法则构建非支配集,降低了时间复杂度。通过实验验证表明,此算法能有效的解决车辆路径问题。