بخشی از مقاله
اصول جستجوی پراکنده
رافائل مارتی، مانوئل لاگوندا، فرد گلوور
چکیده
جستجوی پراکنده یک روش تکاملی است که بصورت موفقیت آمیز برای مسائل سخت در مورد بهینه سازی بکار می رود. اصول و مفاهیم اساسی این روش در دهه 1970 بر اساس فرمول هایی پیشنهاد شد که به تاریخ دهه 1960 برای ترکیب قواعد تصمیم گیری و محدودیت های مسئله باز می گشت. جستجوی پراکنده بر خلاف روشهای تکاملی دیگر (مانند الگوریتم های ژنتیک)، بر اساس این قضیه پی ریزی شده است که روش ها و طرح های سیستماتیک برای ایجاد راه حل های جدید، مزایای مهم تری در مقایسه با مزایای توسل به انتخاب تصادفی دارند. این روش از استراتژی هایی برای تقویت و تنوع بخشی به جستجو استفاده میکند که اثبات شده است که در مسائل بهینه سازی متعددی مؤثر هستند.
این مقاله اصول و ایده های اصلی از جستجوی پراکنده و مرتبط سازی دوباره مسیر تشکیل آن را بیان میکند. ما ابتدا یک طرح مبنا را توصیف میکنیم تا ابزاری برای ایجاد عملکردهای نسبتاً ساده را به خواننده داده باشیم. طرح های پیشرفته تر از این حقیقت برگرفته می شوند که جستجوی پراکنده و مرتبط سازی دوباره مسیر نیز بصورت اساسی با کاوش متای جستجوی ممنوعه (TS) مرتبط هستند، و مزیت اضافی را توسط استفاده از مکانیزم های استفاده از حافظه و حافظه انطباقی جستجوی ممنوعه به ما میدهند که برای زمینه های خاصی مناسب هستند. این فرآیند ها و فرآیند های پیشرفته دیگر که در
این مقاله توصیف شده اند، ایجاد عملکردهای پیچیده را برای مسائلی تسهیل میکنند که اغلب در محیط عملی پیش می آیند. جستجوی پراکنده و مرتبط سازی دوباره مسیر را بعلت انعطاف پذیری و کارایی اثبات شده خود، میتوان با مسائل بهینه سازی سازگار کرد که شامل دامنه کاربردهای وسیع و مجموعه متنوعی از ساختارهای هستند، همانطور که در مقالات این مجموعه نشان داده شده است.
کلمات کلیدی: کاوش متا، روشهای تکاملی، ترکیب، مرتبط سازی دوباره مسیر
1- مقدمه
جستجوی پراکنده (SS) ابتدا در مطالعه گلاور (1977) بعنوان کاوشی برای برنامه سازی صحیح معرفی شد. در طرح اولیه، راه حل هایی بصورت عمدی (به بصورت تصادفی) ایجاد شدند تا خصوصیات آنرا در بخش های مختلف فضای راه حل مورد توجه قرار دهد. جستجوی پراکنده کاوش های خود را بصورت سیستماتیک نسبت به یک سری نقاط مرجع تنظیم میکند که عموماً از راه حل های خوبی تشکیل شده اند که توسط تلاشهای قبلی برای حل مسئله بدست آمده اند، که معیار موجود برای "خوب" محدود به مقادیر تابع هدف نیست، و ممکن است برای زیرمجموع های راه حل ها (و نه برای یک راه حل منفرد) اعمال گردند، مانند مورد مربوط به راه حل هایی که مطابق با خصوصیات معینی، با هم تفاوت دارند.
ترکیبات خطی وزنی مکانیزم اصلی را برای ایجاد نقاط آزمایشی در فضای شامل نقاط مرجع ایجاد میکنند، و مکانیزم روندسازی تعمیم یافته ای را نیز ایجاد میکند تا اطمینان حاصل کند که نقاط آزمایشی دارای شرایط امکان پذیری عدد صحیح در حالتی هستند که بعضی متغیرها نیازمند این هستند که مقادیر صحیح را دریافت کنند. این مکانیزم ها به سمت هدف ایجاد مراکز وزنی از مناطق فرعی انتخاب شده (از جمله مناطق خارجی نسبت به غلاف کوژ نقاط مرجع) متمایل می گردند.
الگوی جستجوی پراکنده (گلاور 1998) بعنوان مرجع اصلی برای اغلب عملکردهای جستجوی پراکنده تاکنون عمل کرده است. الگوی های پراکندگی ایجاد شده توسط این طرح ها در چندین زمینه کاربردی سودمند بوده اند. بخش 2 توصیف جامعی از عناصر و روشهای این الگوی استفاده شده بر مبنای فرمول داده شده در مطالعه لاگوندا و مارتی (2003) ارائه میدهد. با پیروی از این مسئله، بخش 3 طرح های جستجوی پراکنده پیشرفته متفاوتی (از جمله بعضی از ویژگی های اخیر، مانند بروزرسانی سری منابع 3 ردیفی و کاربردهای مرتبط به حافظه) را بررسی میکند. بخش 4 به روش شناسی مرتبط سازی دوباره مسیر اختصاص داده شده است که جستجوی پراکنده را تا محیط فضاهای مجاور (از جمله کاربردهای مبنا و کاربردهای پیشرفته) گسترش میدهد، و در آخر مقاله نیز نتیجه گیری بیان شده است.
2- طرح جستجوی پراکنده مبنا
روش جستجوی پراکنده خیلی انعطاف پذیر است، چون هر کدام از عناصر آن را میتوان به شیوه های مختلف و درجات پیچیدگی مختلفی بکار برد. در این بخش ما طرح مبنایی برای انجام جستجوی پراکنده بر اساس پنج روش معروف ارائه میدهیم، و طرح های پیشرفته را در بخش بعدی توضیح میدهیم. ویژگی های پیشرفته جستجوی پراکنده مربوط به شیوه ای هستند که این پنج روش انجام می شوند. بعبارت دیگر، پیچیدگی از اجرای روش های SS می آید تا اینکه از روشهای تصمیم گیری برای شامل سازی یا حذف بعضی از عناصر بیایند (مانند جستجوی ممنوعه که در بالا بیان کردیم).
این حقیقت که مکانیزم های داخل جستجوی پراکنده محدود به یک طرح منفرد و واحد نیستند، امکان کاوش احتمالات استراتژیکی را به ما میدهد که ممکن است در یک کاربرد خاص سودمند باشند. این اصول و مشاهدات منجر به الگوی زیر برای اجرای جستجوی پراکنده می گردند که از 5 روش تشکیل شده است.
1- روش ایجاد تنوع، برای ایجاد مجموعه ای از راه حل های آزمایشی با استفاده از یک راه حل ازمایشی قراردادی (یا راه حل منشأ) بعنوان یک ورودی.
2- روش بهبود، برای تغییر یک راه حل آزمایشی به یک یا چند راه حل آزمایشی پیشرفته (نه راه حل های ورودی و نه راه حل های خروجی نیازمند این نیستند که امکان پذیر و عملی باشند، با اینکه بیشتر توقع می رود که راه حل های خروجی اینگونه باشند. اکر هیچ بهبودی از راه حل آزمایشی ورودی ایجاد نگردد، فرض می شود که راه حل تقویت شده با راه حل ورودی یکسان باشد).
3- بروزرسانی سری منابع، برای ایجاد و حفظ یک سری منابع تشکیل شده از b تعداد از بهترین راه حل های یافته شده (که مقدار b معمولاً کم است و برای مثال از 20 بیشتر نمی شود)، که سازماندهی شده است تا دسترسی مؤثر توسط قسمت های دیگر این روش را فراهم سازد. راه حل ها مطابق با کیفیت یا تنوع خود در سری منابع طبقه بندی می شوند.
4- روش ایجاد زیرمجموعه، برای عملکرد در سری منابع، تا زیرمجموعه ای از راه حل های خود بعنوان مبنایی برای ایجاد راه حل های ترکیبی ایجاد کند.
5- روش ترکیب راه حل، تا یک زیرمجموعه معین از زیرمجموعه های ایجاد شده توسط روش ایجاد زیرمجموعه را به یک یا چند بردار راه حل حل ترکیبی تبدیل کند.
شکل 1 روابط متقابل بین این پنج روش را نشان میدهد و نقش مرکزی سری منابع را بیان میکند. این طرح مبنا با ایجاد یک سری اولیه از راه حل های P آغاز می گردد، و سپس سری منابع راه حل ها (RefSet) را از آن استخراج میکند.
روش ایجاد تنوع برای ایجاد یک سری بزرگ P از راه حل های متنوع مورد استفاده قرار می گیرد. اندازه P(PSize) معمولاً حداقل 10 برابر اندازه RefSet (سری منابع) است. سری منابع اولیه مطابق روش بروزرسای سری منایع ساخته می شود. برای مثال، روش بروزرسانی سری منابع میتواند متشکل از انتخاب b بصورتمجزا و راه حل هایی با حداکثر پراکندگی از P باشد. یک مکانیزم ساده برای ساختن RefSet در پاراگراف بعدی بیان شده است و در بخش بعدی هم چندین راهکار دیگر برای اجرای روش بروزرسانی سری منایع را بررسی میکنیم. صرفنظر از قوانین استفاده شده برای انتخاب راه حل های مرجع،
راه حل های RefSet مطابق با کیفیت مرتب می شوند، که بهترین راه حل، گزینه اول در لیست می باشد. سپس جستجو توسط تعیین مقدار TRUE برای متغیر بولی NewSolutions آغاز می گردد. در مرحله 3، Newsubsetsایجاد می گردد و NewSolutions به FALSE تغییر داده می شود. ساده ترین شکل روش ایجاد زیرمجموعه از ایجاد همه جفت های راه حل ها
ی مرجع تشکیل می گردد. بعبارت دیگر، این روش بر روی زیرمجموعه هایی با اندازه 2 متمرکز می گردد که منجر به ایجاد می گردد. جفت ها در NewSubsets هر کدام بصورت جداگانه و با ترتیب لغت نویسی انتخاب می گردند و روش ترکیب راه حل اعمال می گردد تا یک یا چند راه حل آزمایشی را در مرحله 5 ایجاد کند. این راه حل های آزمایشی تابع روش بهبود هستند (البته اگر روش بهبود وجود داشته باشد). روش بروزرسانی سری منابع بار دیگر در مرحله 6 اعمال می گردد. ساده ت
رین شکل کاربرد روش بروزرسانی مرجع در این مرحله اینست که RefSet جدید را با بهترین راه حل ها مطابق مقدار تابع هدف، از RefSet جاری و تعیین راه حل های آزمایشی ایجاد کنیم. اگر RefSet پس از کاربرد روش بروزرسانی سری منابع تغییر کند، پرچم NewSolutions در مرحله 7 به TRUE تغییر پیدا میکند، که بیانگر اینست که حداقل یک راه حل جدید در سری منابع وارد شده است. زیرمجموعه s که تابع روش ترکیب بود، در مرحله 8 از NewSubset حذف می گردد.
راهکار مبنا به پایان می رسد پس از اینکه همه زیرمجموعه ها در NewSubsetsتابع روش ترکیب باشند و هیچکدا
م از راه حل های آزمایشی بهبود داده شده مطابق قوانین روش بروزرسانی سری منابع برای RefSet پذیرفته نشده باشند.
شکل 1 : راهکار جستجوی پراکنده مبنا
سری منابع RefSet مجموعه ای از راه حل های کیفیت-بالا و راه حل های متنوع است که برای ایجاد راه حل های جدید توسط اعمال روش ترکیب، بکار می روند. ما در این طرح مبنا می توانیم از یک مکانیزم ساده برای ساخت یک سری منابع اولیه استفاده کنیم و سپس آنرا در حین جستجو بروزرسانی کنیم. اندازه سری منابع توسط نشان داده می شود. ساخت سری منابع اولیه با انتخاب بهترین راه حل از P آغاز می گردد. این راه حل ها به RefSet اضافه می گردند و از P حذف می شوند. برای هر راه حل در P-RefSet ، حداقل فواصل نسبت به راه حل ها در RefSet محاسبه می گردد. سپس راه حل با حداکثر این فواصل حداقل انتخاب می گردد. این راه حل به RefSet اضافه می گردد و از P حذف می شود و فواصل حداقل بروزرسانی می گردند (در اعمال این معیار حداکثر-حداقل، یا هرگونه معیار بر مبنای فواصل، این مسئله می تواند مهم باشد که متغیرهای مسئله را مقیاس بندی کنیم، تا از شرایطی اجتناب کنیم که یک متغیر خاص یا زیرمجموعه ای از متغیرها بر اندازه گیری فاصله حاکم باشد و همکاری مناسب مؤلفه های برداری را تغییر دهد). این فرآیند به اندازه دفعه تکرار می گردد، که می باشد. سری منابع برآیند دارای راه حل کیفیت-بالا و راه حل متنوع است.
پس از اینکه سری منابع اولیه ساخته شد، روش ترکیب برای زیرمجموعه های ایجاد شده اعمال می گردد، همانطور که در مرحله 5 از شکل 1 نشان داده شده است. در طراحی مبنا، ما از بروزرسانی استاتیک سری منابع پس از کاربرد مدل ترکیب استفاده میکنیم. راه حل های آزمایشی که بصورت ترکیبی از راه حل های مرجع ساخته می شوند، در منبع راه حل قرار داده می شوند، که توسط Pool نشان داده می شود. پس از کاربرد هر دو روش ترکیب و بهبود، Pool کامل می گردد و سری منابع بروزرسانی می گردد. سری منابع جدید متشکل از بهترین راه حل های b از راه حل های موجود در سری منابع جاری و راه حل های موجود در Pool می باشد، بعبارت دیگر سری منابع بروزرسانی شامل بهترین راه حل های b در می باشد.
از پنج روش در روش شناسی جستجوی پراکنده، فقط چهار روش بطور شدید مورد نیاز هستند. روش بهبود معمولاً زمانی مورد نیاز خواهد بود که نتایج کیفیت بالا مورد نیاز باشند، اما میتوان یک راهکار جستجوی پراکنده را بدون آن نیز انجام داد. از طرف دیگر، یک راهکار جستجوی ممنوعه کوتاه مدت را میتوان بعنوان روش بهبود بکار برد، همانطور که در بخش بعدی نیز نشان داده شده است.
3- طرح های جستجوی پراکنده پیشرفته
در هنگام بررسی استراتژی های پیشرفته در یک چارچوب کاوش متا، هدف بهبود کارایی اغلب با هدف طراحی راهکاری مغایرت دارد که اجرا و تنظیم آن آسان است. طرح های پیشرفته معمولاً (البته نه همیشه) به پارامترهای جستجوی اضافی و پیچیدگی بالاتر تبدیل می گردند. تا جاییکه ما میدانیم، هیچ دستورالعمل ساده ای وجود ندارد که توسط آن بتوانیم یک ترتیب از پیش تعیین شده را دنبال کنیم که در این ترتیب استراتژی های پیشرفته باید به بهبود کارایی اعمال جستجوی پراکنده اضافه گردند. بنابراین ترتیبی که در آن، این استراتژی ها در این بخش توصیف می گردند، اهمیت یا رتبه بندی آنها را نشان نمی دهند. یک توصیف جامع از طرح های پیشرفته را میتوان در مطالعه لاگونا و مارتی (2003) یافت.
3.1 بروزرسانی RefSetپویا
سری منابع سری منابع قلب راهکار جستجوی پراکنده است. اگر در هر زمانی در حین جستجو، همه راه حل های منابع شبیه به هم باشند – که توسط معیار مناسب اندازه گیری شده است – راهکار جستجوی پراکنده به احتمال زیاد قادر نخواهد بود که بر اساس بهترین راه حل یافت شده پیشرفت کند، حتی زمانیکه از یک راهکار پیچیده برای انجام ترکیبات یا بهبود راه حل های آزمایشی جدید استفاده کند. روش ترکیب توسط راه حل های مرجع محدود می گردد که از آنها بعنوان ورودی استفاده میکند. بنابراین داشتن پیشرفته ترین روش ترکیب مزیت کمی خواهد داشت اگر سری منابع با دقت ساخته نشوند و در حین جستجو باقی بمانند.
در طرح مبنا، راه حل های جدید که عضوی از RefSet می گردند ترکیب نمی گردند تا زمانیکه همه جفت ها در NewSubsetsتابع روش ترکیب باشند. سری منابع جدید با بهترین راه حل ها در اتحاد Pool و راه حل های جاری در RefSet ساخته می شود. این استراتژیبروزرسانی ساکن سری منابع نام دارد. راهکار دیگر، استراتژی بروزرسانی پویا نام دارد، که روش ترکیب را برای راه حل های جدید به شیوه ای اعمال میکند که راه حل های جدید را سریع تر از طرح مبنا ترکیب میکند. بعبارت دیگر، اگر راه حل جدیدی برای سری منابع پذیرفته شود، هدف این خواهد بود که به این راه حل جدید اجازه دهیم که در کمترین زمان تابع روش ترکیب باشد. بعبارت دیگر، بجای اینکه منتظر بمانیم تا همه ترکیب ها انجام شوند تا سری منابع بروزرسانی شود، اگر یک راه حل آزمایشی جدید پذیرش را در سری منابع تضمین کند، سری منابع سریعاً بروزرسانی میشود قبل از اینکه ترکیب بعدی اجرا شود. بنابراین نیازی به یک Pool میانی در این طرح نیست، چون راه حل ها یا منسوخ می گردند و یا به محض اینکه ایجاد شدند قسمتی از RefSet می گردند.
مزیت بروزرسانی پویا اینست که اگر سری منابع شامل راه حل هایی با کیفیت پایین تر باشد، این راه حل ها سریعاً جایگزین میگردند و ترکیبات بعدی با راه حل های بهبود داده شده انجام می شوند. اشکال آن هم اینست که بعضی از ترکیبات امیداوارکننده حذف می شوند قبل از اینکه بررسی گردند. اجرای بروزرسانی پویا خیلی پیچیده تر از بروزرسانی ساکن است. همچنین، در بروزرسانی ساکن ترتیبی که ترکیبات اجرا میشوند مهم نیست چون تا همه ترکیبات اجرا نشوند RefSet بروزرسانی نمی گردد. در بروزرسانی پویا، ترتیب اجرای ترکیبات نسبتاً مهم است چون حذف شدن بعضی از ترکیبات را تعیین میکند. بنابراین در حین اجرای بروزرسانی پویای سری منابع، ممکن است ضروری باشد که با ترتیب های مختلف ترکیبات بعنوان قسمتی از تنظیم راهکار آزمایش کنیم.
3.2 ساخت RefSet
ما اکنون راهکار بروزرسانی جدیدی را معرفی میکنیم که زمانی تحریک می گردد که هیچ راه حل آزمایشی جدیدی برای سری منابع پذیرفته می شود. این بروزرسانی مکانیزمی را اضافه میکند که تا حدودی سری منابع را بازسازی میکند، وقتی که روشهای ترکیب و بهبود، راه حل هایی با کیفیت مناسب برای جایگزینی راه حل های منابع جاری را فراهم نمی سازد.
RefSet تا حدودی با بروزرسانی تنوع بازسازی می شود که بصورت زیر عمل میکند و فرض میکند که اندازه سری منابع است. راه حل های از RefSet حذف می گردد. روش ایجاد تنوع با در نظر گرفتن این دوباره آغاز می گردد که هدف آن اینست که راه حل هایی را ایجاد کند که با توجه به راه حل های منابع متنوع می گردد. سپس روش ایجاد تنوع برای ساخت سری P از راه حل های جدید بکار می رود. راه حل در RefSet بترتیب از P با معیار به حداکثر رساندن تنوع انتخاب می گردد، که معمولاً با
سنجش فاصله تعریف شده در محتوای مسئله حل شده اجرا می شود. سپس، به حداکثر رساندن تنوع توسط به حداکثر رساندن فاصله حداقل انجام میشود. معیار حداکثر-حداقل – که قسمتی از روش بروزرسانی سری منابع است – با توجه به راه حل های در هنگام انتخاب راه حل اعمال می گردد، و سپس با توجه به راه حل های در هنگام انتخاب راه حل اعمال می گردد، و به همین ترتیب ادامه می یابد.
3.3 ردیف های سری منابع
در سطح پایین تر انجام جستجوهای پراکنده، سری منابع توسط جایگزینی راه حل منابع دارای بدترین مقدار تابع هدف با راه حل آزمایشی جدیدی بروزرسانی می گردد که مقدار تابع هدف بهتری دارد. چون ما همیشه فرض میکنیم گه RefSet ترتیب بندی شده است، بهترین راه حل و بدترین راه حل می باشد. بنابراین وقتی که راه حل آزمایشی جدیدی در نتبجه اجرای روشهای ترکیب و بهبود ایجاد می گردد، مقدار تابع هدف راه حل آزمایشی جدید برای تعیین این مسئله بکار می رود که آیا RefSet نیاز به بروزرسانی دارد یا نه. این مرحله با تعیین این مئسله انجام میشود که با حذف و واردسازی x در موقعیتی که ترتیب مشخص سری منابع را حفظ میکند، چه زمانی x از بهتر است. ما اکنون مکانیزم هایی را بررسی میکنیم که راه حل ها را با استفاده از سنجش های اضافی شایستگی متمایز می سازد که بر مبنای مقدار تابع هدف نیست.
بجای منتظر ماندن تا زمانیکه سری منابع با هم همگرا می گردند (یعنی تا زمانیکه به وضعیتی برسد که هیچ راه حل جدیدی پذیرفته نشود)، یک راهکار بروزرسانی که بصورت پویا تنوع را در جستجو وارد می سازد مورد استفاده قرار گیرد. راهکار بروزرسانی از یک طرح 2 ردیفی استفاده میکند، که ردیف اول از راه حل کیفیت-بالا و از راه حل متنوع تشکیل شده است. بروزرسانی دارای هدف حفظ تنوع تا حد زیادی در سری منابع است، بجای اینکه به آن اجازه دهد تا فقط توسط پذیرفتن راه حل های کیفیت-بالا همگن گردد که در بعضی از کاربردها خیلی با هم مشابه هستند. بنابراین علاوه بر بروزرسانی سری منابع در زمانیکه راه حل های آزمایشی جدید کیفیت-بالا با روشهای ترکیب و بهبود یافته می شوند، سری منابع نیز با راه حل های خیلی متنوع بروزرسانی می گردد.
بروزرسانی خصوصاً از تقسیم بندی منابع به دو زیرمجموعه تشکیل شده است:
زیرمجموعه اول زیرمجموعه کیفیت-بالا و زیرمجموعه دوم زیرمجموعه متنوع نامیده می شود. راه حل ها در مطابق با مقدار تابع خود ترتیب بندی می شوند و سری منابع با هدف افزایش کیفیت با استفاده از معیار طرح جستجوی پراکنده مبنا، بروزرسانی می گردد. بعبارت دیگر، راه حل جدید x در مسئله به حداقل رسانی، جایگزین راه حل منابع می گردد. راه حل ها در مطابق با مقدار تنوع خود ترتیب بندی می شوند و بروزرسانی دارای هدف افزایش تنوع است. بنابراین راه حل جدید x جایگزین راه حل منابع می گردد.
بروزرسانی 2 ردیفی را میتوان در ترکیب با مکانیزم بازسازی مورد استفاده قرار داد. اجرای آن توسط نگه داشتن و آغاز دوباره روش ایجاد تنوع برای بازسایی با راه حل هایی که در بین آنها متنوع است و با توجه به آسان می گردد.
لاگونا و مارتی (2000) توسعه ای از این طرح را پیشنهاد می کنند که لیستی از بهترین ایجاد کننده ها را حفظ میکند. یک ایجاد کننده خوب، یک راه حل منابع است که راه حل های آزمایشی کیفیت-بالا را ایجاد میکند، زمانیکه بعنوان ورودی برای روش ترکیب مورد استفاده قرار می گیرد. بروزرسانی 3 ردیفی از سری منابع اندازه استفاده میکند، که به سه زیرمجموعه زیر تقسیم بندی می شود:
و با استفاده از قوانین یکسانی مانند قوانین بروزرسانی 2 ردیفی، بروزرسانی می گردند. برای بروزرسانی ما مسیر را دنبال میکنیم، که مقدار تابع هدف بهترین راه حلی است که تابحال از ترکیب و هرگونه راه حل دیگر ایجاد شده است. مطابق با به شیوه ایمانند شیوه برای مسئله به حداکثر رسانی، ترتیب بندی می گردد. وقتی که در با راه حل کیفیت بالاتری جایگزین میگردد که بتازگی ایجاد شده است، ما را با مقایسه میکنیم و اگر مناسب باشد آنرا بروزرسانی میکنیم.
این طرح خصوصاً در محیطی سودمند خواهد بود که راه حل های دارای کیفیت نسبتاً پایین قابلیت ایجاد راه حل های کیفیت-بالا، توسط اجازه دادن به این ایجاد کننده های خوب برای مشارکت در ترکیبات دیگر را داشته باشند زمانیکه آنها از جایگزین می گردند. آغاز دوباره و مانند طرخ 2 ردیفی است. با بهترین راه حل ها در P آغاز می گردد که در شامل نبودند.
3.4 کنترل تنوع
جستجوی پراکنده اجازه تکرار را در سری منابع نمی دهد، و روشهای ترکیب آن برای بدست آوردن مزیت از عدم وجود تکرار، طراحی می گردند. درهم سازی اغلب برای کاهش تلاش محاسباتی بررسی راه حل های تکرارشده استفاده می گردد. برای نمونه تابع درهم سازی زیر یک راه مؤثر برای مقایسه راه حل ها و اجتناب از وقوع تکرار است، زمانیکه با مسائلی سر و کار داریم که راه حل های انهارا میتوانیم با تبدیل p و اندازه m نشان دهیم:
کامپوس و همکارانش (2001) مزایای این نوع تکرار را در محتوای یک مسئله ترتیب بندی خطی گزارش میکنند.
در حالیکه کاربردهای جستجوی پراکنده ساده تر برای بررسی این مسئله طراحی می گردند که سری منابع شامل موارد تکراری نیست، آنها عموماً تنوع راه حل های کیفیت-بالا را نشان نمی دهند، زمانیکه RefSet اولیه را ایجاد میکنند. از طرف دیگر، بیاد داشته باشید که این مسئله که راه حل های متنوع تابع یک بررسی تنوع دقیق با معیار حداکثر-حداقل است. تست حداقل تنوع را میتوان برای راه حل های کیفیت-بالای اعمال کرد که بعنوان عضوهایی از RefSet بشرح زیر انتخاب می گردند. پس از اینکه سری P ایجاد شد، بهترین راه حل مطابق با مقدار تابع هدف طوری انتخاب می گردد که در سری منابع به اندازه باشد. سپس، از P حذف می گردد و بهترین راه حل بعدی x در P انتخاب می گردد و به RefSet اضافه می گردد، البیته فقط در صورتی که:
بعبارت دیگر، در هر مرحله ما بهترین راه حل را در P اضافه می سازیم فقط در صورتیکه حداقل فاصله بین راه حل انتخاب شده x و راه حل های موجود در RefSet حداقل به بزرگی مقدار سرحد باشد.
3.5 روش ایجاد زیرمجموعه
روشهای ترکیب راه حل در جستجوی پراکنده معمولاً فقط به ترکیب دو راه حل نیستند، و بنابراین روش ایجاد زیرمجموعه در کلی ترین شکل خود از ایجاد زیرمجموعه هایی با اندازه های مختلف تشکیل می گردد. در روش جستجوی پراکنده فرض می شود که سری راه حل های ترکیب شده ممکن است در تمامیت خود در نقطه ای ایجاد گردند که زیرمجموعه های راه حل های منابع ایجاد می گردند. بنابراین وقتی که یک زیرمجموعه مشخص ایجاد می گردد، هیچ صلاحیتی در ایجاد دوباره آن نیست. اینکار موقعیتی را ایجاد میکند که تا حد زیادی با موقعیت فرض شده در محتوای الگوریتم های ژنتیک متفاوت است، که ترکیبات معمولاً توسط چرخش یک میز رولت تعیین می گردند.
راهکار برای ایجاد زیرمجموعه های راه حل های منابع از یک استراتژی برای توسعه جفت ها در زیرمجموعه هایی با اندازه بزرگرت استفاده میکند درحالیکه تعداد کلی زیرمجموعه هایی که باید ایجاد گردند را کنترل میکند. بعبارت دیگر، این مکانیزم از نوع نهایی فرآیندی اجتناب میکند که همه زیرمجموعه های با اندازه 2 و سپس همه زیرمجموعه های با اندازه 3 را ایجاد میکند، و به همبن ترتیب ادامه می یابد تا اینکه به زیرمجموعه هایی با اندازه b-1 و در نهایت نیز به RefSet کلی برسد. این راهکار مسلماً برای استفاده عملی مناسب نیست، با فرض اینکه 1013 زیرمجموعه در یک سری منابع با اندازه معمول وجود داشته باشد. حتی برای یک سری منبع کوچک تر، ترکیب همه زیرمجموعه های احتمالی مؤثر نخواهد بود چون زیرمجموعه های زیادی تقریباً با هم یکسان خواهند بود. راهکار زیر زیرمجموعه های معرف با اندازه های مختلف را توسط ایجاد انواع زیرمجموعه انتخاب می کند:
- زیرمجموعه نوع 1: همه زیرمجموعه های 2 عنصری.
- زیرمجموعه نوع 2: زیرمجموعه های 3 عنصری گرفته شده از زیرمجموعه های 2 عنصری توسط تقویت هر زیرمجموعه 2 عنصری برای عدم شامل سازی بهترین راه حل در این زیرمجموعه.
- زیرمجموعه نوع 3: زیرمجموعه های 4 عنصری گرفته شده از زیرمجموعه های 3 عنصری توسط تقویت هر زیرمجموعه 3 عنصری برای عدم شامل سازی در این زیرمجموعه.
- زیرمجموعه نوع 4: زیرمجموعه های متشکل از بهترین عناصر i، برای .
3.6 استفاده از حافظه
جستجوی پراکنده یک شکل ضمنی از حافظه را بعنوان نتیجه روابط متقابل بین بروزرسانی سری منابع، روش ایجاد راه حل ، و روش ایجاد زیرمجموعه، ترکیب می کند. بروزرساتی سری منابع، در مبنایی ترین شکل خود، برای به حافظه سپردن بهترین راه حل های مشاهده شده در حین جستجو طراحی می گردد. ویژگی های انتخابی این راه حل ها اساسی را برای ایجاد راه حل های آزمایشی جدید با روش ترکیب فراهم می سازد. بنابراین فرآیند کلی در انتقال اطلاعات ادغام شده در راه حل های منابع مفید است.
این نوع ضمنی معمولاً ابتدایی است و می توان آنرا بصورت یک حافظه میراثی طبقه بندی کرد. همه روشهای تکاملی یک حافظه میراثی از نوع مشخصی را ترکیب میکنند، و با اینحال حتی در این سطح اولیه، مکانیزم های حافظه از جستجوی پراکنده تا حدودی بهتر از راهکارهای تکاملی دیگر هستند. این بخاطر روش ایجاد زیرمجموعه است، که مسیر زیرمجموعه های راه حل های منابع را دنبال میکند که تابع مکانیزم ترکیب از یک تکرار به تکرار دیگر هستند. وقتی که راه حل های جدید برای سری منابع پذیرفته می شوند، این روش فقط زیرمجموعه هایی را ایجاد میکند که برای ترکیب در تکرار جاری، مجاز
هستند. روش ایجاد زیرمجموعه این کار را توسط یک ساختار حافظه انجام میدهد که زیرمجموعه هایی را شناسایی میکند که شامل راه حل های منابع جدید هستند. برعکس، راهکارهای تکاملی سنتی مانند الگوریتم های ژنتیک استفاده معادلی از حافظه را بکار نمی برند، بلکه راه حل هایی را با استفاده از گونه ای از طرح نمونه برداری تصادفی، برای اهداف ترکیب انتخاب میکنند (بتازگی تعدادی از راهکارهای تکاملی غیر استاندارد پدیدار شده اند که راه حل های مادر را توسط استراتژی های شبیه به جستجوی پراکنده انتخاب میکنند. البته آنها بر مبنای انتخاب تصادفی هستند، و تا حدی پیشرفت نکرده اند که شکل استراتژی های بر مبنای حافظه را ترکیب کنند که در روش ایجاد زیرمجموعه وجود دارد).
در هر حالت، حافظه میراثی – از جمله نوع موجود در جستجوی پراکنده – به اندازه ای متمرکز یا هدفمند نیست که بتواند نیروی تحلیلی مورد نیاز برای حل مسائل پیچیده را به شیوه مؤثری فراهم سازد (اگر حافظه میراثی چنین خصوصیاتی داشت، مغز انسان ها خیلی بیشتر از اندازه مورد نیاز می بود). این یک دلیل اساسی ک هچرا جستجوی پراکنده ار اصول حافظه انطباقی جستجوی ممنوعه استفاده میکند، و اغلب در رابطه با جستجوی ممنوعه اجرا می گردد. این حقیقت که تعدادی از ایده های کلیدی از دو راهکار از یک منبع مشترک ناشی می گردد (گلاور 1977) پیوند بین آنها را خیلی قوی تر می سازد.
جستجوی ممنوعه بعنوان بخشی از طراحی برای وارد سازی حافظه انطباقی استراتژیک در مقالات کاوش متا، از حافظه ای استفاده میکند که هم واضح است و هم انتساب پذیر است. حافظه واضح راه حل های کامل را ضبط میکند، که معمولاً از راه حل های ممتاز تشکیل شده اند که در حین جستجو پیدا می شوند. حافظه انتساب پذیر اطلاعات مربوط به خصوصیات راه حل را ضبط میکند که در انتقال از یک راه حل به راه حل دیگر تغییر میکند (برای توضیح کامل در این مورد میتوانید به مطالعه گلاور و لاگونا (1977) مراجعه کنید).
در کاربردهای جستجوی پراکنده، یکی از کاربردهای اصلی حافظه واضح در زمینه شبیه سازی های بهینه سازی است، که در مطالعه لاگونا و مارتی (2002) بطور کامل توضیح داده شده است. در این محیط، متغیرهای تصمیم x در مدل بهینه سازی، عوامل ورودی مدل شبیه سازی هستند. مدل شبیه سازی یک خروجی را برای هر سری از مقادیر ورودی ایجاد میکند. بر اساس این ارزیابی، و بر اساس ارزیابی های گذشته که با خروجی های شبیه سازی کنونی جامع سازی و تحلیل شده اند،
جستجوی پراکنده سری جدیدی از مقادیر ورودی را ایجاد میکند. چون ارزیابی سری مقادیر ورودی توسط اجرای مدل شبیه سازی ممکن است نیازمند تلاش محاسباتی زیاد باشد که هر راه حل ایجاد شده و ارزیابی شده ر حین ارزیابی، راهکار موثری در این محیط است. وقتی که یک راه حل آزمایشی جدید با روش ترکیب راه حل ایجاد می گردد و قبل از اینکه برای
ارزیابی به مدل شبیه سازی فرستاده شود، با حافظه واضح مشورت می گردد تا اطمینان حاصل شود که راه حل آزمایشی واقعاً جدید است. چون بهینه سازی معمول اجرا شده در این زمینه حداکثر دهها هزار فراخوانی را به مدل شبیه سازی می فرستد، ساختار حافظه واضح به اندازه ای بزرگ نمی گردد که غیرقابل مدیریت باشد. با این وجود، ممکن است از درهم سازی برای محدود سازی شرایط حافظه و تلاش مورد نیاز برای بررسی این مسئله استفاده شود که آیا یک راه حل آزمایشی قبل در ساختار حافظه واضح ذخیره شده است یا نه.
ساختارهای حافظه انتساب پذیر بجای ضبط راه حل های کامل، بر مبنای خصوصیات ثبت شده هستند. حافظه انتساب پذیر برای اجرای استراتژی های تنوع و تقویت در TS مورد استفاده قرار می گیرد. معمول ترین راهکارهای حافظه انتساب پذیر، حافظه نوین-مبنا و حافظه تکرار-مبنا است. حافظه نوین-مبنا معمول ترین ساختار حافظه مورد استفاده در کاربردهای TS است. ساختار این حافظه همانطور که از نام آن نیز مشخص است، خصوصیاتی از راه حل را دنبال میکند که در گذشته جدیدی رخ داده اند. حافظه تکرار-مبنا نوعی از اطلاعات را فراهم می سازد که اطلاعات ارائه شده توسط حافظه نوین-مبنا را تکمیل میکند، و اساس موجود برای انتخاب انتقال های ترجیحی را گسترش میدهد.
لاگونا و مارتی (2003) روش ایجاد کننده تنوعی را برای بهینه سازی تابع غیرخطی در
یک فضای راه حل مداوم پیشنهاد میکنند. این حافظه تکرار-مبنا با مشاهده ساختمان P بعنوان یک فرآیند تکراری که در هر تکرار از تکرارهای PSize یک راه حل را مشاهده میکند، در طبقه سنجش محل اقامت قرار می گیرد. کامپوس و همکارانش (2001) روش ایجاد تنوعی در زمینه مسئله ترتیب بندی خطی بر مبنای ایده ساخت راه حل هایی که از تکرارهای اصلاح شده استفاده میکنند، را معرفی میکنند. این ایجادکننده از ساختار تبدیل مسئله استفاده میکند. سنجش محل اقامت بکار برده شده در این راهکار به گونه ای است که شمارشگر تکرار برای ثبت تعداد دفعاتی که این بخش در یک محل خاص مشاهده میشود تعیین می گردد. شمارشگر های تکرار برای ثبت عالی بودن یک بخش با توجه به یک محل معین مورد استفاده قرار می گیرند.
تقویت جستجو معمولاً در جستجوی پراکنده با اجرای روش بهبود انجام می شود. وقتی که ساختارهای حافظه به روش بهبود اضافه می گردند، این روش از لحاظ مفهومی و عملی از یک کاوش جستجوی محلی به یک کاوش متا تبدیل می شود که از لحاظ تعریفی کاوش متا به معنای استراتژی است که کاوش های دیگر را راهنمایی و اصلاح میکند تا راه حل هایی را ایجاد کند که فراتر از راه حل هایی باشد که معمولاً در جستجو برای بهینه سازی محلی بدست می آیند. استفاده از یک کاوش متا بعنوان یک روش بهبود، منجر به ایجاد روش ترکیبی می گردد که دو کاوش متا (یعنی جستجوی پراکنده و جستجوی مورد استفاده برای بهبود راه حل ها) را با هم ترکیب میکند. یک مسئله مهم در این طرح اینست که چطور تلاش محاسباتی کلی را به بخش ها اختصاص دهیم. بعبارت دیگر، آیا جستجو باید بیشتر وقت خود را به بهبود راه حل ها اختصاص دهد یا بیشتر وقت خود را به ایجاد راه حل های جدید با روش ایجاد تنوع و روش ترکیب اختصاص دهد؟ تعادل در تلاش محاسباتی باید نه تنها توسط انتخاب راه حل های تابع روش بهبود کنترل گردد، بلکه باید توسط انتخاب قانونی برای متوقف سازی فرآیند بهبود سازی نیز کنترل گردد.
4- مرتبط سازی دوباره مسیر
مرتبط سازی دوباره مسیر (PR) ابتدا بعنوان راهکاری برای ترکیب استراتژی های تقویت و تنوع در زمینه جستجوی ممنوعه معرفی شد (گلاور و لاگونا، 1993، 1997). این راهکار راه حل هایی جدیدی را توسط استفاده از مسیرهایی ایجاد میکند که با شروع از یک راه حل به سمت راه حل های دیگر (با نام راه حل های آغازین)، راه حل های کیفیت-بالا را به هم مرتبط می سازد و مسیری را در فضای مجاور ایجاد میکند (با نام راه حل های راهنما) که به راه حل های دیگر می رسد. اینکار توسط انتخاب انتقال هایی انجام می شود که خصوصیات شامل در راه حل های راهنما را معرفی می کند.
مرتبط سازی دوباره مسیر را میتوان بعنوان گسترشی از روش ترکیب در جستجوی پراکنده تصور کرد. PR بجای اینکه مستقیماً راه حل جدیدی را در هنگام ترکیب دو یا چند راه حل اصلی ایجاد کند، مسیرهایی را بین راه حل های انتخابی و آنطرف آنها در فضای مجاور انتخاب میکند. خصوصیات این مسیرها به آسانی توسط مراجعه به خصوصیات راه حل تعیین می گردد که توسط انتقال های انجام شده اضافه، حذف، و یا اصلاح شده اند. مثالهایی از این خصوصیات شامل گوشه ها و گره های یک نمودار، موقعیت های متوالی در یک برنامه، بردارهای موجود در راه حل های مبنای برنامه ریزی خطی، و مقادیر متغیرها و توابع متغیرها است.
این راهکار را میتوان یم نمونه عالی از استراتژی دانست که توسط ایجاد انگیزه برای استفاده از این خصوصیات در انتقال های انتخاب شده، دنبال خصوصیات ترکیبی راه حل های کیفیت-بالا است. البته راهکار مرتبط سازی دوباره مسیر بجای استفاده از انگیزه ای که صرفاً شامل سازی این خصوصیات را ترغیب میکند، از ملاحظات دیگر برای هدف انتخاب انتقال هایی تبعیت میکند که خصوصیات راه حل های راهنما را معرفی میکنند تا ترکیب خصوصیات خوب را در معیارهای انتخاب متعارف، از یک سری محدود ایجاد کنند – سری انتخاب های موجود که در حال حاضر موجود هستند و حداکثر تعداد خصوصیات (یا حداکثر مقدار وزنی) راه حل های راهنما را با هم ترکیب میکنند (استثناهایی نیز توسط معیارهای جداسازی بیان شده است که در بخش بعدی آمده است). این راهکار مرتبط سازی دوباره مسیر نام دارد، که بخاطر ایجاد یک مسیر جدید بین راه حل های ار قبل مرتبط شده توسط یک سری انتقال های اجرا شده در حین یک جستجو، و یا بخاطر ایجاد یک مسیر بین راه حل هایی است که قبلاً با راه حل های دیگر مرتبط سازی شده اند و با یکدیگر مرتبط سازی نشده اند.
برای ایجاد مسیرهای مطلوب، فقط لازم است که انتقال هایی را انتخاب کنیم که این نقش ها را انجام میدهند: در هنگام آغاز از راه حل آغازین، انتقال ها باید پیوسته خصوصیات مربوط به راه حل راهنما را نشان دهند (یا فاصله بین خصوصیات راه حل های آغازین و راهنما را کاهش دهند). نقش راه حل های آغازین و راهنما قابل تبادل است؛ هر راه حلی را میتوان ترغیب کرد تا بعنوان راهی برای ایجاد ترکیب، بصورت همزمان بسوی راه حل دیگر حرکت کند. ابتدا ایجاد مسیرهایی را در نظر بگیرید که دو راه حل انتخاب شده و را بهم مرتبط می سازد و توجه خود را به قسمتی از مسیر معطوف سازید که در بین راه حل ها قرار دارد و توالی راه حل را ایجاد میکند. برای کاهش تعداد گزینه هایی که باید مر نظر قرار داده شوند، راه حل را میتوان از در هر مرحله توسط انتخاب انتقالی ایجاد کرد که تعداد انتقال های باقیمانده برای رسیدن به را به حداکثر می رساند. مسیر مرتبط سازی شده ممکن است با راه حل هایی روبرو شود که ممکن است بهتر از راه حل آغازین یا راهنما باشد، اما اینکار نقاط دسترسی سودمندی را برای رسیدن به راه حل های دیگر (و تا حدودی بهتر) فراهم می سازد. به همین دلیل این مسئله برای بررسی راه حل های مجاوز در امتداد یک مسیر مرتبط سازی شده و دنبال کردن راه حل های کیفیت-بالا ارزشمند است که میتواند نقطه آغازی را برای شروع جستجوهای دیگر فراهم سازد.
سری منابع (RefSet) را میتوان به گونه ای ساخت که قبلاً برای جستجوی پراکنده بیان شد. البته مرتبط سازی دوباره مسیر معمولاً از یک سری معین از راه حل های ممتاز آغاز می گردد که در حین جستجوی پراکنده بدست می آیند. برای ساده سازی لغات فنی، ما از RefSet برای اشاره به این سری از راه حل های b استفاده میکنیم که در حین کاربرد روش جستجوی ترکیبی انتخاب شده اند. این روش می تواند جستجوی ممنوعه (مانند مطالعات لاگونا، مارتی و کامپوس 1999)، GRASP (مانند مطالعه لاگونا و مارتی 1999)، یا روش ایجاد تنوع ترکیب شده با روش بهبود باشد که در جستجوی پراکنده معرفی می گردد. از این دیدگاه، SS و PR را میتوان در روشهای جمعیت-مبنا در نظر گرفت که یک سری راه حل های منابع را انجام میدهند و اساساً از لحاظی با هم متفاوت هستند که سری منابع تولید، نگهداری، بروزرسانی و بهبود داده می شود.
در طرح های جستجوی پراکنده مبنا (ساده)، همه جفت های راه حل ها در RefSet تابع روش ترکیب هستند. همچنین در نسخه مبنای PR نیز همه جفت ها در RefSet تصور می گردد که یک مرحله مرتبط سازی را انجام میدهند. برای هر جفت دو مسیر را میتوان آغاز کرد: یک مسیر از به و یک مسیر هم از به . چندین مطالعه بصورت تجربی پی برده اند که اینکار راحت تر است که یک کاوش جستجوی محلی را از بعضی از راه حل های ایجاد شده در مسیر مرتبط سازی دوباره اضافه کنیم (همانطور که توسط گلاور (1994) نیز پیشنهاد شده است)، تا نتایج بهبود یافته ای را حاصل دهد. لاگونا و مارتی (1999) و
پینانا و همکارانش (2001) مثال هایی از این بحث ارائه داده اند. دو راه حل متوالی بدست آمده توسط یک مرحله مرتبط سازی دوباره اغلب خیلی با هم مشابه هستند، چون فقط از لحاظ خصوصیاتی با هم تفاوت دارند که با یک انتقال منفرد تغییر می کنند. بنابراین معمولاً اینکار مؤثر نیست که یک روش بهبود را در هر مرحله از فرآیند مرتبط سازی دوباره اعمال کنیم. ما پارامتر NumImpرا معرفی میکنیم و روش بهبود را برای هر مرحله NumImp از فرآیند مرتبط سازی دوباره اعمال میکنیم. یک روش دیگر پیشنهاد شده در مطالعه گلاور (1994) اینست که بهترین راه حل های ایجاد شده در حین ردیابی مسیر، و یا بهترین همسایه های راه حل های ایجاد شده را دنبال کنیم، و سپس دوباره به این راه حل های کاندید ترجیحی باز گردیم تا فرآیند بهبود را آغاز کنیم.
شکل 2 راهکار PR ساده ای را برای مسئله به حداقل رسانی نشان میدهد، که با ایجاد یک سری اولیه از راه حل های ممتاز b (RefSet) آغاز می شود. مانند جستجوی پراکنده، راه حل های موجود در RefSet مطابق با کیفیت ترتیب بندی می شوند، و جستجو توسط تعیین مقدار TRUE برای NewSolutions آغاز می شود. در مرحله 3، NewSubsets با همه جفت راه حل های موجود در RefSetساخته می شود، و NewSolutions به FALSE تغییر پیدا میکند. در این مرحله نیز Pool به صفر تغییر می یابد. جفت های موجود در NewSubsets هر در زمان خاص و بصورت جداگانه بترتیب لغت نویسی انتخاب می شوند و
روش مرتبط سازی دوباره برای ایجاد دو مسیر از راه حل ها در مراحل 5 و 7 اعمال می گردد. راه حل های ایجاد شده در این مراحل به Pool اضافه می گردند. روش بهبود برای هر مرحله NumImp از فرآیند مرتبط سازی دوباره در هر مسیر اعمال می گیردد (مراحل 6 و 8). راه حل های یافته شده در حین کاربرد روش بهبود نیز به Pool اضافه می گردند. هر راه حل در Pool بررسی می گردد تا تعیین شود که آیا با جایگزینی بدترین راه حل موجود در RefSet بهبود می یابد یا نه. اگر اینطور بود، راه حل جدید جایگزین بدترین راه حل موجود می گردد و RefSet در مرحله 9 ثبت می گردد. در مرحله 10 پرچم NewSolutions به TRUE تغییر داده می شود و جفت که بتازگی ترکیب شده بود در مرحله 11 از NewSubsets حذف می گردد.
مانند طرح های جستجوی پراکنده مبنا، بروزرسانی سری منابع در شکل 2 بر مبنای بهبود کیفیت بدترین راه حل است و جستجو متوقف می گردد زمانیکه هیچ راه حل جدیدی برای RefSet پذیرفته نمی شود. روش ایجاد زیرمجموعه نیز خیلی ساده است و از ایجاد همه جفت راه حل ها در RefSet تشکیل شده است که حداقل شامل یک راه حل جدید است. ما استراتژی هایی را برای غلبه بر این طرح مبنا بکار می بریم.
شکل 2 راهکار مرتبط سازی دوباره مسیر مبنا
برای انتخاب از بین مسیرهای مختلف که در حرکت از به امکان پذیر است، را بعنوان تابع هدف انتخاب میکنیم که باید به حداقل مقدار رسانده شود. انتخاب مسیرهای نامناسب نسبت به - از حرکت هایی که نماینده ایجاد مسیر در هر مرحله هستند – یک سری نهایی از حرکت های بهبود داده شده برای تکمیل مسیر را ایجاد میکند. همچنین، انتخاب حرکت های مناسب در هر مرحله، حرکاتی با کیفیت پایین تر را در پایان ایجاد میکند (البته آخرین حرکت بهبود، یا عدم ایجاد هیچگونه تغییری در خواهد بود، اگر بعنوان مقدار بهینه موضعی انتخاب گردد). بنابراین انتخاب بهترین، بدترین و یا حرکات متوسط، گزینه هایی را ایجاد میکند که اثرات مغایری را در تولید توالی نشان داده شده ایجاد میکند. میتوان از معیار جداسازی (مانند جستجوی ممنوعه) برای لغو کردن انتخاب ها در دو مورد آخر استفاده کرد، اگر یک راه حل مناسب موجود باشد (بطور کلی، اینکار معقول به نظر می رسد که بهترین حرکات را در هر مرحله انتخاب کنیم، و سپس به گزینه انتخاب اجازه دهیم تا فرآیند را توسط تعویض و در مسیر مخالف دوباره آغاز کند). علاوه بر این، اگر یک همسایه مناسب در هر نقطه ای از فرآیند یافته شود، معیار جداسازی می تواند اجازه مرتبط سازی دوباره حرکت از مسیر معمول را با حرکت بسوی این همسایه بدهد.
انتخاب یک یا چند راه حل برای تبدیل شدن به نقاط مرجع برای آغاز یک محله جستجوی جدید ترجیحاً طوری ساخته می شود که نه تنها به بستگی داشته باشد بلکه به مقادیر از این راه حل های x نیز بستگی داشته باشد که میتوان با حرکت از به آنها رسید. این فرآیند را می توان طوری تغییر داد که به راه حل ها اجازه دهد تا ارزیابی شوند، نه اینکه را نزدیک تر به ایجاد کند. باز هم معیار جداسازی برای تصمیم گیری در این مورد بکار می رود که آیا این راه حل ها صلاحیت کاندید شدن برای انتخاب را دارند.
راهکار مرتبط سازی دوباره همزمان با هر دو نقطه پایانی و آغاز می شود که بطور همزمان دو توالی و را ایجاد میکند. انتخاب ها در این مورد برای بدست آوردن برای مقادیر نهایی r و s طراحی شده اند. برای پیشرفت بسوی نقطه ای که است، قوانین انتخاب باید به گونه ای باشند که مسیر به آخرین راه حل در مسیر جاری و مسیر دیگر اطراف آن نزدیک شود. مرتبط سازی دوباره همزمان را میتوان بعنوان فرآیندی تصور کرد که راه حل های راهنما برای آن پیوسته تغییر پیدا میکنند تا اینکه با یک نقطه منفرد همگرا می شوند.
نوسانات استراتژیکی مکانیزمی است که در جستجوی ممنوعه استفاده می شود تا به فرآیند اجازه دهد تا با نزیک شدن از دو طرف بسوی این محدوده، راه حل هایی را در اطراف محدوده بحرانی مشاهده کند. معمول ترین کاربرد نوسانات استراتژیکی برای مسائل محدود است، که محدوده بحرانی، همان محدوده امکان پذیری است. فرآیند جستجو از طرف امکان پذیر به طرف غیرامکان پذیر، و همچنین از طرف غیرامکان پذیر به طرف امکان پذیر، از محدوده عبور می کند. مرتبط سازی دوباره مسیر نیز به جستجو اجازه میدهد تا توسط استراتژی تونل زنی، از محدوده امکان پذیری عبور کند. این استراتژی این امکان را ایجاد میکند تا راه حل ها در حین مرتبط سازی و مشاهده گردند. این استراتژی همچنین اجازه می دهد که یا (نه هر دوی آنها) غیرامکان پذیر باشند.
استراتژی تونل زنی از جستجو در مقابل گم شدن در منطقه غیرامکان پذیر محافظت میکند، چون امکان پذیری بطور آشکار باید زمانی بازیابی شود که به می رسد. وقتی که اجازه این را دارد که غیرامکان پذیر باشد، مرتبط سازی دوباره مسیر ممکن است به محض اینکه منطقه امکان پذیر را ترک کند و یا اینکه به برسد، متوقف گردد، چون این امکان برای مسیر وجود دارد که به منطقه امکان پذیر باز گردد قبل از اینکه به برسد. بنابراین اثر تونل زنی شانسی را برای رسیدن به راه حل هایی بوجود می آورد که در غیر اینصورت احتمال داشت که نادیده گرفته شوند. با این وجود، باید تأکید کرد که (مانند جستجوی پراکنده) راه حل میانی ایجاد شده توسط مرتبط سازی دوباره مسیر نباید امکان پذیر گردد، تابعنوان یک راه حل آغازین با راهکار بهبود مرتبط گردد، چون مورد دوم را میتوان طوری طراحی کرد که امکان پذیری را بازیابی کند.
راهکار مرتبط سازی دوباره مسیر فراتر از ملاحظه نقاط بین و می گردد به شیوه ای که ترکیبات خطی فراتر از نقاطی گسترش می یابد که بصورت ترکیبات محدب دو نقطه پایانی نشان داده می شوند، و در نتیجه مرتبط سازی دوباره قیاسی را تعریف کند. ما برای جستجوی مسیری که تا فراتر از ادامه می یابد، مفهومی از جستجوی ممنوعه را معرفی میکنیم که اضافه سازی خصوصیات فعال-ممنوعه را به راه حل جاری ممنوع می سازد. فرض کنید که بیانگر سری خصوصیات راه حل همراه با x
باشد، و بیانگر سری خصوصیات راه حل باشد که توسط حرکات انجام شده برای رسیدن به راه حل جاری حذف می گردند که از آغاز می گردد (این خصوصیات ممکن است مؤلفه های خود بردارهای x باشند، و یا اینکه با تعریف مناسب نقشه برداری، با این مؤلفه ها مرتبط باشند).
یک حرکت را بصورت خصوصیتی از راه حل ایجاد شده توسط حرکات در نظر بگیرید، که البته خصوصیتی از راه حل نیست که حرکت را آغاز می کند. همچنین، را خصوصیتی از راه حل آغاز شده در نظر بگیرید، که البته خصوصیتی راه جدید ایجاد شده نیست. ما سپس حرکتی را در هر مرحله جستجو میکنیم تا تعداد ها را به حداکثر برسانیم که به تعلق دارد، و تابع این است تا تعداد راه حل هایی را که به تعلق دارند به حداقل برساند. چنین قانونی را معمولاً می توان بصورت مؤثر با ساختارهای داده های مناسب اجرا کرد. فرآیند وقتی که می رسد، با تغییر قوانین انتخاب بصورت زیر ادامه می یابد . اکنون معیار ما حرکتی را انتخاب میکند که تعداد آنرا در منهای تعداد آن به حداکثر برساند که در هستند، و تابع این تعداد آنرا به حداقل برساند که به تعلق دارند. ترکیب این معیارها اثر قیاسی را برای فرمول جبری استاندارد برای گسترش یک بخش از خط به آنیوب نقطه پایانی ایجاد میکند . سپس مسیر متوقف می گردد، هر زمانی که هیچ گزینه ای باقی نمانده باشد که به معیار به حداکثررسانی اجازه دهد که مثبت باشد. اهداف به حداکثررسانی این دو معیار تقریبی هستند میتوان آنها را کاهش داد.
نقاط جدید را میتوان از راه حل های راهنمای چندگانه بصورت زیر ایجاد کرد. بجای حرکت ا نقطه به (یا از) نقطه دوم ، ما را با مجموعه ای راه حل های جایگزین میکتیم. در هنگام ایجاد نقطه ، گزینه های موجود برای تعیین نقطه بعدی توسط ترکیب راه حل ها در بیان شده است، و یا بصورت دقیق تر، توسط ترکیب از سری خصوصیات بیان شده است، که می باشد. نقش را در راهکار خصوصیت-مبنا ایفا میکند که قبلاً توضیح داده شد، و با شرط اضافه شده که هر خصوصیت در تطابق با تعداد دفعاتی که در عناصر از مجموعه ظاهر می شود شمارش می گردد. بصورت کلی تر، ما میتوانیم وزنی را برای تعیین کنیم، که به مجموع وزن ها در تبدیل می شود که برای هر خصوصیت قابل اعمال است و اثر مشابهی با اثر ایجاد یک ترکیب خطی وزنی در فضای اقلیدسی ایجاد میکند. مناطق امیدوارکننده را میتوان توسط تغییر وزن های متصل به خصوصیت های راه حل های راهنما، و با تغییر انحراف همراه با کیفیت راه حل و ویژگی های راه حل انتخاب شده، با دقت بیشتری در مرتبط سازی دوباره مسیر جستجو کرد.
تغییر طبیعی از مرتبط سازی دوباره مسیر با استفاده از همسایه های سودمند برای ایجاد راه حل های آزمایشی جدید از مجموعه ای از راه حل های آغازین و راهنما رخ میدهد. در این حالت راه حل های راهنما از زیرمجموعه هایی از راه حل های ممتاز تشکیل می شوند (مانند قبل)، اما راه حل آغازین بصورت یک راه حل جزئی (غیرکامل) یا حتی بصورت یک راه حل صفر آغاز می گردد، که بعضی از مؤلفه های راه حل ها (مانند مقادیر متغیرها) هنوز تعیین نشده اند. استفاده از همسایگی سودمند به این راه حل اجازه میدهد تا توسط یک مسیر مجاور بسوی راه حل های راهنما حرکت کند که پیوسته عناصر
شامل در راه حل های راهنما را معرفی میکند، و یا اینکه بصورت یک ویژگی بر مبنای ترکیب راه حل های راهنما ارزیابی می گردد. ایده استفاده از همسایگی سودمند در زمینه مرتبط سازی دوباره مسیر اولین بار در مطالعه گلاور (1994) با بیان ایده ایحاد ترکیبات ساختاربندی شده معرفی شد. چنین فرآیندی بر مبنای سه ویژگی است.
ویژگی 1 (ویژگی معرفی). هر بردار نشاندهنده یک سری رای ها برای تصمیمات خاصی مانند تصمیم گیری در مورد تعیین یک مقدار خاص برای یک متغیر خاص، یا تعیین یک تسهیلات خاص برای یک محل خاص، یا ایجاد یک رابطه اولویت بین یک جفت عناصر خاص است.
ویژگی 2 (ویژگی راه حل آزمایشی). رای های توصیف شده توسط یک بردار به یک راه حل آزمایشی برای مسئله مورد توجه فرآیند معین تبدیل می گردد . بعنوان مثال یک سری ساده از رای های "بله-خیر" برای گزینه هایی که باید در یک سری شامل گردند، را میتوان به یک راه حل آزمایشی مطابق با توالی معین برای پردازش رای ها تبدیل کرد تا اینکه یا سری پر و کامل می شود و یا اینکه همه رای ها بررسی می گردند. رای های کلی تر برای یک مسئله یکسان نیز میتواند استفاده از یک توالی ارزیابی را تجویز کند. بردارهایی که رای ها را افزایش میدهند ممکن است نشاندهنده راه حل های امکان پذیر برای مسائل بررسی شده نباشند، و یا حتی بیانگر راه حل ها به شیوه معمول باشند.
ویژگی 3 (ویژگی بروزرسانی). اگر تصمیمی مطابق با رای های یک بردار مشخص گرفته شود، یک قانون کاملاً تعریف شده همه بردارها را برای مسئله باقیمانده بروزرسانی میکند بطوریکه ویژگی های 1 و 2 باقی می مانند. برای مثال، در هنگام تعیین یک مقدار خاص برای یک متغیر خاص، رای های بروزرسانی شده باقیمانده از هر بردار، توانایی تبدیل شدن به یک راه حل آزمایشی را برای مسئله باقیمانده حفظ میکنند، که تعیین در آن رخ داده است.
عموماً ایجاد خصوصیات قبلی آسان است و در نتیجه طبقات راهکارهای مرتبط سازی دوباره مسیر را افزایش میدهد که میتواند بعنوان اساسی برای فرآیند های چند-آغازی عمل کند. استراتژی توصیف شده بعدی امکان تغییرات بیشتر بر روی این ایده را ایجاد میکند.
ساخت واژگان ترکیبات ساختاریافته ای را نه تنها توسط استفاده از عناصر ابتدایی همسایگی معمول، بلکه همچنین توسط ساخت و متصل سازی مجموعه های پیچیده تر از این عناصر را ایجاد میکند. این فرآیند نام خود را از قیاس با فرآیند سودمند ساختن کلمات در مراحل سومند، جملات و پاراگراف ها گرفته است، که ساختمان های ارزشمندی در هر سطح را میتوان بصورت کلمات رده بالاتر مشاهده کرد، به همان شیوه ای که زبان های طبیعی کلمات جدیدی را ایجاد میکنند تا جای مجموعه ای از کلمات را بگیرد که حاوی مفاهیم سودمندی است. ساختمان واژگان اساسی انگیزه از این محتواها مزیت می گیرد که تنظیمات جزئی معینی از راه حل ها اغلب بعنوان مؤلفه های راه حل های کامل رخ میدهد. استراتژی جستجوی تنظیمات جزئی خوب نیز میتواند به انفجار ترکیبی کمک کند که تا حدودی از تغییر (فقط) ابتدایی ترین عناصر ناشی می گردد. این فرآیند همچنین از نیاز به ایجاد دوباره ساختار یک تنظیمات جزئی بعنوان اساسی برای ساخت یک راه حل کامل و خوب جلوگیری میکند. بطور کلی، ساخت واژگان بر مبنای فرآیند های مخرب و همچنین فرآیند های سودمند برای ایجاد راه حل های جزئی مطلوب است و تقسیمات راه حل با استفاده از راهکارهای دقیق یا کاوشی با هم ترکیب می گردند.
دسته بندی – که در مطالعه گلاور (1977) بعنوان راهی برای بهبود جستجوی پراکنده معرفی شده است – نیز به همان اندازه با مرتبط سازی دوباره مسیر مرتبط است. تقویت با انتخاب راه حل های مادر از یک دسته معمول ترغیب می گردد، درحالیکه تنوع توسط انتخاب راه حل های مادر از دسته های مختلف ترغیب می گردد. فرآیند های نیچ جدیدتر در الگوریتم های ژنتیک شباهت کمی با این راهکار دارند، بجز از این لحاظ که نیچ ها با عمل کردن با زیر-جمعیت های مختلف ایجاد می گردند، و از هیچ معیار استراتژیکی برای تعیین عضویت در زیر-جمعیت های قابل مقایسه با نوع انتقالی و مقایسه میانی ترکیب شده در فرآیند های دسته بندی استفاده نمی کنند (برای مثال، دسته بندی می تواند عضویت را بصورت مستقل از جمعیت مبدأ تعیین کند که بردار خاضی را ایجاد کرده است و از سنجش های شباهت و مکمل مناسب برای محتوای مسئله استفاده کند). روابط مشروط دارای اهمیت ویژه ای هستند، زمانیکه دسته بندی بعنوان یک مورد الحاقی برای جستجوی ترکیبی بکار می رود (همانطور که در مطالعه گلاور و لاگونا (1997) توضیح داده شده است)، و ما حدس می زنیم که توجه به این روابط میتواند کارایی استراتژی های جاری را افزایش دهد. بطور کلی، دسته بندی و ساخت واژگان با هم امکان های استراتژیکی را برای جستجوی پراکنده ومرتبط سازی دوباره مسیر فراهم می سازندکه شایسته توجه در کاربردهای آتی هستند.
نتیجه گیری ها
تمرکز و تأکید جستجوی پراکنده و مرتبط سازی دوباره مسیر مفاهیمی برای هدف تعیین راهکارهای بهینه سازی بهبود یافته دارند. این فرصت های تحقیقاتی تأکید بر روی تولید سیستماتیک و استراتژیکی قوانین طراحی شده را همراه خود دارند، و از سیاست موکول کردن تصمیمات به انتخاب های تصادفی پیروی نمی کنند، که اغلب در روشهای تکاملی مرسوم است. جهت یابی استراتژیکی در جستجوی پراکنده و مرتبط سازی دوباره مسیر توسط ارتباط با محیط های جستجوی ممنوعه تحریک می گردد که ایده های مرتبط سازی دوباره مسیر ابتدا پیشنهاد شدند، و سپس از ساختارهای حافظه انطباقی در تعیین استراتژی های ایجاد شده استفاده شد.
