چیت‌شیت

بهینه‌سازی ازدحام و یادگیری تقویتی چندایجنت (MARL) برای ایجنت‌ها

Swarm Optimization and MARL for Agents

PSO و ACO برای پرامپت‌ها و مسیریابی، ازدحام‌های مبتنی بر صف، و مقایسه شانه‌به‌شانه‌ی MADDPG، QMIX، MAPPO و خودبازی.

  • ۱۳ بخش
  • ۴ درس مرتبط
  • کد و دستورها عیناً از دوره‌ی اصلی
فهرست مطالب
  1. مقایسه‌ی PSO در برابر ACO
  2. الگوریتم‌های MARL
  3. رژیم‌های MARL
  4. ازدحام مبتنی بر صف در برابر انتساب ثابت
  5. زمان استفاده از هر روش
  6. اجرای الگوها
  7. به‌روزرسانی PSO
  8. مسیریاب ACO
  9. الگوی CTDE
  10. پیش‌فرض‌ها در کد درس
  11. حالت‌های شکست
  12. پرسش‌ها
  13. چک‌لیست استقرار

مقایسه‌ی PSO در برابر ACO

مقایسه
فاکتورPSOACO
مسئلهفضای جستجوی پیوستهمسیریابی یا انتخاب مسیر
حافظهp_best و g_bestفرومون به ازای هر نوع وظیفه × ایجنت
کاربرد در ایجنتLMPSO، مدل‌های ازدحامی (Model Swarms)مسیریابی AMRO-S
بهبود گزارش‌شده13.3% نسبت به 12 خط مبنا4.7 برابر افزایش سرعت
جمعیت10 تا 30 ذره3 ایجنت، 4 نوع وظیفه در دمو
قاعده‌ی به‌روزرسانیاینرسی + شناختی + اجتماعیواپاشی، سپس رسوب‌گذاری مشروط
تابع دموrun_lmpso()run_amro_s()

الگوریتم‌های MARL

مقایسه
فاکتورMADDPGQMIXMAPPO
سال و محل انتشارNeurIPS 2017ICML 2018NeurIPS 2022
محیطهمکارانه، رقابتی، ترکیبیفقط همکارانههمکارانه
سیگنال آموزشناقد هر ایجنت تمام کنش‌ها را می‌بیندترکیب‌کننده‌ی یکنوای Qهای هر ایجنتتابع ارزش متمرکز
نوع سیاستبرون‌سیاستبرون‌سیاستهم‌سیاست PPO
بستر آزمونParticle WorldSMACفوتبال، Hanabi، و MPE
محدودیتبیشتر از ~10 ایجنت، ناقدها بزرگ می‌شوندپاداش باید یکنوا باشدخط مبنای پیش‌فرضی که باید شکستش داد
دموrun_maddpg_stylerun_qmix_stylerun_mappo_style

رژیم‌های MARL

مقایسه
فاکتورIQL / IPPOCTDEخودبازیبازی لیگ
ایدهدیگران محیط محسوب می‌شوندناقد متمرکز، سیاست محلینسخه‌ای از خود در گذشتهجمعیتی از سیاست‌های گذشته
مناسب برایوظایف با جفت‌شدگی ضعیفناوبری همکارانهبازی‌های جمع‌صفرچرخه‌های استراتژی
نمونه‌هاQ مستقلMADDPG، COMA، MAPPO، QMIXAlphaZeroAlphaStar
نکتههمگرایی نظری: نداردرایج‌ترین پارادایم امروزیممکن است در چرخه‌ی برتری‌جویی گیر کندبهره‌بردارها و بهره‌بردارهای اصلی را اضافه می‌کند

ازدحام مبتنی بر صف در برابر انتساب ثابت

مقایسه
فاکتورترتیبیانتساب ثابتازدحام
چه‌کسی کار را انتخاب می‌کندیک کارگرشناسه‌ی ازپیش‌تعیین‌شده‌ی کارگرکارگران از یک صف مشترک کار می‌کشند
تابعrun_sequentialrun_fixed_assignmentrun_swarm
توازن بارهیچکارگران سریع بی‌کار می‌مانندخودکار
مناسب برایصرفاً خط مبنامدت‌زمان از قبل مشخص باشدبسیاری از وظایف مستقل
نقطه‌ضعفزمان واقعیکارگر 0 تمام وظایف کند را دریافت می‌کندترتیب و دیباگ

زمان استفاده از هر روش

مفهوم‌ها
PSO
پارامترهای پیوسته، ارزیابی برازش خودکار و ارزان، جمعیت 10 تا 30.
ACO
مسیریابی تکرارشونده در طول زمان با نیاز به شواهد تفسیرپذیر.
هیچ‌کدام
برازش نیازمند بازبینی انسانی است یا تاخیر باید کاملاً دقیق باشد.
الگوریتم ژنتیک
فضای گسسته‌ی ترکیبیاتی که توسط PSO پوشش داده نمی‌شود.
ازدحام
تعداد زیادی وظیفه مستقل با مدت‌زمان متغیر.
سرپرست
وظیفه به یک نقشه‌ی جامع و هماهنگ نیاز دارد.
MAPPO
نقطه‌ی شروع پیشنهادی برای MARL همکارانه.
خودبازی
بازی‌های جمع‌صفر. بازی لیگ در شرایط چرخش استراتژی‌ها.

اجرای الگوها

کار و کد
وظیفهکد
اجرای هر دموی درسpython3 code/main.py
PSO روی 2 پارامتر پرامپتhistory = run_lmpso()
مسیریابی ACO در برابر تصادفیrun_amro_s(n_tasks=200, seed=0)
چاپ ردپاprint_pheromone_table(router)
گام‌ها تا هدف به ازای هر سبک MARL`bench(label, runner)` over 500 trials
دریافت کار از صف مشترکrun_swarm(tasks, n_workers)
Q مستقل روی گریدindependent_q(episodes=1500)
Q مشترک روی 16 کنشjoint_q_learning(episodes=1500)

