بررسی یک الگوریتم ممتیکی تطبیقی با استفاده از تکامل تفاضلی و Q-learning: مطالعه موردی از برنامه ریزی مسیر جندرباتی

مقاله: بررسی یک الگوریتم ممتیکی تطبیقی با استفاده از تکامل تفاضلی و Q-learning: مطالعه موردی از برنامه ریزی مسیر جندرباتی

این مقاله در سال 2013 توسط Pratyusha Rakshit, و همکارانش در IEEE به چاپ رسیده است.

الگوریتم های ممتیکی، الگوریتم های جستجو فراابتکاری مبتنی بر جمعیت هستند که مزایای تکامل های طبیعی و فرهنگی را با یکدیگر ترکیب می کنند. یک الگوریتم ممتیکی تطبیقی انتخاب تطبیقی مم ها از مخزن مم را به منظور بهبود الگوهای فرهنگی اعضاء الگوریتم جستجو مبتنی بر جمعیت ترکیب می کند.

در این مقاله یک دیدگاه جدید برای طراحی یک الگوریتم ممتیکی تطبیقی ارائه شده است. این کار با ترکیب مزیت های الگوریتم تکامل تفاضلی (DE) برای جستجوی سراسری و Q-learning برای پالایش محلی انجام می شود. در واقع در این مقاله یک تکنیک جدید که ترکیبی از DE و Q-learning می باشد الگوریتم ممتیکی تطبیقی را بهبود می دهد.

چهار نوع الگوریتم تکامل تفاضلی برای مطالعه کارائی الگوریتم ممتیکی تطبیقی برای جنبه های زمان اجرا، ارزیابی تابع هزینه و دقت استفاده می شود. در ادامه به معرفی چند الگوریتم مورد استفاده در این مقاله پرداخته شده است:

 

Q-Learning: این روش ریر مجموعه الگوریتم های تقویتی محسوب می شود. در یادگیری تقویتی، یادگیرنده یک عمل را برای تغییر وضعیت انجام می دهد و متناسب با عملکرد برای رسیدن به هدف مورد نظر پاداش ( یا جریمه) دریافت می کند. در شکل 1 شبه کد Q-learning استاندارد نشان داده شده است.

شکل 1: شبه کد  Q-learning  استاندارد

TDQL: منظور تفاوت زمانی یادگیری Q می باشد که به عنوان یک ماژول تقویتی در الگوریتم ممتیکی تطبیقی محسوب می شود. درواقع برای افزایش محبوبیت یادگیری زمان واقعی استفاده می شود.

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

AMA پیشنهادی : این الگوریتم شامل الگوریتم تکامل تفاضلی برای اکتشاف سراسری و TDQL برای انتخاب تطبیقی مم ها می باشد. این دو ماژول جهت بهبود عملکرد با یکیدگر هماهنگ می باشند. بعد از هر مرحله تکاملی کارائی اعضاء براساس برازش شان مورد ارزیابی قرار می گیرند. اعضاء با کارائی بالا بلافاصله پاداش می گیرند در حالی که اعضاء با کارائی کم جریمه می شوند.

شبیه سازی و نتایج:

شبیه سازی کامپیوتر روی 25 مسئله Benchmark انجام شده است که نشان از این دارد که Q-learning یکی از محبوب ترین و برجسته ترین انواع DE می باشد و الگوریتم متناظر در زمان جرا و دقت کارامدتر می باشد.

 نتایج تجربی روی شبیه سازی و چارچوب کاری واقعی برای برنامه ریزی مسیر چند رباتی نشان از این دارد که الگوریتم پیشنهادی الگوریتم ژنتیک، بهینه سازی ازدحام ذرات و تکامل تفاضلی را بهبود می بخشد. همچنین آزمایشات نشان می دهد که DE-TDQL مبتنی بر الگوریتم ممتیکی تطبیقی،نسبت به تکامل تفاضلی کلاسیک و PSO، ژنتیگ و SaDE بهبود داشته است.

علاوه بر این موارد، این مقاله ادعا دارد که اگر TDQL برای انتخاب فاکتورهای مقیاس پذیری هر نوع از تکامل تفاضلی استفاده شود از نظر جنبه های دقت و زمان همگرائی بهبود حاصل می شود. به طور مثال اگر SaDE TDQL ترکیب شوند کارائی بهتر از نظر دقت و رمان اجرا نسبت به SaDE از خود نشان می دهد. اگر این دو ترکیب شوند افزایش قابل توجهی کارائی SaDE به علت تطبیق فاکتورهای مقیاس پذیری SaDE با استفاده از TDQL خواهد داشت.

در جدول 1 عملکرد الگوریتم پیشنهادی TDQL-DEQL با سایر نوع های دیگر تکامل تفاضلی با Cr=0.9, D=50 مورد مقایسه قرار گرفته شده است.

جدول 1: مقایسه عملکرد الگوریتم پیشنهادی با دیگر نوع های الگوریتم تکامل تفاضلی

در شکل 2 کارائی نسبی متوسط بهترین تابع برازش برای الگوریتم های  FEبرای DE-TDQL و SaDE-TDQL روی الگوریتم های رقابتی SaDE,DEPSO و DE برای تابع Benchmark f25 نشان داده شده است.

شکل 2: مقایسه کارائی الگوریتم های مختلف برای تابع f25

در ادامه مقاله به مطالعه موردی برای برنامه ریزی مسیر چند رباتی پرداخته شده است. برای تشریح این مسئله همان طور که در شکل3 نشان داده شده است مسیرها برای اجرای الگوریتم های مختلف در محیط Khepera با پنچ مانع تعیین شده است.

شکل 3: مسیرها برای اجرای الگوریتم های مختلف در محیط Khepera با پنچ مانع

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

شکل 4: مقایسه میزان مسیر طی شده برای الگوریتم های مختلف متناسب با تعداد ربات مورد استفاده شده

در جدول 2 تعداد گام، میانگین مسیر طی شده (APT ) و میانگین مجموع انحراف معیار مسیر (ATPD) ربات های برای الگوریتم های مختلف مورد مقایسه قرار گرفته شده است.

جدول 2: مقایسه تعداد گام، APT,ATPD ربات ها برای الگوریتم های مختلف

  [1].Pratyusha Rakshit, Amit Konar, Senior Member, IEEE, Pavel Bhowmik, Indrani Goswami,Swagatam Das, Member, IEEE, Lakhmi C. Jain, and Atulya K. Nagar” Realization of an Adaptive Memetic Algorithm Using Differential Evolution and Q-Learning: A Case Study in Multirobot Path Planning”, IEEE,2013.