非支配解集的质量评价方法

多目标演化算法的目的是获得逼近Pareto最优前沿的分布均匀的非支配解集合,非支配解集的质量是多目标演化算法研究的重要领域.本文对目前提出的非支配解集的质量评价方法进行分类比较,为算法的整体性能评价和算法的性能比较提供了参考依据.     

基于高效非支配排序的多目标人工蜂群算法

多目标优化问题广泛存在于科学与工程领域,为了提高求解效率,改进算法中的关键环节——非支配排序,提出了一种基于高效非支配排序的多目标人工蜂群算法。本文算法根据精英指导离散解生成策略进行局部搜索,运用高效非支配排序计算解的前沿面,最后根据前沿面排名和拥挤距离来挑选表现较好的解进行下一轮迭代。在基准函数上的实验验证了本文算法在保证求解性能的前提下,可以降低1/2的比较次数,运行效率提升近65%。     

基于多项式时间近似及其改进算法的WSN设计

为了实现WSN设计中以满足一定的性能目标和网络成本的优化,提出了一种基于多项式时间近似及其改进算法.首先将问题构建为一个多接收器网络-最小成本-跳数约束问题;然后将问题简化为一个加权集合覆盖问题的改进形式,从而采用加权集合覆盖贪婪算法来得到问题的解;其次,为了改进多项式时间近似算法得到的解,在前者的基础上采用启发式工作方式迭代地去除当前解的一部分,并通过试探搜索空间的其他部分来重建解,从而得到更高质量的解.仿真实验结果表明,提出的算法在满足一定的QoS要求下,既能获得较低的设计成本,也能实现较少的执行时间.     

贪婪法在算法设计中的应用与局限

利用贪婪法进行算法设计时速度快,但由于算法只是考虑局部最优解,未从整体最优上加以考虑,有时不能得到全局最优解.以背包问题、克鲁斯卡尔算法为例系统阐述了贪婪法在算法设计中的应用,又以找零钱、数塔问题、货郎担问题为例对于贪婪法求解以及实际最优解做了对比,系统地分析了贪婪法在算法设计中的局限.     

基于多目标离散正弦优化算法的混合零空闲置换流水车间调度

针对以最小化最大完工时间（makespan）和最小化最大拖期（maximum tardiness）为目标的多目标混合零空闲置换流水车间调度问题（Mixed No-idle Permutation Flow Shop Scheduling Problem,MNPFSP）,提出了一种多目标离散正弦优化算法（Multi-objective Discrete Sine Optimization Algorithm, MDSOA）。首先,建立外部档案集（AS）存储Pareto解,并在每次迭代后对AS进行更新;其次,在正弦优化算法（Sine Optimization Algorithm,SOA）的基础上,引入迭代贪婪（IG）算法的破坏重构机制,重新定义了一种适用于离散调度问题的位置更新策略;最后,引入快速非支配排序和拥挤距离对种群进行筛选,在保留精英解的同时保证了解的多样性和分布性。选取Taillard Benchmark中11个不同规模的算例进行仿真实验,并将仿真结果与NSGA-Ⅱ和NSGA-Ⅲ算法进行比较,验证了MDSOA求解MNPFSP的有效性。     

基于贪婪策略整体分布优化算法的0-1背包问题求解

提出了一种思想简单且可用于0-1背包问题求解的基于贪婪策略整体分布优化算法.该算法首先随机产生一个初始种群,经贪婪策略将种群变成价值相对较高的可行解,保留本次最优解;然后以最优解为中心,用柯西分布产生新的种群,经贪婪策略将新种群变成相对价值较高的可行解,再保留本次最优解,重复以上过程,达到最大迭代次数,求出问题的全局最优解;最后,对不同规模的问题进行了实验.结果表明:该算法在求解0-1背包问题上是有效的,比遗传算法、贪婪算法具有更强的寻优能力.     

灰色多目标光学寻优算法

