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

انجام آن قواعد از توصيف آنان ساده‌تر است.
خاصيت اعمال ابتکاري خوب اين است که ابزار ساده‌اي براي تشخيص خط مشي‌هاي بهتر ارائه دهند و در حالي که به صورت شرطي لازم، تشخيص خط مشي‌هاي اثربخش را تضمين نمي‌کنند اما اغلب به صورت شرط کافي اين تضمين را فراهم ‌آورند. بيشتر مسائل پيچيده نيازمند ارزيابي تعداد انبوهي از حالت‌هاي ممکن براي تعيين يک جواب دقيق مي‌باشند. زمان لازم براي يافتن يک جواب دقيق اغلب بيشتر از يک طول عمر است. الگوريتم هاي ابتکاري ‌ها با استفاده از روش‌هايي که نيازمند ارزيابي‌هاي کمتر هستند و جوابهايي در محدوديت‌هاي زماني قابل قبول ارايه مي‌نمايند، داراي نقشي اثربخش در حل چنين مسائلي خواهند بود.
5-3) انواع الگوريتم‌هاي ابتکاري
در حالت کلي سه دسته از الگوريتم‌هاي ابتکاري قابل تشخيص است:
الگوريتم‌هايي که بر ويژگي‌هاي ساختاري مسأله و ساختار جواب متمرکز مي‌شوند و با استفاده از آنها الگوريتم‌هاي سازنده يا جستجوي محلي تعريف مي‌کنند.
الگوريتم‌هايي که بر هدايت ابتکاري يک الگوريتم سازنده يا جستجوي محلي متمرکز مي‌شوند به گونه‌اي که آن الگوريتم بتواند بر شرايط حساس (مانند فرار از بهينه محلي) غلبه کند. به اين الگوريتم‌ها، فراابتکاري60 گفته مي‌شود.
الگوريتم‌هايي که بر ترکيب يک چارچوب يا مفهوم ابتکاري با گونه‌هايي از برنامه‌ريزي رياضي (معمولا روشهاي دقيق) متمرکز مي‌شوند.
فراابتکاري ‌هاي نوع اول مي‌توانند خيلي خوب عمل کنند (گاهي اوقات تا حد بهينگي) اما ممکن است در جواب‌هاي داراي کيفيت پايين گير کنند. همانطور که اشاره شد يکي از مشکلات مهمي که اين الگوريتم‌ها با آن روبرو مي‌شوند افتادن در بهينه‌هاي محلي است، بدون اينکه هيچ شانسي براي فرار از آنها داشته باشند. براي بهبود اين الگوريتم‌ها از اواسط ده? 70، موج تازه‌اي از رويکردها آغاز گرديد. اين رويکردها شامل الگوريتم‌هايي است که صريحاً يا به صورت ضمني تقابل بين ايجاد تنوع جستجو (وقتي علائمي وجود دارد که جستجو به سمت مناطق بد فضاي جستجو مي‌رود) و تشديد جستجو (با اين هدف که بهترين جواب در منطقه مورد بررسي را پيدا کند) را مديريت مي‌کنند. اين الگوريتم‌ها فراابتکاري ناميده مي‌شوند[14],[31]. از بين اين الگوريتم‌ها مي‌توان به موارد زير اشاره کرد:
بازپخت شبيه‌سازي شده
جستجوي ممنوع
الگوريتم‌هاي ژنتيک61
الگوريتم ازدحام ذرات62
الگوريتم رقابت استعماري63
شبکه‌هاي عصبي مصنوعي
بهينه‌سازي مورچه‌اي يا الگوريتم‌هاي مورچگان [13] و …
در ادامه به توضيح سه تا از الگوريتم هاي مطرح در اين حوزه يعني الگوريتم ژنتيک، الگوريتم ازدحام ذرات و الگوريتم رقابت استعماري مي پردازيم.
قبل از شروع توضيح پيرامون اين سه الگوريتم بهتر است نگاهي به ساختار کلي الگوريتم هاي تکاملي بيندازيم. تمامي الگوريتم هاي تکاملي در حالت کلي داراي مراحل زير مي باشند:
1- ايجاد مجموعه اي از جواب هاي تصادفي
2- مقايسه جواب ها، رتبه بندي آن ها و انتخاب بهترين ها
3- ترکيب جواب هاي بدست آمده با شبيه سازي فرآيندهاي طبيعي مانند توليد مثل و ادغام جواب هاي جديد با جواب هاي قديمي
4- بازگشت به مرحله 2 (در صورت نياز)
در واقع تمامي اين الگوريتم هايي که در ادامه به توضيح ساختار آنها خواهيم پرداخت داراي اين مراحل مي باشند اما در شکل اجراي مرحله 2 و 3 با هم کمي تفاوت دارند.
نکته ديگري که بيان آن در اين قسمت خالي از لطف نيست اين است که در هر الگوريتم بهينه سازي دو چيز را همواره بايد مدنظر قرار داد:
جستجو64: يعني الگوريتم تا حد ممکن بيشترين کاوش را در فضاي مسئله براي پيداکردن جواب انجام بدهد.
بهره برداري65: يعني اينکه از جوابي که بدست آورديم بيشترين بهره برداري را براي رسيدن به هدف انجام بدهيم.
در واقع الگوريتمي خوب است که بين اين دو مورد بتواند توازن برقرار کند
1-5-3) الگوريتم ژنتيک:
الگوريتم‌هاي ژنتيک يکي از اعضاي خانواد? مدل‌هاي محاسباتي الهام گرفته شده از روند تکامل است. اين الگوريتم‌ها راه‌حل‌هاي يک مسأله را در قالب کروموزوم‌هاي ساده‌اي کد مي‌کنند و سپس عملگرهاي ترکيبي را بر روي اين ساختارها اِعمال مي‌کنند[2].
اين الگوريتم که روش بهينه‌سازي الهام گرفته از طبيعت جاندار(موجودات زنده) است را مي‌توان در طبقه‌بندي‌ها، به عنوان يک روش عددي، جستجوي مستقيم و تصادفي ياد کرد. اين الگوريتم، الگوريتمي مبتني بر تکرار است و اصول اولي? آن از علم ژنتيک اقتباس گرديده است و با تقليد از تعدادي از فرآيندهاي مشاهده شده در تکامل طبيعي اختراع شده است و به طور موثري از شناسايي و کاوش موجود در يک جمعيت استفاده مي‌کند، تا حل‌هاي جديد و بهبود يافته را ايجاد کند. اين الگوريتم در مسائل متنوعي نظير بهينه‌سازي، شناسايي و کنترل سيستم، پردازش تصوير و مسايل ترکيبي، تعين توپولوژي و آموزش شبکه‌هاي عصبي مصنوعي و سيستم‌هاي مبتني بر تصميم و قاعده به کار مي‌رود.
الگوريتم ژنتيك در هر تكرار چند نقطه از فضاي جستجو را در نظر مي‌گيرد بنابراين شانس اينكه به يك ماكزيمم محلي همگرا شود كاهش مي‌يابد.
در واقع در بيشتر روش‌هاي جستجوي مرسوم (روش گراديان) به اين صورت عمل مي‌كند كه از اين يك نقطه به نقط? ديگر حركت مي‌كند. اين روش‌ها مي‌توانند در فضاهاي جستجو داراي چند بيشين? خطرناك باشند. زيرا ممكن است آنها به يك ماکزيمم محلي همگرا شوند. ليكن الگوريتم ژنتيك جمعيت‌هاي كاملي از رشته‌ها (نقاط) را توليد مي‌كند سپس هر نقطه را به صورت انفرادي امتحان مي‌كند و با تركيب محتويات آنها يك جمعيت جديد را كه شامل نقاط بهبود يافته است تشكيل مي‌دهد[26].
1-1-5-3) مراحل انجام الگوريتم ژنتيک:
1- ايجاد جمعيت تصادفي و ارزيابي آن ها (هر جوابي که توليد شده همان لحظه تابع هزينه آن محاسبه مي شود)
2- انتخاب والدين و ترکيب آن ها براي ايجاد جمعيت فرزندان (مثل ترکيب ايده هاي دو فرد و بدست آوردن يک ايده بهتر)
3- انتخاب اعضاي جمعيت براي اعمال جهش و ايجاد جمعيت جهش يافتگان (مثل اينکه هيچ وقت نمي توان از ترکيب دو ماشين خوب در کارخانه خودروسازي يک هواپيما بدست آورد و حتما بايد يک جهش در کار ايجاد شود)
4- ادغام جمعيت اصلي، فرزندان و جهش يافتگان و ايجاد جمعيت اصلي جديد (در واقع اين جمعيت جديد را از سه منبع گردآوري کرديم)
5- اگر شرايط خاتمه محقق نشده باشند، از مرحله 2 تکرار مي کنيم.
6- پايان
2-1-5-3) عملگرهاي الگوريتم ژنتيک:
به طور خلاصه الگوريتم ژنتيك از عملگرهاي زير تشكيل شده است:
1-2-1-5-3) کدگذاري66
اين مرحله شايد مشكلترين مرحله حل مسأله به روش الگوريتم باشد. الگوريتم ژنتيك به جاي اينكه بر روي پارامترها يا متغيرهاي مسأله كار كند، با شكل كد شد? آنها سروكار دارد. يكي از روشهاي كد كردن، كد كردن دودويي مي باشد كه در آن هدف تبديل جواب مسأله به رشته‌اي از اعداد باينري (در مبناي 2) است.
2-2-1-5-3) ارزيابي67
تابع برازندگي را از اِعمال تبديل مناسب بر روي تابع هدف يعني تابعي كه قرار است بهينه شود به دست مي‌آورند. اين تابع هر رشته را با يك مقدار عددي ارزيابي مي‌كند كه كيفيت آن را مشخص مي‌نمايد. هر چه كيفيت رشته جواب بالاتر باشد مقدار برازندگي جواب بيشتر است و احتمال مشاركت براي توليد نسل بعدي نيز افزايش خواهد يافت.
3-2-1-5-3) ترکيب68
مهمترين عملگر در الگوريتم ژنتيك، عملگر ترکيب است. تركيب فرآيندي است كه در آن نسل قديمي كروموزوم‌ها با يكديگر مخلوط و تركيب مي‌شوند تا نسل تازه‌اي از كروموزوم‌ها بوجود بيايد.
جفت‌هايي كه در قسمت انتخاب به عنوان والد در نظر گرفته شدند در اين قسمت ژن‌هايشان را با هم مبادله مي‌كنند و اعضاي جديد بوجود مي‌آورند. تركيب در الگوريتم ژنتيك باعث از بين رفتن پراكندگي يا تنوع ژنتيكي جمعيت مي‌شود زيرا اجازه مي‌دهد ژن‌هاي خوب يكديگر را بيابند.
4-2-1-5-3) جهش69
جهش نيز عملگر ديگري هست كه جواب‌هاي ممكن ديگري را متولد مي‌كند. در الگوريتم ژنتيك بعد از اينكه يك عضو در جمعيت جديد بوجود آمد هر ژن آن با احتمال جهش، جهش مي‌يابد. در جهش ممكن است ژني از مجموعه ژن‌هاي جمعيت حذف شود يا ژني كه تا به حال در جمعيت وجود نداشته است به آن اضافه شود. جهش يك ژن به معناي تغيير آن ژن است و وابسته به نوع كدگذاري روش‌هاي متفاوت جهش استفاده مي‌شود.
5-2-1-5-3) رمزگشايي70
رمزگشايي، عكسِ عمل رمزگذاري است. در اين مرحله بعد از اينكه الگوريتم بهترين جواب را براي مسأله ارائه كرد لازم است عكس عمل رمزگذاري روي جواب‌ها يا همان عمل رمزگشايي اعمال شود تا بتوانيم نسخه واقعي جواب را به وضوح در دست داشته باشيم.
6-2-1-5-3) انواع روش‌هاي انتخاب71
در مرحله انتخاب، يك جفت از كروموزوم‌ها برگزيده مي‌شوند تا با هم تركيب شوند، عملگر انتخاب رابط بين دو نسل است و بعضي از اعضاي نسل كنوني را به نسل آينده منتقل مي‌كند، بعد از انتخاب، عملگرهاي ژنتيك روي دو عضو برگزيده اعمال مي‌شوند، معيار در انتخاب اعضاء ارزش تطابق آنها مي‌باشد اما روند انتخاب حالتي تصادفي دارد.
شايد انتخاب مستقيم و ترتيبي به اين شكل كه بهترين اعضاء دو‌به‌دو انتخاب شوند در نگاه اول روش مناسبي به نظر برسد اما بايد به نكته‌اي توجه داشت؛ در الگوريتم ژنتيك ما با ژن‌ها روبه‌رو هستيم، يك عضو با تطابق پايين اگرچه در نسل خودش عضو مناسبي نمي‌باشد اما ممكن است شامل ژن‌هاي خوب باشد و اگر شانس انتخاب شدنش صفر باشد، اين ژن‌هاي خوب نمي‌توانند به نسل‌هاي بعد منتقل شوند. پس روش انتخاب بايد به گونه‌اي باشد كه به اين عضو نيز شانس انتخاب شدن داده شود. راه‌حل مناسب، طراحي روش انتخاب به گونه‌اي است كه احتمال انتخاب شدن اعضاي با تطابق بالاتر بيشتر باشد. انتخاب بايد به گونه‌اي صورت بگيرد كه تا جايي كه ممكن است هر نسل جديد نسبت به نسل قبلي‌اش تطابق ميانگين بهتري داشته باشد.
روش‌هاي متداول انتخاب عبارتند از:
انتخاب چرخ رولت72
انتخاب ترتيبي
انتخاب بولتزمن
انتخاب حالت پايدار
نخبه سالاري
انتخاب رقابتي
انتخاب قطع سر
انتخاب قطعي بريندل
انتخاب جايگزيني نسلي اصلاح شده
انتخاب مسابقه
انتخاب مسابقه تصادفي
چون در اين پروژه از چرخ رولت براي انجام کار استفاده شده صرفا به توضيح اين روش مي پردازم.
انتخاب چرخ رولت: انتخاب چرخ رولت كه اولين بار توسط “هولند” پيشنهاد شد يكي از مناسب‌ترين انتخاب‌هاي تصادفي بوده كه ايد? آن، احتمال انتخاب مي‌باشد. احتمال انتخاب متناظر با هر كروموزوم، براساس برازندگيِ آن محاسبه شده كه اگر مقدار برازندگي كروموزوم k ام باشد، احتمال بقاي متناظر با آن كروموزوم عبارت است از:
(معادله 3-1)[2]
حال كروموزوم‌ها را براساس مرتب كرده و كه همان مقادير تجمعي مي باشد که به صورت زير به دست مي‌آيد:
(معادله 3-2)[2]
چرخ رولت به اين صورت عمل مي‌كند كه براي انتخاب هر كروموزوم يك عدد تصادفي بين يك و صفر توليد كرده و عدد مذكور در هر بازه‌اي كه قرار گرفت، كروموزوم متناظر با آن انتخاب مي‌شود. البته روش پياده‌سازيِ چرخ رولت به اين شكل است كه ما يك دايره را در نظر گرفته و آن را به تعداد كروموزوم‌ها طوري تقسيم مي‌كنيم كه هر بخش متناظر با مقدار برازندگي كروموزوم مربوط باشد، حال چرخ را چرخانده و هر كجا كه چرخ متوقف شد به شاخص چرخ نگاه كرده، كروموزوم مربوط به آن بخش انتخاب مي‌گردد.
انتخاب چرخ رولت، روشي است كه نسبت مقدار تطابق، اعضاء را انتخاب مي‌كند. اين روش يك چرخ رولت را شبيه‌سازي مي‌كند تا تعيين كند كدام اعضاء شانس باز توليد را دارند.
هر عضو به نسبت تطابقش، تعدادي از بخش‌هاي چرخ رولت را به خود اختصاص مي‌دهد. سپس در هر

Author: y7oozita

پاسخی بگذارید

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