【数值优化】启发搜索之群体智能(5)-- 人工鱼群

人工鱼群算法(Artificial Fish-Swarm Algorithm,AFS)为山东大学副教授李晓磊2002年从鱼找寻食物的现象中表现的种种移动寻觅特点中得到启发而阐述的群智能优化算法。在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方,人工鱼群算法就是根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群、追尾及随机行为,从而实现寻优。

人工鱼群算法过程

1、人工鱼的四种典型行为

(1)觅食行为
这是鱼趋向食物的一种活动,一般认为它是通过视觉或味觉来感知水中的食物量或食物浓度来选择行动的方向。设置人工鱼当前状态,并在其感知范围内随机选择另一个状态,如果得到的状态的目标函数大于当前的状态,则向新选择得到的状态靠近一步,反之,重新选取新状态,判断是否满足条件,选择次数达到一定数量后,如果仍然不满足条件,则随机移动一步。
(2)聚群行为
大量或少量的鱼聚集成群,进行集体觅食和躲避敌害,这是它们在进化过程中形成的一种生存方式。人工鱼探索当前邻居内的伙伴数量,并计算伙伴的中心位置,然后把新得到的中心位置的目标函数与当前位置的目标函数相比较,如果中心位置的目标函数优于当前位置的目标函数并且不是很拥挤,则当前位置向中心位置移动一步,否则执行觅食行为。鱼聚群时会遵守两条规则:一是尽量向邻近伙伴的中心移动,二是避免过分拥挤。
(3)追尾行为
当某一条鱼或几条鱼发现食物时,它们附近的鱼会尾随而来,导致更远处的鱼也会尾随过来。人工鱼探索周围邻居鱼的最优位置,当最优位置的目标函数值大于当前位置的目标函数值并且不是很拥挤,则当前位置向最优邻居鱼移动一步,否则执行觅食行为。
(4)随机行为
它是觅食行为的一个缺省行为,指人工鱼在视野内随机移动。当发现食物时,会向食物逐渐增多的方向快速的移动。

2、行为选择

公告牌是记录最优人工鱼个体状态的地方。每条人工鱼在执行完一次迭代后将自身当前状态与公告牌中记录的状态进行比较,如果优于公告牌中的状态则用自身状态更新公告牌中的状态,否则公告牌的状态不变。当整个算法的迭代结束后,公告牌的值就是最优解。
行为评价是用来反映鱼自主行为的一种方式,在解决优化问题时选用两种方式评价:一种是选择最优行为执行;另一种是选择较优方向。对于解决极大值问题,可以使用试探法,即模拟执行群聚、追尾等行为,然后评价行动后的值选择最优的来执行,缺省的行为为觅食行为。
一般通过试探法,模拟执行上述几种行为,评价后选择最大者实行。

3、迭代终止条件

通常的方法是判断连续多次所得值得均方差小鱼允许的误差;或判断聚集于某个区域的人工鱼的数目达到某个比例;或连续多次所得的均值不超过已寻找的极值;或限制最大迭代次数。若满足终止条件,则输出公告牌的最优记录;否则继续迭代。

4、迭代步骤

STEP1: 初始化设置,包括种群规模N、每条人工鱼的初始位置、人工鱼的视野Visual、步长step、拥挤度因子δ、重复次数Trynumber。
STEP2: 计算初始鱼群各个体的适应值,取最优人工鱼状态及其值赋予给公告牌。
STEP3: 对每个个体进行评价,对其要执行的行为进行选择,包括觅食Pray、聚群Swarm、追尾Follow和评价行为bulletin。
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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
import numpy as np
import random
import copy
import matplotlib.pyplot as plt
import math

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

class AFSIndividual:
'''
模拟人工鱼个体
'''
def __init__(self, vardim, bound):
'''
个体初始化
vardim: 变量维数
bound: 变量取值范围
'''
self.vardim = vardim
self.bound = bound

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 AFS:
'''
人工鱼群算法
'''
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)) # 演化历史
self.lennorm = 6000

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

def evaluation(self, x):
'''
迭代
'''
x.calculateFitness()

