یک چارچوب مبتنی بر آتاماتای یادگیر توزیع شده توسعه یافته برای حل مسأله یافتن زیرگراف بهینه تصادفی
محورهای موضوعی : مهندسی برق و کامپیوترمحمدرضا ملاخلیلی میبدی 1 , محمدرضا میبدی 2
1 - دانشگاه آزاد اسلامی، واحد میبد
2 - دانشگاه صنعتی امیرکبیر
کلید واژه: آتاماتای یادگیر آتاماتای یادگیر توزیع‌شده توسعه‌یافته شبکه آتاماتاهای یادگیر زیرگراف گراف تصادفی نمونه‌گیری,
چکیده مقاله :
در این مقاله، یک ساختار جدید شبکه‌ای از آتاماتاهای یادگیر موسوم به آتاماتای یادگیر توزیع‌شده توسعه‌یافته معرفی شده و سپس الگوریتمی مبتنی بر این ساختار شبکه‌ای برای حل مسأله زیرگراف بهینه در گراف‌های تصادفی با یال‌های وزن‌دار از طریق نمونه‌گیری ارائه می‌شود. نشان داده شده که ساختار شبکه‌ای جدید پیشنهادی قادر به حل مسایل بهینه‌سازی روی گراف‌های تصادفی از طریق نمونه‌گیری با تعداد نمونه کمتر نسبت به روش نمونه‌گیری استاندارد است. علاوه بر این، اثباتی برای همگرایی آن به جواب بهینه ارائه شده و نشان داده می‌شود که ساختار شبکه‌ای پیشنهادی همواره با احتمال 1 به جواب بهینه همگرا می‌گردد.
In this paper a new structure of learning automata which is called as extended distributed learning automata (eDLA) is introduced. A new eDLA-based iterative sampling method for finding optimal sub-graph in stochastic graphs is proposed. Some mathematical analysis of the proposed algorithm is presented and the convergence property of the algorithm is studied. Our study shows that the proposed algorithm can be converge to the optimal sub-graph.