一文搞懂人工蜂群算法（python）

文摘 2024-06-23 20:21 辽宁

点击上方“进修编程”，选择“星标”公众号

超级无敌干货，第一时间送达！！！

金属质感分割线

今天向大家介绍人工蜂群算法，也是目前较火的算法之一

群体智能(SI) 是计算智能(CI) 的一个子领域，涉及仿生多智能体智能系统的开发。SI 以鸟群和鱼群等自然智能体的集体行为为灵感，创建了这些算法。

这些算法已被证明在解决实际问题方面非常有效。可以使用 SI 算法解决的一些任务包括聚类、行星测绘、控制纳米机器人以及数据挖掘中的各种问题，例如特征选择和分类。

从数学上来说，要使用计算智能算法解决现实世界的优化问题，我们需要问题的数学表示，这种表示称为目标函数，它是描述问题及其所有决策变量的数学规则。

简而言之，优化问题由搜索空间定义，搜索空间是我们寻找解决方案的区域，它是一组决策变量，其中包括影响我们问题的所有参数，当然还有目标函数，它是问题的数学规则，也为我们提供候选解决方案的优度测量。

优化问题的目标是从所有可行解中找到最佳解。这通常意味着我们想要最小化或最大化目标函数。换句话说，我们想要找到一组输入决策变量，使目标函数的值最小化或最大化，也称为适应度值。

人工蜂群算法

人工蜂群（ABC）算法是一种模拟蜂群行为的优化算法，由Karaboga于2005年首次提出，用于实参数优化。

在这个数学模型中，我们的蜂群由三种类型的蜜蜂组成：雇员蜂，负责在特定食物源处收集食物。观察蜂，负责巡逻雇员蜂，以确认特定食物源是否不再有价值；侦察蜂，负责寻找新的食物源位置。

在ABC算法中，食物源被定义为搜索空间中的一个位置（优化问题的候选解决方案），最初食物源的数量等于蜂巢中的蜜蜂数量。食物源的质量由该位置上的目标函数值（适应度值）定义。

蜜蜂新出现的智能行为可以概括为以下几个步骤：

蜜蜂开始随机探索环境寻找良好的食物来源（适应度值）。
找到食物源后，蜜蜂就变成雇员蜂，开始在发现的来源处提取食物。
工蜂带着花蜜返回蜂巢并卸下花蜜。卸下花蜜后，她可以直接返回她发现的来源地，或者通过在舞蹈区跳舞来分享关于她的来源地的信息。
如果食物源耗尽，员工蜂就会变成侦察蜂，开始随机寻找新的食物源。
在蜂巢中等待的旁观蜜蜂观察雇员蜜蜂收集食物来源，并从更有利可图的来源中选择一个来源。

食物来源的选择与来源的质量（适应度值）成正比。

尽管我们描述了三种类型的蜜蜂，但在实施层面，我们意识到只有两种类型：雇员蜜蜂和旁观者蜜蜂。侦察蜂实际上是一种探索行为，雇员蜜蜂和旁观者蜜蜂都可以执行。

在本文中，我将使用 Python给大家演示

import numpy as np
from scipy import optimizefrom deap.benchmarks import schwefel
from abc import ABCMetafrom abc import abstractmethodfrom six import add_metaclass

@add_metaclass(ABCMeta)class ObjectiveFunction(object):
    def __init__(self, name, dim, minf, maxf):        self.name = name        self.dim = dim        self.minf = minf        self.maxf = maxf
    def sample(self):        return np.random.uniform(low=self.minf, high=self.maxf, size=self.dim)
    def custom_sample(self):        return np.repeat(self.minf, repeats=self.dim) \               + np.random.uniform(low=0, high=1, size=self.dim) *\               np.repeat(self.maxf - self.minf, repeats=self.dim)
    @abstractmethod    def evaluate(self, x):        pass

class Sphere(ObjectiveFunction):
    def __init__(self, dim):        super(Sphere, self).__init__('Sphere', dim, -100.0, 100.0)
    def evaluate(self, x):        return sum(np.power(x, 2))

