در این مطلب، الگوریتم بهینه سازی ازدحام ذرات (Particle Swarm Optimization | PSO) به طور کامل و همراه با مثال مورد بررسی قرار گرفته و پیاده‌سازی الگوریتم PSO در پایتون، متلب و جاوا انجام شده است. شایان توجه است که به منظور تشریح محاسبات ریاضی نهفته در پس الگوریتم بهینه سازی ازدحام ذرات یا همان الگوریتم PSO از نسخه کلاسیک این الگوریتم استفاده خواهد شد. در مطلب «الگوریتم بهینه سازی ازدحام ذرات | کد الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع» ابتدا به مفهوم بهینه‌سازی پرداخته شده و سپس، الگوریتم بهینه سازی ازدحام ذرات به طور جامع و کامل مورد بررسی قرار گرفته است. در ادامه مطلب، انواع الگوریتم بهینه سازی ازدحام ذرات تشریح می‌شود. همچنین، روش‌های ترکیبی موجود با بهره‌گیری از الگوریتم بهینه سازی ازدحام ذرات که ترکیبی از روش‌های بهینه‌سازی هیوریستیک و قطعی هستند نیز معرفی می‌شوند.

فهرست مطالب این نوشته پنهان کردن

علاوه بر پرداختن به مباحث بیان شده، در مطلب «الگوریتم بهینه سازی ازدحام ذرات | کد الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع» چالش‌های اساسی که کاربر ضمن استفاده از الگوریتم PSO با آن‌ها مواجه می‌شود نیز مورد بررسی قرار گرفته‌اند. یک بررسی موردی (Case Study) نیز با بهره‌گیری از الگوریتم بهینه سازی ازدحام ذرات یا همان الگوریتم PSO انجام شده است که به درک بهتر مبحث کمک می‌کند. این مثال پیرامون بهینه‌سازی تابع هزینه برای سیستم تولید مثل با استفاده از الگوریتم PSO در بهینه‌سازی ترکیبی است. در نهایت، پیاده‌سازی الگوریتم بهینه سازی ازدحام ذرات در پایتون، متلب و جاوا انجام شده است.

مقدمه‌ای بر بهینه‌سازی و الگوریتم‌های آن

«بیشینه» (Maximizing) کردن «سود» یا «کمینه» (Minimizing) کردن «زیان» (Loss) از جمله مسائل بسیار حائز اهمیت در زمینه‌های گوناگون از جمله حوزه‌های فنی و مهندسی است. در یک تعریف ساده و کوتاه می‌توان گفت که مسائلی که در آن‌ها هدف بیشینه یا کمینه کردن یک تابع است را «مسئله بهینه‌سازی» (Optimization Problem) می‌گویند. برای مطالعه بیشتر پیرامون بهینه‌سازی، مطالعه مطالب «بهینه سازی (ریاضیاتی) چیست؟ — راهنمای جامع» و «بهینه سازی چند هدفه چیست؟ — راهنمای جامع» پیشنهاد می‌شود.

با توسعه فناوری، تعداد و پیچیدگی مسائل بهینه‌سازی نیز در زمینه‌های علمی گوناگون افزایش پیدا کرده است. از متداول‌ترین مسائل موجود در حوزه‌های مهندسی که نیاز به استفاده از روش‌های بهینه‌سازی برای حل آن‌ها وجود دارد می‌توان به تبدیل و توزیع انرژی، لجستیک (Logistics | آمادگاری) و بارگذاری مجدد رآکتورهای هسته‌ای اشاره کرد. مسائل بهینه‌سازی در دیگر زمینه‌ها از جمله هندسه و اقتصاد نیز کاربرد دارند. از دیگر زمینه‌های اصلی کاربرد بهینه‌سازی می‌توان به «هوش مصنوعی» (Artificial Intelligence | AI) و یادگیری ماشین «Machine Learning» اشاره کرد.

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

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

الگوریتم بهینه سازی ازدحام ذرات (PSO)

در اوایل سال ۱۹۹۰ میلادی، پژوهش‌های گوناگونی پیرامون رفتار اجتماعی گروه‌های حیوانات انجام شد. این پژوهش‌ها حاکی از آن بودند که برخی از حیوانات که به یک گروه خاص متعلق هستند، مانند پرندگان، ماهی‌ها و دیگر موارد، قادر به آن هستند که اطلاعات را در گروه‌های (دسته‌های | گله‌های) خودشان به اشتراک بگذارند و چنین قابلیتی به این حیوانات مزایای قابل توجهی برای بقا اعطا می‌کرد.

با الهام گرفتن از این مطالعات، «کندی» (Kennedy) و «ابِرهارت» (Eberhart) در سال ۱۹۹۵ الگوریتم بهینه سازی ازدحام ذرات (Particle Swarm Optimization | PSO) یا الگوریتم PSO را در یک مقاله معرفی کردند. الگوریتم بهینه سازی ازدحام ذرات یا الگوریتم PSO یک الگوریتم «فراابتکاری» (Metaheuristic) است که برای بهینه‌سازی توابع پیوسته غیر خطی مناسب محسوب می‌شود. نویسندگان مقاله مذکور، الگوریتم بهینه سازی ازدحام ذرات یا الگوریتم PSO را از مفهوم هوش ذرات (Swarm Intelligence) که معمولا در گروه‌های حیوانات مانند گله‌ها و دسته‌های حیوانات وجود دارد الهام گرفته و ساخته‌اند.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون و متلب | راهنمای جامع

