کامپیوتر، هوش مصنوعی ۵۴۲۰ بازدید

«هوش ازدحامی» (Swarm Intelligence – SI)، یک زمینه از «هوش محاسباتی» (Computational Intelligence – CI) است که برای ساخت و توسعه سیستم‌های هوشمند چندعامله الهام گرفته از زیست، استفاده می‌شود. این رویکرد از رفتار تجمعی عامل‌های طبیعی مانند دسته پرندگان و ماهی‌ها برای ساخت الگوریتم‌ها الگوبرداری کرده است.

اثبات شده که چنین الگوریتم‌هایی در حل مسائل جهان واقعی عملکرد بسیار موثری دارند. از جمله مسائلی که با استفاده از الگوریتم‌های هوش ازدحامی قابل حل هستند می‌توان به خوشه‌بندی، نگاشت سیاره‌ای، کنترل نانو ربات‌ها و گستره‌ای از مسائل داده‌کاوی مانند انتخاب ویژگی و دسته‌بندی اشاره کرد.

به بیان ریاضی، برای حل مسائل بهینه‌سازی جهان واقعی با استفاده از الگوریتم‌های محاسباتی هوشمند، نیاز به یک ارائه ریاضی‌وار از مساله وجود دارد که به آن «تابع هدف» (Objective Function) گفته می‌شود. تابع هدف در واقع قواعد ریاضی است که مساله و همه متغیرهای تصمیم آن را تشریح می‌کند.

به‌طور خلاصه، یک مساله بهینه‌سازی در فضای جست و جو تعریف می‌شود. این فضا در واقع ناحیه‌ای است که در آن به‌دنبال راهکار گشته می‌شود و شامل یک مجموعه از متغیرهای تصمیم است که خود حاوی همه پارامترهایی هستند که مساله و به‌ویژه تابع هدف را تحت تاثیر قرار می‌دهند. تابع هدف، با ریاضیات مساله را قاعده‌گذاری کرده و حجم خوبی از راهکارهای کاندید برای آن را ارائه می‌کند.

هدف یک مساله بهینه‌سازی، پیدا کردن بهترین راهکار از میان کلیه راه حل‌های امکان‌پذیر است. این یعنی در مساله بهینه‌سازی هدف یافتن کمینه یا بیشینه برای تابع هدف است. به عبارت دیگر، هدف پیدا کردن یک مجموعه از متغیرهای تصمیم ورودی محسوب می‌شود که برابر با کمینه یا بیشینه مقدار تابع هدف است و به آن «مقدار تناسب» نیز می‌گویند.

الگوریتم کلونی زنبور عسل مصنوعی

الگوریتم کلونی زنبور عسل مصنوعی (ABC)، یک راهکار بهینه‌سازی است که رفتار یک کلونی زنبور عسل را شبیه‌سازی می‌کند و برای اولین بار در سال ۲۰۰۵ توسط «کارابوگا» (Karaboga)، برای بهینه‌سازی پارامتر واقعی ارائه شد.

در این مدل ریاضی، کلونی زنبور عسل مصنوعی دارای سه نوع زنبور است. زنبورهای کارگر روی گردآوری غذا و آوردن آن به کندو از یک منبع غذایی خاص کار می‌کنند. زنبورهای ناظر در میان کارگرها گشت می‌زنند تا تشخیص دهند یک منبع غذایی همچنان ارزش استفاده دارد یا خیر و در نهایت زنبورهای دیده‌بان که به‌دنبال کشف منابع غذایی جدید هستند.

در الگوریتم ABC، یک منبع غذایی به عنوان حالتی در فضای جست‌و‌جو تعریف می‌شود (یک راهکار برای مساله بهینه‌سازی)، و تعداد منابع غذایی در ابتدا برابر با تعداد زنبورهای موجود در کندو است. کیفیت منابع غذایی توسط مقدار تابع هدف در آن موقعیت (مقدار تناسب) تعیین می‌شود.

