برچسب: شبیه‌ساز الگوریتم

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

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

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

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

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

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

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

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

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

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


مختصری در مورد الگوریتم تکاملی پیوسته (Continues EA)

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

genetic algorithm

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


معرفی یک شبیه ساز برای بازی پینگ پونگ (Pin-Pong Simulator)

این برنامه که pingball نام دارد توسط Ken Silverman’s نوشته شده که مابقی ژانگولرهای ایشان را در صفحه وب شخصیشان می‌توانید مشاهده کنید. (حتما ببینید، تجارب جالبی داشته است)

اما دلایلی که باعث شده من به این برنامه کوچک علاقمند شده و آن را معرفی کنم:

     – فیزیک بسیار جالب بازی، حتما شما جذب میکند.

     – هوش مصنوعی خوبی دارد.

     – حجم آن بسیار کم است، کمتر از 300 کیلوبایت.

     – امکانات متعدد جهت تنظیم حساسیت کنترلر و سختی بازی.

     – امکان فوق‌العاده بازی در حالت شبکه (p2p).

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


مثالی از پیاده‌سازی الگوریتم ژنتیک در ActionScript 3

این روزها دامنه کاربرد نرم‌افزار Flash، خصوصا به دلیل قدرت بالای زبان ActionScript 3 و انعطاف پذیری آن، به سرعت در حال گسترش بوده و هر روز کاربردهای جدیدی برای آن پیدا می‌شود.
در این رابطه، حتی از محاسبات علمی و برنامه نویسی سیستم‌های هوشمند نیز به عنوان زمینه‌ای از کاربردهای AS3 می‌توان نام برد.
این مسئله در گذشته، به دلیل قدرت پردازش محدود و سرعت کم در اجرای کدهای ActionScript، واقعا دور از ذهن به نظر می‌آمد، اما اکنون شرایط تغییر کرده است.
البته کاملا واضح است که هنوز نمی‌توان قدرت پردازش Flash را در رده زبانهای برنامه‌نویسی واقعی قرار داد، اما اگر بخشی از پروژه مربوطه، به شبیه‌سازی بصری اجزای هوشمند مسئله اختصاص داشته باشد، نرم‌افزار Flash قدرت ارائه خوبی خواهد داشت.

مروری بر الگوریتم تبرید (Simulated Annealing)

الگوریتم تبرید یا شبیه‌سازی حرارتی، یکی از مجموعه الگوریتمهای متاهیوریستیک (فرا اکتشافی) معروف در زمینه الگوریتمهای هوش مصنوعی است.
این الگوریتم در سال 1983 و توسط Scott Kirkpatrick و Daniel Gelatt ابداع شده است. اصولا اکثر الگوریتمهای متاهیوریستیک با الگوگیری و شبیه‌سازی یکی از قوانین یا روابط موجود در طبیعت بنا نهاده می‌شوند. این الگوریتم هم بر مبنای فرآیند تبرید یا بازپخت فلزات بنا نهاده شده است.
در فرآیند تبرید، ابتدا حرارت فلزات را تا دمای بسیار بالایی افزایش داده و سپس، یک فرآیند سردسازی و کاهش دمای تدریجی بر روی آنها صورت می‌گیرد. در این فرآیند در هنگام افزایش حرارت فلز، سرعت جنبش اتمهای آن به شدت افزایش یافته و در مرحله بعد، کاهش تدریجی دما موجب شکل گیری الگوهای خاصی در جایگیری اتمهای آن می‌شود.


  • آرشیو:

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