فهرست بستن

PSO الگوریتمینین پایتون دیلینده نئجه یازیلماسی

PSO الگوریتمی، قوش سورولرینین اجتماعی یاشاملاریندان الهام آلینان بیر  الگوریتم دیر. PSO داهی اونون کیمی الگوریتملر عمومیتله بیر مسئله‌نین متعدد جوابلاری ایله باشلاییب، جوابلاری الگوریتم قاباغا گئتمه‌سی ایله بیر، یاخشیلادارلار؛ اونون اوچون ده بو الگوریتملره «یاخشیلاشدیرما الگوریتملری» آدینی وئره‌بیله‌ریک. یاخشیلاتما قارشیلاشدیغیمیز مسئله ایله معنی‌له‌نیر. بعض مسئله‌لرده گلیری و قازانجی چوخالتماق، بعضی‌لرینده ایسه چیخیری آزالتماق، یاخشیلاتماق معیاریمیز اولور.

بسم الله الرحمن الرحیم

PSO الگوریتمینی آنلاماق اوچون (باشقا الگوریتملر ده اونون کیمی) بیرینجی آتدیم، الگوریتمده اولان جزءلرین نه اولماسینی و نه اوچون اولماسینی آنلاماق دیر. اونون اوچون بو یازینین باشلانیشیندا PSO الگوریتمینین جزءلرینی تانییاجاغیق. بو الگوریتم اؤز ایشینی بیر جمعیت (توپلوم) ایله باشلایار. جمعیت، ذره‌لرین بیر یئره ییغیشماسی دیر. هر بیر ذره‌نین موقعیتی، یئیینلیگی و اولدوغو ان یاخشی موقعیت الگوریتمده دییشدیریله‌جکدیر. ذره‌نین موقعیتی دئیه‌نده قصدیمیز PSOـنو حل ائتمه‌سی اوچون چالیشدیردیغیمیز مسئله‌نین اؤرنک جوابی دیر. ساخلانماسی گرک اولان باشقا شیلر بوتون ذره‌لر آراسیندا تجربه اولونان ان یاخشی موقعیت دیر. بونلاری تانیماقدان سونرا الگوریتمین هر بیر آتدیمیندا نه اولاجاغی آنلایابیله‌ریک. PSO الگوریتمینین آتدیملاری بو قراردا دیر:

۱) جمعیتی یاراتماق اوچون تصادفی اولاراق ذره‌لرین موقعیتی و یئیینلیگینی دوزلتمک (الگوریتمین باشلانیشیندا ذره‌نین ان یاخشی موقعیتی ایله ایندیکی موقعیتی بیردیرلر)

۲) الگوریتمین هر بیر تکراریندا ذره‌لرین موقعیتینی آشاغیدا یازیلان رابطه ایله یئنیله‌مک:

\nu_i = \omega \nu_i + \phi_p r_p (x^{*}_{i} - x_i) + \phi_g r_g (x^{*} - x_{i})

x_i = x_i + \nu_i

بو رابطه ده الگوریتمین اوچ پارامتری یعنی

\omega, \phi_p ,\phi_g

گؤرونور. بونلارین ان یاخشی مقدارینی نئچه یول الگوریتمی اجرالاماقدان سونرا تاپابیله‌ریک. i-نجی ذره‌نین موقعیتی و اونون سرعتی

x_i, \nu_i

عبارتلرییله گؤرسه‌دیلیب دیر. قالان بو ایکی پارامتر ده

r_p, r_g

تصادفی اولاراق سئچیله‌جک دیر. i-نجی ذره‌نین ان یاخشی اولدوغو موقعیتی و بوتون ذره‌لر آراسیندا تجربه اولونان ان یاخشی موقعیتی

x^{*}_{i}, x^{*}

ایله گؤرستمیشیک.

۳) هر بیر ذره‌نین موقعیتینین یئنیلنمگیندن سونرا، یئرلشدیگی موقعیت، گئچنکی موقعیتیندن یاخشیراق اولورسا ذره‌نین ان یاخشی اولدوغو موقعیتی یئنی موقعیت ایله بیر قویمالیییق. بوندان علاوه یئنی موقعیت بوتون ذره‌لر آراسیندا تجربه اولونان ان یاخشی موقعیتدن یاخشیراق اولورسا، اونو دا ذره‌نین یئنی موقعیتی ایله بیر، مقدارلامالیییق.

