【数值优化】启发搜索之群体智能（6）-- 人工蜂群

更新于
人工蜂群算法（Artificial Bee Colony Algorithm，ABC）是一种模仿蜜蜂采蜜机理而产生的群智能优化算法。

人工蜂群算法（Artificial Bee Colony Algorithm，ABC）是一种模仿蜜蜂采蜜机理而产生的群智能优化算法。该算法具有简单和鲁棒性强的特点，在非限制性数值优化函数上比常见的启发式算法具有更加优越的性能，在许多领域中都有研究和应用。

人工蜂群算法过程

1、生物学机理

一般情况下，大多数的工蜂都留在蜂巢内值”内勤”，只有少数作为”侦查员”四处寻找蜜源。一旦发现了有利的采蜜地点或新的优质蜜源植物，就会变成采蜜蜂飞回蜂巢并用圆舞或摇摆舞告知其他蜜蜂。
圆舞或摇摆舞是蜜蜂之间进行信息交流的基本形式，传达了有关蜂巢周围蜜源的重要信息（例如蜜源方向及离巢距离等）
研究表明，如果侦查蜂找到的蜜源在距离蜂巢100米以内时，一般以圆舞方式爬行，即在蜂巢上交替地向左或向右转着小圆圈。
如果超过100米，则改变舞姿，先左右摆动腹部，沿直线蹒跚地爬行一小段距离，然后往一边兜半个圆圈，再回到起点，继续摆动腹部沿直线蹒跚地爬行一小段距离，再向右边兜半个圆圈，呈∞字，故称8字舞或摆尾舞。
在一定时间内，蜜蜂跳摆尾舞数量的多少，表示蜂巢到蜜源距离的远近；蜜蜂头部的位置反映了蜜源的位置；附在身上的花粉味道告知了蜜源的种类。
巢中的工蜂可以通过”侦查员”的舞蹈来判别蜜源的方向和距离，以及蜜源的质量。当舞蹈结束后，这些侦查员就与巢中的一些同伴一起飞回原先找到的蜜源进行采蜜。如果采集后，该蜜源质量仍然很高，他们会回到蜂巢继续通过舞蹈招募更多的同伴去采蜜。跟随采蜜的蜜蜂数量取决于蜜源质量。以这种方式，蜂群就能快速有效地找到高质量的蜜源。
由此可见，蜜蜂采蜜的群体智能行为是通过不同角色之间交流、转换及写作来实现的。

2、人工蜂的三种角色

标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类: 引领蜂、跟随蜂和侦察蜂。
引领蜂：也称为雇佣蜂。在对应食物源上采蜜，并通过跳摇摆舞将食物源信息分享给跟随蜂。
跟随蜂：在巢内等待，通过观察采蜜归来的引领蜂的摇摆舞信息选择优秀食物源进行跟随。
侦查蜂：当某食物源的食物浓度连续limit次未被更新，表面该食物源陷入局部最优，应被放弃，与之对应的引领蜂称为侦查蜂，开始寻找新的食物源。

3、人工蜂群的三种行为模式

人工蜂群算法定义了三种行为模式：搜索食物源，为食物源招募蜜蜂和放弃食物源。招募行为形成算法正反馈，而放弃行为导致负反馈。
初始时刻，种群由引领蜂和跟随蜂组成，引领蜂与跟随蜂数量相同，都等于食物源数量。引领蜂首先飞出蜂巢，在对应食物源周围进行邻域搜索，并利用贪婪原则进行选择。
回到蜂巢后，引领蜂将食物源信息通过跳摇摆舞的形式传递给跟随蜂，跟随蜂观察引领蜂的食物源信息，选择优秀的食物源进行跟随，并再次在其附近进行邻域搜索和贪婪选择。
若跟随蜂搜索新食物源的食物浓度大于原引领蜂的旧食物源时，新食物源替换旧食物源，同时完成角色互换；反之，保持不变。
当某个食物源的食物浓度连续limit次未被更新，该食物源应被放弃，与之对应的引领蜂变为侦查蜂，随机寻找新食物源，找到新食物源后，侦查蜂又变为引领蜂，因此，侦查蜂是一种临时角色，其数量应为1。
人工蜂群算法就是通过不断地角色转换和执行行为模式，最终找到最丰富食物源。在ABC算法中，引领蜂有保持优良食物源的作用，具有精英特性；跟随蜂增加较好食物源对应的蜜蜂数，加快算法的收敛；侦查蜂随机搜索新食物源，帮助算法跳出局部最优。

4、迭代步骤