class Rosenbrock(ObjectiveFunction):
    def __init__(self, dim):        super(Rosenbrock, self).__init__('Rosenbrock', dim, -30.0, 30.0)
    def evaluate(self, x):        return optimize.rosen(x)

class Rastrigin(ObjectiveFunction):
    def __init__(self, dim):        super(Rastrigin, self).__init__('Rastrigin', dim, -5.12, 5.12)
    def evaluate(self, x):        return 10 * len(x)\               + np.sum(np.power(x, 2) - 10 * np.cos(2 * np.pi * np.array(x)))

class Schwefel(ObjectiveFunction):
    def __init__(self, dim):        super(Schwefel, self).__init__('Schwefel', dim, -500.0, 500.0)
    def evaluate(self, x):        return schwefel(x)[0]

人工蜜蜂

要开始开发我们的算法，我们必须找到一种方法来在 Python 代码上表示我们的蜜蜂代理。任何蜜蜂都需要具备三个主要的通用功能。第一个是当蜜蜂由于探索行为而移出我们的决策边界时，它需要能够返回蜂巢。第二个是能够更新蜜蜂正在工作的实际食物源的状态并评估新的邻近区域是否是更好的食物源。最后一个是当食物源耗尽时，蜜蜂必须寻找一些新的食物源。

考虑到这一点，我们可以用 Python 实现ArtificialBee类，如下所示：

import numpy as np
from copy import deepcopyfrom abc import ABCMetafrom six import add_metaclass

@add_metaclass(ABCMeta)class ArtificialBee(object):
    TRIAL_INITIAL_DEFAULT_VALUE = 0    INITIAL_DEFAULT_PROBABILITY = 0.0
    def __init__(self, obj_function):        self.pos = obj_function.custom_sample()        self.obj_function = obj_function        self.minf = obj_function.minf        self.maxf = obj_function.maxf        self.fitness = obj_function.evaluate(self.pos)        self.trial = ArtificialBee.TRIAL_INITIAL_DEFAULT_VALUE        self.prob = ArtificialBee.INITIAL_DEFAULT_PROBABILITY
    def evaluate_boundaries(self, pos):        if (pos < self.minf).any() or (pos > self.maxf).any():            pos[pos > self.maxf] = self.maxf            pos[pos < self.minf] = self.minf        return pos
    def update_bee(self, pos, fitness):        if fitness <= self.fitness:            self.pos = pos            self.fitness = fitness            self.trial = 0        else:            self.trial += 1
    def reset_bee(self, max_trials):        if self.trial >= max_trials:            self.__reset_bee()
    def __reset_bee(self):        self.pos = self.obj_function.custom_sample()        self.fitness = self.obj_function.evaluate(self.pos)        self.trial = ArtificialBee.TRIAL_INITIAL_DEFAULT_VALUE        self.prob = ArtificialBee.INITIAL_DEFAULT_PROBABILITY

员工蜜蜂

工蜂的主要行为是从工蜂正在工作的食物源中提取食物，当食物源耗尽时，工蜂会从食物源中提取食物。在实现层面，这种行为可以看作是在工蜂所在位置附近生成一个新位置，并评估这个新位置是否有更好的食物量。工蜂会一直记住迄今为止获得的最佳食物源位置，直到耗尽为止。

EmployeeBee类可以按如下方式实现：

class EmployeeBee(ArtificialBee):
    def explore(self, max_trials):        if self.trial <= max_trials:            component = np.random.choice(self.pos)            phi = np.random.uniform(low=-1, high=1, size=len(self.pos))            n_pos = self.pos + (self.pos - component) * phi            n_pos = self.evaluate_boundaries(n_pos)            n_fitness = self.obj_function.evaluate(n_pos)            self.update_bee(n_pos, n_fitness)
    def get_fitness(self):        return 1 / (1 + self.fitness) if self.fitness >= 0 else 1 + np.abs(self.fitness)
    def compute_prob(self, max_fitness):        self.prob = self.get_fitness() / max_fitness

