Multiobjective Heuristic Search: An Introduction to intelligent Search Methods for Multicriteria Optimization

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

Solutions to most real-world optimization problems involve a trade-off between multiple conflicting and non-commensurate objectives. Some of the most challenging ones are area-delay trade-off in VLSI synthesis and design space exploration, time-space trade-off in computation, and multi-strategy games. Conventional search techniques are not equipped to handle the partial order state spaces of multiobjective problems since they inherently assume a single scalar objective function. Multiobjective heuristic search techniques have been developed to specifically address multicriteria combinatorial optimization problems. This text describes the multiobjective search model and develops the theoretical foundations of the subject, including complexity results . The fundamental algorithms for three major problem formulation schemes, namely state-space formulations, problem-reduction formulations, and game-tree formulations are developed with the support of illustrative examples. Applications of multiobjective search techniques to synthesis problems in VLSI, and operations research are considered. This text provides a complete picture on contemporary research on multiobjective search, most of which is the contribution of the authors.