۴) اؤزوموز معین ائتدیگیمیز تکرار ساییسیجا الگوریتم ایشله‌مگیندن سونرا مسئله‌میزین جوابی بوتون ذره‌لر آراسیندا تجربه اولونان ان یاخشی موقعیت اولاجاق.

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

class Particle:

    def __init__(self, solution_generator_function, velocity_generator_function):
        self.position = []
        self.velocity = []
        self.cost = float("inf")
        self.best_known_cost = float("inf")
        self.position = solution_generator_function()
        self.velocity = velocity_generator_function()
        self.best_known_position = self.position.copy()
        return

    def __repr__(self):
        o = "Position:\n"
        for d in self.position:
            o += str(d) + "\n"
        o += "Current cost: " + str(self.cost) + "\nBest known position:\n"
        for d in self.best_known_position:
            o += str(d) + "\n"
        o += "Best known cost: " + str(self.best_known_cost)
        return o

ذره‌لر اوچون تعریفله‌دیگیمیز کلاسدان یئنی بیر شی دوزلتمگیمیز اوچون ایکی، تابع شکلینده اولان پارامتر گرک دیر، solution_generator_function و velocity_generator_function. آدیندان بللی اولدوغو کیمی بو تابع‌لرین بیری تصادفی اولاراق ذره‌نین باشلانیش موقیعیتینی، اوبیریسی ایسه ذره‌نین سرعتینی قایتارمالی دیر. بو کدی یازماق دا هدف چیخیری و هزینه‌نی آزالتماق نظرده آلینیب دیر، اونون اوچون ده هر بیر ذره اوچون هزینه (cost) و ذره‌نین تجربه ائتدیگی ان یاخشی هزینه (best_known_cost) بو کلاسدا باشقا دئییلن پارامترلره علاوه ساخلانیلاجاق.

PSO الگوریتمینین کلاسی دا آشاغیدا گلن کیمی تعریفله‌نیب دیر:

class PyPSO:
    
    def __init__(self, cost_function, particle_num, iteration_num, solution_generator_function, velocity_generator_function, omega=0.3, phi_p=0.3, phi_g=2.1):
        self.cost_function = cost_function
        self.particle_num = particle_num
        self.iteration_num = iteration_num
        self.omega = omega
        self.phi_p = phi_p
        self.phi_g = phi_g
        self.particles = []
        self.best_known_cost = float("inf")
        self.best_known_position = []
        for i in range(self.particle_num):
            self.particles.append(Particle(solution_generator_function,velocity_generator_function))
            self.particles[i].cost = self.cost_function(self.particles[i].position)
            self.particles[i].best_known_cost = self.particles[i].cost
            if self.particles[i].cost < self.best_known_cost:
                self.best_known_position = self.particles[i].position.copy()
                self.best_known_cost = self.particles[i].cost
        return
    
    def __repr__(self):
        o = "Best known position:\n"
        for d in self.best_known_position:
            o += str(d) + "\n"
        o += "Best known cost: " + str(self.best_known_cost)
        return o
    
    def solve(self):
        convergence = []
        for i in range(self.iteration_num):
            for particle in self.particles:
                r_p = random.random(size=shape(particle.position))
                r_g = random.random(size=shape(particle.position))
                particle.velocity = self.omega * particle.velocity + \
                    self.phi_p * r_p * (particle.best_known_position - particle.position) + \
                    self.phi_g * r_g * (self.best_known_position- particle.position)
                particle.position += particle.velocity
                particle.cost = self.cost_function(particle.position)
                if particle.cost < particle.best_known_cost:
                    particle.best_known_position = particle.position.copy()
                    particle.best_known_cost = particle.cost
                    if particle.best_known_cost < self.best_known_cost:
                        self.best_known_position = particle.best_known_position.copy()
                        self.best_known_cost = particle.best_known_cost
            print("Iteration. " + str(i+1))
            print(self.best_known_cost)
            convergence.append(self.best_known_cost)
        plt.figure()
        plt.plot(convergence)
        plt.title("Convergence diagram")
        plt.xlabel("Iteration")
        plt.ylabel("Total cost")
        plt.grid(True)
        plt.show()
        return convergence

