بهینهسازی چندهدفه تکاملی مبتنی بر شبیهسازی عامل-محور با الگوریتم NSGA-II
- معرفیشده توسط
- Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
- سال
- 2000s–2010s
- نوع
- Simulation-embedded evolutionary multi-objective optimizer
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
الگوریتم NSGA-II مبتنی بر عامل، الگوریتم تکاملی NSGA-II را در یک حلقه شبیهسازی مبتنی بر عامل جاسازی میکند تا مقادیر هدف برای هر راهحل کاندید از طریق اجرای یک شبیهسازی کامل عامل به جای ارزیابی یک تابع بسته به دست آید. این ترکیب، بهینهسازی چندهدفه را بر روی سیستمهایی که عملکردشان از تعاملات سطح خرد عاملهای خودمختار ناشی میشود، نه از معادلات قابل تحلیل ریاضی، امکانپذیر میسازد.
شهود پشت روش
الگوریتم استاندارد NSGA-II برای امتیازدهی به هر راهحل بر اساس چندین هدف، یک فرمول ریاضی را فراخوانی میکند. هنگامی که رفتار سیستم برای بیان به صورت فرمول بیش از حد پیچیده یا نوظهور است — به اپیدمیها، شبکههای ترافیک، یا زنجیرههای تأمین با بازیگران سازگار فکر کنید — آن فرمول را با یک شبیهسازی مبتنی بر عامل جایگزین میکنید. هر راهحل کاندید پارامترهای خطمشی یا قوانین عامل را رمزگذاری میکند؛ شبیهسازی به جلو اجرا میشود، نتایج تجمعی به عنوان مقادیر هدف اندازهگیری میشوند، و مرتبسازی غیرمغلوب و انتخاب مبتنی بر فاصله ازدحام NSGA-II سپس یک جبهه پارتو متنوع از راهحلهای بدهبستان را ایجاد میکنند. نتیجه مجموعهای از پیکربندیهای پارامتری است که به طور همزمان در تمام اهداف مدلسازی شده، کارآمد پارتو هستند، حتی زمانی که آن اهداف از پویاییهای سازگار پیچیده ناشی میشوند.
تاریخ
NSGA-II توسط Kalyanmoy Deb و همکارانش در IIT Kanpur در سال 2002 به عنوان یک الگوریتم ژنتیک چندهدفه سریع و نخبهگرا معرفی شد و به سرعت به یکی از پر استنادترین الگوریتمها در محاسبات تکاملی تبدیل شد. مدلسازی مبتنی بر عامل به عنوان یک پارادایم محاسباتی در دهه 1990 با پلتفرمهایی مانند Swarm، NetLogo و Repast رشد کرد. ترکیب NSGA-II با شبیهسازیهای مبتنی بر عامل در دهههای 2000 و 2010 با تلاش محققان در برنامهریزی شهری، بومشناسی، همهگیرشناسی و مدیریت زنجیره تأمین برای بهینهسازی خطمشیها در سیستمهایی که برای فرمولبندی تحلیلی بیش از حد پیچیده بودند، ظهور کرد.
چه زمانی استفاده شود
از NSGA-II مبتنی بر عامل زمانی استفاده کنید که دو یا چند هدف متضاد باید به طور همزمان بهینهسازی شوند و آن اهداف از تعاملات عامل ناشی میشوند نه از توابع بسته — به عنوان مثال، متعادل کردن هزینه مهار اپیدمی و فعالیت اقتصادی در یک مدل جمعیت، یا حداقل کردن هزینه زنجیره تأمین در حالی که استحکام را در شبکهای از تأمینکنندگان سازگار حداکثر میکنید. این روش زمانی مناسب است که تصادفی بودن در سیستم ذاتی باشد و باید بر روی تکرارها میانگینگیری شود. زمانی که یک تابع هدف تحلیلی سریع وجود دارد (NSGA-II ساده کافی و بسیار ارزانتر است)، زمانی که فقط یک هدف مرتبط است، زمانی که شبیهسازی عامل در هر اجرا بسیار پرهزینه است به طوری که حتی یک جمعیت کوچک هزینه محاسباتی کل را غیرممکن میسازد، یا زمانی که بیش از سه یا چهار هدف مورد نیاز است (به جای آن، انواع NSGA-III یا MOEA/D را ترجیح دهید)، از آن استفاده نکنید.
محدودیتها و ملاحظات
- از نظر محاسباتی بسیار پرهزینه: هر نسل به N x R اجرای شبیهسازی نیاز دارد، که در آن R تکرار در هر فرد ممکن است زیاد باشد؛ زمان کل ساعت دیواری میتواند بازدارنده باشد.
- عملکرد با بیش از سه یا چهار هدف کاهش مییابد، زیرا مرتبسازی غیرمغلوب قدرت تمایز را از دست میدهد و فاصله ازدحام در فضای هدف با ابعاد بالا غیرقابل اعتماد میشود.
- نتایج به وفاداری مدل شبیهسازی بستگی دارد؛ قوانین عامل غیرواقعی یا پارامترهای ضعیف کالیبره شده، صرف نظر از کیفیت بهینهسازی، جبهههای پارتو گمراهکنندهای تولید میکنند.
- تصادفی بودن در ارزیابی تناسب شبیهسازی میتواند مقایسههای مغلوب را خراب کند اگر تعداد تکرار R خیلی کم باشد، که منجر به رتبهبندی نادرست پارتو میشود.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- مناظر هدف نوظهور، وابسته به مسیر، و تصادفی را که نمیتوانند به صورت تحلیلی بیان شوند، مدیریت میکند و آن را برای سیستمهای سازگار پیچیده قابل استفاده میسازد.
- یک جبهه پارتو کامل را در یک اجرای بهینهسازی واحد تولید میکند و دید صریح بدهبستان را بدون نیاز به وزنهای ترجیحی قبلی به تصمیمگیرندگان میدهد.
- مکانیزم نخبهگرایی NSGA-II تضمین میکند که راهحلهای غیرمغلوب با کیفیت بالا در طول نسلها هرگز دور ریخته نمیشوند.
- میانگینگیری تکرار در هر ارزیابی تناسب به روش اجازه میدهد تا نویز شبیهسازی تصادفی را به شیوهای اصولی مدیریت کند.
- سازگار با هر پلتفرم شبیهسازی مبتنی بر عامل (NetLogo, Repast, AnyLogic, Mesa) از طریق یک رابط پوشش استاندارد شده.
کاربردها
- طراحی مداخله همهگیر: یافتن ترکیبات بهینه پارتو از پوشش واکسیناسیون و محدودیتهای حرکتی که به طور مشترک بار عفونت و هزینه اقتصادی را در یک مدل عامل جمعیت به حداقل میرسانند.
- برنامهریزی کاربری زمین و حملونقل شهری: بهینهسازی پارامترهای منطقهبندی و سرمایهگذاری زیرساخت که به عنوان نتایج تراکم، انتشار آلایندهها و برابری از تعاملات عاملان ساکن و وسایل نقلیه پدیدار میشوند.
- طراحی شبکه زنجیره تأمین: شناسایی پیکربندیهای خطمشی که هزینه، زمان تحویل و تابآوری در برابر اختلال را در شبکههایی از تأمینکنندگان و توزیعکنندگان سازگار متعادل میکنند.
- مدیریت برداشت زیستمحیطی: بهینهسازی قوانین برداشت برای حداکثر کردن همزمان بازده اقتصادی و حفظ تنوع زیستی در یک مدل زیستمحیطی مبتنی بر عامل.
- کنترل ریزشبکه انرژی: همبهینهسازی استراتژیهای مناقصه عاملان مصرفکننده-تولیدکننده برای حداقل کردن هزینه شبکه و انتشار کربن تحت تولید پراکنده تجدیدپذیر تصادفی.
- تحلیل خطمشی نابرابری اجتماعی: یافتن مجموعههای پارامتر مداخله که به طور مشترک برابری درآمد و کارایی بازار کار را در مدلهای اقتصادی مبتنی بر عامل بهبود میبخشند.
چگونه کار میکند
چگونه کار میکند
متغیرهای تصمیم (پارامترهای رفتاری عامل، اهرمهای خطمشی، تخصیص منابع) را تعریف کرده و اهداف متضاد برای بهینهسازی (به عنوان مثال، حداقل کردن هزینه و حداکثر کردن نرخ خدمات) را فهرست کنید. یک مدل شبیهسازی مبتنی بر عامل بسازید یا پارامتردهی کنید که یک بردار متغیر تصمیم را بپذیرد و در پایان هر اجرای شبیهسازی، معیارهای هدف را برگرداند. محدودیتها، مدت زمان شبیهسازی و تعداد تکرارهای تصادفی در هر ارزیابی را مشخص کنید.
یک جمعیت N از بردارهای راهحل کاندید را با نمونهبرداری یکنواخت تصادفی از فضای تصمیم یا از طریق نمونهبرداری مکعب لاتین مقداردهی اولیه کنید. هر فرد نمایانگر یک پیکربندی از پارامترهای عامل یا تنظیمات خطمشی است. ابرپارامترهای NSGA-II را تنظیم کنید: اندازه جمعیت N، احتمال تقاطع، نرخ جهش، و حداکثر تعداد نسل.
برای هر فرد در جمعیت فعلی، شبیهسازی مبتنی بر عامل را R بار (تکرار) اجرا کرده و مقادیر هدف حاصل را میانگینگیری کنید تا نویز تصادفی کاهش یابد. بردار هدف میانگین را برای هر فرد ثبت کنید. این مرحله هزینه محاسباتی را غالب میکند: N فرد ضربدر R تکرار ضربدر T گام زمانی شبیهسازی در هر ارزیابی.
مرتبسازی سریع غیرمغلوب را برای رتبهبندی تمام افراد به جبهههای پارتو F1، F2، ... اعمال کنید. جبهه F1 شامل راهحلهایی است که توسط هیچ فرد دیگری مغلوب نشدهاند؛ F2 شامل آنهایی است که فقط توسط اعضای F1 مغلوب شدهاند، و غیره. در داخل هر جبهه، فاصله ازدحام را محاسبه کنید — مجموع فاصلههای همسایه نرمالشده در امتداد هر محور هدف — تا انزوای هر راهحل را کمیسازی کرده و تنوع را در سراسر جبهه حفظ کنید.
والدین را از طریق تورنمنت دودویی با استفاده از عملگر مقایسه ازدحامی انتخاب کنید: اولویت با فرد در جبهه با شماره پایینتر است، و در صورت تساوی، فرد با فاصله ازدحام بیشتر ترجیح داده میشود. تقاطع دودویی شبیهسازی شده (SBX) و جهش چندجملهای را برای تولید N فرزند اعمال کنید. والدین و فرزندان را در یک مجموعه 2N نفری ادغام کرده، دوباره مرتب کنید، و بهترین N فرد را برای نسل بعدی با استفاده از رتبه جبهه و فاصله ازدحام به عنوان تعیینکننده تساوی حفظ کنید.
پس از رسیدن به معیار توقف (بودجه نسل تمام شده یا همگرایی حجم ابر تأیید شده)، جبهه F1 جمعیت نهایی را به عنوان مجموعه تقریبی پارتو بهینه برگردانید. سطح بدهبستان را در فضای هدف تجسم کرده و حجم ابر یا فاصله نسل معکوس (IGD) را به عنوان معیارهای کیفیت که بر روی چندین اجرای مستقل تجمیع شدهاند، گزارش دهید.
دامهای رایج
- استفاده از تعداد تکرار کم در هر فرد (R = 1 یا 2) زمانی که شبیهسازی تصادفی است — یک تخمین تناسب پر نویز باعث میشود مرحله مرتبسازی مغلوب راهحلها را طبقهبندی اشتباه کند و جبهه پارتو را خراب کند.
- تنظیم اندازه جمعیت N کوچکتر از پیچیدگی مورد انتظار جبهه پارتو، که الگوریتم را مجبور میکند کل مناطق فضای بدهبستان را دور بریزد و یک جبهه تکهتکه برگرداند.
- اعمال این روش برای چهار یا بیشتر هدف بدون تغییر به NSGA-III یا MOEA/D، که باعث میشود بیشتر افراد در جبهه F1 تجمع یابند و انتخاب را تقریباً تصادفی کند.
- تداخل کالیبراسیون مدل عامل و بهینهسازی: مدل شبیهسازی باید قبل از شروع بهینهسازی بر روی دادههای مشاهده شده کالیبره شود — بهینهسازی یک مدل کالیبره نشده، جبهههای پارتو با اعتبار دنیای واقعی تولید میکند.
- نادیده گرفتن محاسبات موازی: از آنجایی که هر اجرای شبیهسازی مستقل است، NSGA-II مبتنی بر عامل به طور ناخواسته قابل موازیسازی است؛ اجرای آن به صورت تکرشتهای سختافزار موجود را هدر میدهد و زمان اجرا را غیرضروری طولانی میکند.
پرسشهای متداول
تفاوت NSGA-II مبتنی بر عامل با NSGA-II معمولی چیست؟
NSGA-II معمولی هر راهحل را با فراخوانی یک تابع تحلیلی ارزیابی میکند که سریع است. NSGA-II مبتنی بر عامل آن فراخوانی تابع را با یک اجرای کامل شبیهسازی مبتنی بر عامل جایگزین میکند، که امکان بهینهسازی بر روی اهداف نوظهور و وابسته به مسیر را فراهم میآورد، اما با هزینه محاسباتی به طور چشمگیری بالاتر در هر ارزیابی.
چند تکرار باید در هر ارزیابی فرد اجرا کنم؟
به اندازهای که ضریب تغییرات هر هدف در طول تکرارها به زیر حدود 5-10% برسد. با R = 10 شروع کنید و تا زمانی که تخمینهای هدف پایدار شوند، افزایش دهید. برای مدلهای بسیار تصادفی، ممکن است R = 30 تا 50 لازم باشد که به تبع آن هزینه را ضرب میکند.
چگونه میتوانم NSGA-II مبتنی بر عامل را از نظر محاسباتی عملی کنم؟
موازیسازی در هستههای CPU یا یک خوشه — اجرای شبیهسازی هر فرد مستقل و به راحتی قابل موازیسازی است. از مدلهای جایگزین (فرایندهای گوسی یا شبکههای عصبی) برای تقریب تناسب برای پیشغربالگری ارزان استفاده کنید و ارزیابیهای شبیهسازی کامل را برای کاندیداهای امیدوارکننده رزرو کنید.
اگر چهار یا بیشتر هدف داشته باشم چه؟
به یک نوع مبتنی بر عامل از NSGA-III یا MOEA/D تغییر دهید. NSGA-III از انتخاب مبتنی بر نقطه مرجع به جای فاصله ازدحام استفاده میکند و تنوع را به طور مؤثر در چهار یا بیشتر هدف حفظ میکند. MOEA/D مسئله را به زیرمسائل مقیاسبندی شده تجزیه میکند و به تنظیمات چندهدفه بهتر مقیاس میشود.
چگونه اعتبارسنجی کنم که جبهه پارتو قابل اعتماد است؟
حداقل 10 اجرای بهینهسازی مستقل با بذرهای تصادفی متفاوت اجرا کرده و برای هر کدام حجم ابر یا IGD را محاسبه کنید. میانگین و دامنه بین چارکی را در طول اجراها گزارش دهید. حجم ابر سازگار در طول اجراها نشان میدهد که بهینهساز به طور قابل اعتماد به همان جبهه پارتو تقریبی همگرا شده است.
روشهای مرتبط
منابع
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
باز کردن مرجع DOIکپی شد.Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.
باز کردن مرجع DOIکپی شد.