【数值优化】启发搜索之群体智能(3)-- 粒子群

粒子群优化算法(partieleswarm optimization,pso)又翻译为粒子群算法、微粒群算法或微粒群优化算法,是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。由Eberhart博士和kennedy博士在1995年提出。其概念简单易于编程实现且运行效率高、参数相对较少,应用非常广泛。
PSO算法和模拟退火算法相比,也是从随机解出发,通过迭代寻找最优解。它是通过适应度来评价解的品质,但比遗传算法规则更为简单,没有遗传算法的“交叉”和“变异”,它通过追随当前搜索到的最大适应度来寻找全局最优。这种算法以其容易实现、精度高、收敛快等优点引起了学术界的重视,并在解决实际问题中展示了其优越性。

粒子群算法过程

STEP1: 随机产生种群。
STEP2: 根据策略计算个体的适应值,从而选择出个体的局部最优位置向量和种群的全局最优位置向量。
STEP3: 速度更新:更新每个个体的速度向量。
STEP4: 位置更新:更新每个个体的位置向量。
STEP5: 局部位置向量和全局位置向量更新:更新个体的和种群的。
STEP6: 终止条件判断:判断迭代次数时都达到,如果满足,输出;否则继续进行迭代,跳转至步骤3。

粒子群算法的代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
import numpy as np
import random
import math
import copy
import matplotlib.pyplot as plt

#========================================================
# 辅助工具
#========================================================

class PSOIndividual:
'''
模拟粒子个体
'''
def __init__(self, vardim, bound):
'''
个体初始化
vardim: 变量维数
bound: 变量取值范围
'''
self.vardim = vardim
self.bound = bound
self.fitness = 0. # 适应性得分

def generate(self):
'''
生成随机性
'''
len = self.vardim
rnd = np.random.random(size=len)
self.chrom = np.zeros(len)
self.velocity = np.random.random(size=len)
for i in range(0, len):
self.chrom[i] = self.bound[0, i] + (self.bound[1, i] - self.bound[0, i]) * rnd[i]
self.bestPosition = np.zeros(len)
self.bestFitness = 0.

def GrieFunc(self, vardim, x, bound):
'''
差分算法
'''
s1 = 0.
s2 = 1.
for i in range(1, vardim + 1):
s1 = s1 + x[i - 1] ** 2
s2 = s2 * math.cos(x[i - 1] / math.sqrt(i))
y = (1. / 4000.) * s1 - s2 + 1
y = 1. / (1. + y)
return y

def calculateFitness(self):
'''
计算适应性
'''
self.fitness = self.GrieFunc(self.vardim, self.chrom, self.bound)

#========================================================
# 核心算法
#========================================================

class PSO:
'''
粒子群算法
'''
def __init__(self, sizepop, vardim, bound, MAXGEN, params):
'''
sizepop: 种群规模
vardim: 变量维数
bound: 变量取值范围
MAXGEN: 最大迭代次数(终止条件)
param: 其他参数(列表)
'''
self.sizepop = sizepop
self.vardim = vardim
self.bound = bound
self.MAXGEN = MAXGEN
self.params = params
self.population = [] # 种群
self.fitness = np.zeros((self.sizepop, 1)) # 适应性评分
self.history = np.zeros((self.MAXGEN, 2)) # 迭代历史

def initialize(self):
'''
初始化种群
'''
for i in range(0, self.sizepop):
ind = PSOIndividual(self.vardim, self.bound)
ind.generate()
self.population.append(ind)

def evaluation(self):
'''
评估环境适应性得分
'''
for i in range(0, self.sizepop):
self.population[i].calculateFitness()
self.fitness[i] = self.population[i].fitness
if self.population[i].fitness > self.population[i].bestFitness:
self.population[i].bestFitness = self.population[i].fitness
self.population[i].bestIndex = copy.deepcopy(
self.population[i].chrom)

def update(self):
'''
更新粒子群
'''
for i in range(0, self.sizepop):
self.population[i].velocity = self.params[0] * self.population[i].velocity + self.params[1] * np.random.random(self.vardim) * (self.population[i].bestPosition - self.population[i].chrom) + self.params[2] * np.random.random(self.vardim) * (self.best.chrom - self.population[i].chrom)
self.population[i].chrom = self.population[i].chrom + self.population[i].velocity

def printResult(self):
'''
绘制粒子群算法优化结果
'''
x = np.arange(0, self.MAXGEN)
y1 = self.history[:, 0]
y2 = self.history[:, 1]
plt.plot(x, y1, 'r', label='optimal value')
plt.plot(x, y2, 'g', label='average value')
plt.xlabel("Iteration")
plt.ylabel("function value")
plt.title("Particle Swarm Optimization algorithm for function optimization")
plt.legend()
plt.show()

def main(self):
'''
主流程:粒子群优化过程
'''
# 迭代次数
self.t = 0
# 种群初始化
self.initialize()
# 评估适应性得分
self.evaluation()
# 评估迭代结果
best = np.max(self.fitness)
bestIndex = np.argmax(self.fitness)
self.best = copy.deepcopy(self.population[bestIndex])
self.avefitness = np.mean(self.fitness)
# 记录迭代历史
self.history[self.t, 0] = (1 - self.best.fitness) / self.best.fitness
self.history[self.t, 1] = (1 - self.avefitness) / self.avefitness
print("Generation %d: optimal function value is: %f; average function value is %f" % (self.t, self.history[self.t, 0], self.history[self.t, 1]))
while self.t < self.MAXGEN - 1:
self.t += 1
# 粒子群更新
self.update()
# 评估适应性得分
self.evaluation()
best = np.max(self.fitness)
bestIndex = np.argmax(self.fitness)
if best > self.best.fitness:
self.best = copy.deepcopy(self.population[bestIndex])
self.avefitness = np.mean(self.fitness)
# 记录演化结果
self.history[self.t, 0] = (1 - self.best.fitness) / self.best.fitness # 最优
self.history[self.t, 1] = (1 - self.avefitness) / self.avefitness # 平均
print("Generation %d: optimal function value is: %f; average function value is %f" % (self.t, self.history[self.t, 0], self.history[self.t, 1]))

# 打印最优结果
print("Optimal function value is: %f; " % self.history[self.t, 0])
# 打印最优粒子性质
print("Optimal solution is:")
print(self.best.chrom)
# 绘制历史
self.printResult()

if __name__ == "__main__":
bound = np.tile([[-600], [600]], 25)
pso = PSO(60, 25, bound, 1000, [0.7298, 1.4962, 1.4962])
pso.main()
0%