人工蜂群（ABC）算法的群體智能優(yōu)化問題方法（Python完整實現(xiàn)）

虎牙變大貓 2018-06-01

展開全文

人工蜂群（ABC）算法的群體智能優(yōu)化問題方法（Python完整實現(xiàn)）

這些算法已被證明在解決實際問題方面非常有效。一些可以使用SI算法解決的任務(wù)是聚類，行星映射，控制納米機器人和數(shù)據(jù)挖掘中的各種問題，如特征選擇和分類。

在數(shù)學(xué)上講，要使用計算智能算法解決現(xiàn)實世界中的優(yōu)化問題，我們需要一個數(shù)學(xué)表示我們的問題，這種表示稱為目標(biāo)函數(shù)，它是描述問題和所有決策變量的數(shù)學(xué)規(guī)則。

簡而言之，優(yōu)化問題由搜索空間定義，搜索空間是我們將尋找解決方案的區(qū)域，一組決策變量，其中包含影響我們問題的所有參數(shù)，當(dāng)然還有目標(biāo)函數(shù)，其中的數(shù)學(xué)規(guī)則這個問題也給了我們一個候選解決方案的良好測量。

優(yōu)化問題的目標(biāo)是從所有可行的解決方案中找到最佳解決方案。這通常意味著我們想要最小化或最大化目標(biāo)函數(shù)。換句話說，我們希望找到最小化我們的目標(biāo)函數(shù)值（也稱為適應(yīng)值）的輸入決策變量集合。

人工蜂群算法

人工蜜蜂群體(ABC)算法是一種模擬蜜蜂群體行為的優(yōu)化算法，并于2005年首次提出由Karaboga提出進(jìn)行實參優(yōu)化。

在這個數(shù)學(xué)模型中，我們的蜜蜂群體由三種蜜蜂組成:工蜂，它們將在特定食物來源的蜂箱上工作。圍觀的蜜蜂會在員工身上進(jìn)行巡邏，以驗證某一特定食物來源是否物有所值，而偵察蜂則會尋找新的食物來源。

在ABC算法中，食物源被定義為搜索空間中的一個位置(優(yōu)化問題的候選解決方案)，最初的食物源數(shù)等于蜂巢上的蜜蜂數(shù)量。食物來源的質(zhì)量是由該位置的目標(biāo)函數(shù)值(適應(yīng)值)來定義的。

來自蜜蜂的新興智能行為可以概括為幾個步驟：

蜜蜂開始隨機探索尋找良好食物來源的環(huán)境（fitness value）。
找到食物來源后，蜜蜂成為員工蜜蜂，并開始在發(fā)現(xiàn)的來源提取食物。
員工蜜蜂用花蜜返回蜂巢并卸載花蜜。卸下花蜜后，她可以直接返回她發(fā)現(xiàn)的來源地點，或者通過在舞池上跳舞來分享她的來源地點的信息。
如果食物來源枯竭，員工蜜蜂就會成為一名偵察員并開始隨機搜索新的食物來源。
旁觀者蜜蜂在蜂巢內(nèi)等待觀察雇員蜜蜂的食物來源收集，并從更有利可圖的來源中選擇一個來源。
食物來源的選擇與來源的質(zhì)量（適應(yīng)值）成正比。

盡管我們描述了三種類型的蜜蜂，但在實施層面，我們意識到只有兩種類型，即員工和旁觀者。偵察蜂實際上是一種可以由員工和旁觀者蜜蜂執(zhí)行的探索行為。

在本文中，我們將使用Python，因為它在數(shù)值計算中越來越顯示出高效性，并且更容易實現(xiàn)一組客觀基準(zhǔn)以重用我們的群智能算法。

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./en/master/)。

人造蜂