PyPSO پارامترلری بو ترتیبده دیرلر:

  1. cost_function: ذره‌نین موقعیتینی آلیب، اونونلا متناظر اولان هزینه‌نی قایتارمالی دیر
  2. particle_num: جمعیتده ذره‌لرین تعدادی
  3. iteration_num: الگوریتمین سونلانماسی اوچون تکرارلارین سایی
  4. solution_generator_function: ذره‌لرین موقعیتی اولان مسئله جوابینی تصادفی اولاراق دوزه‌لدن تابع
  5. velocity_generator_function: ذره‌نین یئیینلیگینی تصادفی اولاراق دوزه‌لدن تابع
  6. omega: الگوریتم پارامترلریندن، یئیینلیگی یئنیلتمه‌ده یئیینلیگین ضریبی (وئریلمه‌سه ۰٫۳ گؤتوروله‌جک)
  7. phi_p: الگوریتم پارامترلریندن، یئیینلیگی یئنیلتمه‌ده ذره‌نین تجربه ائتدیگی ان یاخشی موقعیتین ایندیکی موقعیتله تفاضلونون ضریبی (وئریلمه‌سه ۰٫۳ گؤتورله‌جک)
  8. phi_g: الگوریتم پارامترلریندن، یئیینلیگی یئنیلتمه‌ده بوتون جمعیتین تجبره ائتدیگی ان یاخشی موقعیتین ایندیکی موقعیتله تفاضلونون ضریبی (وئریلمه‌سه ۲٫۱ گؤتوروله‌جک)

بیلدیگینیز کیمی PyPSOـدان بیر اؤرنگین دوزه‌لمه‌سی ایله __init__ تابعی چاغریلاجاق و الگوریتم پارامترلری مقدارلانیب و باشلانغیچ جمعیت تصادفی اولاراق یارادیلاجاق دیر. solve تابعینین چاغیرلماسی ایله ده، اوستده سؤزو سورولن الگوریتم آتدیملاری بیر بیر ائدیلیب، هر بیر تکرار دا ان یاخشی هزینه، یاخینساما شکلینی چکمک اوچون، ساخلاناجاق دیر.

بو کلاس ایله بیر مسئله‌نین نئجه حل اولماسی آشاغیداکی کد ایله آیدینلاشار:

from numpy import random, sin
from PyPSO import PyPSO

def f(x):
    o = 0
    for a in x:
        o += sin(a) ** 2
    return o

def s():
    return 10 * (random.rand(10) - 0.5)

def v():
    return (random.rand(10) - 0.5)

myPSO = PyPSO(f, 200, 100, s, v, 0.3, 0.3, 2.1)
myPSO.solve()
print(myPSO)

بو کودون چیخیشی و یاخینساما شکلینی آشاغیدا گؤره‌بیلرسینیز:

Best known position:
-۱۸٫۸۴۹۵۵۵۹۲۱۵۶۴۰۸۶
۳٫۱۴۱۵۹۲۶۵۳۵۷۴۸۴۲۴
-۳٫۱۴۱۵۹۲۶۵۳۷۳۸۹۹۶۴
-۳٫۱۴۱۵۹۲۶۵۳۴۷۶۸۵۱
۶٫۲۸۳۱۸۵۳۰۷۲۰۱۱۳
۹٫۴۲۴۷۷۷۹۶۰۷۸۷۷۰۲
۲٫۸۹۱۳۵۶۶۲۹۷۵۸۸۷۳e-12
-۱٫۷۰۹۸۰۰۶۹۱۵۹۶۵۱۴۲e-11
۶٫۲۸۳۱۸۵۳۰۷۲۶۰۸۳۹
۳٫۱۴۱۵۹۲۶۵۳۶۳۷۰۳۴۴
Best known cost: 4.58166779334268e-20