الگوریتم ژنتیک

درس 17: الگوریتم ژنتیک

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

مقدمه

محاسبه راه حل بهینه یا Optimal solution برای اکثر مسایل بهینه سازی که در خیلی از زمینه‌های کاربردی و عملی مشاهده می‌گردند، کار دشوار و سختی است. در عمل، معمولا به راه حل‌های خوب که از الگوریتم‌های هیوریستیک Heuristic یا متاهیوریستیک (همان فراابتکاری) Metaheuristic بدست می‌آید، اکتفا می‌گردد. متاهیوریستیک‌ها مجموعه ای از فنون بهینه سازی تقریبی Approximate optimization techniques را که عمدتا در طول دو دهه گذشته شهرت پیدا کرده اند، در بر می‌گیرند. روش‌های فراابتکاری راه حل‌های قابل قبول در زمان معقول را برای مسایل پیچیده و سخت، در زمینه‌های مهندسی و علوم پایه ارایه می نمایند. برخلاف الگوریتم‌های بهینه سازی دقیق Exact optimization algorithms ، فراابتکاری‌ ها بهینه بودن جواب‌های بدست آمده را ضمانت نمی نمایند.الگوریتم ژنتیک

کلمه متاهیوریستیک از کلمه یونانی “Heuriskein” به معنای هنر کشف قواعد جدید برای حل مسایل گرفته شده است. پیشوند “متا” نیز از یک کلمه یونانی به معنای “متدولوژی” سطح بالا گرفته شده است. واژه ” متاهیوریستیک ” اولین بار توسط گلوور در سال 1986 ارایه گردید. روش جستجوی متاهیوریستیک را می توان به صورت متدولوژی‌های عمومی سطح بالایی که می توانند به عنوان یک استراتژی راهنما در طراحی هیورستیک‌های اختصاصی برای حل مسایل بهینه سازی تخصصی به کار روند، تعریف کرد.الگوریتم ژنتیک

برخلاف روش‌های دقیق، متاهیوریستیک‌ها (فراابتکاری‌‌ها) برای مسایل با اندازه‌های بزرگ کاربرد دشوار دارد و راه حل‌هایی راضی کننده ای در زمان معقولی ارایه می نمایند. در این الگوریتم‌ها، هیچ گونه ضمانتی برای یافتن جواب بهینه سراسری یا حدودی از آن وجود ندارد. متاهیوریستیک‌ها (فراابتکاری‌‌ها) در طول بیست سال گذشته شهرت زیادی پیدا کرده اند. کاربرد و استفاده از آن‌ها در خیلی از مسایل، کارایی و اثر بخشی آن‌ها را برای حل مسایل پیچیده و بزرگ نشان می دهد. فراابتکاری‌ها در خیلی از زمینه‌ها از قبیل موارد زیر کاربرد دارند:

• طراحی مهندسی، بهینه سازی توپولوژی، بهینه سازی مسایل الکترونیک، آئرودینامیک، دینامک سیالات، مخابرات، رباتیک
• یادگیری ماشین و کاوش داده‌ها
• مدل سازی سیستم‌ها، شبیه سازی و تحقیق در شیمی، فیزیک، بیولوژی، کنترل، سیگنال، و پردازش تصویر
• مسایل مسیردهی و برنامه ریزی، برنامه ریزی ربات، مسایل تولید و زمان بندی، حمل و نقل و لجستیک، مدیریت زنجیره تامین

روش‌های مختلف الگوریتم‌های فراابتکاری یا متاهیوریستیک تا به حال پیشنهاد شده است که به صورت زیر است:

• بهینه سازی کلونی مورچگان Ant colony optimization
• بهینه سازی کلونی زنبوران Bee colony
• الگوریتم‌های ترتیبی cultural algorithms
• الگوریتم‌های با هم تکاملی Co-evolutionary algorithms
• الگوریتم ژنتیک Genetic algorithm
• جستجوی محلی تکراری Iterated local search
• بهینه سازی توده ذرات particle swarm intelligent
• انجماد تدریجی Simulated Annealing
• جستجوی ممنوع Taboo search
• جستجوی همسایگی متغیر Variable neighboar search