برای شفاف شدن هر چه بیشتر ساز و کار کلی الگوریتم بهینه سازی ازدحام ذرات و دیگر الگوریتم‌هایی که از رفتار گروهی حیوانات الهام گرفته شده‌اند، توضیحاتی پیرامون رفتار گروهی (گله‌ای) حیوانات ارائه می‌شود. این توضیحات می‌تواند به درک چگونگی ساخت الگوریتم بهینه سازی ازدحام ذرات (و دیگر الگوریتم‌های دارای رویکرد مشابه) برای حل مسائل پیچیده ریاضی کمک کند.

الگوریتم بهینه سازی ازدحام ذرات و رفتار گروهی حیوانات

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

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

پژوهش‌هایی که از سال ۱۹۹۰ پیرامون رفتار پرندگان انجام شد، حاکی از آن است که همه پرندگان یک ازدحام (گروه | دسته) که به دنبال نقطه خوبی برای فرود هستند، قادر به آن هستند که از بهترین نقطه برای فرود در هنگامی که آن نقطه توسط یکی از اعضای ازدحام پیدا شد، آگاه شوند. با استفاده از این آگاهی، هر یک از اعضای این ازدحام، تجربه دانش شخصی و ازدحامی خود را متوازن می‌کنند که با عنوان «دانش اجتماعی» (Social Knowledge) شناخته شده است.

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

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون و متلب | راهنمای جامع

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

کندی و اِبِرهارت، از رفتار جمعی پرندگان الهام گرفتند؛ رفتاری که مزایای بقای قابل توجهی را برای پرندگان در هنگام جستجو برای یک نقطه امن برای فرود تضمین می‌کرد. آن‌ها بر همین اساس، الگوریتمی را ارائه کردند که الگوریتم ازدحام ذرات (Particle Swarm Optimization) نامیده می‌شود. الگوریتم PSO می‌تواند رفتاری به مثابه آنچه برای دسته پرندگان گفته شد را تقلید کند.

الگوریتم بهینه سازی ازدحام ذرات کلاسیک

نسخه اولیه الگوریتم ازدحام ذرات یا الگوریتم PSO که با عنوان نسخه کلاسیک این الگوریتم نیز شناخته شده است، در سال ۱۹۹۵ ارائه شد. از آن زمان تاکنون، انواع دیگری از این الگوریتم به عنوان نسخه‌های دیگر الگوریتم کلاسیک ارائه شده‌اند که از جمله آن‌ها می‌توان به «کاهش خطی وزن اینرسی» (Linear-Decreasing Inertia Weight)، «وزن عامل انقباض» (The Constriction Factor Weight) و «اینرسی پویا» (Dynamic Inertia) در کنار مدل‌های ترکیبی یا حتی روش‌های بهینه‌سازی الهام گرفته شده از کوانتوم که روی الگوریتم PSO اعمال شده‌اند اشاره کرد.

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

هدف از مسائل بهینه‌سازی، تعیین متغیری است که با بردار X=[x1x2x3…xn‎]‎ نشان داده می‌شود و بسته به فرمول بهینه‌سازی ارائه شده توسط تابع f(X)‎، بیشینه یا کمینه می‌شود. بردار متغیر X، به عنوان یک بردار مثبت شناخته شده است. این بردار، یک مدل متغیر و بردار n بُعدی آن را نمایش می‌دهد که در آن، n نشانگر تعداد متغیرهایی است که ممکن است در مسئله تعیین شوند. n در مسئله پیدا کردن بهترین نقطه برای فرود دسته پرندگان، طول و عرض جغرافیایی است.

از سوی دیگر، تابع f(X)‎ تابع برازش (Fitness Function) یا تابع هدف (Objective Function) نامیده می‌شود و تابعی است که میزان خوب یا بد بودن یک موقعیت X را ارزیابی می‌کند. این تابع برای مسئله دسته پرندگان، میزان خوب بودن یک نقطه برای فرود است که پرنده پس از پیدا کردن یک نقطه به آن فکر می‌کند. چنین ارزیابی برای مسئله فرود گروه پرندگان، براساس معیارهای بقای گوناگون انجام می‌شود. اکنون، ازدحامی با P ذره در نظر گرفته می‌شود؛ یک بردار مکان $$X_t^i$$ و یک بردار سرعت $$V_t^i$$ در هر تکرار برای هر یک از i ذره‌ای این سرعت را ایجاد می‌کنند، به صورت زیر وجود دارد:

$$X_i^t = (x_{i1}x_{i2}x_{i3} … x_{in})^{T}$$

$$V_i^t = (v_{i1}v_{i2}v_{i3} … v_{in})^{T}$$

این بردارها بر اساس بُعد j مطابق با معادله‌ای که در ادامه آمده است، به روز رسانی می‌شوند:

$$V_{i j}^{t+1}=w V_{i j}^{t}+c_{1} r_{1}^{t}\left(p b e s t_{i j}-X_{i j}^{t}\right)+c_{2} r_{2}^{t}\left(g b e s t_{j}-X_{i j}^{t}\right)$$

و

$$X_{i j}^{t+1}=X_{i j}^{t}+V_{i j}^{t+1}$$

که در آن‌ها، داریم:

i = 1, 2, …, P و j = 1, 2, …, n.

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

سرعتی که اولین عبارت در معادله را به روز رسانی می‌کند، ضرب داخلی پارامتر w و سرعت پیشین ذره است. به همین دلیل است که حرکت پیشین ذره به حرکت کنونی نمایش داده می‌شود. از همین رو، برای مثال، اگر w = 1 بود، حرکت ذره به طور کامل به وسیله حرکت قبلی خودش تحت تاثیر قرار گرفته است؛ بنابراین، ذره ممکن است به حرکت خود در همان جهت ادامه دهد.