رفتار هوشمند ناپایدار زنبورهای عسل را می‌توان در چند گام زیر خلاصه کرد:

  • زنبورها تلاش می‌کنند تا به صورت تصادفی در محیط به‌دنبال منابع غذایی خوب بگردند (مقدار تناسب).
  • پس از یافتن یک منبع غذایی، آن‌ها تبدیل به زنبورهای کارگر می‌شوند و شروع به استخراج غذا از منبع یافت شده می‌کنند.
  • زنبور کارگر با شهد به کندو باز می‌گردد و بار شهد خود را خالی می‌کند. پس از خالی کردن آن، می‌تواند مستقیما به منبع کشف شده خود باز گردد یا اطلاعاتی که درباره منبع غذاییش دارد را با اجرای یک رقص گردون در ناحیه رقص به اشتراک بگذارد.
  • اگر یک منبع غذایی خالی شد، زنبوران کارگر به دیده‌بان مبدل شده و به جست و جوی تصادفی برای منابع غذایی می‌پردازند.
  • زنبورهای ناظر در کندو منتظر مانده و زنبورهای کارگر را در منابع غذایی گردآوری کرده‌شان مورد نظارت قرار می‌دهند و از میان منابع غذایی موجود با بیشترین سود، یک منبع را انتخاب می‌کنند.
  • انتخاب منابع غذایی متناسب با کیفیت آن منبع (مقدار تناسب) است.

با اینکه سه نوع از زنبورهای عسل موجود در کلونی معرفی شدند، در مرحله پیاده‌سازی تنها دو نوع زنبور وجود دارد که زنبورهای کارگر و ناظر هستند. در واقع زنبور دیده‌بان یک رفتار اکتشافی است که می‌تواند توسط زنبورهای کارگر و ناظر انجام شود.

در این مقاله، از زبان پایتون برای پیاده‌سازی استفاده می‌شود زیرا در محاسبات عددی بسیار موثر عمل کرده و پیاده‌سازی یک مجموعه از بنچ‌مارک‌های هدف را برای استفاده مجدد در الگوریتم‌های هوش ازدحامی آسان‌تر می‌سازد.

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 را می‌توان از این مسیر دریافت کرد.

زنبورهای مصنوعی

به منظور آغاز ساخت الگوریتم، ابتدا باید راهکاری برای ارائه عامل زنبور در کد پایتون وجود داشته باشد. سه کارکرد اصلی وجود دارد که هر زنبوری باید دارای آن‌ها باشد. نخست اینکه اگر زنبوری به دلیل رفتار اکتشافی به خارج از ناحیه تصمیم می‌رود باید توانایی بازگشت به کندو را داشته باشد. دومین کارکرد، توانایی به روز رسانی وضعیت منبع غذایی کنونی که زنبور روی آن کار می‌کند و ارزیابی اینکه آیا در همسایگی، ناحیه‌ای با منبع غذایی بهتر وجود دارد یا خیر است. و در نهایت آخرین مورد تشخیص این است که یک منبع غذایی خالی شده و اکنون زنبور باید به یک دیده‌بان مبدل شود و به دنبال منابع غذایی جدید بگردد.

با در نظر گرفتن این مسائل، اکنون می‌توان کلاس 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

الگوریتم کامل کلونی زنبور عسل مصنوعی

پس از پیاده‌سازی عامل‌های اصلی که قرار است در الگوریتم از آن‌ها استفاده شود، اکنون زمان آن فرا رسیده تا کلیه مراحلی که پیش از این تشریح شد با کد پایتون پیاده‌سازی شود.

توجه به این نکته لازم است که هر یک از گام‌های الگوریتم در یک متد جدا پیاده‌سازی شده‌اند. در ابتدا، پارامترهای داخلی الگوریتم 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))

ارزیابی روی تابع بنچ‌مارک

مزیتی که الگوریتم‌های هوش ازدحامی نسبت به الگوریتم‌های کلاسیک و روش‌های مبتنی بر گرادیان دارند، توانایی اجرای خیلی خوب روی توابع غیر مشتق‌پذیر و توابع چند مدله است.

از آنجا که مسائل بهینه‌سازی بسیار مهم هستند، چندین تابع بنچ‌مارک خیلی خوب برای ارزیابی کارایی الگوریتم‌های بهینه‌سازی ارائه شده است. برخی از این توابع روی 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 به میزانی سریع بوده که به سختی می‌توان نمودار آن را مشاهده کرد.

نمودار ۲

چنانکه از نمودار سه مشهود است، الگوریتم ABC عملکرد خوبی برای تابع Rastrigin نیز داشته است.

نمودار ۳

گام بعدی چیست؟

اکنون که چگونگی کارکرد و روش پیاده‌سازی الگوریتم ABC ارائه شد، می‌توان از آن برای حل مسائل جالب مانند خوشه‌بندی و بخش‌بندی تصویر (قطعه‌بندی تصویر | image segmentation) استفاده کرد. برای این امر تنها کافیست تغییرات ریزی روی الگوریتم اعمال و فهمید که چگونه می‌توان آن مسائل را به مساله بهینه‌سازی تبدیل کرد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شود:

^^

بر اساس رای ۱۱ نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد.

مشاهده بیشتر