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

مقدمه

الگوریتم ژنتیك یك روش آماری برای بهینه سازی و جستجو است. الگوریتم ژنتیك جزئی از محاسبات تكاملی است كه خود جزئی از هوش مصنوعی می باشد. ویژگیهای خاص این الگوریتم باعث می شود كه نتوانیم آن را یك جستجوگر تصادفی ساده قلمداد كنیم. در واقع ایده اولیه این روش از نظریه تكاملی داروین Darwin الهام گرفته شده است و كاركرد آن بر اساس ژنتیك طبیعی استوار می باشد ایدة محاسبات تكاملی اولین بار در سال ١٩٦٠ توسط رچنبرگ Rechenberg كه در زمینه استراتژیهای تكاملی تحقیق می كرد بوجود آمد كه نظریه او بعدها توسط دیگر محققان توسعه داده شد.

اصول اولیه الگوریتم ژنتیك توسط هلند Holland و همكارانش در دانشگاه میشیگان در سال ١٩٦٢ ارائه شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم های طبیعی توجه نمودند و برای مدل سازی آن در سیستم های مصنوعی كه باید دارای توانایی های اصلی سیستم های طبیعی باشند، تلاش نمودند.

نتیجه این تلاشها، پیدایش الگوریتم ژنتیك بود. سپس در سال ١٩٧٥، مبانی ریاضی آن در كتابی توسط هلند با نام تطابق در سیستمهای طبیعی و مصنوعی Adaptive in Natural and Artificial System منتشر شد.

در سال ١٩٩٢، جان كوزا John Koza الگوریتم ژنتیك را به منظور انجام وظایف خاصی در برنامه هایش بكار برد . او این روش را برنامه ریزی تكاملی Genetic Programming نامید. در برنامه ریزی تكاملی، هدف پیدا كردن الگوریتمی است كه بتواند جواب هر صورت مساله ای را پیدا كند. در این روش باید برای الگوریتمها مطلوبیت تعریف كرد تا فهمیده شود كه كدام الگوریتم بهتر است.

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

بیولوژی : شبیه سازی تكامل یك جمعیت از ارگانیسم های تك سلولی

علوم كامپیوتر : جستجو برای تكامل تابع ارزشیابی

مهندسی : شناسایی سیستمهای دینامیكی

فیزیك : حل معادلات غیر خطی برای انطباق سطوح پتانسیل ملكولی

تجارت : جستجو برای قوانین پیشگویی كننده سود شركتها

زمینه های بیولوژیكی

بدن تمام موجودات زنده متشكل از سلول می‌باشد. در هر سلول مجموعه‌ای از موجودات هم شكل بنام كرموزوم Chromosome وجود دارند. كرموزومها، رشته های DNA می‌باشند كه هر كدام متشكل از تعدادی ژن Gene یا همان بلوكهای DNA هستند. هر ژن یك پروتئین خاص یا در واقع یك خصیصه را كد code می‌كند. به عنوان مثال رنگ چشم می‌تواند یك خصیصه باشد. مجموعه های ممكن برای یك خصیصه آلل Allel نامیده می‌شوند. هر ژن در كروموزوم موقعیت خاص خودش را دارد كه این موقعیت خاص لوكوس Locous نام دارد. مجموعه كامل همه كروموزمها ژنوم Genome نامیده می‌شود و یك مجموعه خاص از ژنها در ژنوم، ژنوتیپ Genotype نام دارد. ژنوتیپها بعد از تكامل بیشتر به فنوتیپها Phenotype كه همان خصوصیات فیزیكی و روانی مانند رنگ چشم یا هوش و غیره می باشند، تبدیل می‌شوند.

فضای جستجو

وقتیكه ما به دنبال حل مساله ای هستیم، معمولاً به دنبال جوابهایی می گردیم كه بهترین جوابها در میان مجموعه جوابهای موجود باشند. فضای تمام جوابهای قابل قبول، فضای جستجو نامیده می‌شود. هر نقطه در فضای جستجو یك جواب قابل قبول را نشان می‌دهد. هر جواب قابل قبول می‌تواند بر اساس ارزش یا مطلوبیتش برای مساله مشخص گردد. هدف از پیدا كردن جواب، كه می تواند یك نقطه یا بیشتر در میان جوابهای قابل قبول باشد، پیدا كردن یك نقطه یا بیشتر در فضای جستجو است. جستجو برای یك جواب، معادل جستجو برای حدود نهایی (حداقل یا حداكثر) در فضای جواب است.

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

