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

الگوریتم جستجوی پراکندگی اسکتر سرچ باید بر اساس عناوین زیر  میتوان ترسیم گردد :

  1. تولید یک مجموعه شروع شونده از بردار جواب ها تا سطح بحرانی تنوع تامین شود و همچنین به کارگیری الگوریتم ابتکاری طراحی شده برای مساله باید برای بهبود جواب ها باشد. تخصیص مجموعه ای از بهترین بردار ها به جواب های مجموعه مرجع. ( تکرار های بعدی این گام از گام ۴ زیر، شامل جواب های پیشرفته اولیه و بهترین جواب ها از گذشته به عنوان کاندید مجموعه مرجع هستند. ) عبارت ” بهترین ” تنها مختص جواب هایی با معیار ارزیابی تابع هدف نیست. یک جواب در صورتی که درجه تنوع مجموعه را بالا ببرد به مجموعه مرجع اضافه شود حتی اگر مقدار تابع هدف این جواب کمتر از رقبای کاندید برای عضویت در مجموعه مرجع باشد.
  2. جواب های جدید شامل ترکیبات ساخت یافته از زیر مجموعه های جواب های مرجع کنونی ایجاد گردد.
  3. تعدادی از جواب ها انتخاب می شوند تا نقاطی داخل و خارج از فضای محدب پوشش داده شده توسط جواب های مجموعه مرجع تولید کنند.
  4. جواب ها تعدیل و اصلاح می شوند تا به جواب های قابل قبول دست پیدا کنیم. ( برای مثال اگر یک جواب از ترکیب خطی دو یا چند جواب بدست امده باشد، یک فرایند عمومی گرد کردن میتواند برای دستیابی به مقادیر صحیح، با محدودیت صحیح بودن بردار ها بدست آید. یک جواب قابل قبول ممکن است برای محدودیت های دیگر مساله موجه باشد و یا نباشد. )
  5. الگوریتم جستجوی پراکندگی اسکتر سرچ  در قدم ۱ را برای بهبود جواب های تولید شده در گام ۲ به کار ببریم. این فرایند های ابتکاری باید قابلیت کاربرد روی جواب های ناموجه را داشته باشد و می تواند به جواب های موجه یا ناموجه دست یابد.
  6. مجموعه از بهترین جواب های بهبود یافته از قدم ۳ را استخراج و به مجموعه مرجع اضافه می کنیم. عبارت ” بهترین ” مجددا نیز کلی است؛ مقدار تابع هدف را در میان چندین معیار برای ارزیابی مزیت نقاط جدید تولید شده قرار دهید. گام های ۲، ۳ و ۴ را تا زمانی تکرار کنید که مجموعه مرجع دیگر تغییری نکند. با شروع مجدد از گام ۱ مجموعه مرجع را متنوع کنید. و هنگامی که به تعداد مشخصی تکرار رسیدید توقف نمایید.

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

ویژه گی مهم دیگر مرتبط با استراتژی هایی است که برای انتخاب زیر مجموعه های معین از جواب ها برای ترکیب در گام ۲ به کار می رود. این استراتژی ها به گونه ای طراحی شده اند که از نوعی دسته بندی استفاده کنند تا جواب های جدید ” درون دسته ای ” و ” میان دسته ای ” تولید شوند. نهایتا این روش طوری سازمان دهی شده است تا از مکانیزم های بهبود دهنده که قادر به اجرا روی جواب های نا موجه هستند استفاده کند، و محدودیت موجه بودن جواب ها را حذف می کند تا جواب های نا موجه نیز در مجموعه مرجع وارد شوند.

