برچسب: هوش مصنوعی

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

به طور کلی نمودار ذیل، مراحل اجرای الگوریتم ژنتیکی را نمایش میدهد:

ga-shams

حال با توجه به نمودار گردش کار، مراحل کار الگوریتم را به این شکل بیان می‌کنیم:

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

2. تابع ارزیابی (Fitness function) مناسبی جهت ارزیابی کروموزومها (پاسخ‌ها) طراحی می‌کنیم. این مرحله اهمیت بسیار زیادی دارد، چرا که اگر نتوان تابعی مناسب جهت ارزیابی کروموزومهای تولید شده در نسلهای مختلف طراحی نمود، به هیچ وجه نمی‌توان مسئله مور نظر را با استفاده از الگوریتم ژنتیک حل کرد.

3. مقادیر پارامترهای اولیه الگوریتم را با توجه به صورت مسئله تعیین می‌کنیم. مهمترین پارامترهای مورد استفاده عبارتند از، اندازه جمعیت اولیه (N)، احتمالات مربوط به انتخاب (P­S)، ترکیب (PC)، جهش (PM)، ابقاء (PR) و همگرایی (PCN)، نوع انتخاب و نوع عملگرهای ترکیب و جهش.

4. یک جمعیت تصادفی با N کروموزوم تولید می‌شود. N اندازه جمعیت یا تعداد اعضای نسل آغازین بوده و هر کروموزوم نماینده یک جواب برای مساله است.

5. با استفاده از تابع ارزیابی، کیفیت تمام کروموزومهای این نسل را محاسبه و ذخیره می‌نماییم.

6. با توجه به مقدار کمیت درصد انتخاب (P­S)، جفت کروموزومهایی را به عنوان والدها انتخاب می‌کنیم. روند انتخاب والدها با استفاده از مقادیر ذخیره شده تابع ارزیابی انجام می‌گیرد.

7. هر جفت از والدها، با توجه به مقدار احتمال ترکیب (PC)، با یکدیگر ترکیب شده و یک یا دو کروموزوم فرزند تولید می‌کنند.

8. هر کروموزوم فرزند، با توجه به مقدار احتمال جهش (PM)، جهش می‌یابد.

9. با توجه مقدار احتمال ابقاء (PR)، تعدادی از فرزندان برای جایگزین شدن در نسل جدید انتخاب شده و مابقی نسل جدید از کروموزومهای نسل قبلی انتخاب می‌گردند، سپس نسل جدید به جای نسل قبلی در برنامه جایگزین می‌شود.

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


مزایا و معایب الگوریتم ژنتیک

از مزایای GA در مقایسه با دیگر روشهای جستجو می‌توان به این موارد اشاره نمود:

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

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

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

به عنوان مثال:

  • حل مسائل تصمیم‌گیری چند متغیره (Multi-objective problems).
  • الگوریتم‌های مسیریابی (Routing).
  • انواع مسائل مربوط به برنامه‌ریزی و زمانبندی (Scheduling).
  • انواع مسائل بسته‌بندی و تقسیم‌بندی (Partitioning) بهینه.
  • آموزش شبکه‌های عصبی مصنوعی (Artificial Neural Networks) و سیستمهای فازی (Fuzzy systems).
  • بهینه‌سازی طراحی مدارات الکترونیکی (VLSI).
  • بهینه‌سازی ساختارها و ترکیبات شیمیایی.
  • اجرای موازی الگوریتم بر روی سیستمهای چند پردازنده یا توزیع شده.
  • نرم‌افزارهای شناسایی و تشخیص الگو (Pattern recognition).
  • انواع الگوریتم‌های مورد استفاده در صنعت رباتیک.
  • دسته‌بندی (Classification) داده‌ها، داده‌کاوی (Datamining)  و یادگیری ماشین (Machine learning).
  • الگوریتم‌های بکار رفته در انواع بازی‌های کامپیوتری.
  • برخی از الگوریتم‌های پردازش تصاویر (Image processing).
  • انواع محاسبات عددی و روشهای تخمین توابع.
  • سیستمهای شبیه‌سازی حیات مصنوعی (Artificial life).
  • ساخت سیستمهای هوشمند تولید برنامه‌ تکاملی.

چگونه یک مسئله را با الگوریتم ژنتیک حل کنیم؟

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

1.  ساختار مسئله چگونه است؟ آیا یک مسئله بهینه‌سازی محسوب می‌شود؟ هدف از حل این مسئله چیست؟

2.  آیا پاسخ این مسئله را می‌توان به صورت یک کروموزوم یا به عبارتی به شکل آرایه‌ای از متغیرها و پارامتهای مسئله نشان داد؟

3.  آیا می‌توان روند رسیدن به پاسخ را در یک تابع ارزیابی تعریف نمود؟ آیا این تابع ارزیابی در تمام مراحل اجرای الگوریتم و از نسل آغازین تا نسلهای پایانی معتبر بوده و مقادیر صحیحی برمی‌گرداند؟

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

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

پس از شناسایی نوع و ساختار مسئله، می‌بایست روشی برای نمایش پاسخ آن به شکل کروموزوم پیدا کرده و در نهایت تابعی برای ارزیابی کروموزومها طراحی شود.

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

(ادامه مطلب…)


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

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

درنتیجه:
ژنها: به عنوان کمّیت‌ها و متغیرهای مسئله در نظر گرفته می‌شوند.
کروموزوم: لیستی از کمّیت‌ها بوده و نماینده یک راه‌حل از مسئله است.
جمعیت: مجموعه تمام کروموزومهای یک نسل و یا به عبارتی مجموعه تمام راه‌حلهای موجود در فضای جستجوی مسئله است.
(ادامه مطلب…)


گذری بر الگوریتم ایمنی مصنوعی و ساختار آن

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

  –  سلول‌های کمکی که به فعال شدن سلول‌های B کمک می‌کنند.
–  سلول‌های تخریب‌گر که به سلول‌های بیماری‌زا متصل شده و با تزریق ترکیب شیمیایی موجب تخریب آنها می‌شوند.
–  سلول‌های هماهنگ کننده.

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

(ادامه مطلب…)



  • آرشیو:

  • .
    Copyright (c) 2010 www.mshams.ir