مشكلی كه در اینجا وجود دارد این است كه جستجو می تواند خیلی پیچیده باشد. مشخص نیست كه كجاها باید به دنبال جواب گشت و اصولاً از كجا باید شروع كرد. روشهای زیادی برای پیدا كردن جواب مناسب (نه لزوماً بهترین) وجود دارد كه به عنوان مثال می توان به روشهای صعود از تپه، جستجوی محدود، شبیه سازی آبكاری فلزات(S.A) و الگوریتم ژنتیك اشاره كرد. جوابهایی كه از این طریق بدست می آیند، معمولاً جوابهای خوبی هستند، چون واقعاً اثباتی برای اینكه كدام یكی بهینه واقعی است وجود ندارد .

مسائل NP

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

مطالعه و بررسی مسائل NP_complete بخاطر سادگی اعمال شده به مساله می باشد، چون جواب می تواند بله یا خیر باشد. بخاطر وجود كارها و مسائلی با خروجیهای بسیار پیچیده، یك گروه از مسائل، مسائل NP-hard نامیده می شوند. این گروه از مسائل به محدودیت گروه مسائل NP_complete نیستند. حالت NP-hardبیشتر مربوط به مسائل بهینه سازی است .یكی از خصوصیات بارز مسائل این است كه هنگام رویارویی با این مسائل، الگوریتم یا الگوریتمهایی را كه برای حل این مسائل مناسب هستند براحتی می توان یافت و كار آنها تنها جستجوی تمامی جوابهای ممكن است. اما مشكل این است كه این الگوریتمها بسیار كند هستند

و حتی گاهی اوقات برای یك بیت اضافه تر به منظور ایجاد نمونه ای بزرگتر، الگوریتم غیر قابل استفاده می شود. امروزه كسی نمی داند كه آیا الگوریتمهای دقیق سریعتری هم وجود دارد یا خیر؟ اثبات یا عدم اثبات این مطلب جزء وظایف خطیر محققان امروزی می باشد. امروزه خیلی از محققین بر این باورند كه چنین الگوریتمی وجود ندارد و بنابراین به دنبال یافتن بعضی روشهای جایگزین یا فرعی هستند كه الگوریتم ژنتیك یكی از این روشها می باشد.

مفاهیم اولیه در الگوریتم ژنتیك

اصول پایه

الگوریتمهای ژنتیكی براساس تئوری تكاملی داروین می‌باشند و جواب مساله ای كه از طریق الگوریتم ژنتیك حل می‌شود مرتبًا بهبود می‌یابد. الگوریتم ژنتیك با یك مجموعه از جوابها كه از طریق كرموزومها نشان داده می‌شوند شروع می‌شود. این مجموعه جوابها جمعیت اولیه نام دارند. در این الگوریتم جوابهای حاصل از یك جمعیت برای تولید جمعیت بعدی استفاده می‌شوند. در این فرایند امید است كه جمعیت جدید نسبت به جمعیت قبلی بهتر باشد. انتخاب بعضی از جوابها از میان كل جوابها والدین ( Paren) به منظور ایجاد جوابهای جدید یا همان فرزندان Offspring بر اساس میزان مطلوبیت آنها می‌باشد. طبیعی است كه جوابهای مناسبتر شانس بیشتری برای تولید مجدد داشته باشند. این فرایند تا برقراری شرطی كه از پیش تعیین شده است (مانند تعداد جمعیتها یا میزان بهبود جواب) ادامه می‌یابد.

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

1- تولید جمعیت تصادفی شامل n كرموزوم

2- بررسی تابع مطلوبیت (Fittness Function f(x هر كروموزوم x در جمعیت

3- ایجاد یك جمعیت جدید بر اساس تكرار قدمهای زیر :

الف) انتخاب دو كروموزوم والد از یك جمعیت بر اساس میزان مطلوبیت آنها

ب) درنظر گرفتن مقدار مشخصی برای احتمال اعمال عملگر تقاطعی Crossover و سپس انجام عملیات تركیب بر روی والدین به منظور ایجاد فرزندان.اگر هیچ تركیب جدیدی صورت نگیرد فرزندان همان والدین خواهند بود.

ج) در نظر گرفتن احتمال جهش Mutation وسپس تغییرفرزندان در هر لوكوس

د) جایگزینی فرزندان جدید در جمعیت جدید

٤) استفاده از جمعیت جدید برای اجراهای بعدی الگوریتم

٥) توقف اجرای الگوریتم در صورت مشاهده شرایط توقف و برگرداندن بهترین جواب در جمعیت فعلی

