基于粒子群算法的多目标搜索算法（附代码案例）

        在实际工程优化问题中,多数问题是多目标优化问题。相对于单目标优化问题,多目标优化问题的显著特点是优化各个目标使其同时达到综合的最优值。然而,由于多目标优化问题的各个目标之间的相互影响,多个目标难以同时达到最优,因此，一般适用于单目标问题的方法难以用于多目标问题的求解。         多目标优化问题很早就引起了人们的重视，现已经发展出多种求解多目标优化问题的方法。多目标优化问题求解中最重要的概念是非劣解和非劣解集，两者的定义如下：        非劣解(noninferior solution)：在多目标优化问题的可行域中存在一个问题解,若不存在另一个可行解,使得一个解中的目标全部劣于该解,则该解称为多目标优化问题的非劣解。所有非劣解的集合叫做非劣解集(noninferior set)。

        在求解实际问题中，过多的非劣解是无法直接应用的，决策者只能选择其中最满意的一个非劣解作为最终解。最终解选择主要有三种方法。第一种是求非劣解的生成法，包括加权法、约束法、加权法和约束法结合的混合法以及多目标遗传算法，即先求出大量的非劣解，构成非劣解的一个子集，然后按照决策者的意图找出最终解。第二种为交互法，主要为求解线性约束多目标优化的Geoffrion 法，不先求出很多的非劣解，而是通过分析者与决策者对话的方式，逐步求出最终解。第三种是事先要求决策者提供目标之间的相对重要程度，算法以此为依据，将多目标问题转化为单目标问题进行求解。         目前，采用多目标进化算法求解多目标问题已成为进化计算领域中的一个热门方向，粒子群优化、蚁群算法、人工免疫系统、分布估计算法、协同进化算法、进化算法等一些新的进化算法陆续被用于求解多目标优化问题。本案例采用多目标粒子群算法求解多目标背包问题。

        假设存在五类物品，每类物品中又包含四种具体物品，现要求从这五种类别物品中分别选择一种物品放入背包中，使得背包内物品的总价值最大，总体积最小，并且背包的总质量不超过92 kg。背包问题的数学模型为：

        其中，Px 表示背包内物品价值；Rx 表示背包内物品体积；C 表示物品质量；X 为选择物品。P 为每个物品的价值，R 为每个物品的体积。P，R，C 的取值如下：

        基于粒子群算法的多目标搜索算法流程如下图所示。其中，种群初始化模块随机初始化粒子的位置 α 和速度 v，适应度值计算模块根据适应度值计算公式计算个体适应度值，粒子最优更新模块根据新的粒子位置更新个体最优粒子。非劣解集更新模块根据新粒子支配关系筛选非劣解。粒子速度和位置更新模块根据个体最优粒子位置和全局粒子位置更新粒子速度和位置。

         每个个体的适应度值有两个，即价值和体积，同时个体需满足质量约束。

        筛选非劣解集主要分为初始筛选非劣解集和更新非劣解集。初始筛选非劣解集是指在粒子初始化后,当一个粒子不受其他粒子支配(即不存在其他粒子的P.,R均优于该粒子)时，把粒子放入非劣解集中,并且在粒子更新前从非劣解集中随机选择一个粒子作为群体最优粒子。更新非劣解集是指当新粒子不受其他粒子以及当前非劣解集中粒子的支配时,把新粒子放人非劣解集中,并且每次粒子更新前都从非劣解集中随机选择一个粒子作为群体最优粒子。

        粒子更新公式如下：

        其中，w为惯性权重；r1 和 r2 为分布于 [ 0，1 ] 区间的随机数；k 是当前迭代次数；Pk(id) 为个体最优粒子位置；Pk(gd) 为全局最优粒子位置；c1 和 c2 为常数；V 为粒子速度；X 为粒子位置。

        粒子最优包括个体最优粒子和群体最优粒子，其中个体最优粒子的更新方式是从当前新粒子和个体最优粒子中选择支配粒子，当两个粒子都不是支配粒子时，从中随机选择一个粒子作为个体最优粒子。群体最优粒子为从非劣解集中随机选择的一个粒子。

        根据多目标搜索算法原理，在 MATLAB 中实现基于粒子群算法的多目标搜索算法。

        初始化种群并且计算初始粒子的适应度值，程序代码如下：

        种群更新根据全局最优粒子和个体最优粒子更新当前个体的速度和位置，其中全局最优粒子为非劣解集中随机选取的粒子。程序代码如下：