از سوی دیگر، اگر $$0≤w<1$$، این تاثیر کاهش پیدا می‌کند و این یعنی ذرات به منطقه دیگری در ناحیه جستجو می‌روند. بنابراین، با توجه به کاهش پارامتر وزن اینرسی، ازدحام (گروه | دسته) ممکن است نواحی بیشتری را در ناحیه جستجو مورد اکتشاف قرار دهد و این یعنی شانس پیدا کردن بهینه سراسری افزایش پیدا می‌کند. اگرچه، در حالاتی که از مقادیر w کم‌تر استفاده می‌شود نیز هزینه‌ای وجود دارد که شبیه‌سازی‌ها را زمان‌برتر خواهد کرد.

عبارت درک فردی که دومین عبارت در معادله یک است، به وسیله تفاضل بین بهترین موقعیت خود ذره، برای مثال $$pbestij_{ij}$$ و موقعیت کنونی آن $$X_{ij}^t$$ محاسبه می‌شود. شایان توجه است که ایده نهفته در پس این ایده آن است که هر چه فعالیت‌ها فاصله بیشتری از موقعیت $$pbestij_{ij}$$ بگیرند، تفاضل $$(pbestij_{ij}-X_{ij}^t)$$ باید افزایش پیدا کند. بنابراین، این عبارت افزایش پیدا کرده و ذره را به بهترین موقعیت آن جذب می‌کند. پارامتر $$c_{1}$$ که به صورت حاصل‌ضرب در این رابطه وجود دارد، یک ثابت مثبت و یک پارامتر شناخت فردی محسوب می‌شود و به اهمیت تجربیات پیشین خود ذره وزن می‌دهد.

دیگر پارامتری که ضرب عبارت دوم را شکل می‌دهد، عبارت $$r_{1}$$ است. $$r_{1}$$ یک پارامتر مقدار تصادفی با طیف [0,1] است. این پارامتر تصادفی، نقش مهمی را بازی می‌کند، زیرا از همگرایی پارامترها ممانعت و بهینه سراسری احتمالی را بیشینه می‌کند. در نهایت، سومین عبارت مربوط به یادگیری اجتماعی است. به دلیل وجود این پارامتر، همه ذرات در ازدحام قادر به آن هستند که اطلاعات پیرامون بهترین نقطه به دست آمده را صرف نظر از اینکه کدام ذره آن را پیدا کرده است، با یکدیگر به اشتراک بگذارند؛ برای مثال $$gbestij_{ij}$$. فرمت این عبارت نیز درست مانند دومین عبارت است که مربوط به یادگیری فردی می‌شود. بنابراین، تفاضل $$(gbestij_{ij}-X_{ij}^t)$$ مانند یک جاذبه برای ذرات برای بهترین نقطه تا هنگام پیدا شدن نقطه در تکرار t عمل می‌کند. به طور مشابه، $$c_{2}$$ پارامتر یادگیری اجتماعی و وزن آن، اهمیت یادگیری سراسری ذرات است. همچنین، $$r_{2}$$ نیز نقشی مشابه با $$r_{1}$$ دارد.

در ادامه، الگوریتم PSO ارائه شده است و افراد ممکن است متوجه منطق بهینه‌سازی موجود در جستجوهای آن برای کمینه‌ها شوند و همه بردارهای مکانی که توسط تابع f(X)‎ ارزیابی می‌شوند. تابع f(X)‎ با عنوان «تابع برازش» (Fitness Function) شناخته شده است. در تصاویر ۲ و ۳ نیز به روز رسانی‌هایی در سرعت ذرات و موقعیت آن در تکرار t با در نظر داشتن مسئله دوبُعدی با متغیرهای $$x_{1}$$ و $$x_{2}$$ انجام شده است.

  1. مقداردهی اولیه
    1. برای هر i در جمعیت ازدحام با اندازه p:
      1. $$X_{i}$$ را به طور تصادفی مقداردهی اولیه کن.
      2. $$$$x_{i}$V_{i}$$ را به طور تصادفی مقداردهی اولیه کن.
      3. تابع برازش $$f(X_{i})$$ را ارزیابی کن.
      4. $$pbestij_{ij}$$ را با یک کپی از $$X_{i}$$ مقداردهی اولیه کن.
    2. gbest را با یک نسخه از $$X_{i}$$ با بهترین برازش مقداردهی اولیه کن.
  2. مراحل را تا هنگامی که یک معیار توقف ارضا شود، تکرار کن:
    1. برای هر ذره i:
      1. $$V_i^t$$ و $$X_i^t$$ را مطابق با معادلات ۱ و ۲ مقداردهی اولیه کن.
      2. تابع برازش $$f(X_i^t)$$ را ارزیابی کن.
      3. $$pbest_{i} \leftarrow X_i^t$$ اگر f(pbest_{i})<f(X_i^t)
      4. $$gbest \leftarrow X_i^t$$ h’v اگر f(gbest)<f(X_i^t)
الگوریتم بهینه سازی ازدحام ذرات (PSO) به همراه پیاده سازی-- راهنمای جامع
بردار سرعت در تکرار t به صورتی که به وسیله دو مولفه ترکیب شده با ارجاع به یک مسئله دوبُعدی است.
الگوریتم بهینه سازی ازدحام ذرات (PSO) به همراه پیاده سازی-- راهنمای جامع
این بردار مکانی در تکرار t به روز رسانی شده، در حالیکه به وسیله دو مولفه با ارجاع به مسئله دوبُعدی ترکیب شده است.
  • برای مشاهده مجموعه فیلم‌های الگوریتم‌های بهینه‌سازی هوشمند + اینجا کلیک کنید.

