用遗传算法求解多目标0/1背包问题

摘要

扼要介绍多目标优化的Pareto最优性概念,研究搜索多目标0/1背包问题Pareto最优解集的快速遗传算法(FPGA:fast Pareto genetic algorithms).FPGA采用种群中非支配解的层次评价可行解的适应值,提出了一种快速非支配解层次辨识算法,辨识算法仅有O(n2)数量级的计算复杂性;采用基于聚类概率排挤的小生态技术维持种群多样度和Pareto最优解集的分布均匀性.对多种多目标O/1背包问题的仿真优化实验结果表明,FPGA能够以有效的计算成本搜索到精度高的、分布均匀的高质量Pareto非劣解集,其收敛速度和收敛准确性一致地优于代表性的强度Pareto进化算法(SPEA).