در طراحی یک فراابتکاری‌، دو معیار متناقض شامل کاوش (Exploration) و در فضای جستجو (گوناگونی و تنوع) و تبعیت (Exploitation) از بهترین راه حل‌های پیدا شده، باید در نظر گرفته شوند. در کاوش در ناحیه‌های جستجو نشده بررسی صورت می‌گیرد. در تبعیت، در ناحیه‌های امید بخش که تا به حال در آن ناحیه یک جواب خوب پیدا شده است بررسی بیشتر صورت می‌گیرد. در صورتیکه به کاوش اهمیت بیشتری داده شود، الگوریتم رفتار تصادفی بیشتری خواهد داشت و به سمت رفتار تصادفی میل می کند و در صورتی که به رفتار تبعیت توجه بیشتری شود، الگوریتم از رفتار تصادفی فاصله می‌گیرد و جستجو تنها در محدوده راه حل‌های خوب به جستجو می پردازد.

معیار‌های طبقه بندی زیادی ممکن است برای طبقه بندی فراابتکاری‌‌ها استفاده شود که در زیر به بعضی از آن‌ها اشاره می‌شود:

الهام گرفته از طبیعت در مقابل عدم الهام از طبیعت

خیلی از الگوریتم‌های فراابتکاری از فراینده‌های طبیعی الهام گرفته شده اند: از قبیل الگوریتم‌های اجتماع مورچگان و زنبور عسل که از هوش توده ای از گونه‌های مختلف مورچگان و زنبوران استفاده می کنند.

نحوه استفاده از حافظه

بعضی از الگوریتم‌های فراابتکاری از قبیل انجماد تدریجی بدون حافظه هستند و حرکت‌های قبلی را در جایی ذخیره نمی کنند. در مقابل الگوریتم انجماد تدریجی از یک حافظه که بعضی از اطلاعات را در طول جستجو بدست می‌آورد، ذخیره می کند.

قطعی در مقابل احتمالی

یک الگوریتم قطعی، یک مسئله بهینه سازی را از طریق تصمیم گیری قطعی حل می نماید(برای مثال الگوریتم جستجوی محلی و جستجوی ممنوع). در الگوریتم‌های فراابتکاری احتمالی، بعضی از قواعد احتمالی در فرایند جستجو مورد استفاده قرار می‌گیرد که می توان به الگوریتم انجماد تدریجی و الگوریتم ژنتیک اشاره کرد. در الگوریتم‌های قطعی، با داشتن یک راه حل اولیه و اجراهای متفاوت، تنها یک جواب نهایی بدست می‌آید و در حالی که در الگوریتم‌های تصادفی، با داشتن یک راه حل اولیه و اجرا‌های متفاوت، ممکن است که جواب‌های نهایی متفاوتی بدست آید.

تکراری در مقابل حریصانه

در الگوریتم‌های تکراری، الگوریتم با یک راه حل کامل شروع شده و در هر تکرار راه حل یا راه حل‌ها تغییر پیدا می کنند. در الگوریتم‌های حریصانه یک راه حل کامل در اختیار نبوده بلکه با یک راه حل ساخته نشده شروع شده و در هر مرحله، یک متغیر تصمیم از مسئله یک قسمت از راه حل را می سازد. اغلب الگوریتم‌های فراابتکاری، الگوریتم‌های تکراری هستند.

در ادامه الگوریتم ژنتیک که الگوریتمی است که از طبیعت الهام گرفته است و در رده الگوریتم‌های احتمالی، و تکراری با حافظه قرار می‌گیرد صحبت می‌شود.

الگوریتم ژنتیک

براساس تئوری انتخاب طبیعی، گیاهان و موجودات زنده ای که در حال حاضر وجود دارند، نتیجه میلیون‌ها سال تطابق با تقاضای‌های محیط می باشند. در هر زمانی، تعدادی از جانداران مختلف، ممکن است که با هم دیگر در یک اکوسیستم زندگی نمایند و برای دستیابی به منابع مشترک با هم دیگر به رقابت بپردازند. موجوداتی که توانایی بیشتری در دستیابی به منابع و تولید مثل داشته اند، در طبیعت نیز بیشتر مشاهده می شوند. موجوداتی که توانایی کمتری داشته اند، به دلایل مختلف، به مرور تعداد آن‌ها کم و کمتر شده و حتی به نابودی کشیده شده اند. در این حالت، گفته می شود که گونه‌های اول نسبت به گونه‌های بعدی شایسته تر می باشند و مشخصه هایی که موجب شده است تا بعضی گونه‌های شایسته تر باشند مشخصه‌های ارجح می نامند. در طول زمان، گفته می شود که کل جمیعت اکوسیستم دچار تکاملی شده است به طور متوسط، شامل موجوداتی شده است که شایسته تر از موجودات قبلی آن می باشند، زیرا این موجودات مشخصاتی داشته اند که منجر به بقای بیشتر آن‌ها شده است.