اصول زیر بنیان روش الگوریتم جستجوی پراکندگی اسکتر سرچ را خلاصه می کند :

  • اطلاعات مفید در باره ی شکل ( یا مکان ) جواب های بهینه معمولا در مجموعه جواب های منتخب و خوب وجود دارد.
  • وقتی که جواب ها به عنوان یک استراتژی برای استفاده از چنین اطلاعاتی با هم ترکیب می شوند، داشتن مکانیزمی که قادر به ساختن ترکیباتی باشد تا فراتر از نواحی پوشش داده شده توسط جواب ها را برون یابی کند، ضرورت دارد. به طریق مشابه شامل کردن فرایند های ابتکاری برای ترسیم جواب های ترکیبی به جواب های جدید ضرورت دارد. هدف این مکانیزم های ترکیب رسیدن به کیفیت و تنوع در جواب ها است.
  • به عنوان یک بنیان برای تولید ترکیبات، در نظر گرفتن چندین جواب به صورت همزمان، شانس بهرمندی از اطلاعات جواب های منتخب و خوب را افزایش می دهد.
  • این نکته قابل توجه است که در برخی از موارد جواب های با کیفیت بالا اغلب نزدیک مرز های ناحیه شدنی اتفاق می افتند. برای مسائلی که به دلیل وجود محدودیت های تساوی از نظر تکنیکی فضای داخلی ندارند نیز این پدیده عنوان شده می تواند اتفاق بیافتد، خواه نسبت به یک زیر مجموعه از محدودیت ها که نامساوی هستند و یا نسبت به فضای ایجاد شده با حذف متغیر هایی که نقش اسلک را برای تساوی های مشخصی دارند و بنابراین ان ها را به نا مساوی تبدیل می کنند. بنابراین ترکیبات خطی گرایش به تولید نقاطی دارند که در نزدیکی انتخاب شده از مرز فضای موجه هستند.

این امر که مکانیزم های درون الگوریتم جستجوی پراکندگی اسکتر سرچ به یک شکل واحد محدود نیستند، سبب جستجوی استراتژی هایی که امکان موثر واقع شدن را دارند، می شود. این مبانی و مشاهدات به قالب و طرح زیر برای پیاده سازی جستجوی پراکندگی می انجامد. ( قالبی مشابه این نیز برای پیاده سازی ترکیبات تولید شده توسط پیوند مجدد مسیر همانطور که بعدا توضیح می دهیم استفاده می شود. )

  1. روش تولید تنوعبرای تضمین مجموعه ای از جواب های متنوع، با استفاده از جواب های تصادفی ازمایشی ( یا جواب های هسته ) به عنوان ورودی.
  2. یک روش بهبود دهنده برای تبدیل یک جواب ازمایشی به جوابی بهتر. هیچ یک از جواب های ورودی یا خروجی لازم نیست موجه باشند اگرچه جواب های خروجی معمولا انتظار می رود که موجه باشند. اگر هیچ بهبودی در جواب ازمایشی ایجاد نشد، جواب ارتقاء یافته همانند جواب ورودی در نظر گرفته می شود. )
  3. یک روش بروز رسانی مجموعه مرجع برای ساختن و نگه داری b تا از ” بهترین ” جواب های یافته شده ( معمولا مقدار b کوچک است و کمتر از ۲۰ است )، که برای دسترسی موثرتر بوسیله ی بقیه قسمت های روش سازمان یافته است. جواب ها بر اساس تنوع یا کیفیتشان عضو مجموعه مرجع می شوند.
  4. یک روش تولید زیر مجموعه برای عمل روی مجموعه مرجع برای تولید زیر مجموعه ای از جواب ها به عنوان پایه ای برای ساخت جواب های ترکیبی.
  5. یک روش ترکیب جواب برای تبدیل یک مجموعه داده شده از جواب های تولید شده توسط روش تولید زیر مجموعه به یک یا بیش از یک جواب ترکیبی.

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

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

ابتدا تولید مسیر هایی که دو جواب انتخاب شده x’ و x” را اتصال می دهند در نظر می گیریم. توجه خود را به قسمتی از مسیر معطوف می کنیم که ” بین ” جواب ها وجود دارد و توالی جواب x’=x(1),x(2),…,x(r)=x” را می سازیم. برای کاهش تعداد انتخاب هایی که باید لحاظ شوند، در هر مرحله جواب x(i+1) می تواند از جواب x(i) با انتخاب حرکتی که تعداد کاهش یافته حرکت های باقی مانده برای رسیدن به x را رها می کند، بدست آید ( یا با شدت بیشتر، ” کمترین ” تعداد حرکت ). این دستورالعمل اگر بدون استثنا به کار گرفته شود، تعداد قابل توجهی از انتخاب های ممکن برای تولید جواب بعدی در هر مرحله را حذف می کند. در نتیجه همانطور که مختصرا نشان داده شد، معیار های اضافی با ساختن مسیر مرتبط هستند.

