Scatter Search: Methodology and Implementations in C

کتاب جستجوی پراکنده اثر مانوئل لاگونا و رافائل مارت! نشان دهنده یک "حلقه گمشده" مورد انتظار در ادبیات روش های تکاملی است. جستجوی پراکنده (SS) - همراه با شکل تعمیم یافته آن به نام Path Relinking - تنها رویکرد تکاملی را تشکیل می دهد که مجموعه ای از اصول جستجوی Tabu (TS) را در بر می گیرد، رویکردی که عموماً از رویه های تکاملی جدا شده است. دیدگاه TS، که مسئول معرفی استراتژی‌های حافظه تطبیقی ​​در ادبیات فراابتکاری (در سطح هدفمند فراتر از مکانیسم‌های وراثت ساده) است، ممکن است در ابتدا با رویکردهای مبتنی بر جمعیت در تضاد به نظر برسد. با این حال، این دیدگاه، SS را با یک پایه قابل توجه موثر برای حل طیف گسترده ای از مسائل عملی مجهز می کند. موفقیت‌هایی که توسط جستجوی پراکنده ثبت شده است، نه چندان ناشی از پذیرش حافظه تطبیقی ​​در طیف راه‌های پیشنهادی در جستجوی تابو (به جز مواردی که اغلب اتفاق می‌افتد، SS به طور سودمند با TS همراه است)، بلکه از استفاده از ایده‌های استراتژیک که در ابتدا پیشنهاد شده بود، به دست می‌آید. برای بهره برداری از حافظه تطبیقی، که به طور هماهنگ با ساختار جستجوی پراکندگی ترکیب می شود. از منظر تاریخی، استفاده اختصاصی از استراتژی‌های اکتشافی هم برای هدایت فرآیند ترکیب راه‌حل‌ها و هم برای ارتقای کیفیت فرزندان به عنوان یک نوآوری کلیدی در روش‌های تکاملی اعلام شده است که گاهی اوقات «هیبرید» نامیده می‌شود. یا \"memetic\") رویه های تکاملی. فرآیندهای زیربنایی در جریان اصلی روش‌های تکاملی (مانند الگوریتم‌های ژنتیک، برای مثال) با یک سری مراحل تدریجی که از اواخر دهه 1980 شروع شد، معرفی شدند.

The book Scatter Search by Manuel Laguna and Rafael Mart! represents a long-awaited "missing link" in the literature of evolutionary methods. Scatter Search (SS)-together with its generalized form called Path Relinking-constitutes the only evolutionary approach that embraces a collection of principles from Tabu Search (TS), an approach popularly regarded to be divorced from evolutionary procedures. The TS perspective, which is responsible for introducing adaptive memory strategies into the metaheuristic literature (at purposeful level beyond simple inheritance mechanisms), may at first seem to be at odds with population-based approaches. Yet this perspective equips SS with a remarkably effective foundation for solving a wide range of practical problems. The successes documented by Scatter Search come not so much from the adoption of adaptive memory in the range of ways proposed in Tabu Search (except where, as often happens, SS is advantageously coupled with TS), but from the use of strategic ideas initially proposed for exploiting adaptive memory, which blend harmoniously with the structure of Scatter Search. From a historical perspective, the dedicated use of heuristic strategies both to guide the process of combining solutions and to enhance the quality of offspring has been heralded as a key innovation in evolutionary methods, giving rise to what are sometimes called "hybrid" (or "memetic") evolutionary procedures. The underlying processes have been introduced into the mainstream of evolutionary methods (such as genetic algorithms, for example) by a series of gradual steps beginning in the late 1980s.