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 پارامترلری بو ترتیبده دیرلر:
- cost_function: ذرهنین موقعیتینی آلیب، اونونلا متناظر اولان هزینهنی قایتارمالی دیر
- particle_num: جمعیتده ذرهلرین تعدادی
- iteration_num: الگوریتمین سونلانماسی اوچون تکرارلارین سایی
- solution_generator_function: ذرهلرین موقعیتی اولان مسئله جوابینی تصادفی اولاراق دوزهلدن تابع
- velocity_generator_function: ذرهنین یئیینلیگینی تصادفی اولاراق دوزهلدن تابع
- omega: الگوریتم پارامترلریندن، یئیینلیگی یئنیلتمهده یئیینلیگین ضریبی (وئریلمهسه ۰٫۳ گؤتورولهجک)
- phi_p: الگوریتم پارامترلریندن، یئیینلیگی یئنیلتمهده ذرهنین تجربه ائتدیگی ان یاخشی موقعیتین ایندیکی موقعیتله تفاضلونون ضریبی (وئریلمهسه ۰٫۳ گؤتورلهجک)
- 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