تحقیق مقاله آشنائی با الگوریتم های ژنتیک

شنائی با الگوریتم­های ژنتیک

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

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

تشریح ساختار الگوریتم­های ژنتیک

روند اجرای الگوریتم­های ژنتیک به صورت زیر است:

انتخاب والدین

باز ترکیبی

جهش

انتخاب فرزندان

تست شرط خاتمه

ارزیابی جمعیت

مساله

بازنمائی

جستجوی ژنتیکی

جواب

تشکیل جمعیت اولیه

همانطور که می­بینید، برای حل یک مساله با استفاده از الگوریتم­های ژنتیک بایستی مراحل زیر را طی کنیم:

1.     مدلسازی مساله یا بازنمائی

2.     تشکیل جمعیت اولیه

3.     ارزیابی جمعیت

4.     انتخاب والدین

5.     بازترکیبی

6.     جهش

7.     انتخاب فرزندان

8.     شرط خاتمه الگوریتم

در ادامه به تشریح هر یک از قسمتهای این الگوریتم­ها می­پردازیم.

مدلسازی مساله یا بازنمائی

بر خلاف بسیاری از روشهای حل مساله که از همان فرم کلی مساله برای حل مساله استفاده می­کنند، برای اینکه بتوانیم یک مساله را بوسیله الگوریتم­های ژنتیک حل کنیم، بایستی آنرا به فرم مخصوص مورد نیاز این الگوریتم­ها تبدیل کنیم.

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

به عنوان مثال در یک مساله مرتب سازی، کروموزوم را می­توانیم به این شکل تعریف کنیم که بعنوان مثال از چپ به راست، اندیس عناصر از کوچک به بزرگ را نگهداری کند. که در این حالت سمت چپ­ترین عنصر، اندیس کوچک­ترین و سمت ­راست­ترین عنصر، اندیس  بزرگترین عنصر آرایه باشد.

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

اینکه چه نوع بازنمائی را برای مساله استفاده شود، به شخص طراح و فرم مساله بستگی دارد. در زیر چند نمونه از بازنمائی­هایی  را که معمولاً استفاده می­شوند را تعریف می­کنیم:

< >اعداد صحیحرشته­­های بیتی اعداد حقیقی در فرم نقطه شناوراعداد حقیقی به فرم رشته های بیتییک مجموعه از اعداد حقیقی یا صحیحماشینهای حالت محدودهر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم 

تشکیل جمعیت اولیه

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

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

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

ارزیابی جمعیت

برای اینکه بتوانیم موجودات بهتر را درون جمعیت تشخیص بدهیم بایستی معیاری را تعریف کنیم که بر اساس آن موجودات بهتر را تشخیص دهیم.

به این کار، یعنی تعیین میزان خوبی یک موجود، ارزیابی آن موجود می­گویند. ارزیابی، اینگونه است که بر حسب اینکه موجود چقدر خوب است یک عدد به آن نسبت می­دهیم، این عدد که برای موجودات بهتر بزرگتر (یا کوچکتر) است را شایستگی آن موجود می­نامیم.

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

بسته به نوع مساله ما می­خواهیم شایستگی را بیشینه و یا کمینه کنیم. البته معمولاً در مطالعات تئوری فرض بر این گذاشته می­شود که می­خواهیم مقدار شاسیتگی را کمینه کنیم.

در مطالب این فصل تعاریف به گونه­ای ارائه شده­اند که در آنها سعی در مینیمم کردن یک تابع داریم، اما شایستگی عناصر به گونه­ای تعریف شده­ است که برای عناصر کوچکتر، مقادیر بزرگتری ارائه می­دهد.

انتخاب والدین

در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می­کنند که تولید مثل کنند. به این عناصر که از میان جمعیت انتخاب می­شوند، والدین می­گویند. روشهای مختلفی برای انتخاب والدین وجود دارند. در زیر به چند مورد از این روشها اشاره می­کنیم:

< >انتخاب تمام جمعیت بعنوان والدین: در واقع هیچگونه انتخابی انجام نمی­دهیم.انتخاب تصادفی: بصورت تصادفی تعدادی از موجودات جمعیت را بعنوان والدین انتخاب می­کنیم، این انتخاب می­تواند با جایگذاری یا بدون جایگذاری باشد.روشهای مبتنی بر شایستگی: در این روشها عناصر با شایستگی بیشتر شانس بیشتری برای انتخاب شدن بعنوان والدین را دارند. سایر روشها: این روشها با استفاده از تکنیکهایی سعی می­کنند که انتخابهایی را ارائه دهند، که هم رسیدن به جواب نهایی را تسریع کنند و هم اینکه کمک می­کنند که جواب بهینه­تری پیدا شود.باز ترکیبی (Recombination)

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

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

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