ترکیب الگوریتم ازدحام ذرات با روش‌های قطعی

به طور کلی، روش‌های بهینه‌سازی به دو دسته قطعی (Deterministic) و هیوریستیک (Heuristic) تقسیم می‌شوند. هدف روش‌های قطعی پیدا کردن یک فرایند تکرار شونده شامل گرادیان (شیب) است که پس از تعداد مشخصی از تکرارها، به کمینه تابع هدف همگرا می‌شود. روال تکرار شونده این نوع از روش را می‌توان به صورت زیر نوشت:

$$x^{k+1} = x^{k}+a^{k}d^{k}$$

x بردار متغیر، α اندازه گام، d جهت کاهش و k تعداد تکرار است. بهترین ویژگی که از هر روش گرادیان قطعی انتظار می‌رود، همگرایی آن به یک نقطه ثابت است که معمولا کمینه محلی محسوب می‌شود. روش‌های هیوریستیک برخلاف روش‌های قطعی، از تابع هدف گرادیان در جهت رو به پایین استفاده نمی‌کنند. هدف آن‌ها تقلید طبیعت به منظور پیدا کردن بیشینه یا کمینه تابع هدف با انتخاب کردن نقاطی که این تابع محاسبه خواهد کرد، به شیوه‌ای ظریف و سازمان یافته است.

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

مقالات گوناگونی طی این سال‌ها ارائه شده‌اند که حاکی از کارایی و اثربخشی فرمول‌های ترکیبی هستند. همچنین، طی  یک دهه اخیر تعداد رو به رشدی مقاله پیرامون روش‌های ترکیبی برای بهینه‌سازی ارائه شده است. در این زمینه، الگوریتم PSO را می‌توان با روش‌های قطعی ترکیب کرد و بدین شکل، شانس پیدا کردن محتمل‌ترین بهینه سراسری را افزایش داد. در ادامه، سه روش قطعی که الگوریتم PSO با آن‌ها ترکیب شده است معرفی می‌شوند. این روش‌ها عبارتند از: «روش گرادیان مزدوج» (Conjugate Gradient Method)، «روش نیوتون» (Newton’s Method) و «روش شبه‌نیوتون» (Quasi-Newton Method | BFGS). فرمول‌های هر یک از این الگوریتم‌ها در ادامه مطلب «الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع» به طور خلاصه مورد بررسی قرار گرفته‌اند.

الگوریتم گرادیان مزدوج

روش گرادیان مزدوج نرخ همگرایی «روش شدیدترین کاهش» (Steepest Descent Method) را با انتخاب جهت‌های کاهشی فراهم می‌کند که ترکیب خطی از جهت گرادیان با جهت کاهش تکرار پیشین هستند. بنابراین، روابط آن‌ها به صورت زیر است.

$$x^{k+1} = x^{k}+a^{k}d^{k}$$

$$d^{k} = -\triangledown(x^{k})+\gamma^{k}d^{k-1}$$

در روابط بالا، $$\gamma$$ ضریب مزدوجی است که با تنظیم اندازه بردارها کار می‌کند. در نسخه «فلچر-ریوز» (Fletcher-Reeves)، ضریب مزدوجی (هم‌یوغی) بر اساس رابطه زیر به دست می‌آید.

$$\gamma^{k}=\frac{\parallel-\triangledown(x^{k})\parallel^{2}}{\parallel-\triangledown(x^{k-1})\parallel^{2}}$$

روش نیوتون

در حالی که روش‌های شدیدترین کاهش و گرادیان مزدوج از اطلاعات مشتق مرتبه اول استفاده می‌کنند، روش نیوتون (Newton’s Method) از اطلاعات مشتق مرتبه دوم برای شتاب‌دهی به هم‌گرایی فرایند تکرار شونده استفاده می‌کند. الگوریتم مورد استفاده در این روش، در ادامه ارائه شده است.

$$x^{k+1}=x^{k}+\alpha^{k}d^{k}$$

$$d^{k}=-\mid{H(x)}\mid^{-1}\triangledown{U(x^{k})}$$

در رابطه بالا، H(x)‎، «ماتریس هسین» (Hessian Matrix) تابع است. به طور کلی، این روش نیازمند تکرارهای کمی برای همگرا شدن است. اگرچه، این روش نیاز به یک ماتریس دارد که با اندازه مسئله، رشد کند. اگر تخمین با کمینه تفاوت زیادی داشته باشد، ماتریس هسین ممکن است به طور ضعیفی در شرایط صدق کند. علاوه بر آن، این مورد شامل کشف ماتریسی است که موجب می‌شود روش‌ها به لحاظ کامپیوتری حتی پرهزینه‌تر هم باشند.

روش شبه نیوتنی (BFGS)

BFGS گونه‌ای از روش شبه نیوتنی (Quasi-Newton) است. این روش به دنبال تخمین معکوس ماتریس هسین با استفاده از اطلاعات گرادیان تابع است. این تخمین به گونه‌ای است که شامل مشتق مرتبه دوم نمی‌شود. بدین ترتیب، این روش دارای نرخ همگرایی کمتری نسبت به روش نیوتون است؛ هرچند که به لحاظ محاسباتی، سریع‌تر از روش نیوتون عمل می‌کند. الگوریتم روش شبه نیوتونی در ادامه ارائه شده است.

$$x^{k+1} = x^{k} + a^{k} d^{k}$$