為了開始我們的算法的開發(fā)，我們必須找到一種方法在python代碼上表示我們的Bee代理。任何蜜蜂都需要有三個主要的通用功能。第一個是由于探索行為，一只蜜蜂離開我們的決策邊界，它需要有能力返回蜂巢。第二個是能夠更新蜜蜂工作的實際食物來源的狀態(tài)，并評估新鄰里地區(qū)是否是更好的食物來源。最后一個意識到何時食物來源枯竭，現(xiàn)在蜜蜂必須尋找一些新的食物來源。

考慮到這一點，我們可以在python中實現(xiàn)類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]="">
return pos
def update_bee(self, pos, fitness):
if 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

員工蜜蜂

員工蜜蜂的主要行為是從員工正在工作的食物來源中提取食物。在實施層面，這種行為可以被看作是靠近員工蜜蜂的位置產(chǎn)生一個新的位置，并評估這個新位置是否有更多的食物。員工蜜蜂總是會記住迄今為止取得的最佳食物來源地位，直到它耗盡為止。

該EmployeeBee類可以實現(xiàn)如下：

class EmployeeBee(ArtificialBee):
def explore(self, max_trials):
if self.trial <=>
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

旁觀者蜜蜂

旁觀者蜜蜂將巡視員工蜜蜂的工作。會飛過蜂房，檢查他們工作的進(jìn)展情況，并評估哪些員工在收集食物方面更加成功。

旁觀者的蜜蜂總是以最優(yōu)秀的員工為目標(biāo)，采用概率方法作為“交匯點”，其他蜜蜂應(yīng)該來到這個成功的位置，希望能提取更多的食物。

在實施層面上，旁觀者蜜蜂將通過最優(yōu)秀的員工進(jìn)行調(diào)查并嘗試改善食物來源。經(jīng)過特定次數(shù)的試驗后，旁觀者蜜蜂會告訴蜂房這種食物來源已耗盡，必須丟棄。

該OnlookerBee類可以實現(xiàn)如下：

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 <=>
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 <=>
self.pos = n_pos
self.fitness = n_fitness
self.trial = 0
else:
self.trial += 1

完全人工蜂群算法

在實現(xiàn)將要使用的主要類型的代理之后，它有時間用一些python代碼實際實現(xiàn)前面描述的所有步驟。

注意我們已經(jīng)在分離的方法中實現(xiàn)了我們算法的每一步。首先我們重置我們的ABC算法的內(nèi)部參數(shù)，并將我們的員工蜜蜂和旁觀者蜜蜂初始化為隨機位置。一個在現(xiàn)實世界問題中取得成功的默認(rèn)策略是將整個蜂房的一半初始化為員工蜜蜂，而將另一半初始化為旁觀者蜜蜂。

之后，我們開始派員工蜜蜂在他們各自的最初食物來源收集食物，并且總是在周圍尋找更好的食物。一旦員工蜜蜂階段完成，我們會派出旁觀者蜜蜂來巡視他們的工作，并評估每種食物來源的食物提取效果。最后，是時候檢查一些食物來源是否已經(jīng)耗盡，此時無論是員工還是旁觀者都可以成為偵察蜂，并開始尋找新食物來源的探索過程。

完整的ABC算法可以實現(xiàn)如下：

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 = 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))

Bechmark功能測試

SI算法優(yōu)于經(jīng)典和基于梯度的方法的優(yōu)點是能夠在非可微函數(shù)和多模函數(shù)上表現(xiàn)得非常好。

就優(yōu)化問題而言，有幾個眾所周知的基準(zhǔn)函數(shù)用于評估優(yōu)化算法的性能。其中一些函數(shù)在我們的objective_function.py上實現(xiàn)，其公式如下所示。

人工蜂群（ABC）算法的群體智能優(yōu)化問題方法（Python完整實現(xiàn)）

用于測量優(yōu)化算法性能的一些對象函數(shù)列表

為了測試我們的框架并檢查我們的ABC算法是否按預(yù)期行事，我們可以實現(xiàn)以下測試代碼并繪制迭代中的適應(yīng)值，并評估最小化過程對每個函數(shù)的執(zhí)行情況。

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()