Skip to content
بازگشت به نتایج جست‌وجو

الگوریتم ژنتیک مبتنی بر عامل — جستجوی تکاملی توزیع‌شده از طریق عامل‌های خودمختار

معرفی‌شده توسط
Adamidis, P. & Petridis, V. (early formal treatment); broader community development in 1990s
سال
1990s
نوع
Hybrid evolutionary-agent simulation
خانواده
Simulation / optimization

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

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

شهود پشت روش

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

تاریخ

الگوریتم‌های ژنتیک توزیع‌شده و موازی در اوایل دهه ۱۹۹۰ ظهور کردند زیرا محققان به دنبال غلبه بر همگرایی زودهنگام و بهره‌برداری از سخت‌افزار موازی بودند. Adamidis و Petridis (1996) جمعیت‌های عامل همکار با رفتارهای تکاملی متفاوت را رسمی کردند. چارچوب مبتنی بر عامل در اواخر دهه ۱۹۹۰ و دهه ۲۰۰۰ با گسترش مدل‌سازی مبتنی بر عامل در علوم محاسباتی، محبوبیت یافت و مدل تعامل خودمختار و تحت کنترل توپولوژی را که اکنون به طور گسترده در بهینه‌سازی پیچیده به کار می‌رود، رسمی کرد.

چه زمانی استفاده شود

هنگامی که چشم‌انداز برازش ناهموار یا چندوجهی است و الگوریتم‌های ژنتیک استاندارد به طور مداوم زود همگرا می‌شوند؛ هنگامی که سخت‌افزار موازی یا توزیع‌شده در دسترس است که می‌تواند فرآیندهای عامل همزمان را میزبانی کند؛ یا زمانی که ساختار مسئله به طور طبیعی با زیرمسائل نیمه‌مستقل مطابقت دارد (مانند زنجیره‌های تأمین منطقه‌ای، سیاست‌های چندبخشی). همچنین زمانی که کاوش رفتار الگوریتم تحت فشارهای تکاملی ناهمگن مناسب است. زمانی که مسئله دارای یک چشم‌انداز تک‌وجهی است (الگوریتم ژنتیک ساده‌تر کافی است)، زمانی که سربار ارتباطات بین عامل‌ها بر محاسبات غلبه می‌کند، زمانی که اندازه‌های جمعیت برای تقسیم معنادار خیلی کوچک هستند، یا زمانی که یک جمعیت متمرکز برای تکرارپذیری دقیق مورد نیاز است، از ABGA استفاده نکنید.

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

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

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

توپولوژی عامل را تعریف کنید: تعداد عامل‌ها (زیرجمعیت‌ها)، ساختار همسایگی آن‌ها (حلقه، شبکه، گراف دنیای کوچک، یا کاملاً متصل)، و پروتکل ارتباطی که زمان و نحوه تبادل افراد توسط عامل‌ها را تعیین می‌کند، مشخص کنید. هر عامل یک موجودیت محاسباتی خودمختار با استخر کروموزومی خود است.

2

زیرجمعیت محلی هر عامل را با کروموزوم‌های تولید شده به صورت تصادفی (یا راه‌حل‌های اولیه) مقداردهی اولیه کنید. اندازه جمعیت محلی، عملگرهای ژنتیک (نوع و نرخ تقاطع، نرخ جهش)، و مکانیزم انتخاب (تورنمنت، گردونه، رتبه‌بندی) را به طور مستقل برای هر عامل یا به طور یکنواخت در تمام عامل‌ها تنظیم کنید.

3

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

4

در فواصل مهاجرت تعریف شده، عامل‌ها زیرمجموعه‌ای از افراد با بالاترین برازش خود را با عامل‌های همسایه طبق سیاست مهاجرت (مثلاً بهترین‌ها را بفرست، بدترین‌ها را دریافت کن/جایگزین کن) به اشتراک می‌گذارند. نرخ مهاجرت و توپولوژی، تعادل بین بهره‌برداری محلی و کاوش جهانی را شکل می‌دهند؛ مهاجرت بیش از حد مکرر تنوع را از بین می‌برد، مهاجرت بسیار نادر معماری توزیع‌شده را هدر می‌دهد.