旁观者蜜蜂

巡视蜂会巡视工蜂的工作。它们会飞过蜂巢检查工蜂的工作进度，并评估哪些工蜂在采集食物方面更成功。

旁观蜜蜂总是会用概率方法瞄准最好的员工作为“会面点”，其他蜜蜂应该来到这个成功的位置，希望提取更多的食物。

在执行层面，旁观蜂会筛选出最优秀的员工，并尝试改善该食物来源。经过一定次数的尝试后，旁观蜂会告诉蜂巢，该食物来源已耗尽，必须丢弃。

OnlookerBee类可以按如下方式实现：

class OnLookerBee(ArtificialBee):
    def onlook(self, best_food_sources, max_trials):        candidate = np.random.choice(best_food_sources)        self.__exploit(candidate.pos, candidate.fitness, max_trials)
    def __exploit(self, candidate, fitness, max_trials):        if self.trial <= max_trials:            component = np.random.choice(candidate)            phi = np.random.uniform(low=-1, high=1, size=len(candidate))            n_pos = candidate + (candidate - component) * phi            n_pos = self.evaluate_boundaries(n_pos)            n_fitness = self.obj_function.evaluate(n_pos)
            if n_fitness <= fitness:                self.pos = n_pos                self.fitness = n_fitness                self.trial = 0            else:                self.trial += 1

完整的人工蜂群算法

在实现了将要使用的代理的主要类型之后，就该使用一些 Python 代码来实际实现前面描述的所有步骤了。

请注意，我们已使用不同的方法实现了算法的每个步骤。首先，我们重置 ABC 算法的内部参数，并在随机位置初始化我们的雇员蜂和旁观蜂。在实际问题中非常成功的默认策略是将整个蜂巢的一半初始化为雇员蜂，另一半初始化为旁观蜂。

之后，我们开始派遣工蜂到各自的初始食物源收集食物，并始终在食物源周围寻找更好的食物点。工蜂阶段结束后，我们派遣观察蜂巡视工作并评估每个食物源的食物提取情况。最后，是时候检查某个食物源是否已经耗尽了，此时工蜂或观察蜂都可以成为侦察蜂，并开始寻找新食物源的探索过程。

完整的ABC算法可以实现如下：

