1. 粒子群算法简介
- 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，属于进化算法的一种，是通过对模拟鸟群扑食行为设计的。
-
基本思想：
从随机解出发，通过迭代寻找最优解，通过适应度来评价解的品质。 -
场景设定 :
一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 -
粒子群算法的几个概念
- 粒子：场景中的一只鸟；
- 种群：场景中的一群鸟；
- 位置：粒子（鸟）所在的位置；
- 速度：鸟的飞行速度，粒子的移动速度；
- 适应度：鸟距离食物远近，粒子距离目标的评价。
2. 算法分析
-
算法流程
粒子群算法流程.png -
流程描述
1.首先随机生成粒子，并组成种群；其中粒子的数量及种群的大小可以控制；
2.计算每个粒子的适应度值；
3.通过当前适应度值是pBest(当前粒子的历代最佳值)和gBest(种群的历代最佳值)进行对比，来更新当前粒子的速度和位置；
4.判断是否满足退出条件（达到迭代次数或者最优解的误差满足设定的阈值），若不满足则转向2. -
速度与位置的更新
粒子群算法的核心就是每个粒子位置和速度的更新-
速度更新
速度更新公式
v：粒子当前的速度；w是惯性因子；position是粒子当前的位置；pBest是当前粒子历代最好的位置；gBest是种群中当前最好的位置；c1和c2是学习因子，分别是向pBest和gBest学习。 -
速度更新的三部分解读
-
w*v: 惯性保持部分，粒子沿着当前的速度和方向惯性飞行，不会偏移。假如没有惯性部分，粒子会很快向pBest和gBest移动，很容易陷入局部最优。有了惯性，粒子就会有在空间中自由飞行的趋势，能够在整个空间寻找最优解。 -
c1*rand()*(pBest-position):自我认知部分，粒子有回到自身历代最好位置的意愿。假如没有自我认知部分，粒子将很快向gBest移动，很容易陷入局部最优。 -
c2*rand()*(gBest-postion):社会认知部分，粒子有向种群中最好位置学习的意愿。假如没有社会认知部分，所有的粒子都向各自的pBest移动，各自陷入自身的最优解，从而导致整个过程不收敛。
-
位置更新
-
位置更新公式
3. TSP问题
TSP问题（Travelling Salesman Problem）即旅行商问题： 又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP问题是一个组合优化问题， 是一个NPC问题，分为两类： 一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。
4. 粒子群算法解决TSP问题
-
算法的实现
- 粒子的表示：TSP问题的一个解为一个序列，可以表示为一个粒子；
- 速度的表示：用一个序列的交换序列表示粒子的速度。
- 适应度函数的定义： 当前序列的路径长度即为适应度值，通过经纬度坐标计算。
- 惯性因子的定义：自身的交换序列即惯性因子
-
Java代码实现
- 速度和位置的更新
更新公式：Vii=wVi+ra(Pid-Xid)+rb(Pgd-Xid)
- 速度和位置的更新
private void evolution() {
for (int t = 0; t < MAX_GEN; t++) {
for (int k = 0; k < scale; k++) {
ArrayList<SO> vii = new ArrayList<>();
//第一部分:惯性保持部分，自身交换对
int len = (int) (w * listV.get(k).size());
for (int i = 0; i < len; i++) {
vii.add(listV.get(k).get(i));
}
//第二部分：自我认知部分，和当前粒子中出现最好的结果比较，得出交换序列
//ra(Pid-Xid)
ArrayList<SO> a = minus(mUnits.get(k).getPath(), Pd.get(k).getPath());
float ra = random.nextFloat();
len = (int) (ra * a.size());
for (int i = 0; i < len; i++) {
vii.add(a.get(i));
}
//第三部分：社会认知部分，和全局最优的结果比较，得出交换序列
//rb(Pgd-Xid)
ArrayList<SO> b = minus(mUnits.get(k).getPath(), Pgd.getPath());
float rb = random.nextFloat();
len = (int) (rb * b.size());
for (int i = 0; i < len; i++) {
vii.add(b.get(i));
}
listV.remove(0);
listV.add(vii);
//执行交换，生成下一个粒子
exchange(mUnits.get(k).getPath(), vii);
}
//更新适应度的值
for (int i = 0; i < scale; i++) {
mUnits.get(i).upDateFitness();
if (Pd.get(i).getFitness() > mUnits.get(i).getFitness()) {
Pd.put(i, mUnits.get(i));
}
if (Pgd.getFitness() > Pd.get(i).getFitness()) {
Pgd = Pd.get(i);
bestT = t;
}
}
}
}