همانطوركه مشاهده می شود، اصول پایه ای الگوریتم ژنتیك بسیار عمومی است. بنابراین برای مسائل مختلف فاكتورهای مختلف زیادی وجود دارد كه باید مورد بررسی قرار گیرد. اولین سؤال این است كه ایجاد یك كروموزوم چگونه است؟ یا اینكه چه نوعی از كدینگ انتخاب شود؟

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

مساله ای كه ممكن است در اینجا مورد سؤال باشد این است كه اگر جمعیت جدید تنها از طریق فرزندان جدید ایجاد شود، این فرایند منجر به حذف بهترین كرموزومهای نسل قبل می گردد. برای جلوگیری از این پیشامد، همیشه بهترین جواب نسل قبل را بدون هیچ تغییری به نسل جدید منتقل می كنیم.

كدكردن Encoding

الگوریتم ژنتیك بجای اینكه بر روی پارامترها یا متغیرهای مساله كاركند، با شكل كدشده آنها بطور مناسب سروكار دارد. روشهای كدگذاری متداول در الگوریتم ژنتیك عبارتند از كدینگ باینری، كدینگ جهشی Permutation Encodingc ، كدینگ ارزشی Valu Encoding و كدینگ درختی Tree Encoding. تعداد بیتهایی كه برای كدگذاری متغیرها استفاده می‌شود وابسته به دقت مورد نظر برای جوابها، محدوده تغییرات پارامترها و رابطه بین متغیرها می‌باشد.

انواع كدینگ

كدینگ به دو صورت كلی می‌باشد :

كدینگ مستقیم :

در این روش كل یك جواب به عنوان یك كروموزوم در نظر گرفته می شود. برای مسائل پیچیده چنین روشی مناسب نیست، زیرا عملگرهای ژنتیكی بخاطرگستردگی زیاد فرزندان غیركاربردی می شوند و در نتیجه منجر به جوابهای غیرقابل قبول و غیرقانونی می شوند.

كدینگ غیرمستقیم

در این روش تنها قسمتی از یك جواب بصورت یك كروموزوم كد می شود.

روشهای كدینگ

1) كدینگ باینری :
این نوع كدینگ، متداولترین نوع كدینگ می باشد. در این روش كدگذاری، هر كروموزوم یك رشته از بیتهای شامل ٠و ١ می باشد. كدینگ باینری می تواند حالتهای زیادی را پوشش دهد، حتی در مواردی كه تعداد آلل ها كم باشد. از طرف دیگر این نوع كدینگ برای خیلی از مسائل حالت طبیعی ندارد و اغلب اوقات لازم است كه بعد از تقاطع و جهش اصلاحاتی صورت بگیرد.

2) كدینگ جهشی :
این نوع كدینگ می تواند در مسائل ترتیبی نظیر مساله فروشنده دوره گرد یا مساله ترتیب كارها بكار رود. در كدینگ جهشی، هر كروموزوم یك رشته از اعداد می باشد. شكل زیر نمونه ای از این نوع كدینگ را نشان می دهد. كدینگ جهشی تنها برای مسائل ترتیبی مفید است. حتی برای همین مسائل نیز گاهی اوقات باید تقاطعها و جهشهای اصلاحی به منظور ایجاد كروموزومهای سازگار و مناسب انجام شود.

3) كدینگ ارزشی
این نوع كدینگ درمسائلی كه در آنها مقادیر پیچیده نظیر اعداد حقیقی بكار می روند استفاده می شود. استفاده از كدینگ باینری برای چنین مسائلی بسیار سخت می باشد. در كدینگ ارزشی هر ژن یك كروموزوم ارزش خاصی دارد. این پارامتر باارزش می تواند عدد، حرف یا كلمه باشد. دراین نوع كدینگ نیاز به توسعه عملگرهای جابجایی و جهش جدیدی برای مسائل خاص می باشد.

٤) كدینگ ارزشی

5) كدینگ درختی
كدینگ درختی در برنامه های تكاملی به منظور برنامه ریزی تكاملی بكار می‌رود. در كدینگ درختی هركروموزوم یك درخت از اشیائی نظیر توابع یا دستورها در زبان برنامه نویسی می‌باشد. شكل زیر دو نمونه از این كروموزومها را نشان می‌دهد. این نوع كدینگ برای برنامه های تكاملی بسیار عالی است. زبان برنامه نویسی LISPاغلب از این نوع كدینگ استفاده می‌كند و این بدین علت است كه برنامه های آن به این فرم نمایش داده می‌شوند و می‌توانند براحتی مورد تجزیه قرار بگیرند. بنابراین عمل تقاطع و جهش نیز به همان نسبت راحت انجام می‌شوند.