تبلیغات
بچه های برق دانشگاه آزاد کازرون - الگوریتم‌های ژنتیك - ‌پرواز در فضای حالت مسئله‌
قالب وبلاگ قالب وبلاگ

بچه های برق دانشگاه آزاد کازرون
 

آپلود عکس رایگان و دائمی
 

اشتراک و ارسال مطلب به:

نوشته شده در تاریخ شنبه 13 خرداد 1391 توسط مجتبی جباری

الگوریتم‌های ژنتیك - ‌پرواز در فضای حالت مسئله‌


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


الگوریتم‌های ژنتیك - ‌پرواز در فضای حالت مسئله‌

كیوان تیرداد
ماهنامه شبكه - آذر ۱۳۸۵ شماره 71

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

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

2- داستان كوتاه
در ادامه سعی می‌كنم كاركرد الگوریتم ژنتیك را با داستانی خیالی برایتان تشریح كنم. در سال‌های بسیار دور در یك غار تاریك و نم‌دار كه راهی به فضای بیرون نداشت، موجوداتی به نام سوتك زندگی می‌كردند. سوتك‌های داستان ما زندگی بسیار راحت و آرامی داشتند. آن‌ها فقط دارای حس لامسه و شنوایی بودند. بدین‌ترتیب آن‌ها در گوشه و كنار غار حركت می‌كردند و سعی می‌كردند در قسمت‌های نم‌دار غار از جلبك‌ها تغذیه كنند و البته آن‌ها جلبك‌ها را بسیار دوست داشتند و هر گاه بیكار می‌شدند، به سوت زدن سوتك‌های دیگر گوش می‌كردند.

در غار موجود دیگری زندگی نمی‌كرد و بدین ترتیب سوتك‌ها از هیچ چیزی نمی‌ترسیدند. در قسمتی از كف غار رودخانه‌ای وجود داشت كه آب مورد نیاز سوتك‌ها و جلبك‌ها را تأمین می‌كرد. بدین ترتیب سوتك‌های داستان ما هیچ نیازی به حس بینایی در فضای تاریك غار نداشتند. سال‌های متمادی سوتك‌ها بدین‌ترتیب زندگی می‌كردند تا این‌كه یك روز زلزله مهیبی رخ داد و در اثر آن، قسمتی از غار خراب شد و راهی به بیرون باز شد و برای اولین بار سوتك‌ها گرمای نور خورشید را روی پوست خود احساس كردند.

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

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

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

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

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

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

بدین ترتیب تركیب ژن‌ها این امكان را به وجود میآورد تا ارگانیزم‌های جدیدتری به دست آوریم كه تركیبی از مزایای هر دو والد باشد.

3- الگوریتم ژنتیك در دنیای كامپیوتر

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

1011011010000101011111110

‌یا

1264196352478923455548216

‌برای شروع فعالیت الگوریتم ژنتیك نیازمند جمعیتی از كروموزوم‌ها به صورت تصادفی هستیم. یعنی در ابتدا به عنوان قدم اول، تعدادی كروموزوم به صورت تصادفی ایجاد می كنیم. فرض كنید N كروموزوم و این N را جمعیت آغازین می‌نامیم.

در ادامه تابعی به نام تابع ارزش تشكیل می‌دهیم كه این تابع به عنوان ورودی یك كرومزوم را دریافت می‌كند (یك جواب مسئله) و به عنوان خروجی عددی را مبتنی بر میزان بودن كرومزوم نسبت به جواب نهایی بر می‌گرداند. در حقیقت این تابع میزان خوب بودن جواب را مشخص می‌كند. برای همه نمونه‌های جمعیت مقدار تابع ارزش را حساب می‌كنیم.

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

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

بدین ترتیب دو كرومزوم جدید تولید می‌شود (دو جواب جدید). راه دیگری نیز برای انجام عمل تركیب وجود دارد و آن انتخاب چند نقطه شكست است. مثلاً به شكل زیر برای 2 نقطه شكست توجه كنید. 


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

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

4- نكات مهم در الگوریتم های ژنتیك
1- شرایط جمعیت اولیه می‌تواند در  سرعت رسیدن به جواب بسیار تأثیرگذار باشد. یعنی اگر جمعیت اولیه مناسب‌تر باشد، بسیار سریع‌تر به جواب می‌رسیم. بنابراین گاهی در بعضی از مسئله‌ها به جای آن كه جمعیت اولیه به صورت تصادفی ایجاد شود، از اعمال شرایط خاص مسئله به جمعیت اولیه نیز استفاده می‌شود.

2- با توجه به وجود پارامترهای تصادفی در الگوریتم مسئله حتی در صورت استفاده از جمعیت اولیه یكسان ممكن است در اجراهای مختلف الزاماً جواب‌های یكسان به دست نیاید و البته در صورت استفاده از جمعیت اولیه متناوت این پدیده ملموس‌تر خواهد بود.

3- تابع ارزش در این‌گونه از الگوریتم‌ها از اهمیت بسزایی برخوردار است؛ چرا كه معمولاً در اكثر مسائل در اثر تركیب، حالت‌هایی رخ می‌دهد كه منطبق بر شرایط مسئله نیست و حتی فاقد معنی و مفهوم است. بنابراین تابع ارزش باید به گونه‌ای طراحی شود كه به ازای این حالات مقادیر بسیار كمی برگرداند و از طرفی باید برای نزدیك شدن به هدف بسیار خوب تخمین بزند.

4- یكی از پدیده‌های جالب این است كه ممكن است در نسل‌های میانی نمونه‌هایی بروز كنند كه از نظر تابع ارزش و خوب بودن بسیار مناسب باشند. یك روش این است كه اینگونه موارد را شناسایی كنیم و در نسل بعدی نیز از آن‌ها استفاده كنیم. به این تكنیك نخبه‌گرایی می‌گویند كه عملاً تأثیر بسزایی در رسیدن به جواب مسئله دارد.

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





طبقه بندی: مقالات برق، 
.: Weblog Themes By Pichak :.


شرکت کوشا الکام پارس نماینده رسمی اینترنت پرسرعت شاتل در کازرون * سرعت فوق العاده * ادرس:چهار راه بانک ملی مجتمع تجاری کوثر واحد 1 * تلفن:11-2219410

اللّهُمَّ كُنْ لِوَلِیِّكَ الْحُجَّةِ بْنِ الْحَسَنِ صَلَواتُكَ عَلَیْهِ وَعَلى آبائِهِ فی هذِهِ السّاعَةِ وَفی كُلِّ ساعَةٍ وَلِیّاً وَحافِظاً وَقائِدا ‏وَناصِراً وَدَلیلاً وَعَیْناً حَتّى تُسْكِنَهُ أَرْضَك َطَوْعاً وَتُمَتِّعَهُ فیها طَویلاً

Google

در این وبلاگ
در كل اینترنت

دریافت کد قلب دنبال موس
تمامی حقوق این وبلاگ محفوظ است
قالب وبلاگقالب وبلاگ
تحلیل آمار سایت و وبلاگ