$$d^{k} = -H^{k} \triangledown{U} (x^{k})$$

$$H^{k} = H^{k-1} + M^{k-1} + N^{k-1}$$

$$
M^{k-1}=\left[1+\frac{\left(Y^{k-1}\right)^{T} \cdot H^{k-1} \cdot Y^{k-1}}{\left(Y^{k-1}\right)^{T} \cdot d^{k-1}}\right] \frac{d^{k-1} \cdot\left(d^{k-1}\right)^{T}}{\left(d^{k-1}\right)^{T} \cdot Y^{k-1}}
$$

$$N^{k-1} = -\frac{d^{k-1} (Y^{k-1})^T H^{k-1} + H^{k-1} Y^{k-1} (d^{k-1})^T)}{(d^{k-1})^T}$$

$$Y^{k-1} = \triangledown{U} (x^{k}) – \triangledown{U} (x^{k-1})$$

کاربردهای الگوریتم PSO و چالش‌های آن

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

در حوزه مهندسی، کاربردهای الگوریتم ازدحام ذرات یا همان الگوریتم PSO بسیار گوناگون است. مسائل بهینه‌سازی از جمله PSO را می‌توان در ادبیات پژوهش‌های سیستم‌های انتقال حرارت و الگوریتم‌های پیشی‌بینی ضریب انتقال حرارت نیز پیدا کرد. در این زمینه از ترمودینامیک، می‌توان به مقالات بهینه‌سازی شامل سیستم‌های حرارت مانند «سیکل رانکین آلی-موتور دیزل» (Diesel Engine–Organic Rankine Cycle)، سیستم دیزل ترکیبی ORC/فتوولتاییک (Hybrid Diesel-ORC/Photovoltaic) و «نیروگاه سیکل ترکیبی خورشیدی» (Solar Combined Cycle Power Plants | ISCC) اشاره کرد.

همچنین از الگوریتم PSO برای مسائل بهینه‌سازی جغرافیایی به منظور پیدا کردن بهترین پیکربندی سیستم استفاده می‌شود که به بهترین شکل محدودیت‌های طراحی را ارضا می‌کند. در این زمینه، می‌توان به مطالعاتی اشاره کرد که شامل «بهینه‌سازی نوری-هندسی» (Optical-Geometric Optimization) متمرکز کننده‌های تابش خورشیدی و بهینه‌سازی جغرافیای برای «محوطه‌های تابشی» (Radiative Enclosures) می شود که توزیع دمایی و جریان گرما را ارضا می‌کند.

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

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

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

مثال از الگوریتم PSO: هزینه یک سیستم تولید هم‌زمان

این مسئله، یک مسئله کمینه‌سازی تابع است که کل هزینه عملیات یک سیستم تولید هم‌زمان به نام CGAM را نشان می‌دهد. این سیستم بر اساس نام سازندگان آن یعنی A. Valero ،G. Tsatsaronis ،C. Frangopoulos و M. von Spakovsky نام‌گذاری شده است که تصمیم به استفاده از سیستم مشابه برای مقایسه پاسخ‌های مسئله بهینه‌سازی با روش‌های گوناگون داشتند. در تصویر زیر، سیستم CGAM قابل مشاهده است.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

سیستم CGAM  یک سیستم تولید هم‌زمان شامل «کمپرسور هوا» (Air Compressor | AC)، «محفظه احتراق» (Combustion Chamber  | CC)، «توربین گاز» (Gas Turbine | GT)، «پیش‌گرم‌کن هوا» (Air Preheater | APH) و یک «دیگ‌بخار بازیافت حرارت» (Heat Recovery Steam Generator | HRSG) hsj که شامل یک اکونومایزر برای پیش‌گرم کردن آب و تبخیر کننده می‌شود. هدف از این چرخه، تولید ۳۰ مگاوات الکتریسیته و ۱۱ کیلوگرم بخار اشباع شده در فشار ۲۰ بار است. توضیح اقتصادی این سیستم، در این مطلب کاملا مشابه با مقاله اصلی است و هزینه سوخت سالیانه و هزینه‌های سالیانه مرتبط با تحصیل و عملیات هر تجهیزاتی می‌شود. معادلات برای هر مولفه در ادامه آمده است.

کمپرسور هوا:

$$Z_{AC} = (\frac{C_{11} \dot{m}_a}{C_{12} – \eta_{AC}})(\frac{P_{2}} {P_{1}}) ln(\frac{P_{2}} {P_{1}})$$

محفظه احتراق:

$$Z_{cc} = (\frac{C_{21}\dot{m}_a} {{C}_{22}-\frac{P_4}{P_3}})$$

توربین:

$$Z_{GT} = (\frac{C_{31}\dot{m}_{g}}{C_{32}-\eta_{GT}})ln(\frac{P_4}{P_5} )[1+exp(C_{33}T_{4}-C_{34})]$$

پیش‌گرم‌کن:

$$Z_{APH} = C_{41}(\frac{\dot{m}(h_5-h_6)}{(U)(\triangledown{TLM})})^{0.6}$$

دیگ بخار بازیافت حرارت:

$$Z_{HRSG} = C_{51}((\frac{Q_{PH}}{(\triangledown{TLM})_{PH}})^{0.8}+(\frac{Q_{PH}}{(\triangledown{TLM})_{PH}})^{0.8})+C_{52}\dot{m}_{st}+C_{53}\dot{m}_g^{1.2}$$

عبارت کلی برای نرخ هزینه مربوط به سرمایه‌گذاری (S/$) برای هر مولفه در معادله زیر داده شده است.