class ABC(object):
    def __init__(self, obj_function, colony_size=30, n_iter=5000, max_trials=100):        self.colony_size = colony_size        self.obj_function = obj_function
        self.n_iter = n_iter        self.max_trials = max_trials
        self.optimal_solution = None        self.optimality_tracking = []
    def __reset_algorithm(self):        self.optimal_solution = None        self.optimality_tracking = []
    def __update_optimality_tracking(self):        self.optimality_tracking.append(self.optimal_solution.fitness)
    def __update_optimal_solution(self):        n_optimal_solution = \            min(self.onlokeer_bees + self.employee_bees,                key=lambda bee: bee.fitness)        if not self.optimal_solution:            self.optimal_solution = deepcopy(n_optimal_solution)        else:            if n_optimal_solution.fitness < self.optimal_solution.fitness:                self.optimal_solution = deepcopy(n_optimal_solution)
    def __initialize_employees(self):        self.employee_bees = []        for itr in range(self.colony_size // 2):            self.employee_bees.append(EmployeeBee(self.obj_function))
    def __initialize_onlookers(self):        self.onlokeer_bees = []        for itr in range(self.colony_size // 2):            self.onlokeer_bees.append(OnLookerBee(self.obj_function))
    def __employee_bees_phase(self):        map(lambda bee: bee.explore(self.max_trials), self.employee_bees)
    def __calculate_probabilities(self):        sum_fitness = sum(map(lambda bee: bee.get_fitness(), self.employee_bees))        map(lambda bee: bee.compute_prob(sum_fitness), self.employee_bees)
    def __select_best_food_sources(self):        self.best_food_sources =\            filter(lambda bee: bee.prob > np.random.uniform(low=0, high=1),                   self.employee_bees)        while not self.best_food_sources:            self.best_food_sources = \                filter(lambda bee: bee.prob > np.random.uniform(low=0, high=1),                       self.employee_bees)
    def __onlooker_bees_phase(self):        map(lambda bee: bee.onlook(self.best_food_sources, self.max_trials),            self.onlokeer_bees)
    def __scout_bees_phase(self):        map(lambda bee: bee.reset_bee(self.max_trials),            self.onlokeer_bees + self.employee_bees)
    def optimize(self):        self.__reset_algorithm()        self.__initialize_employees()        self.__initialize_onlookers()        for itr in range(self.n_iter):            self.__employee_bees_phase()            self.__update_optimal_solution()
            self.__calculate_probabilities()            self.__select_best_food_sources()
            self.__onlooker_bees_phase()            self.__scout_bees_phase()
            self.__update_optimal_solution()            self.__update_optimality_tracking()            print("iter: {} = cost: {}"                  .format(itr, "%04.03e" % self.optimal_solution.fitness))

基准函数测试

SI 算法相对于经典方法和基于梯度的方法的优势在于它能够在不可微函数和多峰函数上表现非常出色。

就优化问题而言，有几种众所周知的基准函数可用于评估优化算法的性能。其中一些函数已在我们的 objective_function.py 中实现，其公式如下所列。

一些用作衡量优化算法性能的基准的对象函数列表

为了测试我们的框架并检查我们的 ABC 算法是否按预期运行，我们可以实现以下测试代码并绘制迭代中的适应度值，并评估每个函数的最小化过程的进展情况。

import numpy as npimport matplotlib.pyplot as plt
from algorithm.abc import ABC
from matplotlib.style import use
from objection_function import Rastriginfrom objection_function import Rosenbrockfrom objection_function import Spherefrom objection_function import Schwefel

use('classic')

def get_objective(objective, dimension=30):    objectives = {'Sphere': Sphere(dimension),                  'Rastrigin': Rastrigin(dimension),                  'Rosenbrock': Rosenbrock(dimension),                  'Schwefel': Schwefel(dimension)}    return objectives[objective]

def simulate(obj_function, colony_size=30, n_iter=5000,             max_trials=100, simulations=30):    itr = range(n_iter)    values = np.zeros(n_iter)    box_optimal = []    for _ in range(simulations):        optimizer = ABC(obj_function=get_objective(obj_function),                        colony_size=colony_size, n_iter=n_iter,                        max_trials=max_trials)        optimizer.optimize()        values += np.array(optimizer.optimality_tracking)        box_optimal.append(optimizer.optimal_solution.fitness)        print(optimizer.optimal_solution.pos)    values /= simulations
    plt.plot(itr, values, lw=0.5, label=obj_function)    plt.legend(loc='upper right')

def main():    plt.figure(figsize=(10, 7))    simulate('Rastrigin')    plt.ticklabel_format(axis='y', style='sci', scilimits=(-2, 2))    plt.xticks(rotation=45)    plt.show()

if __name__ == '__main__':    main()

我们可以通过分析每个基准函数的适应度与迭代次数的关系图来检查结果，还可以检查optimizer.optimal_solution.pos的输出，并检查 ABC 是否对我们的基准函数的最佳点获得了非常好的近似值。

看来 ABC 的 Sphere 功能做得很好对于 Rosenbrock 来说，它收敛得如此之快，以至于你几乎看不到图表Rastrigin 函数也表现出色

好了，现在我们知道了 ABC 的工作原理和实现方法，我们可以用它来解决一些有趣的问题，比如聚类和图像分割。我们只需要对算法进行一些细微的更改，就可以了解如何将这些问题转化为优化任务！

本人接python，matlab程序设计欢迎交流

— 完 —

进修编程

提升编程技能，学习编程技巧