def forage(self, x):
'''
觅食行为
'''
newInd = copy.deepcopy(x)
found = False
for i in range(0, self.params[3]):
indi = self.randSearch(x, self.params[0])
if indi.fitness > x.fitness:
newInd.chrom = x.chrom + np.random.random(self.vardim) * self.params[1] * self.lennorm * (
indi.chrom - x.chrom) / np.linalg.norm(indi.chrom - x.chrom)
newInd = indi
found = True
break
if not (found):
newInd = self.randSearch(x, self.params[1])
return newInd

def randSearch(self, x, searLen):
'''
随机行为
'''
ind = copy.deepcopy(x)
ind.chrom += np.random.uniform(-1, 1, self.vardim) * searLen * self.lennorm
for j in range(0, self.vardim):
if ind.chrom[j] < self.bound[0, j]:
ind.chrom[j] = self.bound[0, j]
if ind.chrom[j] > self.bound[1, j]:
ind.chrom[j] = self.bound[1, j]
self.evaluation(ind)
return ind

def huddle(self, x):
'''
聚群行为
'''
newInd = copy.deepcopy(x)
dist = self.distance(x)
index = []
for i in range(1, self.sizepop):
if dist[i] > 0 and dist[i] < self.params[0] * self.lennorm:
index.append(i)
nf = len(index)
if nf > 0:
xc = np.zeros(self.vardim)
for i in range(0, nf):
xc += self.population[index[i]].chrom
xc = xc / nf
cind = AFSIndividual(self.vardim, self.bound)
cind.chrom = xc
cind.calculateFitness()
if (cind.fitness / nf) > (self.params[2] * x.fitness):
xnext = x.chrom + np.random.random(self.vardim) * self.params[1] * self.lennorm * (xc - x.chrom) / np.linalg.norm(xc - x.chrom)
for j in range(0, self.vardim):
if xnext[j] < self.bound[0, j]:
xnext[j] = self.bound[0, j]
if xnext[j] > self.bound[1, j]:
xnext[j] = self.bound[1, j]
newInd.chrom = xnext
self.evaluation(newInd)
return newInd
else:
return self.forage(x)
else:
return self.forage(x)

def follow(self, x):
'''
追尾行为
'''
newInd = copy.deepcopy(x)
dist = self.distance(x)
index = []
for i in range(1, self.sizepop):
if dist[i] > 0 and dist[i] < self.params[0] * self.lennorm:
index.append(i)
nf = len(index)
if nf > 0:
best = -999999999.
bestIndex = 0
for i in range(0, nf):
if self.population[index[i]].fitness > best:
best = self.population[index[i]].fitness
bestIndex = index[i]
if (self.population[bestIndex].fitness / nf) > (self.params[2] * x.fitness):
xnext = x.chrom + np.random.random(self.vardim) * self.params[1] * self.lennorm * (self.population[bestIndex].chrom - x.chrom) / np.linalg.norm(self.population[bestIndex].chrom - x.chrom)
for j in range(0, self.vardim):
if xnext[j] < self.bound[0, j]:
xnext[j] = self.bound[0, j]
if xnext[j] > self.bound[1, j]:
xnext[j] = self.bound[1, j]
newInd.chrom = xnext
self.evaluation(newInd)
return newInd
else:
return self.forage(x)
else:
return self.forage(x)

def distance(self, x):
'''
计算到目标个体的距离
'''
dist = np.zeros(self.sizepop)
for i in range(0, self.sizepop):
dist[i] = np.linalg.norm(x.chrom - self.population[i].chrom) / 6000
return dist

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("Artificial Fish Swarm algorithm for function optimization")
plt.legend()
plt.show()

def main(self):
'''
主流程
'''
self.t = 0
self.initialize()
for i in range(0, self.sizepop):
self.evaluation(self.population[i])
self.fitness[i] = self.population[i].fitness
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
for i in range(0, self.sizepop):
xi1 = self.huddle(self.population[i])
xi2 = self.follow(self.population[i])
if xi1.fitness > xi2.fitness:
self.population[i] = xi1
self.fitness[i] = xi1.fitness
else:
self.population[i] = xi2
self.fitness[i] = xi2.fitness
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)
afs = AFS(60, 25, bound, 500, [0.001, 0.0001, 0.618, 40])
afs.main()
0%