فصل اول
آشنایی با برخی از انواع الگوریتم¬های بهینه سازی
مقدمه ای بر بهینه سازی
بهینه سازی در ادبیات مهندسی به فرآیند بهتر کردن هر چیزی اطلاق می شود. یک مهندس و یا یک محقق ایده جدیدی خلق می کندو بهینه سازی به این ایده خلق شده کیفیت می بخشد در فرآیند بهینه سازی تغییراتی بر روی ایده اولیه انجام می شود و با نتایج حاصل از این تغییرات ایده اولیه بهبود می یابد. مادآمی که بتوان ایده مورد نظر را در غالب الکترونیکی نوشت کامپیوتر وسیله ای مناسب برای بهینه سازی خواهد بود. در زبان برنامه نویسی و ریاضیات بهینه سازی را فرآیند تعریف می کنند که در آن از طریق انتخاب و طراحی ساختارهای داده¬ای الگوریتم ها و دستورالعمل های مناسب به تولید برنامه های کار آمد(کوچکتر یا سریعتر)دست پیدا کرد. در تعاریف دیگر در بحث بهینه سازی در علوم مهندسی بهینه سازی به معنای رسیدن به وضعیتی بهینه در محاسبات مربوط میباشد که در آن کمترین محاسبه و بیشترین میزان بازدهی میسر می شود. در دهه های اخیر همزمان با مطرح شدن مسا ئل بهینه سازی جدید، روش های جدید بهینه سازی نیز ابداع شدند. مهمترین گروه از این روشهای بهینه سازی روش های تکاملی می باشند که توانایی حل مسائل با ابعاد بزرگ و تعداد متغیرهای زیاد را دارا هستند از سوی دیگر مسائل مورد توجه در علوم مهندسی ازجمله مسائلی هستند که غالبا دارای متغیرهای زیاد می باشند. در این بحث بهینه سازی توابع مطرح میباشد، از این رو استفاده از روشهای تکاملی چندگاه در این گونه مسائل در سال های اخیر مورد توجه قرار گرفته است به همین دلیل در حل مسائل تک هدف مهندسی از الگوریتم بهینه سازی ذرات استفاده بسیاری شده است بهینه سازی توابع ریاضی و یافتن و رسم یک سری اطلاعات در برخی از اطلاعات و داده های غیر خطی از مسائلی بوده که همواره این مسائل مد نظر می باشد .که الگوریتم ها شامل 1- الگوریتم فرا اکتشافی است که از حرکت گروهی از پرندگان یا ماهی ها می باشد 2- الگوریتم ژنتیک، الگوریتم ژنتیک تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی فرگشتی مانند وراثت و جهش استفاده میکند. این الگوریتم برای اولین بار توسط جان هلند معرفی شد. 3-الگوریتم تکاملی کاربرد این روش ها و بهینه سازی و یافت تابع مورد نظر توجه بسیاری از محققین قرار گرفته است.
1- 1 الگوریتم اجتماع پرندگان
الگوریتم بهینه سازی ذرات ،یک الگوریتم بهینه سازی فرا اکتشافی است که از حرکات گروهی از پرندگان یا دسته ای از ماهیان که به شکل گروهی زندگی می کنند، الگوبرداری شده است. این الگوریتم از مفهوم اثر متقابل اجتماعی برای حل کردن مسئله استفاده می کند. در واقع این الگوریتم رفتار گروهی از پرندگان را شبیه سازی می کند به سنا ریو زیر توجه کنید:
یک گروه از پرندگان بطور تصادفی در حال جستجوی غذا دریک ناحیه می باشند و تنها یک قطعه غذا در ناحیه مورد جستجو قرار دارد و هیچ یک از پرندگان اطلاعی از مکان غذا ندارند اما می دانند که در هر مرحله چه فاصله ای از غذا دارند. در واقع مسئله در اینجا یافتن بهترین راه برای پیدا کردن غذا می باشد. یک روش موثر دنبال کردن پرندگانی می باشد که کمترین فاصله را با غذا دارند pso مانند همه ی الگوریتم های تکاملی دیگر، با ایجاد یک جمعیت تصادفی از افراد شروع می شود که در اینجا با عنوان یک گروه از ذره ها خوانده می شوند. مشخصات هر ذره در گروه براساس مجموعه ای از پارامتر ها تعیین می شود. در این روش هر ذره یک نقطه از فضای جواب مسئله را نشان می دهد .هر کدام از ذرات دارای حافظه هستند یعنی بهترین موقعیتی که در فضای جستجو به آن می رسند را بخاطر می سپارند. به طور کلی این الگوریتم از یک مجموعه از نقاط(ذره)به مجموعه ای دیگر از نقاط در یک تکرار واحد، حرکت می کند که به طور احتمال با استفاده از ترکیب قوانین بهبودهایی حاصل می دهد.
در واقع یک الگوریتم رایانه‌ای مبتنی بر جمعیت برای حل مسئله است. این تکنیک ها بسیار رشد کرده‌اند و نسخه اصلی این الگوریتم به طور واضحی در نسخه های امروزی قابل شناخت است. تاثیر گذاری اجتماعی و یاد گیری اجتماعی یک شخص را قادر میسازد تا ثبات دانستنی‌هایش را برقرار سازد. انسانها مسائل شان را به کمک صحبت با دیگران و نیز به کمک برهم کنش با باورهای شان، گرایش هایشان و تغییر رفتارشان حل می کنند؛ این تغییرات را می توان به طور نمونه به شکل حرکت افراد به سوی یکدیگر در فضای آگاهی اجتماعی مجسم کرد. ساختار ارتباطی یا شبکه اجتماعی برای واگذار کردن هر همسایگی به یک فرد تعریف شده تا آن فرد با آن همسایگی بر هم کنش داشته باشد. سپس گروه کارگزاران به عنوان مهمان های سر زده برای راه حلهای مسئله تعریف میشوند که آنها را به نام "ذرات" نیز می شناسیم؛ از این رو آنها را "ذرات دسته جمعی" نام نهاده ایم. یک فرآیند تکراری برای بهبود کاندیداها در طی حرکت ذرات در نظر گرفته شده است. ذرات مکررا شایستگی راه حلهای کاندیدا را ارزیابی میکنند و موقعیتی را که در آن بهترین موفقیت را داشته‌اند، به خاطر می سپارند. بهره راه حل کارگزاران "بهترین ذره" یا "بهترین محل" نامیده میشود. هر ذره این اطلاعات را برای دیگر ذرات موجود در همسایگی قابل دسترسی میکند.
همچنین آنها نیز میتوانند ببینند که دیگر ذرات موجود در همسایگی در کجا بهترین موفقیت را داشته‌اند.
PSO تحت نامهای مختلفی همچون الگوریتم انبوه ذرات، الگوریتم ازدحام ذرات و الگوریتم پرندگان درایران شناخته شده است.عبارت Swarm در زبان انگلیسی به اجتماع دسته انبوهی از جانوران و حشرات اشاره می کند. در زیر یک swarm از زنبور ها را می بینید.
شکل(1)_تصویر یک swarm از زنبورها
چون منبع این الگوریتم از رفتار اجتماعی حیوانات، همانند حرکت دسته جمعی پرندگان و ماهی‌ها بود، از این رو PSO نیز با یک ماتریس جمعیت تصادفی اولیه، شروع میشود. برخلاف الگوریتم ژنتیک ، PSO هیچ عملگر تکاملی همانند جهش و تزویج ندارد. در واقع الگوریتم PSO از تعداد مشخصی از ذرات تشکیل می شود که به طور تصادفی، مقدار اولیه می گیرند. برای هر ذره دو مقدار وضعیت و سرعت، تعریف می شود که به ترتیب با یک بردار مکان و یک بردار سرعت، مدل میشوند. این ذرات، بصورت تکرارشونده ای در فضای n بعدی مسئله حرکت می کنند تا با محاسبة مقدار بهینگی به عنوان یک ملاک سنجش، گزینه‌های ممکن جدید را جستجو کنند. بُعد فضای مسئله، برابر تعداد پارامترهای موجود در تابع مورد نظر برای بهینه سازی می باشد. یک حافظه به ذخیرة بهترین موقعیت هر ذره در گذشته و یک حافظه به ذخیرة بهترین موقعیت پیش آمده در میان همة ذرات، اختصاص می‌یابد. با تجربة حاصل از این حافظه ها, ذرات تصمیم می گیرند که در نوبت بعدی، چگونه حرکت کنند. در هر بار تکرار، همة ذرات در فضای n بعدی مسئله حرکت می کنند تا بالاخره نقطة بهینة عام، پیدا شود. ذرات، سرعت‌هایشان و موقعیت‌شان را بر حسب بهترین جواب‌های سراسری و محلی به‌روز میکنند. الگوریتم PSO، بردار سرعت هر ذره را به‌روز کرده و سپس مقدار سرعت جدید را به موقعیت و یا مقدار ذره می‌افزاید. به‌روز کردن‌های سرعت، تحت تأثیر هر دو مقدار بهترین جواب محلی و بهترین جواب مطلق قرار می‌گیرند. بهترین جواب محلی و بهترین جواب مطلق، بهترین جوابهایی هستند که تا لحظه‌ی جاری اجرای الگوریتم، به ترتیب توسط یک ذره و در کل جمعیت به دست آمده‌اند. مزیت اصلی PSO این است که پیاده‌سازی این الگوریتم ساده بوده و نیاز به تعیین پارامترهای کمی دارد. همچنین PSO قادر به بهینه‌سازی توابع هزینه‌ی پیچیده با تعداد زیاد مینیمم محلی است.]1[
1-2 الگوریتم ژنتیک
الگوریتم ژنتیک تکنیک جستجویی در علم رایانه برای یافتن راه‌حل تقریبی برای بهینه‌سازی و مسائل جستجو است. الگوریتم ژنتیک نوع خاصی از الگوریتمهای تکامل است که از تکنیکهای زیست‌شناسی مانند وراثت و جهش استفاده میکند.
در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی برای یافتن فرمول بهینه جهت پیش‌بینی یا تطبیق الگو استفاده میکنند. مختصرا گفته میشود که الگوریتم ژنتیک یا GA یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده میکند. مسئله‌ای که باید حل شود ورودی است و راه‌حلها طبق یک الگو کد گذاری میشوند که تابع fitness نام دارد هر راه حل کاندید را ارزیابی میکند که اکثر آنها به صورت تصادفی انتخاب میشوند.
اخیرا الگوریتم های ژنتیک توجهات زیادی را به خود معطوف کرده اند. در حال حاضر آنها کاربردهای موفق بسیاری دارند. الگوریتم های ژنتیک، گونه ای از الگوریتم های جستجو هستند که برخی از فرآیندهای تکامل طبیعی را به شکل اولیه نشان می دهند. الگوریتم های ژنتیک معمولاً مکانیسم های جستجوی مؤثری را بدست می آورند که می توانند برای بهینه سازی و طبقه بندی کار کردها بکار گرفته شوند. الگوریتم های ژنتیک به جای یک تک نقطه با مجموعه ای از نقاط کار می کنند که هر نقطه در حقیقت برداری در فضا است که نشانگر یک راه کار بالقوه یا گزینشی برای مسئلهی بهینه سازی می باشد.
یک مجموعه، تنها دسته، یا گروهی از بردار ها در فضا است. هر بردار در مجموعه یک فرد و گاهی یک کروموزوم نامیده می شود. از آنجا که اعداد حقیقی در الگوریتم های ژنتیک با استفاده از اعداد باینری، رمز گذاری میشوند، چند بعدی بودن بردار مسئله می تواند متفاوت از چند بُعدی بودن یک رشته بیت کروموزوم باشد. تعداد عناصر (اجزاء) در هر بردار (فرد) برابر است با تعداد پارامترهای حقیقی در مسئله ی بهینه سازی.
هر یک عنصر از بردار، عموماً با یک پارامتر یا بُعد از بردار عددی متناظر است. هر عنصری می تواند با هر تعداد از بیت ها (bits) رمز گذاری شود که این بستگی به نمایش هر پارامتر دارد. تعداد کلّی بیت ها می تواند بُعد ابر فضای مورد جستجو را تعریف کند.
سری عملیاتی که در زمان اجرای یک الگوی الگوریتم ژنتیک انجام می شود، بدین صورت است:
1- تعیین مجموعه
2- محاسبهی تناسب (fitness) برای هر فرد در مجموعه
3- بازسازی افراد منتخب برای تشکیل یک مجموعه ی جدید
4- ایجاد دوگانگی و جهش در مجموعه
5- بازگشت به مرحله ی دوم تا زمانی که شرایط خاص برقرار شود.
دو مرحله ی اصلی برای تبدیل یک مسئله بهینه سازی تکاملی عبارتست از نمایش کروموزوم و ارزیابی کروموزوم.
در مرحله اول که مختص مسئله است هر راه حل مسئله ی بهینه سازی به شکل یک رشته ی باینری (یعنی یک کروموزوم) ارائه می گردد.
در مرحله دوم یک تابع ارزیابی که بصورت تابع تناسب عمل می کند، به منظور مقایسه ی کروموزوم ها در فرآیند تکامل ارائه می شود. رمز گذاری مسئله و انتخاب تابع صحیح تناسب دارای تأثیرات مهمی بر موفقیت روش الگوریتم ژنتیک هستند.]2[
1-3 الگوریتم کلونی مورچه ها
این روش از توانائی مورچهها در پیدا کردن کوتاه ترین مسیر بین لانه و یک منبع غذایی الهام گرفته است. وقتی مورچهها در محیط اطراف حرکت مینمایند، اثری شیمیایی به نام فرومون از خود به جای میگذارند. وقتی جمعیتی از مورچهها از چند مسیر بین لانه و یک منبع غذایی حرکت میکنند، پس از مدت زمانی معینی مشاهده میشود که در مسیرهای متفاوت مقدار فرومونهای بر جای گذاشته شده، متفاوت میباشد. این امر ناشی از این واقعیت است که مورچههایی که در مسیر کوتاهتر حرکت میکنند، به علت کوتاه تر بودن مسیر دریک مدت زمان معین تردد بیشتری داشته‌اند.چون مورچهها ذاتاً مسیری را انتخاب میکنند که دارای فرومون بیشتری است، پس مدت زمانی معین مشاهده می شود که مورچهها، مسیر کوتاه تر را انتخاب کرده‌اند. با استفاده از روش مورچهها، روش جستجوئی پیاده سازی میشود که هر مرحلهای از اطلاعات مراحل قبلی برای رسیدن به هدف استفاده می نماید. برای فهم بهتر الگوریتم بهتراست به طراحی مسئله فروشنده دوره گرد بوسیله کلونی مورچگان مراجعه کنید.مسئله فروشنده دورگرد عبارت است از یافتن مسیری شامل تمام شهرها به طوری که مسیر حاصل دارای کمترین طول باشد. به این منظور هر مورچه در شهری که به طور تصادفی انتخاب شده است قرار داده میشود. در این سیستم بسته هر مورچه حافظهای دارد که اطلاعات را در مورد تور خود ذخیره مینماید. این شهرها نقاط شروع هستند. مورچهها به صورت احتمالی شهرهای بعدی را انتخاب مینمایند تا جائی که هر مورچه تمام شهرها را ملاقات نماید.
همانطور که می¬ دانیم مسئله یافتن کوتاهترین مسیر، یک مسئله بهینه سازی است که گاه حل آن بسیار دشوار است و گاه نیز بسیار زمان براست. برای مثال مسئله فروشنده دوره گرد را نیز میتوان مطرح کرد. در این روش(ACO)، مورچه های مصنوعی به وسیله حرکت بر روی نمودار مساله و با باقی گذاشتن نشانه‌هایی بر روی نمودار، همچون مورچه های واقعی که در مسیر حرکت خود نشانه‌های باقی میگذارند، باعث میشوند که مورچه های مصنوعی بعدی بتوانند راه‌حل‌های بهتری را برای مساله فراهم نمایند. همچنین در این روش میتوان توسط مسائل محاسباتی-عددی بر مبنای علم احتمالات بهترین مسیر را در یک نمودار یافت.
فهرست مطالب
فصل اول: "آشنایی با برخی ازانواع الگوریتم های بهینه سازی "
مقدمه ای بر بهینه سازی
1- 1 الگوریتم اجتماع پرندگان(particle swarm optimization Algorithm - pso) ..............3
1-2 الگوریتم ژنتیک(Genetic Algorithm - GA)...................................................6
1-3 الگوریتم کلونی مورچه ها(Aco- Ant colony optimization Algorithm )..................7
1-4 الگوریتم کلونی زنبور عسل(Abc-Artificial bee colony algorithm)........................11
1-5 الگوریتم چکه های آب هوشمند یا چکاه(Intelligent water Drops Algorithm -Iwd)........13
فصل دوم : " الگوریتم(particle swarm optimization - pso) و
" Cooperative Particle swarm optimization – cpso) (
مقدمه
2-1 ماهیت الگوریتم..................................................................................................17
2-2 مفاهیم اولیه.....................................................................................................19
2-3 فلو چارت.........................................................................................................20
2-4 اطلاعات فنی.....................................................................................................21
2-5 ساختار کلی .....................................................................................................22
2-6 قاعده کلی توپولوژی همسایگی................................................................................23
2-7 نکات کلیدی .....................................................................................................26
2-7-1 خاصیت هوش جمعی........................................................................................26
2-7-2 هوش ذرات.................................................................................................26
2-7-3 کنترل الگو ریتم.............................................................................................26
2-7-4 تعداد ذرات.................................................................................................27
2-7-5 محدوده ی ذرات...........................................................................................27
2-7-6 شرایط توقف.................................................................................................27
2- 8 مزایا و کاربردهای الگو ریتم..................................................................................27
2-9 ذرات swarm در تعدادی فضای واقعی.......................................................................28
2-10مثال هایی از حرکت ذرات....................................................................................37
2-10 مثالی از پرواز پرندگان برای یافتن غذا......................................................................38
2-11 الگوریتم Cooperative Particle swarm optimization ................................................42
2-12 معرفی نرم افزار بکار رفته در شبیه سازی پروسه............................................................45
فصل سوم: به " بکار گیری cpsoو pso در پروسه ی Curve Fitting"
مقدمه
3-1 ماهیت کار.......................................................................................................47
3-2 مراحل انجام کار به کمک الگوریتمpso.......................................................................48
3-2-1 بدست آوردن تابع برازندگی...............................................................................52
3-2-2 مشخص کردن اندازه جمعیت اولیه و ابعاد آن............................................................53
3-2-3 بررسی خروجی های بدست آمده از تابع Fitnessدر تکرار اول........................................53
3-2-4 ایجاد لیست اول جهت نگهداری خروجی های بدست آمده.............................................54
3-2-5 پیدا کردن بهترین خروجی تابع Fitness و یافتن مکان آن در لیست اول...............................54
3-2-6 آبدیت کردن سرعت و مکان ذرات با توجه به اینکه سرعت اولیه ذرات قبلا تعریف ....................55
3-2-7 ایجاد لیست دوم جهت نگهداری خروجی های تابع Fitness در تکرار دوم.............................56
3-2-8 پیدا کردن مکان بهترین ذره در جمعیت دوم.............................................................56
3-2-9 مقایسه خروجی های تابع Fitness در دو تکرار اول.....................................................56
3-2-10 پیدا کردن بهترین ذرات در دو جمعیت اول و دوم و تولید جمعیت سوم...............................56
3-2-11 محاسبه تابع Fitness برای جمعیت سوم.................................................................57
3-2-12 تکرار از مرحله پنجم الی یازدهم تا رسیدن به نقاط بهینه..............................................57
3-3 مراحل انجام کار برای الگوریتمcpso........................................................................57
فصل چهارم : نتایج
4-1 انجام پروسه توسط الگوریتم pso............................................................................60
4-2 انجام پروسه توسط الگوریتم cpso..........................................................68
4-3 بررسی تفاوت بین psoوcpso..............................................................71
فصل پنجم: نتیجه گیری و پیشنهاد
5-1 نتیجه گیری...................................................................................73
5-2 پیشنهاد.......................................................................................76
مراجع.........................................................................................79
پیوست..................................................................................................81
شامل 93 صفحه Word
دانلود تحقیق آشنایی با الگوریتم بهینه سازی PSO و بکارگیری آن در پروسه ی Curve Fitting