جستجوی تَبُو چندهدفه (MOTS) — فراابتکاری برای حلهای بهینه پارتو
- معرفیشده توسط
- Hansen, M. P.; building on Glover (1989) Tabu Search
- سال
- 1997
- نوع
- Metaheuristic multi-objective optimization
- خانواده
- Simulation / optimization
این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید
چه کاری انجام میدهد؟
جستجوی تَبُو چندهدفه (MOTS) یک الگوریتم فراابتکاری است که چارچوب جستجوی تَبُو کلاسیک را گسترش میدهد تا به طور همزمان دو یا چند تابع هدف متعارض را بهینه کند. به جای یک بهینه واحد، به دنبال تقریب جبهه پارتو است — مجموعهای از راهحلها که در آن هیچ هدفی بدون بدتر کردن هدف دیگر قابل بهبود نیست — و این امر آن را برای مسائل بهینهسازی ترکیبی و پیوسته پیچیده در مهندسی، لجستیک و تحقیق در عملیات مناسب میسازد.
شهود پشت روش
تصور کنید در حال کاوش یک منظره ناهموار با تپهها و درههای متعدد هستید، اما چندین نقشه دارید که زمینهای مختلفی را نشان میدهند (یکی برای هر هدف) که با یکدیگر در تضاد هستند. MOTS با حرکت به سمت راهحلهای همسایه، نگهداری یک لیست حافظه کوتاهمدت (لیست تَبُو) از نقاط اخیراً بازدید شده برای جلوگیری از چرخه زدن، و نگهداری آرشیوی از راهحلهای غیرمغلوب یافت شده تا کنون، در این فضا پیمایش میکند. به طور دورهای، تنوعبخشی استراتژیک، جستجو را به مناطق کشف نشده جبهه پارتو سوق میدهد و بهرهبرداری از مناطق امیدوارکننده را با کاوش جهانی متعادل میکند.
تاریخ
جستجوی تَبُو چندهدفه، جستجوی تَبُو تکهدفه معرفی شده توسط فرد گلاور در سال ۱۹۸۹ را گسترش میدهد. اولین فرمولبندی سیستماتیک MOTS — شامل بایگانی پارتو و معیارهای پذیرش چندهدفه — توسط M. P. Hansen در کنفرانس MCDM سال ۱۹۹۷ ارائه شد. کارهای بعدی توسط Gandibleux، Teghem و دیگران، انواع مختلفی را برای مسائل ترکیبی تدوین کردند و MOTS از آن زمان به عنوان یک جایگزین رقابتی برای الگوریتمهای چندهدفه تکاملی در زمانبندی، لجستیک و طراحی مهندسی به کار گرفته شده است.
چه زمانی استفاده شود
زمانی که با یک مسئله بهینهسازی ترکیبی یا عدد صحیح مختلط با دو یا چند هدف متعارض (مانند هزینه در مقابل کیفیت، زمان در مقابل ریسک) روبرو هستید و روشهای دقیق از نظر محاسباتی غیرقابل حل هستند، از MOTS استفاده کنید. این الگوریتم در مسائل زمانبندی، مسیریابی وسایل نقلیه، طراحی شبکه و انتخاب پرتفوی که فضای جستجو برای شمارش جامع بسیار بزرگ است، عالی عمل میکند. زمانی که ساختار محیط معنیدار است و عملگرهای حرکتی را میتوان به وضوح تعریف کرد، MOTS را به جستجوی کاملاً تصادفی ترجیح دهید. از MOTS استفاده نکنید زمانی که: مسئله هدف واحدی دارد (جستجوی تَبُو ساده کافی است)؛ زمانی که جبهه پارتو را میتوان به طور دقیق شمارش کرد؛ زمانی که اطلاعات گرادیان در دسترس است و منظره محدب است (به جای آن از برنامهریزی ریاضی استفاده کنید)؛ یا زمانی که تصمیمات بلادرنگ به خروجیهای قطعی و تکرارپذیر بدون تغییرات تصادفی نیاز دارند.
محدودیتها و ملاحظات
- عملکرد به شدت به طول لیست تَبُو، تعریف محیط و استراتژی تنوعبخشی حساس است — که نیاز به تنظیم دقیق پارامترها دارد.
- هیچ تضمینی برای همگرایی به جبهه پارتو واقعی وجود ندارد؛ کیفیت راهحل به طول اجرا و ساختار مسئله بستگی دارد.
- از نظر محاسباتی در هر تکرار گران است، زمانی که محیطها بزرگ هستند یا ارزیابی اهداف پرهزینه است.
- نگهداری و بهروزرسانی آرشیو پارتو میتواند با افزایش تعداد اهداف و اندازه آرشیو، پرهزینه شود.
- پیادهسازی موازی به دلیل ماهیت مبتنی بر حافظه و ترتیبی مکانیزم تَبُو، ساده نیست.
شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.
نقاط قوت
- با استفاده از لیست تَبُو، از بازدید مجدد راهحلهای اخیر اجتناب میکند و خطر چرخه زدن در مناظر پیچیده را کاهش میدهد.
- معیارهای پذیرش، لغو محدودیتهای تَبُو را زمانی که یک حرکت منجر به بهبود استثنایی میشود، امکانپذیر میسازد و حافظه را با انعطافپذیری متعادل میکند.
- نیازی به اطلاعات گرادیان ندارد و آن را برای توابع هدف غیرقابل تفکیک، گسسته یا جعبه سیاه قابل استفاده میسازد.
- در یک اجرا، تقریب کل جبهه پارتو را تولید میکند و از تصمیمگیری چندمعیاره پشتیبانی میکند.
- طراحی انعطافپذیر محیط و عملگر حرکتی، سفارشیسازی خاص مسئله را امکانپذیر میسازد.
- مکانیزمهای تنوعبخشی، امکان فرار از بهینههای محلی و پوشش بهتر جبهه پارتو را فراهم میکنند.
کاربردها
- مسیریابی وسایل نقلیه چندهدفه و زمانبندی لجستیک (به حداقل رساندن هزینه و زمان تحویل به طور همزمان)
- زمانبندی پروژه دوهدفه: حداقل کردن زمان تکمیل و هزینه منابع تحت محدودیتهای پیشنیاز
- بهینهسازی پرتفوی: متعادل کردن بازده مورد انتظار در مقابل ریسک در کلاسهای دارایی متعدد
- طراحی شبکه: حداقل کردن هزینه نصب در حالی که قابلیت اطمینان یا توان عملیاتی را به حداکثر میرساند
- برنامهریزی فرآیند تولید: بهینهسازی مشترک زمان چرخه، مصرف انرژی و معیارهای کیفیت
- مدیریت محیط زیست: متعادل کردن خروجی اقتصادی در مقابل آلودگی یا تأثیر زیستمحیطی
چگونه کار میکند
چگونه کار میکند
جستجو را با یک یا چند راهحل اولیه (به صورت تصادفی تولید شده یا با روش ابتکاری ساخته شده) مقداردهی اولیه کنید. یک لیست تَبُو خالی با طول ثابت L تنظیم کرده و آرشیو پارتو را با راهحلهای غیرمغلوب از جمعیت اولیه مقداردهی اولیه کنید.
محیط N(s) راهحل فعلی s را با اعمال عملگرهای حرکتی (تعویض، درج، اغتشاش) تولید کنید. تمام راهحلهای همسایه را روی هر تابع هدف ارزیابی کنید تا نامزدها برای پیشرفت شناسایی شوند.
فیلتر تَبُو را اعمال کنید: همسایههایی را که حرکات تعریفکننده آنها در لیست تَبُو ظاهر میشود حذف کنید، مگر اینکه معیار پذیرش را برآورده کنند — معمولاً اینکه همسایه تمام اعضای فعلی آرشیو را مغلوب کند یا بهترین مقدار شناخته شده را در حداقل یک هدف بهبود بخشد. این از چرخه زدن جلوگیری کرده و کاوش را اجبار میکند.
بهترین همسایه غیر تَبُو (یا برنده معیار پذیرش) را به عنوان راهحل فعلی بعدی انتخاب کنید. آرشیو پارتو را با افزودن راهحل جدید در صورتی که غیرمغلوب باشد بهروزرسانی کنید؛ اعضای آرشیو را که توسط ورودی جدید مغلوب شدهاند حذف کنید.
استراتژیهای تنوعبخشی را زمانی که جستجو راکد میشود اعمال کنید: حافظه فرکانس بلندمدت مناطق به ندرت بازدید شده را شناسایی میکند؛ از راهحلهای آرشیو نخبه یا راهحلهای اغتشاش یافته تصادفی مجدداً شروع کنید تا پوشش جبهه پارتو را گسترش دهید.
مراحل محیط، فیلتر و آرشیو را تکرار کنید تا زمانی که معیار توقف برآورده شود — معمولاً حداکثر تعداد تکرارها، ارزیابیهای تابع، یا زمان CPU سپری شده. آرشیو پارتو را به عنوان جبهه بهینه پارتو تقریبی برگردانید.
دامهای رایج
- تنظیم لیست تَبُو خیلی کوتاه باعث چرخه زدن میشود؛ تنظیم آن خیلی طولانی جستجو را بیش از حد محدود کرده و راهحلهای خوب را از دست میدهد — کالیبراسیون تجربی ضروری است.
- نادیده گرفتن تنوعبخشی منجر به همگرایی زودهنگام در یک منطقه از جبهه پارتو میشود و تقریب ضعیفی تولید میکند.
- استفاده از MOTS با بیش از سه هدف، عملکرد را کاهش میدهد زیرا مدیریت آرشیو و حفظ تنوع از نظر محاسباتی طاقتفرسا میشود؛ برای مسائل چندهدفه، روشهای مبتنی بر تجزیه را در نظر بگیرید.
- استفاده از عملگرهای حرکتی عمومی بدون طراحی خاص مسئله، کیفیت راهحل را در مقایسه با پیادهسازیهای سفارشی شده به شدت محدود میکند.
- گزارش تنها آرشیو نهایی بدون بررسی تاریخچه همگرایی میتواند رکود زودهنگام را پنهان کند.
پرسشهای متداول
MOTS چگونه لیست تَبُو را در صورت وجود چندین هدف مدیریت میکند؟
لیست تَبُو حرکات (نه راهحلها) را ذخیره میکند، بنابراین مانند جستجوی تَبُو تکهدفه عمل میکند. تفاوت کلیدی این است که انتخاب بین همسایگان غیر تَبُو از مغلوبیت چندهدفه یا یک تابع مقیاسبندی استفاده میکند، و معیار پذیرش مجدداً تعریف میشود تا یک حرکت تَبُو مجاز باشد اگر راهحل حاصل توسط تمام اعضای فعلی آرشیو مغلوب نشود.
آرشیو پارتو چیست و اندازه آن چقدر باید باشد؟
آرشیو پارتو تمام راهحلهای غیرمغلوب یافت شده در طول جستجو را ذخیره میکند. حداکثر اندازه آن معمولاً محدود است (مثلاً ۱۰۰-۵۰۰ راهحل) تا هزینه حافظه و بهروزرسانی قابل مدیریت باقی بماند. هنگامی که آرشیو پر است، حذف با فاصله ازدحام یا مبتنی بر شبکه، راهحلها را از مناطق پر ازدحام حذف میکند تا تنوع حفظ شود.
MOTS چگونه با NSGA-II برای مسائل چندهدفه مقایسه میشود؟
NSGA-II از یک رویکرد تکاملی مبتنی بر جمعیت با تقاطع و جهش استفاده میکند و در اوایل جستجو در کاوش جهانی بهتر عمل میکند. MOTS به حرکات محیط و حافظه متکی است که اغلب کیفیت جستجوی محلی دقیقتری را ارائه میدهد. در عمل، MOTS تمایل دارد در مسائل ترکیبی با ساختار محیط قوی بهتر عمل کند، در حالی که NSGA-II برای مسائل پیوسته رایجتر است.
معمولاً به چند تکرار نیاز است؟
قانون جهانی وجود ندارد. رویه معمول این است که به جای تکرارها، ارزیابیهای تابع را بودجهبندی کنید — معمولاً ۱۰,۰۰۰ تا ۱۰۰,۰۰۰ ارزیابی بسته به اندازه مسئله — و چندین شروع مستقل را برای ارزیابی کیفیت راهحل و پایداری جبهه پارتو اجرا کنید.
آیا MOTS میتواند بیش از دو هدف را مدیریت کند؟
بله، اما اثربخشی با افزایش تعداد اهداف فراتر از سه («نفرین ابعاد» در فضای هدف) کاهش مییابد. برای چهار یا چند هدف، اندازه آرشیو منفجر میشود و حفظ تنوع دشوار میشود؛ رویکردهای مبتنی بر تجزیه یا مبتنی بر شاخص اغلب ترجیح داده میشوند.
روشهای مرتبط
منابع
Hansen, M. P. (1997). Tabu search for multiobjective optimization: MOTS. Presented at the 13th International Conference on Multiple Criteria Decision Making (MCDM), Cape Town, South Africa.
باز کردن مرجع انتشارکپی شد.Glover, F. (1989). Tabu Search — Part I. ORSA Journal on Computing, 1(3), 190–206.
باز کردن مرجع DOIکپی شد.