اتوماتای یادگیر توزیع شده گسترش یافته

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

گراف تصادفی

گراف تصادفی G از G=(V,E,Q) تشکیل شده است که V مجموعه ای از گره هاست، E مجموعه ای از یال ها ست و Q_n*n نیز توزیع احتمالی است که آمار طول یال ها را توصیف می کند و n نیز تعداد گره هاست.

اتوماتای یادگیر تصادفی

اتوماتای یادگیر با ساختار متغیر از سه تائی (α,β,T) تشکیل شده است که در آن α ها مجموعه ای از فعالیت هاست و β مجموعه ای از پاسخ ها در محیط می باشد که بین صفر و یک می باشد. T یک الگوریتم یادگیر را نشان می دهد. که از یک رابطه بازخوردی برای تغییر عمل انتخابی استفاده می کند.

ارتباط بین اتوماتای یادگیر و محیط تصادفی در شکل زیر نشان داده شده است.

شکل : ارتباط بین اتوماتای یادگیر و محیط تصادفی

گراف تصادفی:

یک گراف تصادفی با G={V,E,Q} نمایش داده می شود. که V مجموعه گره ها، E مجموعه یال ها و Q_n*n یک ماتریس n*n می باشد که اندازه یال ها را مشخص می کند و n نشان دهنده تعداد گره ها می باشد.

اتوماتای یادگیر تصادفی:

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

اتوماتای یادگیر توزیع شده:

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

شکل : اتوماتای یادگیر توزیع شده

اتوماتای یادگیر توزیع شده توسعه یافته

در این مقاله یک اتوماتای یادگیر توزیع شده توسعه یافته ارائه شده است. eDLA یا اتوماتای یادگیر توزیع شده توسعه یافته شبکه ای از اتوماتاهای یادگیر همکاری بهم پیوسته است که به وسیله مجموعه ای از قوانین ارتباطی ، که ترتیب انجام عملیات اتوماتاها را کنترل می کند، نظارت می شود. در eDLA هر اتوماتا سطح فعالیتی است که بر اساس اینکه چه مسئله ای حل می شود و قوانین ارتباطی تغییر پیدا می کند. در هر لحظه فقط یک اتوماتا می تواند در محیط فعالیت کند.

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

منابع

1. Mohammad Reza Mollakhalili Meybodi, Mohammad Reza Meybodi “Extended distributed learning automata An automata-based framework for solving stochastic graph optimization problems”,springer,Applied intelligence,2014.