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

برنامه‌ریزی عدد صحیح مبتنی بر عامل — شبیه‌سازی-بهینه‌سازی ترکیبی برای سیستم‌های تصمیم‌گیری گسسته

معرفی‌شده توسط
Emerged from multi-agent systems and operations research communities
سال
1990s–2000s
نوع
Hybrid simulation-optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

بسیاری از مسائل بهینه‌سازی دنیای واقعی شامل تصمیم‌گیرندگان متمایز (عامل‌ها) هستند که با یکدیگر تعامل دارند، سازگار می‌شوند و به یکدیگر پاسخ می‌دهند، اما انتخاب‌های جمعی آن‌ها باید محدودیت‌های سخت عدد صحیح را برآورده کند. برنامه‌ریزی عدد صحیح خالص سیستم را یکپارچه در نظر می‌گیرد و پویایی‌های نوظهور را از دست می‌دهد؛ مدل‌های صرفاً مبتنی بر عامل رفتار غنی تولید می‌کنند اما تضمین‌های بهینگی سراسری را ندارند. ABIP با اجازه دادن به عامل‌ها برای شبیه‌سازی لایه رفتاری در حالی که یک فرمول‌بندی IP محدودیت‌های ساختاری و تابع هدف را در بر می‌گیرد، این شکاف را پر می‌کند. حل‌کننده ساختار ترکیبی را مدیریت می‌کند؛ عامل‌ها رفتار سازگار و ناهمگن را مدیریت می‌کنند — با هم راه‌حل‌هایی تولید می‌کنند که هم امکان‌پذیر و هم از نظر رفتاری واقع‌گرایانه هستند.

تاریخ

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

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

زمانی از ABIP استفاده کنید که سیستم شامل تصمیم‌گیرندگان ناهمگن و در تعامل باشد که رفتار جمعی آن‌ها الگوهای نوظهوری ایجاد می‌کند که بر امکان‌پذیری یا کیفیت بهینه‌سازی با محدودیت عدد صحیح تأثیر می‌گذارد (به عنوان مثال، زنجیره‌های تأمین چند سطحی، شبکه‌های حمل‌ونقل، بازارهای برق، تخصیص وظیفه چند ربات). این روش به‌ویژه زمانی ارزشمند است که IP خالص برای ثبت رفتار سازگار عامل بیش از حد سفت و سخت باشد، یا زمانی که شبیه‌سازی صرفاً مبتنی بر عامل نمی‌تواند امکان‌پذیری تصمیمات گسسته را تضمین کند. زمانی از آن استفاده نکنید که عامل‌ها همگن و غیرتعاملی هستند (IP استاندارد کافی است)، زمانی که سیستم پیوسته است (به جای آن از برنامه‌ریزی خطی مبتنی بر عامل استفاده کنید)، یا زمانی که منابع محاسباتی به‌شدت محدود هستند — حلقه ترکیبی شبیه‌سازی-بهینه‌سازی از نظر محاسباتی پرهزینه است.

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

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

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

نقاط قوت

  • رفتار نوظهور و سازگار را که مدل‌های یکپارچه برنامه‌ریزی عدد صحیح نمی‌توانند نشان دهند، ثبت می‌کند.
  • محدودیت‌های سخت عدد صحیح و ترکیبی را که مدل‌های صرفاً مبتنی بر عامل فاقد آن هستند، اعمال می‌کند.
  • از عامل‌های ناهمگن با اهداف، قوانین و مجموعه‌های اطلاعاتی متفاوت پشتیبانی می‌کند.
  • امکان تحلیل سیاست پرسش و پاسخ (what-if) را با تغییر مستقل قوانین عامل یا محدودیت‌های IP فراهم می‌کند.
  • به‌طور طبیعی سیستم‌های غیرمتمرکز را مدل‌سازی می‌کند که در آن هیچ عاملی کنترل همه تصمیمات را ندارد.

