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

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

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

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

基于随机算子的快速多目标遗传算法

在NSGA-Ⅱ算法的基础上,对NSGA-Ⅱ构造非支配集的方法进行了改进,用擂台赛法则构造非支配集,当非支配集小于种群大小时,采用随机算子在可行域内随机产生新的解个体填充到下一代父种群中,形成了一种新的多目标遗传算法。在实验部分将改进后的算法和NSGA-II进行了性能比较,实验结果表明改进后的算法具有良好的分布性,算法运行效率也较高。     

多目标差分进化在热连轧负荷分配中的应用

提出一种基于差分进化算法的多目标进化算法, 该算法个体的选择是通过非支配排序和拥挤度距离进行综合考虑. 保证了算法收敛到Pareto最优解集的同时, 提高了最优解个体分布的多样性. 通过与非支配排序遗传算法Ⅱ(NSGA Ⅱ)算法进行仿真对比, 结果显示基于拥挤度排序的多目标差分进化算法在收敛性和Pareto最优解集分布的多样性上均优于NSGA Ⅱ算法. 最后将其引入到热连轧负荷分配优化计算中, 给出了目标函数的表达方式, 对多目标进化算法在热连轧负荷分配计算中的应用进行了研究.     

基于非支配解排序的快速多目标微分进化算法

为解决基于帕累托(Pareto)支配解排序的多目标进化算法高时间复杂度问题,依据非支配解排序潜在特性,介绍了一种快速的非支配解排序方法,每次只处理当前种群中最高等级个体,且在分配等级的同时,能选择个体进入下一代,下一代被选足时即结束程序,减少了排序处理个体的数量,大幅度降低时间复杂度;另外,给出一种均匀的拥挤距离计算方法;最后,将快速非支配解排序和均匀拥挤距离计算与微分进化算法结合,提出基于非支配解排序的快速多目标微分进化算法(FMODE)。采用标准多目标优化问题ZDTl～ZDT4和ZDT6进行仿真实验：当种群个体较多(大于500)时,FMODE所用时间远小于NSGAⅡ;FMODE的总体性能上均优于经典的NSGAⅡ、SPEAⅡ和DEMO;在FMODE框架内,采用均匀拥挤距离在性能上也明显优于经典拥挤计算方法;并通过实验确定了FMODE算法的参数。实验结果表明FMODE能够减少计算等级时的处理时间,并在收敛性和多样性指标上明显优于对比算法。     

具有多形态种群协同进化的多目标优化算法

为提高进化多目标优化算法在维持最优解多样性方面的性能,获得分布更均匀的Pareto非支配解集,文中提出一种具有多形态种群协同进化的多目标优化算法.该算法构建一种多形态种群协同进化架构,通过引入最小向量夹角的相似性度量方法,给出次优非支配个体选择策略,从而提高种群的多样性.算法还提出一种基于排序链表的拥挤个体删除策略,进一步提高解集分布的均匀性和宽广性.与经典算法对比结果表明,文中算法在解的分布性和多样性方面均有较好表现,尤其在解集分布均匀性方面优势较明显.     

星型结构的多目标粒子群算法求解多模态多目标问题

首先,根据多目标粒子群算法中的粒子结构信息,利用非支配解集构造粒子个体邻域之间的拓扑结构,提出星型结构的多目标粒子群算法用于求解多模态多目标问题。其次,针对多目标粒子群中全局最优个体选择困难,提出一种非支配解集分布均匀程度的评价方法,评价结果用于确定当前粒子对应的全局最优个体。最后,结合2种方法提出带均匀计算方法的星型拓扑结构多目标粒子群优化算法STMOPSONCMIU。通过测试函数分析算法的收敛性,表明改进的算法比原来的算法收敛速度快。实验结果表明,该算法可以较好地兼顾问题的目标空间和决策空间的分布,有效解决多模态多目标问题。     

一种结合多目标免疫算法和线性规划的双行设备布局方法

设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后Pareto解. 实验结果表明, 该方法对于小规模问题能获得最优Pareto解, 对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.     

基于改进庄家法则的多目标进化算法

