基于对称拉丁超立方设计的多目标进化算法

随着科技和经济的飞速发展,人类不断地在各个领域遇到复杂的多目标优化问题。这些问题通常要求以最少的代价,实现几个相互冲突的目标同时达到最优。比如:在设计通信基站的分布时,一方面要求通信基站覆盖最大的区域,另一方面要求基站的数目尽可能的少,以节约成本等等。多目标优化问题与单目标优化问题的不同之处在于多目标优化问题的解不再是单纯的绝对最优解,而是一个最优解集,通常该最优解集包含无穷多个Pareto最优解。因此如何获得这个最优解集,且使该最优解集中的Pareto最优解均匀的分布,为决策者提供具有重要价值的方案,已成为一个迫切需要解决的问题。 传统的多目标优化算法,如加权和法,目标规划法,ε-约束法等基于权重的多目标优化方法,都是通过加权等方式将多目标问题转化为单目标,然后用数学规划的方法来求解。这类方法不能求出非凸Pareto前端的Pareto最优解,对于复杂的多目标规划效率往往较低。多目标进化算法是一种有效的全局搜索方法,采用自然进化机制来表现复杂的现象,能快速可靠地解决非常困难的问题,可在单轮优化期间产生多个非劣解,而且对Pareto前端的形状和连续性不敏感,能够很好地逼近非凸的或不连续的Pareto前端。 本文首先分别介绍多目标优化问题传统算法和多目标进化算法的基本概念,关键理论,算法框架等,并分析经典传统算法和多目标进化算如:线性加权法,主要目标法,以及NSGA,SPEA等算法的优点与局限性。接着提出基于对称拉丁超立方设计的多目标进化算法。该算法基于对称拉丁超立方设计“充满空间”的性质,构造出多样的,分布广泛的权向量,并将生成的权向量与目标函数的线性组合作为适应度函数,从而扩大解的搜索区域,不再是从单一固定的方向搜索Pareto最优解。同时给出了基于对称拉丁超立方设计的初始种群和交叉算子,引进精英保留策略,增强了算法的搜索能力,提高了解集的多样性和收敛性。本文引进个体密度数,保证了小超立方体内Pareto最优解满足一定的数量条件,从而使得算法得到均匀分布的Pareto最优解。实验结果表明,该算法具有优良的搜索性能,能够搜索出非凸Pareto前端的非劣解,且得到的Pareto最优解集比NSGAⅡ得到Pareto最优解集更能接近真实的Pareto前端,且解分布均匀广泛。