STEP1： 种群初始化。
STEP2： 重复以下过程：

  • 将引领蜂与蜜源一一对应，更新蜜源信息
  • 跟随蜂根据引领蜂所提供的信息采用一定的选择策略选择蜜源，更新蜜源信息
  • 确定侦查蜂，寻找新的蜜源
  • 记忆迄今为止最好的蜜源

STEP3： 判断终止条件是否成立。

人工蜂群算法的代码实现

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
import numpy as np
import random
import copy
import matplotlib.pyplot as plt
import math

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

class ABCIndividual:
    '''
    模拟蜜蜂个体
    '''
    def __init__(self,  vardim, bound):
        '''
        个体初始化
        vardim: 变量维数
        bound: 变量取值范围
        '''
        self.vardim = vardim
        self.bound = bound
        self.fitness = 0.
        self.trials = 0.

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

    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 ABC:
    '''
    人工蜂群算法
    '''
    def __init__(self, sizepop, vardim, bound, MAXGEN, params):
        '''
        sizepop: 种群规模
        vardim: 变量维数
        bound: 变量取值范围
        MAXGEN: 最大迭代次数(终止条件)
        param: 其他参数(列表)
        '''
        self.sizepop = sizepop
        self.vardim = vardim
        self.bound = bound
        self.foodSource = int(self.sizepop / 2)
        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.foodSource):
            ind = ABSIndividual(self.vardim, self.bound)
            ind.generate()
            self.population.append(ind)

    def evaluation(self):
        '''
        迭代
        '''
        for i in range(0, self.foodSource):
            self.population[i].calculateFitness()
            self.fitness[i] = self.population[i].fitness

    def employedBeePhase(self):
        '''
        引领蜂
        '''
        for i in range(0, self.foodSource):
            k = np.random.random_integers(0, self.vardim - 1)
            j = np.random.random_integers(0, self.foodSource - 1)
            while j == i:
                j = np.random.random_integers(0, self.foodSource - 1)
            vi = copy.deepcopy(self.population[i])
            vi.chrom[k] += np.random.uniform(low=-1, high=1.0, size=1) * (vi.chrom[k] - self.population[j].chrom[k])
            if vi.chrom[k] < self.bound[0, k]:
                vi.chrom[k] = self.bound[0, k]
            if vi.chrom[k] > self.bound[1, k]:
                vi.chrom[k] = self.bound[1, k]
            vi.calculateFitness()
            if vi.fitness > self.fitness[i]:
                self.population[i] = vi
                self.fitness[i] = vi.fitness
                if vi.fitness > self.best.fitness:
                    self.best = vi
            vi.calculateFitness()
            if vi.fitness > self.fitness[i]:
                self.population[i] = vi
                self.fitness[i] = vi.fitness
                if vi.fitness > self.best.fitness:
                    self.best = vi
            else:
                self.population[i].trials += 1

    def onlookerBeePhase(self):
        '''
        跟随蜂
        '''
        accuFitness = np.zeros((self.foodSource, 1))
        maxFitness = np.max(self.fitness)

        for i in range(0, self.foodSource):
            accuFitness[i] = 0.9 * self.fitness[i] / maxFitness + 0.1

        for i in range(0, self.foodSource):
            for fi in range(0, self.foodSource):
                r = random.random()
                if r < accuFitness[i]:
                    k = np.random.random_integers(0, self.vardim - 1)
                    j = np.random.random_integers(0, self.foodSource - 1)
                    while j == fi:
                        j = np.random.random_integers(0, self.foodSource - 1)
                    vi = copy.deepcopy(self.population[i])
                    vi.chrom[k] += np.random.uniform(low=-1, high=1.0, size=1) * (vi.chrom[k] - self.population[j].chrom[k])
                    if vi.chrom[k] < self.bound[0, k]:
                        vi.chrom[k] = self.bound[0, k]
                    if vi.chrom[k] > self.bound[1, k]:
                        vi.chrom[k] = self.bound[1, k]
                    vi.calculateFitness()
                    if vi.fitness > self.fitness[i]:
                        self.population[i] = vi
                        self.fitness[i] = vi.fitness
                        if vi.fitness > self.best.fitness:
                            self.best = vi
                    else:
                        self.population[i].trials += 1
                    break

    def scoutBeePhase(self):
        '''
        侦查蜂
        '''
        for i in range(0, self.foodSource):
            if self.population[i].trials > self.params[0]:
                self.population[i].generate()
                self.population[i].trials = 0
                self.population[i].calculateFitness()
                self.fitness[i] = self.population[i].fitness

    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 Bee Swarm 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.employedBeePhase()
            self.onlookerBeePhase()
            self.scoutBeePhase()
            # 评估迭代结果
            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)
    abc = ABC(60, 25, bound, 1000, [100,  0.5])
    abc.main()
0%