非支配集的构造方法是多目标进化算法中最重要的问题。在用庄家法则构造非支配集时,若非支配个体较多,由于需要进行多轮比较,所以算法的计算复杂度较高。在庄家法则中引入一个副庄家,用以减少下一轮比较个体的个数,从而最终减少比较的轮数。数值实验表明：改进后的算法具有较高的运行效率。     

一种快速的双目标非支配排序算法

提出一种快速的双目标非支配排序算法(BNSA)。设计了前向比较操作,以便快速识别非支配个体。提出了按需排序策略,避免生成多余的非支配前沿。论证BNSA算法的正确性,分析其时间复杂度为O(NlogN)。在9个标准的双目标优化测试问题上进行了比较实验。实验结果表明与其它3种非支配排序算法相比,BNSA算法在大多数测试问题上具有更快速的性能。当进化代数超过400代时,BNSA在所有的测试问题上都具有最好的加速效果。此外,BNSA算法简明、易于编程实现,可集成到任何基于非支配排序的多目标进化算法中,能较大程度地提高双目标优化的运行速度。     

量子多目标进化算法研究

本文首次将量子计算的理论用于多目标优化,提出量子多目标进化算法（QMOEA）,其采用量子位染色体表示法,利用量子门旋转策略和量子变异实现群体的进化,使用ε支配关系构造外部种群以此保持算法的较好分布性,提出基于快速排序的非劣最优解构造方法加快算法运行效率,实验表明,这种方法与经典的多目标进化算法SPEA2相比,其收敛性更好且分布更均匀     

基于Java的按位拆分快速排序并行算法

针对大数据量排序算法优化问题,提出一种基于Java的按位拆分的排序新算法。该排序算法按照位拆分数据,并结合Java的多线程对拆分的数据进行并行处理。数据实验结果表明,对于大数据量排序,该算法性能明显优于快速排序算法,而且算法具有很好的并行效率。     

利用帕累托非支配关系实现高效三目标差分进化的方法

在多目标进化算法中,时间复杂度过高是普遍的问题,特别是三个目标函数以上时,解的等级分配占用了过多运算时间。针对三目标问题,利用帕累托支配关系,对解的等级分配进行研究,发现经典的等级排序及分配方法存在一定冗余操作,需对全部的解先排序后,才能再分配等级并选择下一代,造成部分不必要的运算。为减少该冗余,利用帕累托非支配关系结合差分进化,实现高效三目标进化算法。算法每次迭代对种群中最高等级的个体进行计算,在分配等级同时进行选择后代个体操作,当后代种群生成时便跳出计算,从而减少个体的计算数量,降低运算量,同时给出该方法的相关理论分析和证明过程。然后,针对一系列三目标优化问题,将提出方法与著名排序方法NSGAII,及近年来优秀的ENS方法进行对比实验。仿真实验结果表明,提出方法在时间复杂度和收敛速度上优于经典方法,稍差于ENS方法。在标准测试函数DTLZ1-DTLZ6的性能上,提出方法近似于ENS方法,优于NSGAII算法,从而验证了提出方法的有效性和正确性。     

多目标旅行商问题的模拟植物生长算法求解

针对多目标旅行商问题,提出了一种基于模拟植物生长的优化算法。该算法将Deb等人提出的非支配排序及构造偏序集等方法用于模拟植物生长的过程中,克服了模拟植物生长算法搜索空间过大及收敛性不够理想的缺点。基于该算法的核心思想,用MATLAB编程实现,对参考文献的算例进行仿真测试。与其他算法比较,获得了满意的结果。     

超快速排序算法

快速排序算法结构简单,平均性能较佳;基数排序性能较稳定。结合快速排序和基数排序,提出超快速排序算法,通过理论分析和实验表明,新算法的性能优于快速排序算法和基数排序算法。     

基于聚类的快速多目标遗传算法

多目标遗传算法非常适合于求解多目标优化问题．讨论了进化个体之间的支配关系及有关性质，论证了可以用快速排序的方法对进化群体中的个体进行分类，同时探讨了用聚类方法来保持群体的多样性，具体讨论了基于层次凝聚距离的聚类，在此基础上提出了用分类和聚类的方法构造新的进化群体．理论分析与实验结果表明，所讨论的方法比较国际上已有的方法具有更快的收敛速度．     

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

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