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

مقدمه

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

چند سال بعد از ارائه تئوری ژنتیک، چارلز داروین در سال 1859، نظریه ” منشاء انواع” را منتشر نمود. در این تئوری او به شرح و بسط نحوه تکامل موجودات زنده در قالب یک پدیده طبیعی می پردازد. تئوری ژنتیک مندل می‌توانست کمک بزرگی به داروین بنماید، ولی متأسفانه داروین از مفاد آن بی‌اطلاع بود. به هر حال، یک مشخصه مهم تئوری، تفوق بیشتر و شانس بقای انواع موجودات زنده قویتر یا سازگارتر با محیط، در طول زندگی و حتی نسل های بعدی می باشند. به عبارت ساده، قوی‌بنیه‌ها و سازگارترها زنده می‌مانند و این ویژگی را به فرزندان خود منتقل می‌کنند. داروین به این مسئله، عبارت و اصطلاح ” انتخاب طبیعی” اطلاق می‌کند. بدین ترتیب، یک رشد تکاملی سریع از موجوداتی خواهیم داشت که بهتر از والدین و نسل های قبل‌ترشان با محیط خودشان تعامل داشته و خو می‌گیرند.

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

جان هلند ، دانشمند علوم کامپیوتر و روانشناس، مبدع شاخه ای از علوم کامپیوتربه نام «سیستم‌های تطبیقی پیچیده» می‌باشد. او در کتاب خود یک سیستم تطبیقی یا وفقی را چنین شرح می‌دهد که سیستم مربوطه به طور یکنواخت و پیوسته خودش را تغییر می‌دهد تا از محیط اطراف خود بهتر استفاده کند. هُلند در خلال توسعه تئوری خود برای سیستم‌های تطبیقی به شرح اپراتورهای ژنتیک برای تغییر حالت سیستم می‌پردازد. گر چه کتاب هُلند، اختصاصاً برای سیستم‌های تطبیقی نگاشته شده‌است ولی یک مشخصه بسیار مهم دارد و آن ابداع و معرفی الگوریتم ژنتیک می‌باشد.

ژنتیک بیولوژیکی

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

هر کروموزوم شامل بیت های اطلاعاتی و تکه‌های رقومی هستند. هر کدام از این تکه‌ها موسوم به ژن می‌باشند. در یک بیان تناظری، نسبت مادی ژن به کروموزوم به فرد مثل نسبت معنوی حرف به کلمه به جمله می‌باشد. هر ژن می‌تواند مقادیری را اختیار کند و هر مقدار ممکن موسوم به یک اَلل می‌باشد. در صورتی که ژن کد باینری باشد، آنگاه دو اَلل بیشتر نداریم، یکی مقدار صفر (0) و دیگری مقدار (1) و موقعیت یک ژن در کروموزوم مربوطه معروف به مکان یا موقعیت می‌باشد. جهت تفهیم و تعمیق اصطلاحات یادشده، یک مجموعه ساده پنج عضوی از پرندگان یک نژاد خاص (مثلاً اُردک ها) را در نظر بگیرید.

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

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

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

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

الگوریتم های بهینه سازی

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

در آغاز الگوریتم، تعدادي از افراد به‌عنوان جمعیت اولیه و معمولاً به‌صورت تصادفی ساخته‌شده و معیاري از کیفیت به نام تابع هدف یا برازندگی براي تک تک آن ها ارزیابی می شود. اگر شرط رسیدن به جواب برقرار نباشد (به جواب بهینه نرسیده باشیم)، نسل بعدي با انتخاب والدین بر اساس میزان برازندگی آن ها تولید می شود.

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

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

معرفی یک الگوریتم ژنتیک ساده

الگوریتم هاي ژنتیک، به‌جای آنکه بر روي پارامترها کار کنند با شکل کد شده آن ها سروکار دارند. براي مثال فرض کنید که بیشینه کردن تابع f(x,y)=X^2+Y^2 (با محدودیت‌هاي x و y اعداد صحیح و x بین 0 تا 7 و y بین 0 تا 31 مدنظر باشد. متداول-ترین روش کدگذاري، کدگذاري باینري است.

ازاین‌رو پارامتر با دنباله مناسبی از اعداد جایگزین می شود. هر عدد صحیح از 0 تا 31 را می‌توان با 5 بیت و هر عدد صحیح از 0 تا 7 را با 3 بیت می‌توان نمایش داد. براي مثال شکل زیر کدگذاری باینري دو متغیر x= 9 و y=5 را نشان می‌دهد.

بنابراین با هر نقطه از فضاي دوبعدی (x,y) دنباله‌ای به‌صورت شکل زیرمتناظر است.

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

تعریف‌ها

الف) ژن: مقدار کد شده هر متغیر را ژن گویند. در کدگذاري باینري ژن متناظر با x=9 مطابق شکل 2-5 عبارت است از: 01001.

ب)کروموزوم: به رشته یا دنباله اي از ژن ها که به‌عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسئله موردنظر به کار می رود کروموزوم گویند.

ج) جمعیت: در هر مرحله تکرار از الگوریتم ژنتیکی تعدادي مشخص از کروموزوم ها مورد ارزیابی قرار می گیرد. به مجموعه این کروموزوم ها جمعیت می گویند.

د) عدد برازندگی: مناسب بودن یا نبودن را با معیاري که باهدف(مورد بهینه‌سازی) رابطه دارد می‌سنجند.

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

و) عملگر جهش: این عملگر روي یک دنباله منفرد عمل می کند به‌این‌ترتیب که با احتمال کوچکی به نام احتمال جهش هر ژن از کروموزوم ها را تغییر می دهد. در شکل زیر نحوه تغییر ژن هاي یک کروموزوم براثر عملگر جهش نشان داده‌شده است.

ز) کروموزوم فرزند: به دنباله اي که پس از عمل جابه جایی و عمل جهش به دست می آید کروموزوم فرزند می گویند.

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

ط) عملگر انتخاب: براي ایجاد افراد نسل جدید، از عملگر انتخاب استفاده می‌شود.

ي) مرحله تولید: به هر بار تولید یک جمعیت جدید یک مرحله تولید گویند.