آموزش الگوریتم فراابتکاری جستجوی پراکندگی ( اسکتر سرچ)

جستجوی پراکندگی (اسکتر چرچ) و نمود کلی تر آن که پیوند مجدد مسیر (PR) نامیده می شود، مثال هایی جدید از روش های تکاملی هستند، زیرا آن ها این فرض را که الگوریتم های تکاملی باید بر اساس تصادفی سازی باشند ( فوگل ۱۹۹۸ را ببینید )، نقض می کند اگر چه آن ها می توانند به صورت تصادفی نیز پیاده سازی شوند. SS و PR نیز در مقایسه با دسته معروف الگوریتم های تکاملی ژنتیک (GA)، جدید هستند و بر اساس استراتژی هایی بنا شده اند که بصورت تدریجی به عنوان استدلال هایی از GA بیش از یک دهه بعد از اولین پیدایش خود در الگوریتم جستجوی پراکندگی مطرح شده اند.

همانند دیگر روش های تکاملی، الگوریتم جستجوی پراکندگی ، به جای کار با یک جواب، با جمعیتی از جواب ها کار می کنند و از رویه هایی برای ترکیب جواب ها به منظور ساخت جمعیت جدید استفاده می کنند. ( معنای ” ترکیب ” و علت وجود آن یک ویژه گی خاص و بنیادی در پیاده سازی های SS/PR است. ) یکی از ویژه گی های مهم این رویکرد ارتباط تنگاتنگ آن با الگوریتم فراابتکاری جستجوی ممنوعه (TS ) و همچنین استفاده از اصولی برای برخورداری از حافظه تطبیقی به همراه اصولی برای استفاده موثر از حافظه است. در واقع الگوریتم جستجوی پراکندگی و جستجوی ممنوعه ریشه مشترکی دارند و SS ابتدایی به عنوان یکی از جزء فرایند های موجود در چهارچوب TS بررسی می شد. اگر چه خیلی از ادبیات TS و پیاده سازی های TS به این جزء توجهی نکرده اند. این امر باعث شده تا مزیت جستجوی پراکنده، تا این اواخر که مطالعات اندکی آن را بصورت یک الگوریتم تکاملی مستقل در نظر گرفتند، ناشناخته باقی بماند. ( کلمه “مستقل” بطور نسبی است زیرا تقریبا تمامی پیاده سازی های SS از برخی از طراحی های حافظه تطبیقی TS استفاده کرده اند. برای اینکه روش TS بهتر شناخته شود، ما در این مقاله بر روی اجزایی از SS و PR تمرکز می کنیم که از فرایند های مرتبط با TS مجزا هستند. )

برای فهم بهتر جستجوی پراکنده و پیوند مجدد مسیر و ارتباط ان ها با جستجوی ممنوعه ما تاریخچه ای از توسعه ان ها بیان می کنیم. قسمت های زیر شامل بحث هایی از پیشرفت های اخیر، بر اساس گلور (۱۹۹۷،۱۹۹۹) و گلور، لاگونا و مارتی (۲۰۰۰) هستند.

فرایند الگوریتم جستجوی پراکندگی، بر اساس اصولی بنا شده است که اساس طراحی محدودیت جایگزین را تشکیل می دهد و سازماندهی شده است تا

(۱) اطلاعاتی را که بطور جداگانه در بردار اصلی موجود نمی باشند را ثبت کند،

(۲) از روش های ابتکاری کمکی در انتخاب اجزایی که باید ترکیب شوند و برای تولید بردار های جدید استفاده کند.

جستجوی تصادفی بر روی مجموعه ای از جواب ها کار می کند که به آن مجموعه مرجع گویند و این جواب ها را با یکدیگر ترکیب می کند تا جواب های جدید ساخته شوند. هنگامی که مکانیزم اصلی برای ترکیب جواب ها طوری هست که جواب جدید از ترکیب خطی دو جواب دیگر ساخته شود.

برخلاف “جمعیت” در الگوریتم ژنتیک، اندازه مجموعه مرجع در الگوریتم جستجوی پراکندگی تقریبا کوچک است. در الگوریتم های ژنتیک، دو جواب به طور تصادفی از جمعیت انتخاب می شوند و یک مکانیزم تقاطع یا ترکیب برای تولید فرزند بکار گرفته می شود. یک اندازه معمولی جمعیت در الگوریتم ژنتیک شامل ۱۰۰ جزء می شود که بطور تصادفی برای ایجاد ترکیبات از آن ها نمونه گرفته می شود. در مقابل، الگوریتم جستجوی پراکندگی دو یا بیش از دو جزء از مجموعه مرجع را با هدف ساخت جواب های جدید، طی یک فرایند سیستماتیک انتخاب می کند. به این دلیل که تعداد زیر مجموعه های مجموعه مرجع ( مثلا دو عضوی تا پنج عضوی ) خیلی زیاد می شود، حتی یک فرایند تولید ترکیبات جواب که قربالگری زیادی در انتخاب مثال های مطلوب این زیر مجموعه ها دارد، می تواند تعداد زیادی از ترکیبات را تولید نماید، پس بسیار ضروری است تا تعداد اعضای مجموعه مرجع کم باشد. معمولا در الگوریتم جستجوی پراکندگی مجموعه مرجع شامل ۲۰ جواب یا کمتر است. در یک طراحی استاندارد، اگر مجموعه مرجع شامل b جواب باشد، این رویه تقریبا تعداد (۳b-7)b/2 ترکیب از چهار نوع مختلف را بررسی می کند. نوع پایه ای شامل ترکیب دو جواب است؛ نوع بعدی سه جواب را ترکیب می کند و … . توجه داشته باشید که الگوریتم ژنتیک برای داشتن درجه ی تنوع بالا به یک جمعیت بزرگ احتیاج دارد ( که بوسیله ی نمونه گیری تصادفی که در مکانیزم جستجوی ان وجود دارد تولید می شود )، در حالی که الگوریتم جستجوی پراکندگی تنوع را با فرایندی سیستماتیک در مجموعه مرجع وارد می کند.

محدود گردن حوزه جستجو به یک گروه خاص از ترکیبات می تواند به عنوان مکانیزمی برای کنترل تعداد ترکیبات ممکن در مجموعه مرجع به کار رود. یک راه موثر برای انجام این کار تقسیم کردن مجموعه مرجع به تعدادی سطوح است و اینکه الزام کنیم جواب های ترکیبی باید حداقل یک ( یا تعداد مشخصی ) از اجزای هر سطح را داشته باشند.

شمای کلی این الگوریتم در شکل زیر نشان داده شده است

الگوریتم جستجوی پراکندگی

شاختار کلی الگوریتم جستجوی پراکندگی