حل مسائل بهينه سازي گسسته با الگوريتم ژنتيک باينري
صورت مساله
الگوريتم ژنتيک تکنيک جستجويي در علم رايانه براي يافتن راه‌حل تقريبي براي بهينه‌سازي و مسائل جستجو است. الگوريتم ژنتيک نوع خاصياز الگوريتمهاي تکاملي است که از تکنيکهاي زيست‌شناسي فرگشتي مانند وراثت و جهش استفاده مي‌کند.
در واقع الگوريتمهاي ژنتيک از اصول انتخاب طبيعي داروين براي يافتن فرمول بهينه جهت پيش‌بيني يا تطبيق الگو استفاده مي‌کنند. الگوريتمهاي ژنتيک اغلب گزينه خوبي براي تکنيکهاي پيش‌بيني بر مبناي رگرسيون هستند. مختصراً گفته مي‌شود که الگوريتم ژنتيک يک تکنيک برنامه‌نويسي است که از تکامل ژنتيکي به عنوان يک الگوي حل مسئله استفاده مي‌کند.مسئله‌اي که بايد حل شود ورودي است و راه‌حلها طبق يک الگو کد گذاري مي‌شوند که تابع برازش يا تابع هزينه، هر راه حل کانديد را ارزيابي مي‌کند که اکثر آنها به صورت تصادفي انتخاب مي‌شوند.
کلاً اين الگوريتم‌ها از بخش هاي زير تشکيل مي‌شوند :
تابع برازش
نمايش
انتخاب
تغيير
موتور الگوريتم ژنتيک يک جمعيت اوليه از فرمول ايجاد مي‌کند. هر فرد در برابر مجموعه‌اي از دادههاي مورد آزمايش قرار مي‌گيرند و مناسبترين آنها (شايد 10 درصد از مناسبترين‌ها) باقي مي‌مانند؛ بقيه کنار گذاشته مي‌شوند. مناسبترين افراد با هم جفتگيري (جابجايي عناصر دي ان اي) و تغيير (تغيير تصادفي عناصر دي ان اي) کرده‌اند. مشاهده مي‌شود که با گذشت از ميان تعداد زيادي از نسلها، الگوريتم ژنتيک به سمت ايجاد فرمول‌هايي که دقيقتر هستند، ميل مي‌کنند. در حالي که شبکه‌هاي عصبي هم غير‌خطي و غير‌پارامتريک هستند، جذابيت زياد الگوريتمهاي ژنتيک اين است نتايج نهايي قابل ملاحظه‌ترند. فرمول نهايي براي کاربر انساني قابل مشاهده خواهد بود، و براي ارائه سطح اطمينان نتايج مي‌توان تکنيکهاي آماري متعارف را بر روي اين فرمول‌ها اعمال کرد. فناوري الگوريتمهاي ژنتيک همواره در حال بهبود است و براي مثال با مطرح کردن معادله ويروس‌ها که در کنار فرمول‌ها و براي نقض کردن فرمول‌ها‌ي ضعيف توليد مي‌شوند و در نتيجه جمعيت را کلاً قويتر مي‌سازند.
عموماً راه‌حلها به صورت 2 تايي 0 و 1 نشان داده مي‌شوند، ولي روشهاي نمايش ديگري هم وجود دارد. تکامل از يک مجموعه کاملاً تصادفي از موجوديت‌ها شروع مي‌شود و در نسلهاي بعدي تکرار مي‌شود. در هر نسل، مناسبترين‌ها انتخاب مي‌شوند نه بهترين‌ها.
يک راه‌حل براي مسئله مورد نظر، با يک ليست از پارامترها نشان داده مي‌شود که به آنها کروموزوم يا ژنوم مي‌گويند. کروموزوم‌ها عموماً به صورت يک رشته ساده از داده‌ها نمايش داده مي‌شوند، البته انواع ساختمان دادههاي ديگر هم مي‌توانند مورد استفاده قرار گيرند. در ابتدا چندين مشخصه به صورت تصادفي براي ايجاد نسل اول توليد مي‌شوند. در طول هر نسل، هر مشخصه ارزيابي مي‌شود وارزش تناسب توسط تابع تناسب اندازه‌گيري مي‌شود.
گام بعدي ايجاد دومين نسل از جامعه است که بر پايه فرآيندهاي انتخاب، توليد از روي مشخصه‌هاي انتخاب شده با عملگرهاي ژنتيکي است: اتصال کروموزوم‌ها به سر يکديگر و تغيير.
براي هر فرد، يک جفت والد انتخاب مي‌شود. انتخاب‌ها به گونه‌اي‌اند که مناسبترين عناصر انتخاب شوند تا حتي ضعيفترين عناصر هم شانس انتخاب داشته باشند تا از نزديک شدن به جواب محلي جلوگيري شود. چندين الگوي انتخاب وجود دارد: چرخ منگنه‌دار(رولت)، انتخاب مسابقه‌اي،... .
معمولاً الگوريتمهاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6 و 1 است که احتمال به وجود آمدن فرزند را نشان مي‌دهد. ارگانيسم‌ها با اين احتمال دوباره با هم ترکيب مي‌شوند. اتصال 2 کروموزوم فرزند ايجاد مي‌کند، که به نسل بعدي اضافه مي‌شوند. اين کارها انجام مي‌شوند تا اين که کانديدهاي مناسبي براي جواب، در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است. الگوريتمهاي ژنتيک يک احتمال تغيير کوچک و ثابت دارند که معمولاً درجه‌اي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال، کروموزوم‌هاي فرزند به طور تصادفي تغيير مي‌کنند يا جهش مي‌يابند، مخصوصاً با جهش بيت‌ها در کروموزوم ساختمان داده‌مان.
اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزوم‌ها‌يي مي‌شود، که با نسل قبلي متفاوت است. کل فرآيند براي نسل بعدي هم تکرار مي‌شود، جفت‌ها براي ترکيب انتخاب مي‌شوند، جمعيت نسل سوم به وجود مي‌آيند و .... اين فرآيند تکرار مي‌شود تا اين که به آخرين مرحله برسيم.
شرايط خاتمه الگوريتمهاي ژنتيک عبارتند از:
* به تعداد ثابتي از نسلها برسيم
* زمان اختصاص داده‌شده تمام شود
* يک فرد(فرزند توليد شده) پيدا شود که مينيمم (کمترين) ملاک را برآورده کند
* بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود
* بازرسي دستي
* ترکيبهاي بالا
|