کاربردها

  • بهینه‌سازی زنجیره تأمین چند سطحی که در آن عامل‌های تأمین‌کننده رفتار سفارش‌دهی را تطبیق می‌دهند و یک IP مرکزی تخصیص موجودی گسسته را انجام می‌دهد.
  • تخصیص وظیفه و زمان‌بندی چند ربات در سیستم‌های اتوماسیون انبار.
  • توزیع بازار برق که در آن عامل‌های تولیدکننده به‌صورت استراتژیک پیشنهاد قیمت می‌دهند و یک ISO برنامه واحد تعهد (unit-commitment) IP را حل می‌کند.
  • طراحی شبکه حمل‌ونقل شهری با عامل‌های مسافر ناهمگن و تصمیمات سرمایه‌گذاری پیوند گسسته.
  • تخصیص منابع مراقبت‌های بهداشتی که جریان‌های عامل بیمار را با زمان‌بندی گسسته تخت و کارکنان با محدودیت عدد صحیح ترکیب می‌کند.

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

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

1

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

2

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

3

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

4

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

5

حالت‌های عامل و محیط را بر اساس راه‌حل IP به‌روز کنید. عامل‌ها تخصیص یا برنامه بهینه‌شده را دریافت کرده و برنامه‌های خود را بر این اساس تنظیم می‌کنند. این حلقه بازخورد ممکن است باعث انطباق رفتاری بیشتری شود.

6

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

دام‌های رایج

  • ABIP را به عنوان یک جعبه سیاه در نظر گرفتن بدون اعتبارسنجی اینکه آیا قوانین عامل رفتار واقعی تصمیم‌گیرندگان را به‌درستی منعکس می‌کنند.
  • نادیده گرفتن حلقه بازخورد: حل IP یک بار بدون بازگشت به شبیه‌سازی عامل، پویایی‌های سازگار را که در ابتدا انگیزه استفاده از ABIP را ایجاد کرده بود، از دست می‌دهد.
  • بیش از حد محدود کردن IP تا حدی که رفتار عامل را بی‌ربط کند و ارزش افزوده رویکرد ترکیبی را از بین ببرد.
  • استفاده از ABIP برای مسائلی که برنامه‌ریزی عدد صحیح تصادفی (stochastic IP) با پارامترهای تصادفی کافی بود و بسیار کم‌هزینه‌تر بود.

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

ABIP چگونه با برنامه‌ریزی عدد صحیح تصادفی متفاوت است؟

IP تصادفی عدم قطعیت را از طریق توزیع‌های احتمال بر روی پارامترها مدل می‌کند اما تعاملات عامل منفرد را شبیه‌سازی نمی‌کند. ABIP به‌طور صریح رفتار عامل ناهمگن و پویایی‌های نوظهور را مدل می‌کند که IP تصادفی نمی‌تواند آن‌ها را ثبت کند — عدم قطعیت در ABIP ناشی از تعاملات عامل است، نه فقط تصادفی بودن پارامترها.

آیا IP باید در هر تکرار تا حد بهینگی حل شود؟

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

آیا ABIP می‌تواند مسائل چندهدفه را مدیریت کند؟

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

چه پلتفرم‌های نرم‌افزاری از ABIP پشتیبانی می‌کنند؟

پیاده‌سازی‌های رایج پلتفرم‌های مبتنی بر عامل (NetLogo, Repast, Mesa, AnyLogic) را با حل‌کننده‌های IP (CPLEX, Gurobi, CBC) ترکیب می‌کنند. به‌ویژه AnyLogic از ادغام تنگاتنگ شبیه‌سازی مبتنی بر عامل با بهینه‌سازی از طریق اتصالات حل‌کننده داخلی پشتیبانی می‌کند.

حلقه شبیه‌سازی-بهینه‌سازی چه زمانی همگرا می‌شود؟

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

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

منابع

  1. Wooldridge, M. (2009). An Introduction to MultiAgent Systems (2nd ed.). Wiley.

    شابک: 9780470519462
    کپی شد.
  2. Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.

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