结合光学原理以及灰色系统思想提出了一种求解多目标问题的新方法.此方法利用自然界中最基本的光学现象设计迭代机制,同时与应用灰色系统原理维护外部档案的机制有机地结合在一起形成多目标优化方法.在数值实验中设计多种组合实验,分别从算法性能、Pareto最优集效果、收敛性多样性指标方面与经典算法进行比较.结果表明:灰色理论的引入大大加强了非劣解的均匀性,同时光学的迭代原理有效地增强了收敛性,为快速解决高维多目标优化问题提供新思路.     

基于改进萤火虫算法的移动机器人多目标路径规划

针对复杂室内环境下移动机器人的路径规划问题,提出一种面向多目标同时优化的改进萤火虫算法;该算法利用栅格地图对机器人作业环境进行建模,将Pareto支配关系引入到萤火虫个体的亮度评价过程,构建精英库保留算法迭代过程中的Pareto非支配解,采用自适应网格划分策略维护种群的多样性;以路径长度、路径安全性和路径平滑度为目标进行运动路径的搜索与优化。仿真结果表明,与经典的带精英策略的非支配排序遗传算法相比,面向多目标同时优化的改进萤火虫算法求得Pareto非支配解集更优越。     

解多目标最优化问题的权衡割平面法

在现有的一些解多目标问题交互算法的基础上,提出了一种解决一般非线性多目标最优化问题的交互式算法——权衡割平面法.它每次迭代前后所得到的解都是有效解,搜索策略灵活实用,且对线性多目标最优化问题只需一次迭代就得到最优解.     

资源受限最小赋权树形图的一种贪婪分解启发式算法

资源受限的最小赋权树形图问题(RMWA)是NP-难的,针对RMWA问题给出一种新的贪婪分解启发式算法.通过分解目标函数和约束条件,把RMWA模型分解成一个最小赋权树形图问题和n个独立的特殊背包问题.对这n个独立的特殊背包问题,设计贪婪算法求其解,其时间复杂度为O(nmlog2m);然后调整该解使其满足树形图的约束条件得到RMWA问题的一个可行解,该算法总的复杂度为O(nm2).最后,给出实例来阐述该贪婪分解启发式算法.     

面向多目标优化问题的基于Species的遗传算法

为了能够快速准确地获得多目标优化问题的一组非支配解,提出了一种基于Species的多目标遗传算法.该算法采用Tchebycheff方法构建一定数量的子问题,进而基于Species机制构造多种群实现了对多个子问题的并行求解.这种采用多个体对一个最优解的搜索方式提高了算法的探索能力和开发能力.最后,对一组标准测试函数进行仿真实验,结果表明所提出的算法能够快速准确地获得一定数量的非支配解.     

基于改进动态规划法的HEV多目标能量管理策略

混合动力汽车能量管理策略（EMS）优化问题是一类需要综合优化混合动力汽车多个性能指标的多目标多阶段决策问题,而传统的多目标优化算法在求解EMS这类问题时面临求解效率低、收敛性难以保证等挑战。本文结合非支配排序算法的思想,将传统的动态规划法（DP）拓展到多目标优化领域,提出了非支配排序动态规划法（NSDP）。该算法首先将行驶工况划分为多个阶段,在每个阶段中求取混合动力汽车在不同控制策略产生的累积目标值向量,并通过非支配排序算法获得当前的非支配解集以及对应的控制策略,然后利用各个阶段的非支配解集依次逆向迭代,直至获取整个行驶工况的非支配解集前沿以及对应的能量管理控制策略。在仿真实验中,分别应用加权动态规划法（WDP）和非支配排序动态规划法求解功率分流式混合动力汽车和串并联式混合动力汽车在匀加速工况的多目标能量管理策略优化问题,结果表明NSDP能够有效完成求解并保证收敛性,且求解结果在解集均匀性和求解效率方面具有显著的优势。进一步,运用NSDP求解在世界轻型车辆测试工况（WLTC）下串并联式混合动力汽车能量管理优化问题,所得非支配解集可用于分析汽车的工作特性,并能够为实际能量管理策略的制定提...     

