a*算法matlab代码_基于粒子群算法的多目标搜索算法讲解（附MATLAB代码）

本文依然参考《MATLAB智能算法30个案例分析》一书，文末的源代码也来自本书

上周有小伙伴后台问小编能否讲解一下关于多目标优化问题的算法，本周小编做足了功课，为大家更新这篇推文。

在讲解多目标优化问题之前，小编想先讲一个小故事，说有一位女生，她想每天都吃好多好吃的，同时又想保持好身材，我们都知道这在现实生活中很难实现的。这其实可以抽象为一个实际问题模型，如何保证每天摄入食物最多，且体重最小，比如说女生1每天摄入2kg食物，体重50Kg；女生2每天摄入2Kg食物，体重52Kg；女生3每天摄入1Kg食物，体重50Kg；女生4每天摄入1Kg食物，体重48Kg。

我们最终得出的结论是女生1要好于女生2，因为吃同样多的饭，女生1比女生2瘦；女生1也好于女生3，虽然两人体重相同，但女生1更能吃；女生4要好于女生3，因为吃同样多的饭，女生4比女生3瘦；But，女生1和女生4谁更优秀呢，我们无法比较，这里实质上就是说这个问题不只有一个“最优解”。当然小编只是举个例子。目的是告诉大家，多目标问题没有一个所谓的最优解，而是有一个最优解的集合，看到这里各位可能会有点蒙，没关系，下面小编给出一个实例，让大家直观感受一下小编刚才说的是什么意思。

问题描述：

假设存在五类物品，每类物品中又包含四种具体物品，现要求从这五类物品中分别选择一种物品放入背包中，使得背包内物品的总价值最大，总体积最小，并且背包的总质量不超过92Kg。其中P为每个物品的价值，R为每个物品的体积，C为每个物品质量。

下面给出3种不同的选择方案：

方案1：我们第1类物品中取第1各物品，第2类物品中取第1个物品，第3类物品中取第1个物品，第4类物品中取第3个物品，第5类物品中取第1个物品。

经计算可知该种选法的

物品总价值sumP1=3+4+9+12+2=30

总体积sumR1=0.2+0.3+0.4+0.5+0.1=1.5

总质量sumC1=10+13+24+28+4=79<92

方案2：我们第1类物品中取第1各物品，第2类物品中取第1个物品，第3类物品中取第2个物品，第4类物品中取第2个物品，第5类物品中取第1个物品。

经计算可知该种选法的

物品总价值sumP2=3+4+8+10+2=27

总体积sumR2=0.2+0.3+0.38+0.45+0.1=1.43

总质量sumC2=10+13+22+26+4=75<92

方案3：我们第1类物品中取第1各物品，第2类物品中取第1个物品，第3类物品中取第1个物品，第4类物品中取第4个物品，第5类物品中取第1个物品。

经计算可知该种选法的

物品总价值sumP3=3+4+9+10+2=28

总体积sumR3=0.2+0.3+0.4+0.6+0.1=1.6

总质量sumC3=10+13+24+32+4=83<92

经比较发现：方案1优于方案3，因为方案1的物品总价值>方案3的物品总价值，即sumP1>sumP3；方案1的物品总体积sumR1<sumR3；并且两种方案都满足重量约束，即sumC1<92，sumC3<92，因此方案1的选择方案选择的物品使背包内物品的总价值又大，总体积又小。但是方案1与方案2无法比较，因为方案1的物品总价值>方案2的物品总价值，即sumP1>sumP2；但是方案1的物品总体积>方案2的物品总体积，即sumR1>sumR2；并且两种方案都满足重量约束，即sumC1<92，sumC2<92，因为虽然方案1的选择方案使背包内物品的总价值大于方案2的选择方案背包内物品的总价值，但是方案1的选择方案使背包内的总体积也大于方案2选择方案背包内物品的总体积。这两种方案种的两个目标同时比较时，无法做到某一个方案的所有目标都优于另一个方案的所有目标，所以这两种方案无法比较优劣。

由上述内容可以引出多目标优化问题的两个基本概念：Pareto最优解和Pareto最优前沿。

Pareto最优解：对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解。

Pareto最优前沿：对于组成Pareto最优解集的所有Pareto最优解，其对应目标空间中的目标矢量所构成的曲面称作Pareto最优前沿。

就上文提到的背包问题，方案1和方案2都属于Pareto最优解，方案1和方案2共同构成Pareto最优解集。

本文要求解的多目标优化问题，前文已经给出，其实问题的结果就是一个1行5列的行向量，比如说问题的解为[1 1 1 3 1]，则表明第1类物品中取第1各物品，第2类物品中取第1个物品，第3类物品中取第1个物品，第4类物品中取第3个物品，第5类物品中取第1个物品。

本文用粒子群算法求解多目标问题，不知道小伙伴们还记不记得《混合粒子群算法通俗讲解(附MATLAB代码)》一文中所讲的粒子群算法的两大特点：个体最优和群体最优，忘了的小伙伴可以回去稍微复习一下。

在这里小编想给出用粒子群算法求解多目标优化问题的流程图：

下面详细解释每个步骤的涵义：

1. 种群初始化：随机初始化粒子的位置x和速度v。
2. 适应度值计算：每个个体的适应度值有两个，即价值sumP和体积sumR，同时个体必须满足质量约束(sumC<92)。
3. 粒子最优更新：包括个体最优最优粒子更新和群体最优粒子更新，其中个体最优粒子的更新方式是从当前粒子和个体最优粒子中选择支配粒子(一个粒子支配另一个粒子的意思就是该粒子的sumP和sumR都好于另外一个粒子)，当两个粒子都不是支配粒子时，从中随机选择一个粒子作为个体最优粒子。群体最优粒子为从Pareto最优解集中随机选择的一个粒子。
4. Pareto最优解集更新：当新粒子不受其他粒子及当前Pareto最优解集中的粒子的支配时，把新粒子放入Pareto最优解集中。
5. 粒子速度和位置更新：在这里小编介绍一下粒子速度和位置更新的公式，因为接下来的代码中有用到这两个公式。

其中，

为惯性权重；r1和r2为均分布于[0,1]区间的随机数；k是当前迭代次数；

为个体最优粒子位置；

为全局最优粒子位置；c1和c2为常数；V为粒子速度；X为粒子位置。这里粒子位置X可以随机生成，形式如[1 1 1 3 1]，粒子初始速度V可设置为0，从上面两个公式也可以看出，更新粒子速度V目的是为了更新粒子位置X。

最后附上PSO求解多目标优化问题的MATLAB代码(后台回复“PSO多目标”提取代码)：

链接：https://pan.baidu.com/s/1jExRuCXUrDfR7L4lb9thpA 

提取码：cwwe 

最后，小编想说如果大家觉得文章写得还可以的话，麻烦大家动动小手点个赞，你们的支持是小编前进的动力。