5

تمام کروموزوم‌های وارد شده و تکامل یافته محلی در برابر تابع برازش مشترک ارزیابی می‌شوند. عامل‌ها ممکن است پس از مهاجرت فشار انتخاب محلی را برای ادغام افراد دریافت شده در جمعیت خود اعمال کنند و به طور بالقوه افراد کم‌برازش قبلی را حذف کنند. ارزیابی برازش، هزینه محاسباتی غالب است.

6

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

دام‌های رایج

  • تنظیم نرخ مهاجرت بیش از حد بالا، تنوع زیرجمعیت را به یک استخر واحد در عمل فرو می‌پاشد و مزیت اصلی معماری عامل را از بین می‌برد.
  • نادیده گرفتن طراحی توپولوژی همسایگی: یک توپولوژی کاملاً متصل باعث همگرایی سریع می‌شود؛ یک حلقه با فرکانس مهاجرت ضعیف ممکن است عامل‌ها را منزوی و راکد بگذارد.
  • ارزیابی برازش فقط به صورت محلی بدون تابع برازش جهانی مشترک، منجر به بهینه‌سازی اهداف ناسازگار توسط عامل‌ها می‌شود.
  • اشتباه گرفتن ABGA با الگوریتم ژنتیک چندهدفه: ABGA یک نوع معماری برای کارایی جستجو است، نه ذاتاً یک روش چندهدفه — ABGA چندهدفه نیاز به ماشین‌آلات پارِتو اضافی دارد.
  • توقف بر اساس همگرایی عامل منفرد به جای همگرایی جهانی می‌تواند راه‌حل‌های بهتر که هنوز در عامل‌های دیگر در حال تکامل هستند را از دست بدهد.

پرسش‌های متداول

ABGA چگونه با یک الگوریتم ژنتیک استاندارد موازی تفاوت دارد؟

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

از چه توپولوژی مهاجرتی باید استفاده کنم؟

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

چند عامل و چه اندازه زیرجمعیت مناسب است؟

یک قاعده سرانگشتی رایج 4 تا 16 عامل با اندازه‌های زیرجمعیت 20 تا 50 فرد در هر کدام است، که در مجموع جمعیتی قابل مقایسه با آنچه یک الگوریتم ژنتیک استاندارد استفاده می‌کند، ایجاد می‌کند. تعداد کم عامل‌ها مزیت تنوع معماری را از بین می‌برد؛ تعداد زیاد عامل‌ها با زیرجمعیت‌های کوچک دچار رانش می‌شوند. تنظیم تجربی بر روی مسئله خاص ضروری است.

آیا ABGA می‌تواند برای بهینه‌سازی چندهدفه استفاده شود؟

بله، اما ماشین‌آلات پارِتو اضافی (مانند رتبه‌بندی NSGA-II در هر عامل) باید اضافه شود. سپس معماری عامل به حفظ تقریب بهتر جبهه پارِتو کمک می‌کند. این اساس انواع ABGA چندهدفه است.

آیا ABGA تضمین شده است که به بهینه سراسری دست یابد؟

خیر. مانند تمام الگوریتم‌های ژنتیک، ABGAها ابتکاری هستند و هیچ تضمینی برای بهینگی سراسری ارائه نمی‌دهند. حفظ تنوع بهبود یافته، احتمال اجتناب از بهینه‌های محلی را در عمل افزایش می‌دهد، اما تضمین‌های همگرایی قوی‌تر از الگوریتم‌های ژنتیک استاندارد نیستند و یک سؤال تحقیقاتی نظری فعال محسوب می‌شوند.

روش‌های مرتبط

منابع

  1. Adamidis, P., & Petridis, V. (1996). Co-operating populations with different evolution behaviors. Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1996), 188-191. IEEE.

    باز کردن مرجع انتشار
    کپی شد.
  2. Genetic algorithm. Wikipedia.

    باز کردن مرجع انتشار
    کپی شد.