群智能(SI)是计算智能(CI)的一个子领域,关注生物启发式多智能体智能系统的发展。SI使用鸟群和鱼群等天然代理的集体行为作为创建这些算法的灵感。
这些算法已被证明在解决实际问题方面非常有效。一些可以使用SI算法解决的任务是聚类,行星映射,控制纳米机器人和数据挖掘中的各种问题,如特征选择和分类。
在数学上讲,要使用计算智能算法解决现实世界中的优化问题,我们需要一个数学表示我们的问题,这种表示称为目标函数,它是描述问题和所有决策变量的数学规则。
简而言之,优化问题由搜索空间定义,搜索空间是我们将寻找解决方案的区域,一组决策变量,其中包含影响我们问题的所有参数,当然还有目标函数,其中的数学规则这个问题也给了我们一个候选解决方案的良好测量。
优化问题的目标是从所有可行的解决方案中找到最佳解决方案。这通常意味着我们想要最小化或最大化目标函数。换句话说,我们希望找到最小化我们的目标函数值(也称为适应值)的输入决策变量集合。
人工蜂群算法
人工蜜蜂群体(ABC)算法是一种模拟蜜蜂群体行为的优化算法,并于2005年首次提出由Karaboga提出进行实参优化。
在这个数学模型中,我们的蜜蜂群体由三种蜜蜂组成:工蜂,它们将在特定食物来源的蜂箱上工作。围观的蜜蜂会在员工身上进行巡逻,以验证某一特定食物来源是否物有所值,而侦察蜂则会寻找新的食物来源。
在ABC算法中,食物源被定义为搜索空间中的一个位置(优化问题的候选解决方案),最初的食物源数等于蜂巢上的蜜蜂数量。食物来源的质量是由该位置的目标函数值(适应值)来定义的。
来自蜜蜂的新兴智能行为可以概括为几个步骤:
- 蜜蜂开始随机探索寻找良好食物来源的环境(fitness value)。
- 找到食物来源后,蜜蜂成为员工蜜蜂,并开始在发现的来源提取食物。
- 员工蜜蜂用花蜜返回蜂巢并卸载花蜜。卸下花蜜后,她可以直接返回她发现的来源地点,或者通过在舞池上跳舞来分享她的来源地点的信息。
- 如果食物来源枯竭,员工蜜蜂就会成为一名侦察员并开始随机搜索新的食物来源。
- 旁观者蜜蜂在蜂巢内等待观察雇员蜜蜂的食物来源收集,并从更有利可图的来源中选择一个来源。
- 食物来源的选择与来源的质量(适应值)成正比。
尽管我们描述了三种类型的蜜蜂,但在实施层面,我们意识到只有两种类型,即员工和旁观者。侦察蜂实际上是一种可以由员工和旁观者蜜蜂执行的探索行为。
在本文中,我们将使用python,因为它在数值计算中越来越显示出高效性,并且更容易实现一组客观基准以重用我们的群智能算法。
import numpy as np
from scipy import optimize
from deap.benchmarks import schwefel
from abc import ABCMeta
from abc import abstractmethod
from 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]
你可以在这里下载deap软件包(https://deap.readthedocs.io/en/master/)。
人造蜂
为了开始我们的算法的开发,我们必须找到一种方法在python代码上表示我们的Bee代理。任何蜜蜂都需要有三个主要的通用功能。第一个是由于探索行为,一只蜜蜂离开我们的决策边界,它需要有能力返回蜂巢。第二个是能够更新蜜蜂工作的实际食物来源的状态,并评估新邻里地区是否是更好的食物来源。最后一个意识到何时食物来源枯竭,现在蜜蜂必须寻找一些新的食物来源。
考虑到这一点,我们可以在python中实现类ArtificialBee,如下所示:
import numpy as np
from copy import deepcopy
from abc import ABCMeta
from 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, \”.03e\” % self.optimal_solution.fitness))
Bechmark功能测试
SI算法优于经典和基于梯度的方法的优点是能够在非可微函数和多模函数上表现得非常好。
就优化问题而言,有几个众所周知的基准函数用于评估优化算法的性能。其中一些函数在我们的objective_function.py上实现,其公式如下所示。
用于测量优化算法性能的一些对象函数列表
为了测试我们的框架并检查我们的ABC算法是否按预期行事,我们可以实现以下测试代码并绘制迭代中的适应值,并评估最小化过程对每个函数的执行情况。
import numpy as np
import matplotlib.pyplot as plt
from algorithm.abc import ABC
from matplotlib.style import use
from objection_function import Rastrigin
from objection_function import Rosenbrock
from objection_function import Sphere
from 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功能也是一个很好的表现
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。