$$\dot{Z}_{i,invest} = \frac{{Z}_{iφ}CRF}{N.3600}$$

CRF فاکتور بازیابی کلی (۱۸/۲ درصد)، N تعداد ساعات کاری نیروگاه (۸۰۰۰ ساعت)، و φ فاکتور نگهداری (۱/۰۶) است. علاوه بر آن، Cf هزینه سوخت به ازای واحد انرژی (۰.۰۰۴ MJ/$) است. جدول زیر نشان‌گر ثابت‌های هزینه پذیرفته شده برای هر مولفه است.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
ثابت‌های هزینه

معادله زیر نشان‌گر هزینه کلی نرخ عملیات است.

$$F = c_{1}\dot{m}_1PCI + \dot{Z}_{AC}+\dot{Z}_{APH}+\dot{Z}_{GT}+\dot{Z}_{HRSG}$$

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

  • نرخ فشرده‌سازی ($$\frac{P_{2}}{P_{1}}$$)
  • بازدهی هم‌آنتروپی کمپرسور $$(\eta_{CA})$$
  • بازدهی هم‌آنتروپی توربین $$(\eta_{GT})$$
  • دمای هوا در خروجی پیش‌گرم کن $$(T_{3})$$
  • دمای گاز سوخت در ورودی توربین $$(T_{4})$$

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

هیوریستیک قطعی
ترکیب ۱ ازدحام ذرات گرادیان هم‌مزدوج
ترکیب ۲ ازدحام ذرات شبه نیوتون
ترکیب ۳ ازدحام ذرات نیوتون

برای حل معادله ترمودینامیکی این مسئله، شبیه‌سازی تخصصی فرایند IPSEpro®‎ نسخه ۶.۰ مورد استفاده قرار گرفته است. IPSEpro®‎ یک شبیه‌سازی فرایند است که برای مدل‌سازی و شبیه‌سازی سیستم‌های حرارتی مختلف از طریق معادلات ترمودینامیکی آن‌ها استفاده می‌شود. این برنامه به وسیله «سیم‌تک» (SimTech) توسعه پیدا کرده و دارای یک رابط کاربرپسند و همچنین، طیف وسیعی از مولفه‌ها است که به کاربر امکان مدل‌سازی و شبیه‌سازی نیروگاه‌های متداول، سیستم‌های تولید هم‌زمان، چرخه‌های خنک کننده، چرخه‌های ترکیبی و بسیاری از دیگر موارد را می‌دهد. روال‌های روش‌های بهینه‌سازی در متلب نوشته شده‌اند و الگوریتم مورد استفاده با IPSEpro®‎ به منظور حل مسئله ترمودیناکی و انجام بهینه‌سازی یکپارچه شده است. برای انجام بهینه‌سازی، محدودیت‌ها برای متغیرهای مسئله به صورتی مقرر شده‌اند که در جدول زیر مشخص شده است.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
محدودیت‌های متغیرها

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

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
محدودیت متغیرها

نتایج بهینه‌سازی در نمودارهای زیر ارائه شده است.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
بهینه‌سازی ترکیبی ۱
الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
بهینه‌سازی ترکیبی ۲
الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع
بهینه‌سازی ترکیبی ۳

معرفی فیلم‌های آموزش بهینه سازی فرادرس

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون و متلب | راهنمای جامع

