الگوریتم ژنتیک و قابلیت جستجو


Widget not in any sidebars
شبه برنامه و الگوریتم نشان داده شده در شکل ٣-٩، نحوه عملکرد روش بهینهسازى تجمعى ذره را در مسائل بهینه سازى تک هدفه نشان مىدهند. ابتدا موقعیت و سرعت ذرات در جمعیت اولیه به صورت تصادفى ایجاد مىشود. بهترین تجربه شخصى مربوط به هر ذره محاسبه شده و بهترین تجربه گروهى نیز انتخاب مىگردد. در تکرار دوم، با حرکت ذرات با معادلات (٣-17) و (٣-18)، موقعیت جدید ذرات ایجاد مىشود. در این مرحله نیز بهترین تجربه شخصى و بهترین تجربه گروهى تعیین مىگردد. این فرایند تکرار مىشود تا شرط خاتمه برقرار شود. معمولاً شرط خاتمه رسیدن به تعداد تکرار و یا دقت معینى مى باشد. در آخرین تکرار بهترین تجربه گروهى به عنوان نقطه بهینه معرفى مىگردد.]24[
شکل3-10: شبه برنامه روش تجمعی ذره
٣-٣-٣-۵ بررسى ضریب وزن و ضرایب یادگیرى
ضرایب الگوریتم تجمعى ذره اهمیت بسیارى در سرعت، همگرایى و بازدهى این الگوریتم دارد. ضریب وزن در همگرایى ذرات، نقش حیاتى را ایفا مىکند. این ضریب تعادل بین قابلیت جستجوى محلى و جستجوى سراسرى در جمعیت را تنظیم مىکند. مقادیر بزرگ ضریب مذکور به جستجوى سراسرى کمک مىکند، در حالى که مقادیر کوچک آن، جستجوى محلى را آسان مىسازد. بنابراین مقدارى براى ضریب وزن مناسب است که بین جستجوى محلى و سراسرى تعادل برقرار کند و متعاقبا جواب بهینه در کم ترین تعداد تکرار، پیدا شود. در ابتدا ضریب وزن به صورت ثابت در نظر گرفته مىشد، اما نتایج تجربى نشان داد که بهتر است در شروع، مقدار آن بزرگ انتخاب شود تا جستجوى گستردهترى در سراسر فضاى جستجو صورت گیرد و به تدریج براى یافتن پاسخ دقیق تر، مقدار آن کاهش یابد[43].
تعادل بین جستجوى محلى و سراسرى، در هنگام عملیات جستجو، نکتهاى حیاتى براى یک الگوریتم جستجوى مستقیم به شمار مىآید. همان طور که گفته شد در الگوریتم تجمعى ذره این وظیفه به عهده ضریب وزن بوده و با تغییر این ضریب، قابلیت هاى جستجوى این الگوریتم تنظیم مىشود.
ابتدا، مقدار ضرایب یادگیرى برابر عدد ثابت ٢ در نظر گرفته مىشدند[15]. اما پس از مدتى مشخص گردید که علاوه بر ضریب وزن، ضرایب یادگیرى نیز نقش مؤثرى بر تنظیم جستجوى محلى و سراسرى دارند[44]. به طورى که با افزایش ضریب تجربه شخصى، جستجوى سراسرى بهتر و با افزایش ضریب تجربه گروهى، جستجوى محلى بهترى صورت مىگیرد. در مرجع [45]، تأثیر ضرایب بر الگوریتم تجمعى ذره مطالعه شده است. براى محدود کردن میزان حرکت ذرات، سرعت ذرات در بازه [ ] در نظر گرفته مىشود و مقادیر بزرگ تر و کوچک تر به این بازه تصویر مىشوند. در این پایان نامه سرعت بیشینه برابر با 10% بازه جستجو در نظر گرفته شده است و همچنین براى ضریب وزن در ابتداى الگوریتم با مقدار بزرگترى شروع شده تا جستجوى گستردهترى انجام گیرد و با طى شدن تکرارها مقدار آن کاهش مىیابد تا ذرات فرصت همگرایى به سمت نقطه بهینه را بیابند. همچنین براى اینکه مقادیر ضرایب یادگیرى و ضریب وزن بهینه باشد، از روش ضرایب انقباضى که توسط کندى ارائه شد، مورد استفاده قرار مى گیرد. این روش در مرجع [46] بطور کامل اثبات شده است و حالت بهینه ضرایب براى شروع الگوریتم در نظر گرفته شده است. لازم بذکر است تنظیمات این روش طورى است که تعادل مناسبى بین توانایى پروراندن پاسخ هاى فعلى (توانایى استخراج) و توانایى تولید پاسخهاى جدید (توانایى جستجو) برقرار مىکند. سپس با توجه به نتایج اثبات شده در [43] مبنى بر اینکه کاهش ضریب وزن با پیش روى الگوریتم در تکرارهاى بالاتر موجب دستیابى به پاسخ دقیق تر مىشود، در پایان هر تکرار در الگوریتم ، ضریب 0.95 در ضریب وزنى ضرب مىشود تا به تدریج کاهش یابد.
٣-٣-۴ الگوریتم ترکیبى ژنتیک و تجمعى ذره
در سالهاى اخیر محققان بسیارى به ترکیب روش بهینه سازى تجمعى ذره با سایر روشهاى بهینهسازى از جمله الگوریتم ژنتیک، پرداختهاند [41و47]. عملگرهاى تکاملى مانند انتخاب، ترکیب و جهش از الگوریتم ژنتیک به شکلهاى مختلفى در این روش اعمال شدهاند. در ادامه به دو روش ترکیب این دو الگوریتم اشاره شده و جزییات آن تشریح مىشود.
٣-٣-۴-١ الگوریتم ترکیبى HGAPSO
یکى از روشهاى ترکیب الگوریتم ژنتیک و بهینه سازى تجمعى ذره، روشى به نام HGAPSO است ]41و47[. این روش داراى سه عملگر اصلى مى باشد: ارتقاء، ترکیب و جهش. قبل از آنکه این سه عملگر تشریح شوند، ابتدا نحوه شروع این الگوریتم ترکیبى توضیح داده مى شود.
نحوه شروع: در این روش، براى هر دو الگوریتم ژنتیک و تجمعى ذره، جمعیت یکسانى در نظر گرفته مىشود. در ابتدا جمعیت به صورت تصادفى تولید مىشود. اعضاى جمعیت را مىتوان هم به عنوان کروموزوم در روش الگوریتم ژنتیک و هم به عنوان ذره در روش تجمعى ذره در نظر گرفت.
ارتقاء: در هر مرحله، بعد از آن که مقدار برازندگى همه اعضاى جمعیت محاسبه شد، نیمى از اعضاى جمعیت که داراى عملکرد بهترى هستند، انتخاب مىشوند. این افراد به عنوان نخبه در نظر گرفته مىشوند. ابتدا ارتقاء مىیابند.
ترکیب: براى اینکه اعضاى ایجاد شده توسط عملگر ترکیب، عملکرد بهترى داشته باشند، والدین از بین نخبگان ارتقاء یافته انتخاب مىشوند. فرایند انتخاب والدین را مىتوان توسط عملیاتى همچون تورنمت، چرخ رولت و غیره انجام داد. با انجام عملیات ترکیب از هر دو والد ، دو فرزند تولید مىگردد. معمول ترین عملگرهاى ترکیب، روش ترکیب k نقطهاى، روش ترکیب هموار مىباشند. در [47]، از روش ترکیب دونقطهاى استفاده شدهاست.
جهش: در این روش ترکیبى، جهش همزمان با ترکیب رخ مىدهد. جهش، عملگرى است که ژنهاى ناهمسان مجاور یک کروموزوم را به طور تصادفى تغییر داده و یک کروموزوم جدید ایجاد مىکنند. در [47]، از روش جهش یکنواخت استفاده شده است.
٣-٣-۴-٢ روش ترکیبى GAPSO
روش معرفى شده در مثال قبل، قدرت نسبتاً بیشترى نسبت به الگوریتم ژنتیک و تجمعى ذره به تنهایى داشت، ولى این برترى براى مسئله موجود در این پایان نامه برای مقایسه با نتایج تکامل تفاضلی زیاد محسوس نبود. براى بالا بردن سرعت و قدرت همگرایى الگوریتم در این پایان نامه از روشى مشابه روش مطرح شده در ]48[ استفاده شدهاست. در [48] براى نصف تکرارها از الگوریتم ژنتیک و براى بقیه از روش تجمعی ذره بر روى نتایج حاصل از الگوریتم ژنتیک اعمال شد ولى در الگوریتم استفاده شده در این مسئله، در هر تکرار از الگوریتم ژنتیک کروموزومها به صورت ذره وارد الگوریتم تجمعی ذره شده و پس از 3 تکرار به الگورتم ژنتیک بازگردانده میشوند.
٣-٣-۴-٢-١ روند کلى الگوریتم
در این الگوریتم از روش تجمعى ذره و الگوریتم ژنتیک استفاده شده است. در ابتدا جمعیت به صورت تصادفى در بازه موردنظر تولید مىشود. اعضاى جمعیت را مىتوان هم به عنوان کروموزوم در روش الگوریتم ژنتیک و هم به عنوان ذره در روش تجمعى ذره در نظر گرفت. سپس مقادیر تابع هدف و پارامتر هاى اولیه روش تجمعى ذره (بهترین تجربه شخصى و بهترین تجربه محلى) طبق روش تجمعى ذره محاسبه مىشود. در هر تکرار الگوریتم، بر روى کل جمعیت اولیه، ابتدا عملگرهاى الگوریتم ژنتیک وارد مىشوند و جمعیت تولید شده به عنوان جمعیت جدید قرار داده مىشوند. در این مرحله با توجه به احتمال جهش و ترکیب، بر روى جمعیت اولیه اپراتورهاى ژنتیک وارد مىشود. لازم بذکر است در این الگوریتم ژنتیک براى عملگر ترکیب از روش ترکیب محاسباتى که در مسائل پیوسته معمولاً بهتر جواب مىدهد، استفاده شده است و براى عملگر جهش، از روش جهش گاوسى استفاده مىشود.
بعد از مرتب شدن کل اعضاى تولید شده که حاصل از جمعیت اولیه و جمعیت حاصل از ترکیب و جهش است، به تعداد جمعیت اولیه از بهترینهاى جمعیت انتخاب و براى این تعداد ذرات انتخابى، اپراتورهاى اولیه روش پیشنهادى ذره یعنى بهترین تجربه شخصى و بهترین تجربه کل جمعیت محاسبه مىشود. سپس این جمعیت جدید به عنوان جمعیت اولیه براى روش تجمعى ذره فرستاده مىشوند. سپس بر روى همه اعضاى جمعیت موجود، عملگرهاى روش تجمعى ذره وارد شده و جمعیت حاضر را هر چه بیشتر به سمت نقطه بهینه هدایت مىکند. در روش تجمعى ذره از روش ضرایب انقباضى [46] براى برقرار کردن تعادل مناسب بین جستجوى محلى و جستجوى سراسرى استفاده شده است. در پایان هر تکرار در الگوریتم ضریب ٠.٩۵ در ضریب وزنى ضرب مىشود تا به تدریج کاهش یابد. کاهش ضریب وزن با توجه به نتایج اثبات شده در [43]، با پیش روى الگوریتم در تکرارهاى بالاتر موجب دستیابى به پاسخ دقیق تر مى شود.
همچنین با توجه به اینکه معمولاً روش تجمعى ذره در پیدا کردن پاسخ بهینه محلى توانایى همگرایى بیشترى نسبت به روش الگوریتم ژنتیک دارد [49و50]، در این الگوریتم در هر تکرار تعداد اجرا شدن هر کدام از روش هاى الگوریتم ژنتیک و روش تجمعى ذره، توسط کاربر قابل تنظیم مىباشد. تعداد زیرتکرار هر یک از الگوریتم هاى ترکیب شده در تکرار کلى GAPSO یا به عبارتى دفعات اعمال شدن عملگرهاى ژنتیک و تجمعى ذره بر روى جمعیت، از ابتداى الگوریتم به صورت نسبت 1 به 3 میباشد، یعنی یک تکرار برای الگوریتم ژنتیک و 3 تکرار برای روش تجمعی ذره. لازم بذکر است اگر تعداد دفعات اجراى هر کدام از الگوریتم هاى ترکیب شده را صفر قرار دهیم، الگوریتم دیگر به طور خاص اجرا مىشود، مثلاً با صفر قرار دادن تعداد زیرتکرار الگوریتم ژنتیک الگوریتم کلى تبدیل به روش تجمعى ذره خالص مىشود. این الگوریتم ترکیبى از قدرت هر دو الگوریتم ژنتیک و تجمعى ذره بطور هم زمان بهره مىبرد و همچنین قابلیت تبدیل شدن به هر کدام از الگوریتم ها را دارا مىباشد. در ادامه شبه کد این الگوریتم در شکل ٣-11 نشان داده شده است]51[.
شکل3-11: شبه برنامه روش GAPSO
با توجه به اینکه هر کدام از الگوریتمهاى بهینهسازى، متناسب با ماهیت مسئله مى تواند بر دیگرى برترى داشته باشد و براى اینکه کارایى این الگوریتمهاى تک هدفى بر روى مکانیزم ششمیلهای مشخص شود، در فصل بعد مقایسهاى از آنها در به دست آوردن مقدار بهینه توابع هدف مسئله موردنظر در این پایان نامه، بررسى مىشوند.
٣-۴ روش هاى بهینه سازى چند هدفى
در اکثر زمینههاى علمى، مسائل بهینهسازى بیش از یک تابع هدف دارند. همچنین در بیشتر این مسائل، اهداف موردنظر که مىبایست بهینه شوند، در تقابل با یکدیگر هستند. در چنین حالتى یافتن جوابى که بهترین تعادل ممکن را بین اهداف برقرار سازد، مطلوب است. به طور کلى هنگام حل یک مسئله بهینهسازى چندهدفى، دستیابى به نتایج زیر مدنظر است: