寻优算法之粒子群

WindChaser

2019-06-27

导言

粒子群PSO算法相比遗传算法实现会简单一点，核心就是根据算子更新个体历史最优和全局最优。粒子群用的不多，给我的感觉是收敛很快的一种算法。这种算法较为容易陷入局部最优，若问题具有欺骗性（具有多个假峰，且优化资源集中在其中一个峰上）就不容易找到全局最优。学院有个学长改进PSO发了篇论文，好像是将（全局最优-个体最优）加入到算子当中，这会一定程度上跳出局部最优。

遗传算法回顾

核心算子：

v[i] = w * v[i] + c1 * rand() * (pbest[i] - present[i]) + c2 * rand() * (gbest - present[i])
 present[i] = present[i] + v[i]

其中v[i]代表第i个粒子的速度，w代表惯性权值,c1和c2表示学习参数，rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的历史最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。

算法思想

模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，会不停改变地自己在空中飞行的位置与速度。改变的方向会根据个体的历史最优p_best和全局最优g_best来做出改变，也就是上面的核心算子。可以比喻为每只鸟会一定程度上追随每次迭代中找食物最厉害的那只鸟，这里的找食物最厉害就是能最大可能解出目标函数。

算法过程：

还是解决遗传算法当中的简单单目标问题，求解函数f的最大值

max f (x1, x2) = 21.5 + x1·sin(4 pi x1) + x2·sin(20 pi x2)
s. t. -3.0 <= x1 <= 12.1
        4.1 <= x2 <= 5.8

寻优算法之粒子群
种群初始化：

import random
import numpy as np

pop_size = 100
dec_num = 2    #变量个数
dec_min_val = (-3, 4.1)    #变量约束范围
dec_max_val = (12.1, 5.8) 
pop_x = np.zeros((pop_size, dec_num))  # 所有粒子的位置
pop_v = np.zeros((pop_size, dec_num))  # 所有粒子的速度
p_best = np.zeros((pop_size, dec_num))  # 个体经历的最佳位置

def init_population(pop_size, dec_num, dec_min_val, dec_max_val, pop_x, pop_v, p_best):
    for i in range(pop_size):
        for j in range(dec_num):
            pop_x[i][j] = random.uniform(dec_min_val[j], dec_max_val[j])
            pop_v[i][j] = random.uniform(0, 1)
        p_best[i] = pop_x[i]  # p_best存储个体的历史最优

迭代更新：

import random
import matplotlib.pyplot as plt
from Initialization import init_population

max_gen = 100
w = 0.4  # 自身权重因子
c1 = 2  # 学习因子
c2 = 2
g_best = np.zeros((1, dec_num))  # 全局最佳个体的位置
popobj = []

def fitness(s):    #个体适应值计算
    x1 = s[0]
    x2 = s[1]
    y = 21.5 + x1 * math.sin(4 * math.pi * x1) + x2 * math.sin(20 * math.pi * x2)
    return y


if __name__ == '__main__':
    init_population(pop_size, dec_num, dec_min_val, dec_max_val, pop_x, pop_v, p_best)
    temp = -1    
    #    ------------更新全局最优-------------
    for i in range(pop_size):   
        fit = fitness(p_best[i])
        if fit > temp:
            g_best = p_best[i]
            temp = fit
    #    ------------迭代优化-------------
    for i in range(max_gen):
        for j in range(pop_size):
            #   ----------------更新个体位置和速度-----------------
            pop_v[j] = w * pop_v[j] + c1 * random.uniform(0, 1) * (p_best[j] - pop_x[j]) + \
                        c2 * random.uniform(0, 1) * (g_best - pop_x[j])
            pop_x[j] = pop_x[j] + pop_v[j]
            for k in range(dec_num):    # 越界保护
                if pop_x[j][k] < dec_min_val[k]:
                    pop_x[j][k] = dec_min_val[k]
                if pop_x[j][k] > dec_max_val[k]:
                    pop_x[j][k] = dec_max_val[k]
            #   -----------------更新p_best和g_best-----------------
            if fitness(pop_x[j]) > fitness(p_best[j]):
                p_best[j] = pop_x[j]
            if fitness(pop_x[j]) > fitness(g_best):
                g_best = pop_x[j]
        popobj.append(fitness(g_best))
        print(fitness(g_best))

    # -------------------画图--------------------
    plt.figure(1)
    plt.title("Figure1")
    plt.xlabel("iterators", size=14)
    plt.ylabel("fitness", size=14)
    t = [t for t in range(0, 100)]
    plt.plot(t, popobj, color='b', linewidth=3)
    plt.show()

结果和遗传算法差不多，但速度是快了，不需要像遗传算法那样交叉变异，另一方面粒子群的参数设置有点多。

寻优算法之粒子群