جستجوی تبو مبتنی بر عامل — بهینهسازی فراابتکاری چند عاملی توزیعشده
- معرفیشده توسط
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- سال
- 1989–1995
- نوع
- Hybrid metaheuristic — agent-based distributed tabu search
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
جستجوی تبو مبتنی بر عامل (ABTS) فراابتکاری جستجوی تبو را در یک چارچوب چند عاملی جاسازی میکند که در آن عاملهای خودمختار هر کدام نخهای جستجوی تبو مستقل یا همکاریکننده را اجرا میکنند، راهحلهای امیدوارکننده را برای فرار از بهینههای محلی به اشتراک میگذارند و فضاهای جستجوی ترکیبی یا پیوسته بزرگ را بهطور مؤثرتر از یک پیادهسازی تکنخی کاوش میکنند.
شهود پشت روش
جستجوی تبو کلاسیک حتی با مکانیسم حافظه کوتاهمدت خود میتواند در کاوش یک ناحیه باریک گیر کند. با استقرار عاملهای خودمختار متعدد، که هر کدام لیست تبو و همسایگی خود را حفظ میکنند، جستجو در نقاط شروع متنوع پخش میشود. عاملها بهطور دورهای راهحلهای نخبه (تشدید) را به اشتراک میگذارند و عمداً به مناطق کاوشنشده پراکنده میشوند (تنوعبخشی). این ساختار همکاری در عین حال مستقل، رفتار ازدحام بیولوژیکی را منعکس میکند — هیچ عاملی تصویر کاملی ندارد، اما جمع بهطور قابل توجهی سریعتر از هر جستجوگر فردی راهحلهای با کیفیت بالا پیدا میکند.
تاریخ
جستجوی تبو توسط فرد گلاور در سالهای 1986-1989 رسمی شد. انواع توزیعشده و موازی در اوایل دهه 1990 پدیدار شدند زیرا محققان به دنبال بهرهبرداری از معماریهای چند پردازندهای بودند. ورهوفن و آرتس (1995) مطالعه سیستماتیکی از جستجوی محلی موازی از جمله استراتژیهای تبو همکاریکننده ارائه دادند. چارچوب مبتنی بر عامل در دهه 2000 با ورود واژگان مدلسازی مبتنی بر عامل به تحقیق در عملیات، برجسته شد.
چه زمانی استفاده شود
هنگام حل مسائل بهینهسازی ترکیبی یا مختلط صحیح دشوار (زمانبندی، مسیریابی، طراحی شبکه، تخصیص منابع) که در آن جستجوی تبو تکنخی دچار رکود میشود و منابع محاسباتی موازی در دسترس هستند، از جستجوی تبو مبتنی بر عامل استفاده کنید. این روش بهویژه زمانی مؤثر است که چشمانداز جستجو دارای بهینههای محلی با کیفیت مشابه زیادی باشد. زمانی از آن اجتناب کنید که مسئله به اندازه کافی کوچک برای حلکنندههای دقیق (MILP، شاخه و کران) باشد، زمانی که یک ارزیابی واحد از نظر محاسباتی ممنوع است (که باعث میشود ارزیابیهای موازی متعدد غیرممکن شود)، یا زمانی که الزامات تکرارپذیری با پویاییهای غیرقطعی و تعامل عامل مغایرت دارد.
محدودیتها و ملاحظات
- سربار همگامسازی و هزینه ارتباط بین عاملها میتواند مزایای موازیسازی را در سیستمهای بهشدت جفتشده یا شبکههای کند خنثی کند.
- پارامترهای بیشتری نسبت به جستجوی تبو تکنخی: تعداد عاملها، توپولوژی ارتباطی، فرکانس همگامسازی و محرکهای تنوعبخشی همگی نیاز به تنظیم دارند.
- تضمینهای همگرایی نظری ضعیفتر از روشهای دقیق هستند؛ کیفیت راهحل به شدت به تنظیمات و ساختار مسئله بستگی دارد.
- دستیابی به تکرارپذیری دشوار است زیرا تعاملات عامل، تصادفی بودن اضافی فراتر از مقداردهی اولیه تصادفی را معرفی میکند.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- کاوش موازی به طور قابل توجهی زمان رسیدن به راهحل را در مسائل ترکیبی بزرگ در مقایسه با جستجوی تبو تکنخی کاهش میدهد.
- چارچوب چند عاملی به طور طبیعی از تنوعبخشی پشتیبانی میکند و خطر همگرایی زودهنگام به بهینههای محلی ضعیف را کاهش میدهد.
- معماری انعطافپذیر امکان عاملهای ناهمگن با ساختارهای همسایگی متفاوت، استراتژیهای مدت زمان تبو، یا حتی فراابتکاریهای ترکیبی را فراهم میکند.
- اشتراکگذاری راهحلهای همکاریکننده، اکتشافات را بین عاملها منتقل میکند و تشدید در اطراف مناطق با کیفیت بالا را تسریع میبخشد.
- به خوبی با هستههای محاسباتی موجود مقیاسپذیر است و آن را برای محیطهای محاسباتی مدرن چند هستهای و توزیعشده مناسب میسازد.
کاربردها
- مسیریابی وسایل نقلیه و لجستیک: هماهنگ کردن عاملهای متعدد که هر کدام زیرمسائل مسیر را بهینهسازی میکنند.
- زمانبندی کارگاه و تولید انعطافپذیر: عاملها زیرمجموعههای ماشین را بهطور همکاریکننده مدیریت میکنند.
- طراحی شبکه مخابراتی: تخصیص کانال توزیعشده و بهینهسازی توپولوژی.
- برنامهریزی زنجیره تأمین: بهینهسازی موجودی و توزیع چند سطحی.
- پیشبینی ساختار پروتئین: جستجوی همسایگی موازی در فضاهای پیکربندی.
- زمانبندی دانشگاهی و زمانبندی دورهها با عاملهای سطح دپارتمان توزیعشده.
چگونه کار میکند
چگونه کار میکند
مجموعهای از عاملهای خودمختار را تعریف کنید. به هر عامل نقشی اختصاص داده میشود: برخی بر تشدید (جستجوی محلی عمیق در اطراف مناطق امیدوارکننده) تمرکز میکنند، برخی دیگر بر تنوعبخشی (فرار به مناطق کاوشنشده). هر عامل لیست تبو خود از حرکات ممنوعه، یک راهحل فعلی و یک ساختار همسایگی متناسب با نوع مسئله (به عنوان مثال، حرکات تعویض، درج، یا 2-opt برای مسائل ترکیبی) را حفظ میکند.
عاملها را با راهحلهای شروع متمایز مقداردهی اولیه کنید، که بهصورت تصادفی تولید شدهاند یا از طریق یک فراابتکاری سازنده (مانند نزدیکترین همسایه برای مسیریابی) بذرپاشی شدهاند. تنوع در راهحلهای شروع حیاتی است — شروعهای یکسان منجر به جستجوهای موازی تکراری میشود. تابع هدف را برای هر راهحل اولیه ارزیابی کنید و بهترین راهحل جهانی را در بین همه عاملها ثبت کنید.
هر عامل حلقه جستجوی تبوی خود را اجرا میکند: همسایگی راهحل فعلی را تولید کنید، همه (یا زیرمجموعهای از) راهحلهای همسایه را ارزیابی کنید، بهترین همسایه غیر تبو را به عنوان حرکت بعدی انتخاب کنید (معیار استیذان اجازه میدهد لیست تبو را نادیده بگیرید اگر کاندیدا از بهترین جهانی فراتر رود)، و لیست تبو را با افزودن حرکت معکوس با مدت زمان مشخص شده از یک دامنه ثابت یا تطبیقی بهروز کنید.
عاملها در فواصل همگامسازی تعریف شده یا محرکهای رویداد ارتباط برقرار میکنند. استراتژیهای رایج شامل پخش بهترین جهانی فعلی به همه عاملها (که ممکن است از آن مجدداً شروع کنند)، تزریق راهحل نخبه به یک استخر مشترک که عاملها بهطور دورهای با آن مشورت میکنند، یا تبادل راهحل همتا به همتا بین عاملهای همسایه در یک توپولوژی (حلقه، کاملاً متصل، یا تصادفی) است. کنترلهای تنوع با جریمه کردن عاملهایی که راهحلهای یکسان دارند، از همگرایی زودهنگام جلوگیری میکنند.
زمانی که بودجه حداکثر تکرار، محدودیت زمانی ساعت دیواری، یا معیار رکود برآورده شود (به عنوان مثال، عدم بهبود در بهترین جهانی برای تعداد معینی تکرار) خاتمه دهید. بهترین راهحل جهانی یافت شده در بین همه عاملها در تمام تکرارها را به عنوان خروجی نهایی انتخاب کنید. در صورت پیگیری اهداف چندگانه، بهطور اختیاری یک جبهه پارتو را گزارش کنید.
دامهای رایج
- تنظیم همه عاملها به راهحلهای شروع یکسان، ظرفیت موازی را تلف میکند — مقداردهی اولیه متنوع را تضمین کنید.
- ارتباط بیش از حد مکرر عاملها را مجبور به ورود به همان حوزه راهحل میکند، مزایای تنوعبخشی را از بین میبرد و جستجو را به طور مؤثر به یک نخ کاهش میدهد.
- نادیده گرفتن معیار استیذان در طراحی لیست تبو میتواند باعث شود عاملها راهحلهای بدیهی بهتر را از دست بدهند، بهویژه در مرحله اولیه جستجو.
- اعمال ABTS بر روی مسائلی که در آنها ارزیابی همسایگی بدون مدل جایگزین بسیار پرهزینه است، منجر به زمان اجرای ممنوع خواهد شد.
پرسشهای متداول
جستجوی تبو مبتنی بر عامل چگونه با اجرای صرف چندین نخ جستجوی تبو متفاوت است؟
تفاوت کلیدی همکاری است. در اجرای موازی مستقل، نخها هرگز اطلاعات را به اشتراک نمیگذارند. در ABTS، عاملها فعالانه راهحلها را تبادل میکنند، یک استخر نخبه مشترک را بهروز میکنند، یا محرکهای تنوعبخشی را بر اساس وضعیت جمعی اتخاذ میکنند — رفتارهای جستجوی نوظهوری را تولید میکنند که از اجرای مستقل غایب است.
چند عامل باید استفاده کنم؟
یک نقطه شروع رایج، یک عامل برای هر هسته CPU موجود است. تحقیقات نشان میدهد که بازده نزولی فراتر از 8-16 عامل برای اکثر مسائل ترکیبی وجود دارد، زیرا سربار ارتباطی افزایش مییابد. آزمایشهای آزمایشی با 4، 8 و 16 عامل به شناسایی نقطه بهینه برای یک مسئله معین کمک میکند.
آیا ABTS میتواند مسائل چندهدفه را مدیریت کند؟
بله. عاملها میتوانند تقریبهای محلی از یک جبهه پارتو را حفظ کنند و راهحلهای غیر مغلوب را از طریق یک بایگانی مشترک به اشتراک بگذارند. این گاهی اوقات جستجوی تبو چندهدفه مبتنی بر عامل نامیده میشود و با ABTS استاندارد تکهدفه متفاوت است.
کدام توپولوژی ارتباطی بهترین است؟
توپولوژیهای کاملاً متصل، راهحلهای خوب را سریعتر پخش میکنند اما هزینه ارتباط بالایی ایجاد میکنند. توپولوژیهای حلقه یا دنیای کوچک، انتشار اطلاعات را با استقلال متعادل میکنند. برای اکثر مسائل عملی، یک توپولوژی حلقه یا تصادفی پراکنده به عنوان پیشفرض به خوبی کار میکند.
چه زمانی الگوریتم ژنتیک یا پارتیکل سوارم را بر ABTS ترجیح دهم؟
روشهای مبتنی بر جمعیت (GA، PSO) را زمانی ترجیح دهید که مسئله دارای چشمانداز پیوسته و هموار باشد یا زمانی که عملگرهای تقاطع/تولید مثل بهخوبی تعریف شده باشند. ABTS در مسائل گسسته و ترکیبی با عملگرهای همسایگی بهخوبی تعریف شده که در آنها حافظه تبو مزیت جستجوی قوی را فراهم میکند، برتری دارد.
روشهای مرتبط
منابع
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
باز کردن مرجع DOIکپی شد.Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
باز کردن مرجع DOIکپی شد.