پایان نامه با کلید واژه های الگوریتم، کلی، بهینه

قبل‍ی شود را در خلال هر نسل تع‍ی‍ین و بررس‍ی م‍یکند. مقدارG برای روشهای ژتت‍یک‍ی سنت‍ی برابر یک م‍یباشد. در این صورت در ط‍ی هر نسل کل جمع‍یت جایگزین نسل قبل‍ی م‍یشوند. به این دل‍یل تعداد ارزیابیهای تابع صلاح‍یت بس‍یار زیاد و زمان پردازش بطور نسب‍ی بالا خواهد بود.
یک‍ی دیگر از معایب روشهای سنت‍ی این است که احتمال باق‍ی ماندن گونههای خوب در نسل بعدی کم م‍یباشد که موجب اختلال در روند همگرای‍ی خواهد شد. به منظور حداقل کردن گس‍یختگ‍ی در فرایند جستجو و بهبود کارای‍ی تع‍ی‍ین شکاف نسل کوچک مف‍ید م‍یباشد. ویو و چاو مقدارG را به صورت زیر پ‍یشنهاد نمودهاند:
(3-17)
رابطه کنون‍ی نشانگر آن است که در هر مرحله تنها دو رشته برای تکث‍یر انتخاب شده و دو رشته فرزند جایگزین دو رشته بدترین افراد جمع‍یت کنون‍ی خواهند شد و بق‍یه افراد ثابت خواهند بود. بنابراین به مقدار() از ارزیابی تابع صلاح‍یت در هر نسل کاهش م‍ییابد و در نت‍یجه تلاش محاسبات‍ی بطور چشمگیری کاهش خواهد یافت.
لازم به ذکر است دو رشته جدید تول‍ید شده صلاح‍یت بالاتری در مقایسه با دو رشته حذف شده قبل‍ی از جمع‍یت کنون‍ی خواهند داشت. مقدار تابع هدف ن‍یز بطور پایدار همگرا شده و کارای‍ی محاسبات‍ی بهبود عمده ای م‍ییابد. سه پارامتر اندازه جمع‍یت، احتمال پ‍یوند و احتمال جهش پارامترهای کنترل کننده الگوریتم ژنتیک م‍یباشند و نقش مهم‍ی را در عملکرد الگوریتم ژنت‍یک ایفا م‍یکنند.
?3-3-6- مزایای الگوریتم ژنتیک
برخی از مزایای الگوریتم ژنتیک را میتوان به شرح ذیل نام برد:
1. بهینهسازی را هم توسط متغیرهای پیوسته و گسسته انجام میدهد.
2. اطلاعات مشتق شده لازم نمیباشد.
3. به طور هم زمان از یک نمونه وسیع تابع هدف جستجو میکند.
4. با تعداد زیادی از متغیرها سر و کار دارد.
5. برای محاسبهگرهایی که به طور موازی کار میکنند، بسیار مناسب است.
6. متغیرهایی که تابع هدف بسیار پیچیده دارند را بهینه میکند.
7. لیستی از متغیرهای بهینه تهیه میکند و تنها یک راه حل ندارد.
این مزایا سبب تولید نتایج جالبی شده است در حالی که برخی از روشهای بهینهیابی ناموفق هستند.
3-4- الگوریتم بهینه یابی گروه ذرات (PSO)30
3-4-1- مقدمه
روش بهینهیابی گروه ذرات یکی دیگر از الگوریتمهای تکاملی الهام گرفته از طبیعت، بر اساس تکرار و احتمال است. یک جمعیت اساس این تکنیک بهینهیابی است که الهام گرفته شده از رفتار اجتماعی پرندگان مهاجر و یا گروهی از ماهیها در هنگام مهاجرت یا در پیدا کردن غذا میباشد. هر عضو از این جامعه از اکتشافات خود و تجربیات گذشتهی همه اعضای گروه در جهت رسیدن به اهداف خود استفاده میکند.
شکل 3-9- مقایسه حرکت جمعی و انفرادی پرندگان[149]
ایده PSO ، توسط کندی و ابرهارت در سال 1995 [149] در پاسخ به مجموعه ای از پرسشها، که چرا پرندگان و ماهیها زندگی گروهی را به زندگی فردی ترجیح میدهند؟، حاصل رفتار اجتماعی آنها چیست؟ و رفتار اجتماعی آنها نسبت به زندگی اجتماعی انسانها چه مزایایی دارد؟، مطرح شد. همچنین در سال 1986، Reynolds [150] پس از سلسله تحقیقاتی گسترده مدلی متناسب با حرکت گروهی حیوانات ارائه داد،?که از سه قانون ساده زیر تبعیت میکند:
جدایی: هر عضو سعی میکند در صورتیکه به همسایگانش بسیار نزدیک شد، از آنها فاصله بگیرد.
جهتگیری: هر عضو سعی میکند در جهت میانگین جهت حرکت همسایگانش حرکت کند.
همگرایی: هر عضو سعی میکند به مکان میانگین همسایگان مجاورش حرکت کند.
شکل3-10- نحوه حرکت ذره در میان گروه[149]
کندی و ابرهارت برای آنکه بتوانند مدلسازی این ایده را براحتی صورت دهند،?قوانین آنرا بصورت دیگری مدل کردند. آنها در ابتدا یک هدف مشترک که همه ذرات تمایل رسیدن به آن دارند،?تعریف کردند و آنرا Roost ?نامیدند. این هدف مشترک را میتوان منزلگاه برای پرندگان یا محل غذا برای ماهیها تعریف کرد.?این سه قانون عبارتند از?:
1. هر عضو به مکان محل منزلگاه جذب میشود.
2. هر عضو به خاطر میسپارد در کدام مکان به منزلگاه نزدیکتر بوده است.
3. هر عضو اطلاعات خود را با همسایگانش درباره نزدیکترین محل به منزلگاه به اشتراک میگذارد.
شکل3-11- قوانین حرکت ذرات[149]
در نهایت، پس از طی این فرآیند سرانجام همه پرندگان در منزلگاه فرود میآیند.
3-4-2- نحوه ارتباط بین اجزاء در فرآیند رسیدن به هدف
نحوه ارتباط و تبادل اطلاعات بین اجزاء مختلف با استفاده از همسایگی ذرات صورت میگیرد. در حقیقت همسایگی،?نحوه اطلاع ذرات از نقطه بهینه کلی در بین سایر ذرات را تعیین میکند. همسایگی بصورت کلی به دو قسمت تقسیم میشود که عبارتند از:
3-4-2-1- همسایگی جغرافیایی
در این همسایگی محیط به چند قسمت تقسیم شده،?ذرات هر قسمت صرفاً از نقطه بهینه در محیط جغرافیایی خود،?مطلع میشوند. بعبارتی ما فضای جستجو را به چندین فضای جستجو تقسیم میکنیم، در?هر?کدام بهینهسازی را انجام میدهیم، در انتها جوابهای نهایی را با هم مقایسه میکنیم و بهترین نقطه بهینه کلی را از بین آنها انتخاب میکنیم. مزیت این روش، سرعت بیشتر بوده چون همه ذرات از بهینه کلی در بین کل ذرات مطلع نمیشوند. اما اگر بهینه کلی در جایی بین این محدودههای جغرافیایی بود (ممکن است همه ذرات در کل فضای جستجو پراکنده نباشند) آن نقطه از دست میرود علاوه بر آن بعلت آنکه هر چه ذرات کمتری در کل فضای جستجو حرکت کنند احتمال آنکه نقطه بهینه اصلی از دست برود و در بهینه محلی گرفتار شود، بیشتر است.
شکل3-12- همسایگی جغرافیایی[149]
3-4-2-2- همسایگی به شیوه شبکه های اجتماعی
در این روش،?شبکههای اجتماعی خاصی نحوه اشتراک اطلاعات بین ذرات را تعیین میکنند. بعنوان مثال اگر هر ذره با دو ذره مجاورش در ارتباط باشد شبکه حلقوی تشکیل میشود. هر قدر ذرات بیشتری با یکدیگر در ارتباط باشند دقت الگوریتم بالاتر و سرعت اجرای آن بیشتر خواهد بود. در شکل (3-13) چند نمونه از گرافهای متداول شبکههای اجتماعی نشان داده شده است.
شکل3-13-گراف نحوه ارتباط در همسایگی به شیوه شبکههای اجتماعی[149]
در مقایسه روشهای مختلف همسایگی، روش مقایسه همه ذرات با بهترین کل?(global best) جواب بهتری در مقایسه با سایر روشها خواهد داشت که با تعداد تکرار کمتری کل الگوریتم به جواب خواهد رسید اما در عین حال برای هر بار اجرای الگوریتم،?حافظه و زمان بیشتری مورد نیاز است.
3-4-3- تشریح روش گروه ذرات
روش PSO در طبیعت به صورت تصادفی است. این الگوریتم از یک بردار سرعت برای تعیین موقعیت جدید ذرات استفاده میکند. بردار سرعت براساس اطلاعات ذخیره شدهی هر ذره و اطلاعات به دست آمده از گروه ذرات تشکیل میشود. موقعیت جدید ذرات در تکرار ام با استفاده از روابط زیر به دست میآید:
(3-18)
در این رابطه مقدار گام زمانی است که در تمام روابط برابر یک در نظر گرفته میشود، سرعت ذرات در مرحله ام است که از ترکیب سه فاکتور سرعت قبلی ، حرکت در جهت بهترین حل محلی و حرکت در جهت بهترین حل کلی، تشکیل شده است:
(3-19)
که در این رابطه وزن اینرسی برای کنترل تاثیر سرعت قبلی است؛ و دو عدد تصادفی هستند که به طور یکنواخت در محدوده توزیع شدهاند و و ضرایب شتاب هستند. موقعیت و سرعت اولیه ذرات با استفاده از روابط زیر محاسبه میگردد:
(3-20)
(3-21)
در این رابطه یک عدد تصادفی است که در محدوده قرار دارد و و به ترتیب مرزهای پایینی و بالایی متغیرهای طراحی هستند.
نقش مهمی در رفتار همگرایی الگوریتم ایفا میکند، از آنجایی که این پارامتر برای کنترل توانایی اکتشاف گروه ذرات به کار گرفته میشود. این پارامتر به طور مستقیم سرعت جاری ذره را تحت تاثیر قرار میدهد. مقادیر بزرگ پارامتر باعث افزایش جستجوی کلی در فضای طراحی میگردد، در حالی که مقدار کم این پارامتر باعث تمرکز جستجو در یک فضای محدودی میشود. شکل زیر موقعیت و سرعت ذره، قبل و بعد از حرکت را نشان میدهد.
شکل 3-14- تعیین موقعیت و سرعت جدید ذره
مراحل انجام این الگوریتم به شرح زیر است:
مرحله اول- تعیین تصادفی موقعیت و سرعت اولیه ذرات به طوری که در سرتاسر فضای جستجو گسترده شوند و از مرزها عبور نکنند.
مرحله دوم- تعیین مقادیر تابع هدف ذرات.
مرحله سوم- بازتعریف بهترین حل محلی ، و بهترین حل کلی .
مرحله چهارم- تعیین موقعیت و سرعت جدید ذرات.
مرحله پنجم- تکرار مراحل 2 تا 4 تا یک معیار توقف ارضا گردد.
3-4-3-1- همگرایی الگوریتم PSO
با جایگذاری رابطه سرعت در موقعیت ذرات و مرتب کردن این رابطه، موقعیتامین ذره در تکرار برابر است با:
(3-22)
و با جایگذاری رابطه موقعیت در رابطه سرعت ذرات و مرتب کردن آن، خواهیم داشت:
(3-23)
روابط (3-23) را میتوان به شکل ماتریسی زیر نوشت:
(3-24)
که این رابطه میتواند به عنوان یک سیستم دینامیک-گسسته برای PSO بیان شود و حالتی است که در معرض ورودی خارجی قرار دارند و اولین و دومین ماتریس به ترتیب متناظر با ماتریسهای دینامیک و ورودی است.
با فرض این که هیچ تحریک کننده خارجی در سیستم دینامیک وجود ندارد، بنابراین ثابت است (ذرات به موقعیت بهتر نمیرسند)، سپس یک رفتار همگرا میتواند به دست آید. در چنین حالتی اگر سپس که ماتریس دینامیک به صورت زیر حاصل میشود:
(3-25)
که این رابطه زمانی برقرار است که و و هردو همزمان با صفر شوند. توجه شود که چنین موقعیتی لزوما یک مینیمم محلی و یا کلی نیست و در عوض یک نقطه تعادل است. هرچند که اگر یک محرک خارجی در سیستم دینامیک وجود داشته باشد به طوری که موقعیتهای مینیم محلی و کلی بهتر، از فرآیند بهینهیابی پیدا شود، چنین نقطهای به سمت نقطه بهینه بهبود خواهد یافت.
3-4-3-2- بهبودهای الگوریتم
به علت اهمیت وزن اینرسی در کنترل رفتار PSO در جستجوی محلی و کلی الگوریتم، بهبودهای زیر اعمال میگردد:
– یک بهبود دینامیکی به وسیله اعمال یک جستجوی کلی اولیه به وسیله یک وزن اینرسی زیاد و سپس کاهش آن به طوری که اکتشاف الگوریتم به سمت جستجوی محلی برود، صورت میگیرد. دو روش اصلی برای چنین تغییرات دینامیکی به کار میرود.
1- یک تغییر وزن اینرسی دینامیک توسط Shi و Eberhart [151] معرفی شده است که مقدار وزن اینرسی به صورت خطی با افزایش شماره تکرار کاهش پیدا میکند:
(3-26)
2- روش دیگری توسط Fourie و Groenwold پیشنهاد شده است که کاهش دینامیکی مقدار براساس یک ضریب در زمانی که هیچ بهبودی در تعداد از پیش تعیین شدهای تکرار متوالی الگوریتم حاصل نگردد، انجام میگیرد [152]:

مطلب مرتبط با این موضوع :  منبع پایان نامه دربارهطبقه بندی، ISO

دیدگاهتان را بنویسید