ممکن است در جستجوی پراکنده x’ و x” توسط یک مسیر تولید شده بوسیله فرایندی ابتکاری ( یا یک فرایند فراابتکاری مثل جستجوی ممنوعه ) متصل شده باشند. در این رویداد مسیر جدید تولید شده توسط پیوند مجدد مسیر تقریبا از مسیر اولیه متمایز است و مسیر مستقیم تر میان دو نقطه را انتخاب می کند. همانطور که در شکل ۲ نشان داده شده است.

همچنین ممکن است که x’ و x” اصلا در مسیر جستجوی قبلی متصل نشده باشند، اما روی مسیر جستجوی دیگری که توسط یک ابتکاری یا فرایند های پیوند مجدد قبلی تولید شده اند، موجود باشند. این وضعیت در شکل ۳ نشان داده شده است.

در این مورد مسیر مرتبط x’ و x” ، با تغییر ارتباطاتی که x’ و x” را ساخته اند، یک تابع پیوند مجدد را اجرا می کند. مسیر پیوند مجدد این نمودار به صورت بسط فراتر از نقاط x’ و x”  نشان داده می شود. ما این نوع از ساختن را با عنوان پیوند مجدد درون یابی شده بررسی می کنیم.

برای انتخاب از میان مسیر های مختلفی که از x’ به x” می رود، فرض کنید (c(x نشان دهنده تابع هدفی باشد که میخواهیم حداقل نماییم. انتخاب حرکت های غیر جذاب بر اساس (c(x از میان حرکت های کاندید برای تولید مسیر در هر مرحله به تولید سری نهایی از حرکت های بسیار بهبود بخش برای تکمیل مسیر می انجامد. بطور متناظر انتخاب حرکت های جذاب در هر مرحله باعث ایجاد حرکت های با کیفیت کم در انتها می شود. ( اگر x” یک بهینه محلی باشد، حرکت اخر یا بهبود بخش است و یا c(x) را تغییری نمیدهد. )، بنابراین انتخاب بهترین و بدترین حرکت ها و یا حرکت های متوسط اثرات متضادی در تولید توالی نشان داده شده دارد. یک معیار مطلوبیت همانطور که در جستجوی ممنوعه هست می تواند استفاده شود تا انتخاب های دو مورد آخر را اگر یک جواب بطور کافی جذاب وجود داشته باشد، لغو کند.

انتخاب یک یا بیش از یک جواب (x(i برای مرجع قرار گرفتن و انجام عملیات جستجوی جدید، ترجیحا به مقادیر ((c(x(i بستگی ندارد، بلکه به مقادیر (c(x ای بستگی دارد که در حرکت از (x(i) می توان به آن رسید. این فرایند می تواند تغییر کند تا به جواب ها، به جز جواب هایی که (x(i+1 نزدیک تر به x” حاصل می کنند، اجازه ارزیابی بدهد. معیار مطلوبیت نیز با اینکه آیا این جواب ها به عنوان کاندید برای انتخاب واجد شرایط هستند یا خیر، مرتبط است.

در توضیح فرایند، فرض کنید )x*(i نشان دهنده ی یک همسایه از (x(i باشد که منجر به حداقل مقدار (c(x در گام ارزیابی می شود، به استثنای (x*(i)=x(i+1 . اگر قوانین انتخاب بطور اتوماتیک احتمال (x*(i)=x(h برای h<i را از بین نبرد، آنگاه یک محدودیت ممنوعه می تواند به سادگی این کار را بکند  سپس روش یک جواب (x*(i را که به مقدار حداقل برای ((c(x*(i می رسد به عنوان نقطه جدید برای اجرای جستجو انتخاب می کند. اگر تنها مجموعه ی محدودی از همسایه های (x(i برای تعیین x*(i) امتحان شود، کمترین هزینه برتر جواب (x(i به استثنای x’ و x” می تواند به جای آن انتخاب شود. ختم اولیه در رویارویی با (x*(i که به c(x*(i))<min(c(x’),c(x”),c(x(pبیانجامد بطوریکه (x(p حداقل هزینه (x(h برای h<i است، ممکن است ( هرچند اجباری نیست ). این رویه ادامه می یابد اگر (x(i، در مقابل x*(i) به مقدار کمتر (c(x از x’ و x” برسد، چون (x(i بطور موثری نقش x’ را ایفا می کند.

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