نحوه انجام عملیات بازترکیبی

روش کار به صورت زیر است:

< >بصورت تصادفی یک نقطه از کروموزوم را انتخاب می­کنیمژنهای مابعد آن نقطه از کروموزوم­ها را جابجا می­کنیمشایان ذکر است که عمل بازترکیبی را می­توان هم از نقاط آغازین ژن­ها انجام داد و هم اینکه می­توان بدون توجه به محل شروع ژن، عمل بازترکیبی را انجام داد.

همچنین اگر مانند مثال فوق عملیات بازترکیبی را در یک نقطه انجام دهیم به آن بازترکیبی تک نقطه­ای (Single Point Crossover) می­گویند. اما می­توانیم این عملیات را در چند نقطه انجام دهیم، که به آن بازترکیبی چند نقطه­ای (Multipoint Crossover) می­گویند، و در پایان اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع (Uniform Crossover) می­گوئیم. در این دو مورد اخیر، روند کار به این صورت است:

با احتمال ثابتی مثل Pc عمل بازترکیبی را انجام می­دهیم

روش کار به صورت زیر است:

< >به ازای هر یک از قسمت­های کروموزوم:یک عدد تصادفی بین صفر و یک تولید می­کنیماگر این عدد از مقدار ثابتی مثل Pc  کوچکتر باشد، ژنهای مابعد آن نقطه از کروموزوم­ها را جابجا می­کنیملازم به ذکر است که عملیات بازترکیبی موجودات جدیدی تولید نمی­کند و تنها باعث می­شود که موجودات موجود بهتر شوند.

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

جهش

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

برای حل کردن این مشکل به این صورت عمل می­کنیم که با تغییرات تصادفی در ژنها، کروموزوم­ها را به نقاط ناشناخته پرتاب می­کنیم، به این امید که احتمالاً این نقطه جدید ما را به مینیمم کلی هدایت کند.

برای انجام جهش به این صورت عمل می­کنیم:

< >بصورت تصادفی تعدادی از کروموزوم­های فرزند را انتخاب می­کنیم به صورت تصادفی مقادیر یک یا چند ژن وی را تغییر می­دهیم. همچنین در هنگام پیاده سازی به صورت زیر عمل می­کنیم:< >به ازای هر کروموزوم اعمال زیر را انجام می­دهیم:یک عدد تصادفی بین صفر و یک تولید می­کنیماگر عدد تولید شده کوچکتر از Pm  بود، به ازای هر ژن اعمال زیر را انجام می­دهیم، در غیر اینصورت از جهش دادن کروموزوم صرفنظر می کنیم یک عدد تصادفی بین صفر و یک تولید می­کنیماگر عدد تولید شده کوچکتر از Pg  بود، ژن مربوطه را جهش می دهیم بعنوان مثال جهش برای کروموزوم­های به فرم باینری به صورت زیر می­باشد:

نحوه انجام عملیات جهش

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

برای سایر ارائه­ها نیز انواع خاصی از جهش پیشنهاد شده است.

با توجه به اینکه هدف از جهش بهتر شدن کروموزوم­ها و یا اینکه پیدا شدن یک راه حل جدید است، می­توانیم به جای تغییر تصادفی کروموزوم­ها، تغییرات کروموزوم­ها  را هدفمند کنیم. برای اینکار، بسته به نوع مساله، بر روی کروموزوم انتخاب شده یکی از روشهای کلاسیک حل مساله  را اعمال کرده، و جواب حاصل را بعنوان کروموزوم جدید جایگزین می­کنند. استفاده از این روش که از آن با عنوان جهش ابتکاری (Heuristic) یاد می­شود، بسته به نوع مساله ممکن است دستیابی به راه حل نهایی را سریعتر کنند. البته در این موارد بایستی از روشهای ابتکاری سریع استفاده کنیم و یا اینکه با الگوریتم­های کم هزینه تنها به بهتر کردن کروموزوم بپردازیم.

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

انتخاب بازماندگان

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

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

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

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