مجموعه آموزش الگوریتم های بهینه سازی هوشمند فرادرس شامل آموزش‌های متعدد و متنوع در حوزه بهینه‌سازی ریاضیاتی است. در حال حاضر، بیش از ۱۰۹۰۰ دقیقه و نزدیک به ۴۰ عنوان آموزش در این مجموعه وجود دارد. برخی از عناوین آموزش‌های موجود در این مجموعه به همراه توضیحات اجمالی آن‌ها، در ادامه مطلب «الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع» بیان شده‌اند.

  • فیلم آموزش بهینه‌سازی مبتنی بر جغرافیای زیستی یا BBO در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: یک ساعت و پنجاه و یک دقیقه): برای مشاهده فیلم آموزش بهینه‌سازی مبتنی بر جغرافیای زیستی یا BBO در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم چرخه آب برای حل مسائل بهینه‌سازی (مدرس دوره: دکتر علی سعداله، طول مدت دوره: چهار ساعت و چهار دقیقه): برای مشاهده فیلم آموزش  + کلیک کنید.
  • فیلم آموزش الگوریتم بهینه‌سازی جهش قورباغه یا SFLA در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: سه ساعت و سی و پنج دقیقه): برای مشاهده فیلم آموزش الگوریتم چرخه آب برای حل مسائل بهینه‌سازی + کلیک کنید.
  • فیلم آموزش الگوریتم بهینه‌سازی مبتنی بر آموزش و یادگیری یا TLBO (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: یک ساعت و پانزده دقیقه): برای مشاهده فیلم آموزش الگوریتم بهینه‌سازی مبتنی بر آموزش و یادگیری یا TLBO + کلیک کنید.
  • فیلم آموزش الگوریتم PSO، شامل مباحث تئوری و عملی (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: نه ساعت و پنجاه و سه دقیقه): برای مشاهده فیلم آموزش الگوریتم PSO، شامل مباحث تئوری و عملی + کلیک کنید.
  • فیلم آموزش پیاده‌سازی و برنامه‌نویسی الگوریتم ازدحام ذرات (PSO) گسسته باینری (مدرس دوره: دکتر اسماعیل آتش‌پز گرگری، طول مدت دوره: یک ساعت و چهل دقیقه): برای مشاهده فیلم آموزش پیاده‌سازی و برنامه‌نویسی الگوریتم ازدحام ذرات (PSO) گسسته باینری + کلیک کنید.
  • فیلم آموزش الگوریتم فرهنگی یا Cultural Algorithm در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: دو ساعت و سی و شش دقیقه): برای مشاهده فیلم آموزش الگوریتم فرهنگی یا Cultural Algorithm در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم گروه میگوها با پیاده‌سازی در MATLAB (مدرس دوره: دکتر بهداد آرندیان، طول مدت دوره: یک ساعت و بیست دقیقه): برای مشاهده فیلم آموزش الگوریتم گروه میگوها با پیاده‌سازی در MATLAB + کلیک کنید.
  • فیلم آموزش جستجوی ممنوع یا Tabu Search در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: دو ساعت و سی و شش دقیقه): برای مشاهده فیلم آموزش جستجوی ممنوع یا Tabu Search در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم بهینه‌سازی علف هرز مهاجم یا IWO در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: دو ساعت و بیست و شش دقیقه): برای مشاهده فیلم آموزش الگوریتم بهینه‌سازی علف هرز مهاجم یا IWO در متلب + کلیک کنید.
  • فیلم آموزش جامع کلونی زنبور مصنوعی یا Artificial Bee Colony در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: دو ساعت و چهل و یک دقیقه): برای مشاهده فیلم آموزش جامع کلونی زنبور مصنوعی یا Artificial Bee Colony در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم جستجوی هارمونی یا Harmony Search در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: یک ساعت و پنجاه و چهار دقیقه): برای مشاهده فیلم آموزش الگوریتم جستجوی هارمونی یا Harmony Search در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم زنبورها یا Bees Algorithm در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: دو ساعت و یک دقیقه): برای مشاهده فیلم آموزش الگوریتم زنبورها یا Bees Algorithm در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم تکامل تفاضلی، شامل مباحث تئوری و عملی (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: یک ساعت و چهار دقیقه): برای مشاهده فیلم آموزش الگوریتم تکامل تفاضلی، شامل مباحث تئوری و عملی + کلیک کنید.
  • فیلم آموزش الگوریتم کرم شب‌تاب یا Firefly Algorithm در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: یک ساعت و دوازده دقیقه): برای مشاهده فیلم آموزش الگوریتم کرم شب‌تاب یا Firefly Algorithm در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم بهینه‌سازی ملخ (GOA) و پیاده‌سازی آن در MATLAB (مدرس دوره: مهندس حسن سعادتمند، طول مدت دوره: پنج ساعت و هفت دقیقه): برای مشاهده فیلم آموزش الگوریتم بهینه‌سازی ملخ (GOA) و پیاده‌سازی آن در MATLAB + کلیک کنید.
  • فیلم آموزش الگوریتم رقابت استعماری در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: سیزده ساعت و هشت دقیقه): برای مشاهده فیلم آموزش الگوریتم رقابت استعماری در متلب + کلیک کنید.
  • فیلم آموزش شبیه‌سازی تبرید یا Simulated Annealing در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: چهار ساعت و بیست و هشت دقیقه): برای مشاهده فیلم آموزش شبیه‌سازی تبرید یا Simulated Annealing در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم بهینه‌‌سازی شیرمورچه و پیاده‌سازی آن در متلب (مدرس دوره: دکتر بهداد آرندیان، طول مدت دوره: یک ساعت و چهل و نه دقیقه): برای مشاهده فیلم آموزش الگوریتم بهینه‌‌سازی شیرمورچه و پیاده‌سازی آن در متلب + کلیک کنید.
  • فیلم آموزش الگوریتم مورچگان در متلب (مدرس دوره: دکتر سید مصطفی کلامی هریس، طول مدت دوره: شش ساعت و چهل و هفت دقیقه): برای مشاهده فیلم آموزش الگوریتم مورچگان در متلب + کلیک کنید.

پیاده‌سازی الگوریتم بهینه سازی ازدحام ذرات در پایتون

همانطور که پیش از این بیان شد، اساس الگوریتم ازدحام ذرات یا الگوریتم PSO بر این موضوع بنا شده است که با هم کار کردن برای رسیدن به هدف، موثرتر از کار نکردن به صورت تیمی است. در الگوریتم PSO این رفتار اجتماعی با به اشتراک‌گذاری اطلاعات بین یک مجموعه از راه حل‌های ممکن که هر یک «ذره» (Particle) نامیده می‌شوند، انجام شده است. یک ذره (چنانکه پیش از این نیز اشاره شد) به صورت زیر تعریف می‌شود:

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

به اشتراک‌گذاری اطلاعات در الگوریتم ازدحام ذرات محلی و الگوریتم ازدحام ذرات سراسری به دو صورت مختلف انجام می‌شود که در ادامه بیان شده‌اند.

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

در انیمیشن زیر ساز و کار الگوریتم بهینه سازی ازدحام ذرات یا الگوریتم PSO قابل مشاهده است.

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون و متلب | راهنمای جامع

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

نقاطی که در اینجا باید مورد بررسی قرار بگیرند، مقداردهی اولیه ذرات و به روز رسانی‌های آن‌ها هم برای مکان و هم سرعت است.

  • ذرات به طور تصادفی و با استفاده از «توزیع یکنواخت» (Uniform Distribution) مقداردهی اولیه می‌شوند.
  • به روز رسانی‌ها با استفاده از نسخه اندکی ویرایش شده الگوریتم اصلی (ویرایش توسط نویسندگان مقاله اصلی انجام شده) انجام می‌شود. در ادامه، کد پایتون برای پیاده‌سازی الگوریتم PSO ساده ارائه شده است.