به‌روزرسانی PSO

کد
python
w, c1, c2 = 0.6, 1.2, 1.2                              # اینرسی، شناختی، اجتماعی
r1, r2 = rng.random(), rng.random()
cognitive = c1 * r1 * (p.p_best[d] - p.x[d])
social = c2 * r2 * (g_best_x[d] - p.x[d])
p.v[d] = w * p.v[d] + cognitive + social
p.x[d] += p.v[d]
p.x[d] = max(bounds[d][0], min(bounds[d][1], p.x[d]))  # محدودسازی در بازه (clamp)
f = fitness(p.x)                                       # صرفاً ارزیاب، بدون گرادیان
if f > p.p_best_fit:                                   # سپس بررسی g_best_fit

مسیریاب ACO

کد
python
router = PheromoneRouter(task_types, agents)         # هر مسیر از 1.0 شروع می‌شود
aco_agent = router.choose(tt, rng)                   # نمونه‌گیری بر اساس وزن فرومون
aq = simulate_task(aco_agent, tt, rng)
router.deposit(tt, aco_agent, aq)
self.pheromones[task_type][a] *= (1.0 - self.decay)  # واپاشی برای تمام ایجنت‌ها
if quality >= self.quality_threshold:                # فیلتر کیفیت
    self.pheromones[task_type][agent] += self.reinforce * quality

الگوی CTDE

معماری
آموزشگرادیاناستقراراستقرارگرادیانوضعیت جهانیهمه‌ی مشاهدات + کنش مشترکناقد متمرکزصرفاً هنگام آموزشمشاهده‌ی ایجنت 1o_iاکتور 1mu_i(o_i)مشاهده‌ی ایجنت 2o_iاکتور 2mu_i(o_i)

پیش‌فرض‌ها در کد درس

پیش‌فرض‌ها
تنظیمپیش‌فرضنکته
n_particles20جمعیت run_lmpso
iterations30تکرارهای PSO
decay0.05واپاشی فرومون در هر رسوب‌گذاری
reinforce0.2رسوب برابر است با تقویت ضرب در کیفیت
quality_threshold0.6هیچ رسوبی پایین‌تر از آن انجام نمی‌شود
n_tasks200وظایف مسیریابی‌شده در run_amro_s
epsilon0.15اکتشاف در independent_q
gamma0.95تخفیف، با alpha برابر 0.1

حالت‌های شکست

عیب‌یابی
  • قفل شدن مسیریاب روی یک ایجنت بد

    علت
    ایجنت سریع اما غلط فرومون گرفته است
    راه‌حل
    اعمال فیلتر کیفیت روی رسوب‌گذاری‌ها
  • واگرایی بهترین برازش

    علت
    انحراف فاجعه‌بار پس از تغییر توزیع داده
    راه‌حل
    بازنشانی یا دوبرابر کردن نرخ واپاشی
  • ازدحام راه‌حل‌های خوب را فراموش می‌کند

    علت
    واپاشی بیش از حد سریع
    راه‌حل
    واپاشی کندتر، پایش بهترین برازش
  • وظایف طولانی هرگز اجرا نمی‌شوند

    علت
    قحطی در صف
    راه‌حل
    صف اولویت‌دار با کهنه‌گی (aging)
  • خروجی وظیفه دو بار ظاهر می‌شود

    علت
    کرش کردن کارگر در حین اجرا
    راه‌حل
    کارگران بی‌اثر در تکرار، صف بادوام
  • تعقیب بی‌حاصل ایجنت‌ها توسط یکدیگر

    علت
    دریفت سیاست، نامانایی
    راه‌حل
    ناقد متمرکز، نرخ‌های یادگیری پایین
  • بازپخش قدیمی به یادگیری آسیب می‌زند

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

    علت
    دور زدن پاداش از طریق هماهنگی تبهکارانه
    راه‌حل
    طراحی دقیق پاداش، اعمال قیود

پرسش‌ها

پرسش و پاسخ
چرا روش‌های بدون گرادیان برای پرامپت‌ها؟
پرامپت یک رشته‌ی گسسته است. PSO و ACO فقط به یک ارزیاب نیاز دارند.
هزینه‌ی یک PSO با 20 ذره و 50 تکرار چقدر است؟
حدود $20 با فرض ~$0.02 به ازای هر فراخوانی.
چرا QMIX نامتمرکز عمل می‌کند؟
ترکیب یکنوا به هر ایجنت اجازه می‌دهد به طور مستقل argmax خود را بگیرد.
چرا MARL را برای ایجنت‌های LLM آموزش نمی‌دهیم؟
بیشتر سیستم‌ها سیاست‌ها را پرامپت می‌کنند. آموزش فقط با داده، پاداش و زیرساخت انجام می‌شود.
چرا مقیاس‌پذیری دموی joint-Q کند است؟
فضای کنش آن برای دو ایجنت برابر با |A|² = 16 است.

چک‌لیست استقرار

نکته‌ها
  • با 10 تا 20 ذره و 20 تا 50 تکرار شروع کنید.
  • فرومون‌ها یا g_best را در هر تکرار ثبت کنید.
  • یک متریک هزینه-به-ازای-تکرار صادر کنید.
  • به هر وظیفه در ازدحام یک شناسه‌ی ردگیری اختصاص دهید. با رشد صف، فشار معکوس اعمال کنید.
  • مسیر اجرا را محدود کنید که فقط o_i را ببیند.
  • جریان مشاهده و کنش تک‌تک ایجنت‌ها را لاگ کنید.