تکنیک محاسبات تکاملی یا Evolutionary computation یا EC قواعد تکامل را در الگوریتم هایی برای جستجوی راه حل‌های بهینه‌ مسایل به کار می گیرد. در واقع، تکنیک محاسبات تکاملی، توسعه علوم تکامل بیولوژیکی به حوزه علوم محاسباتی و کامپیوتر بوده است. در یک الگوریتم جستجو، تعدادی از راه حل‌های ممکن از یک مسئله در اختیار بوده و هدف یافتن بهترین راه حل ممکن در زمان محدود می باشد. تفاوت اصلی الگوریتم‌های تکاملی نسبت به الگوریتم‌های دیگر این است که این الگوریتم‌ها مبتنی بر جمعیت عمل می نمایند. در این الگوریتم ها، معمولا یک جمعیت اولیه ایجاد و سپس تکامل داده می شود.

الگوریتم ژنتیک یا Genetic Algorithm مشهورترین تکنیک در تحقیقات الگوریتم‌های تکاملی است. این الگوریتم یک تکنیک جستجو را برای یافتن راه حل‌های نزدیک به بهینه‌ در زمان قابل قبول برای مسایل بهینه‌سازی ارایه می نماید.

الگوریتم ژنتیک با یک جمعیت اولیه از راه حل‌ها شروع می شود. هر راه حل از طریق یک کروموزوم نمایش داده می شود و تمامی راه حل‌های ممکن باید با استفاده از یک سیستم کدگذاری، تبدیل به کد شوند. سپس مجموعه ای از اپراتورهای تولید مثل، باید تعیین گردد. اپراتورهای تولید مثل، مستقیما روی کروموزوم‌ها عمل نموده و سپس کروموزوم‌ها تحت اپراتور جهش و ترکیب قرار می گیرند. طراحی ساختار کدگذاری و اپراتورها باید با حوصله و دقت فراوان انجام گردد. این طراحی، تاثیر بسیار زیادی روی عملکرد الگوریتم ژنتیک خواهد داشت.

رویه انتخاب برای رقابت افراد در داخل جمعیت به کار می رود که بر اساس یک تابع شایستگی عمل می‌نماید. برای هر کروموزوم، یک مقدار مرتبط با شایستگی راه حل که نمایش می دهد، وجود دارد. الگوریتم ژنتیک به دنبال حداکثر کردن مقدار تابع شایستگی است. البته در صورتی که تابع هدف به صورت حداقل سازی یک تابع هدف باشد، به هنگام کردن الگوریتم برای حداقل سازی کاری ساده ای است. هر تابع هزینه به راحتی قابل تبدیل به یک تابع شایستگی است مثلا با معکوس کردن تابع هزینه، می توانی یک تابع شایستگی متناسب آن ساخت.

بعد از این که مراحل تولید مثل و تابع برازندگی تعریف شد، یک الگوریتم ژنتیک براساس یک ساختار مشابه و پایه طراحی می گردد. این ساختار ساده با تولید یک جمعیت اولیه از کروموزوم‌ها شروع می گردد. معمولا، جمعیت اولیه به صورت تصادفی تولید می گردد.

مراحل الگوریتم ژنتیک

الگوریتم ژنتیک یک رویه تکراری را به منظور تکامل جمعیت انجام می دهد که در آن فعالیت‌های زیر انجام می شود.

انتخاب

اولین قدم شامل انتخاب افرادی از جمعیت برای تولید مثل است. این انتخاب به صورت تصادفی، با استفاده از یک احتمال متناسب با تابع برازندگی افراد انجام می گردد. بنابراین، همواره بهترین فرد شانس بیشتری برای انتخاب نسبت به فرد ضعیف تر دارد.

تولید مثل

در قدم دوم، عملگر ترکیب و جهش روی افراد انتخاب شده به کار گرفته شده و کروموزوم‌های جدید تولید می گردند. در این مرحله، فرزندان جدید تولید می شوند.

ارزیابی

در این مرحله، میزان برازندگی فرزندان جدید تولید شده تعیین می شود.

جابه جایی

در این مرحله، افرادی از جمعیت قبلی حذف و با افراد جدیدی که به تازگی تولید شده جایگزین می شوند.