多目标进化算法测试问题的设计

为了有效地检测多目标进化算法在求解各类多目标优化问题时的性能,从3个方面讨论了多目标优化测试问题的设计,即约束条件、最优解分布的均匀性、算法逼近Pareto最优前沿的难度.针对每一方面,都设计了一个相关的测试问题,并采用NSGA Ⅱ算法进行了仿真实验.结果显示,测试问题能够有效检测算法在上述三方面的性能,尤其是在约束处理方面.这些测试问题可供研究人员用来评价他们所设计的多目标优化算法.     

基于多目标遗传算法的云服务部署优化方法

将服务部署优化问题建模为多目标组合优化问题.在多目标遗传算法的基础上,把部署方案转换为基因编码,用轮盘赌选择机制选择个体,用单点交叉算子产生新的子代,并以设定的概率发生变异.对合适个体考虑支配值和稀疏值设计适应度函数;对不合适个体根据支配值和SLA冲突设计适应度函数.最后给出了优化过程.通过仿真实验可以看出:随着迭代次数的增加,适应度值及各个优化指标值逐渐收敛于一个固定且较优值,说明利用设计的优化算法,能使各个优化目标值较快地收敛到一个较优解,能较好地帮助基础设施即服务(SaaS)提供商在部署应用服务时进行有效规划和决策.     

离散正弦余弦算法求解大规模0-1背包问题

针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。     

基于混合变邻域遗传算法的柔性车间调度研究

针对柔性作业车间调度的问题，以最大完工时间为目标建立数学模型，提出一种混合变邻域遗传算法。采用三种初始化方法保证初始解的质量，用遗传算法进行初步搜索，将搜索的结果通过迭代贪婪策略进一步搜索，以提高解的质量，再对关键路径进行邻域搜索，设计“跨机器工序搜索邻域”、“同机器工序搜索邻域”、“次优工序搜索邻域”三种邻域结构，加强局部搜索能力。引入迭代贪婪策略和改进的邻域结构可显著提高算法的稳定性与迭代速度。通过对国际通用的柔性作业车间调度基准算例进行测试，实验结果表明所提改进算法能够有效求解柔性作业车间调度问题。     

基于层次粒子群算法的配送中心双层规划选址策略

在考虑物流网络宏观决策部门和客户双方利益的基础上,建立物流配送中心双层规划的选址模型.此类问题大多属于非凸优化问题,现有的求解算法存在算法复杂度及计算效率问题.基于进化博弈及多目标优化非支配排序的思想设计层次粒子群算法,通过两个粒子群算法的交互迭代求解物流配送中心双层规划选址问题.通过测试算例验证算法的有效性.     

考虑需求满意度与救援时间公平的应急物资调度多目标模型及算法

针对突发灾害后的应急物资调度问题,本文基于各个灾点物资满足程度情况构建了灾民满意度目标函数,以各个灾点救援时间构建了时间公平目标函数,以灾民满意度最大化与救援时间公平、成本最小化为目标建立了多目标数学模型。设计了一种改进的非支配排序萤火虫算法求解该类多目标问题帕累托解。通过算例进行模拟实验表明,所提出的模型和算法可以有效解决突发事件下应急物资调度问题,且改进算法的性能更优。     

带有盒子约束的多目标优化问题的进化算法

针对带盒子约束的多目标优化问题,提出一种多目标优化进化算法。在选择过程中．采用Pareto支配和聚集距离排序来挑选出有代表性的个体。在变异过程中,沿着权重梯度方向搜索来寻找可行的Pareto最优解。最后,采用两个数值算例测试算法的性能,通过与NSGA—II的比较结果表明该算法能获得多目标优化问题的可行Pareto最优解并且具有很好的分散性。     

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

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