برخی از نکاتی که باید پیرامون پیاده سازی الگوریتم بهینه سازی ازدحام ذرات در پایتون به آن‌ها توجه داشت در ادامه بیان شده‌اند.
  1. نقطه اولیه اهمیت زیادی در کارایی الگوریتم بهینه‌سازی دارد. به عنوان یک قاعده سر انگشتی، هرچقدر که نقطه اولیه از بهینه دور باشد، همانقدر طول می‌کشد تا الگوریتم همگرا شود. (این مورد برای همه الگوریتم‌های بهینه‌سازی صحت دارد.)
  2. PSO یک الگوریتم تصادفی است و به روز رسانی‌ها با استفاده از یک فرایند تصادفی انجام می‌شوند. این امر موجب می‌شود که پیگیری راه حل برای اجرای چند فرایند بهینه‌سازی دشوار باشد. اگرچه، همیشه می‌توان از دانه‌دهی (Seed) برای اعداد تصادفی استفاده کرد.
  3. این الگوریتم همیشه راه حل بهینه سراسری را پیدا نمی‌کند، اما در پیدا کردن بهینه‌ای که بسیار نزدیک به بهینه سراسری است، عملکرد بسیار خوبی دارد. برای تابع sphere بهینه سراسری در (0, 0, 0) است. کد الگوریتم PSO در پایتون که در اینجا ارائه شده است، نقطه دیگری را پیدا می‌کند که خیلی بد نیست.
  4. بسته به تعداد ذرات، همگرایی ممکن است زمان بیشتری طول بکشد. به طور کلی، بهتر است که این کار بیش از ۵۰ تکرار طول نکشد.
  5. برای توابع دشوار، ممکن است نیاز به تکرارهای بیشتری پیش از پیدا کردن بهترین راه حل باشد. برای مثال، می‌توان بین ۵۰۰ تا ۱۰۰۰ تکرار داشت.

کد الگوریتم بهینه‌سازی ازدحام ذرات در متلب

در ادامه، یک پیاده‌سازی ساده از الگوریتم بهینه‌سازی ازدحام ذرات در متلب نیز ارائه شده است.

Main

ObjectiveFunction

PSO

کد الگوریتم بهینه سازی ازدحام ذرات در جاوا

در ادامه، کد الگوریتم PSO در جاوا انجام شده است.

معرفی فیلم‌های آموزش الگوریتم PSO فرادرس

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

فیلم آموزش مبانی محاسبات تکاملی و بهینه‌سازی هوشمند

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

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

  • برای دیدن فیلم آموزش مبانی محاسبات تکاملی و بهینه‌سازی هوشمند + کلیک کنید.

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

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

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

  • برای دیدن فیلم آموزش پایتون برای پیاده‌سازی مسائل بهینه‌سازی + کلیک کنید.

فیلم آموزش الگوریتم PSO — شامل مباحث تئوری و عملی

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

طول مدت این دوره آموزشی برابر با نه ساعت و پنجاه و سه دقیقه و مدرس آن، دکتر سید مصطفی کلامی هریس است. این دوره آموزشی برای افرادی مناسب است که قصد دارند الگوریتم PSO را از پایه همراه با مباحث تئوری و پیاده‌سازی عملی بیاموزند. از جمله سرفصل‌های این دوره آموزشی می‌توان به معرفی الگوریتم بهینه‌سازی ازدحام ذرات یا الگوریتم PSO ، حل مساله دیسپاچینگ اقتصادی توسط الگوریتم PSO، حل مسائل گسسته با استفاده از الگوریتم PSO ، حل مساله فروشنده دوره گرد با الگوریتم PSO ، برازش منحنی و مدل سازی بابهره‌گیری از الگوریتم PSO ، حل مساله کوله پشتی (knapsack Problem) با الگوریتم PSO و طراحی مسیر (Path Planning) با الگوریتم PSO اشاره کرد.

  • برای دیدن فیلم آموزش الگوریتم PSO — شامل مباحث تئوری و عملی + کلیک کنید.

فیلم آموزش پیاده سازی ترکیب الگوریتم ژنتیک و PSO در متلب 

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

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

  • برای دیدن فیلم آموزش پیاده‌سازی ترکیب الگوریتم ژنتیک و PSO در متلب + کلیک کنید.

فیلم آموزش پیاده‌سازی و برنامه‌نویسی الگوریتم ازدحام ذرات (PSO) گسسته باینری

الگوریتم بهینه سازی ازدحام ذرات | پیاده سازی الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع

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

  • برای دیدن فیلم آموزش پیاده‌سازی و برنامه‌نویسی الگوریتم ازدحام ذرات (PSO) گسسته باینری + کلیک کنید.

نتیجه‌گیری

در مطلب «الگوریتم بهینه سازی ازدحام ذرات | کد الگوریتم PSO در پایتون ، متلب و جاوا | راهنمای جامع»، مباحث پایه‌ای روش PSO بیان، الگوریتم PSO تشریح و مزایا و معایب این روش مورد بررسی قرار گرفت. همچنین، روش‌های ترکیبی با الگوریتم PSO که در واقع ترکیبی از روش‌های قطعی و هیوریستیک هستند نیز به منظور بررسی مزایا و معایب آن‌ها مورد بررسی قرار گرفتند. سپس، مثال‌هایی پیرامون الگوریتم PSO ارائه و پیاده‌سازی الگوریتم ازدحام ذرات در زبان‌های برنامه‌نویسی پایتون، متلب و جاوا انجام شد.

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

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

 

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

الهام حصارکی (+)

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

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *