ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی الگوریتم جستجوی ممنوعه
الگوریتم جستجو ممنوعه یا الگوریتم جستجوی ممنوع Taboo search اولین بار توسط فرد گلوور در مقاله ای که در سال 1986 منتشر گردید، ارایه شد. همچنین بعدا دو مقاله از ایشان با نام ساده “جستجو ممنوع” در سال‌های 1989 و 1990 منتشر گردید که در آن، خیلی از کاربردهای جستجو ممنوع را معرفی کرد.
اساس نامگذاری این روش، استفاده آن از لیستی به نام لیست ممنوع Tabu listمی باشد. این لیست برای جلوگیری از افتادن الگوریتم در نقطه بهینه‌های محلی طراحی شده است. به طور خلاصه، این روش به صورت مقابل بیان می‌شود. این الگوریتم از یک نقطه یا راه حل شروع کرده و در اطراف آن نقطه، به جستجوی همسایگی می پردازد. در بین همسایه‌ها، بهترین را انتخاب و به آن نقطه حرکت می نماید. این جستجوی را تا زمانی ادامه می دهد که یک معیار توقف برآورده گردد. در پایان جستجو، نقطه بهینه گزارش می‌شود. این الگوریتم فراابتکاری برای جلوگیری از افتادن در بهینه محلی، از یک حافظه کوتاه مدت استفاده می نماید. وظیفه این حافظه کوتاه مدت نگهداری از آخرین حرکت‌ها است که تعداد آن‌ها محدود شده است. این حرکت‌ها در یک لیست (لیست ممنوع) نگهداری می‌شوند. در هر حرکت، در صورتی که حرکت در لیست ممنوع قرار گرفته باشد، از آن انتقال جلوگیری می‌گردد مگر آنکه حرکت ممنوع دارای شرایط خاصی باشد.
اصول کلی الگوریتم جستجوی ممنوعه
الگوریتم فراابتکاری جستجوی ممنوع را می توان به عنوان یک استراتژی جستجوی محلی در نظر گرفت. این جستجو شامل حرکت از یک محل ( همان جواب یا نقطه) به راه حل دیگری در همسایگی او مطابق با بعضی از قواعد تعریف شده می باشد. برای مثال، مسئله حداقل سازی یک تابع همچون (F(x روی یک مجموع محدود از نقاط X را به عنوان یک حالت عمومی از یک مساله بهینه سازی ترکیبی در نظر بگیرید. روش جستجوی ممنوع از یک راه حل اختیاری شروع شده و در هر مرحله، به جستجوی همسایگی می پردازد. در این جستجو همسایگی، به هر یک زیر مجموعه اختصاص داده می‌شود که همسایه x نامیده می‌شود. در مرحله n، یک راه حل جدید در همسایگی از راه حل جاری را انتخاب می نماید. معمولا این راه حل بهترین راه حل در بین همسایه‌ها بوده و دارای شرط زیر می باشد.
الگوریتم، بعد از انتخاب راه حل xn+1 از نقطه xn به xn+1 حرکت می نماید و آنگاه راه حل xn+1 به عنوان راه حل جاری بعدی شناخته می‌شود. این جستجو تا زمانی ادامه می یابد که یک شرط توقف تعریف شده برآورده شود.
ممکن است به هنگام حرکت از یک نقطه به نقطه دیگر مشکلی پیش آید که به نام افتادن در بهینه محلی معروف است. شکل زیر را در نظر بگیرید.
همان طور که در این شکل دیده می‌شود، فضای جواب مساله دارای دو نقطه مینیم یا بهینه می باشد. نقطه بهینه، نقطه ای تعریف می‌شود که آن نقطه بهترین نقطه در تمامی نقاط اطراف خود باشد. به عبارت دیگر، نقطه ای مینیمم است که تمامی راه حل‌های اطراف آن بدتر از خود آن باشند. در این شکل، یک نقطه بهینه محلی و یک نقطه بهینه سراسری نمایش داده شده است.
مشکل افتادن در بهینه محلی، زمانی اتفاق می افتد که الگوریتم به نقطه بهینه محلی می‌رسد. در این نقطه، الگوریتم به جستجوی همسایگی پرداخته و یک همسایه را انتخاب می نماید. لازم به توضیح است که الگوریتم در جستجوی همسایگی، حتما باید یک نقطه را از بین همسایگان و غیر از خود انتخاب کند و به آن نقطه حرکت نماید، حتی اگر کیفیت آن نقطه پایین تر باشد. زمانی که الگوریتم در بهینه محلی قرار دارد، نقاط همسایه او دارای مقدار تابع یا کیفیت بدتر از خود نقطه بهینه محلی می باشند. از روی اجبار، الگوریتم به یکی از نقطه بین آن‌ها انتقال می یابد. بعد از حرکت به آن نقطه، دوباره به جستجوی همسایگی می پردازد و با توجه به اینکه نقطه بهینه محلی قبلی در همسایگی نقطه جدید قرار دارد و از نقطه فعلی بهتر است مجددا به بهینه محلی بر می‌گردد. در این حالت الگوریتم در یک دور یا سیکل افتاده و از آن خارج نمی‌گردد. این وضعیت به افتادن در بهینه محلی معروف می باشد که در شکل زیر نشان داده می‌شود.
در این شکل بهینه محلی با نقطه 1 نمایش داده شده و همسایه انتخاب شده برای حرکت، نقطه 2 می باشد. بعد از حرکت به نقطه 2، بهترین نقطه در همسایگی او، نقطه 1 می باشد و به آن بر می‌گردد. این روند همواره تکرار شده و الگوریتم از این دور یا سیکل خارج نمی‌گردد.
الگوریتم جستجوی ممنوع برای جلوگیری از این مشکل از ابزار لیست ممنوع استفاده می کند. در هر مرحله، در هنگام حرکت از یک نقطه به نقطه دیگر، مشخصاتی از حرکت (برای مثال فاصله و جهت) را به حافظه سپرده و در نقطه جدید از انجام حرکتی که منجر به برگشت به عقب می‌شود خودداری می کند. به منظور کارایی بیشتر، به جای یک حرکت قبلی، مجموعه ای از حرکت‌های قبلی را به حافظه سپرده و آن‌ها در لیستی به نام لیست ممنوع ذخیره می نماید. این لیست پویا بوده و در طول الگوریتم به هنگام می‌گردد. به عبارت دیگر، در هر حرکت، مشخصه حرکت جدید وارد لیست شده و مشخصه حرکت‌های قدیمی از لیست حذف می‌گردد. یک قاعده ساده این است که لیست طول محدودی داشته و زمان ورود یک حرکت به لیست، قدیمی ترین حرکت از آن خارج گردد.
الگوریتم‌ها در هر مرحله، بهترین نقطه را در بین همسایگان جستجو نموده و در صورتی به آن نقطه حرکت می نماید که آن حرکت ممنوع نباشد. به عبارت دیگر، حرکت مدنظر را با لیست ممنوع مقایسه نموده و در صورتی که حرکت ممنوع باشد، از آن حرکت صرفه نظر نموده و بهترین حرکت بعدی را در بین همسایگان انتخاب می نماید. نقطه بعدی انتخاب شده نیز با لیست ممنوع مقایسه می‌گردد.
لیست ممنوع با وجود مقید بودن، محدودیت‌هایی را برای الگوریتم به وجود می‌آورد. در طول جستجو الگوریتم، ممکن است یک حرکت ممنوع باشد، ولی انجام حرکت با وجود ممنوع بودن تاثیر بالایی در بهبود جهت حرکت و کیفیت جواب های الگوریتم دارد. برای این منظور، الگوریتم از یک معیار به نام معیار آرمانی برای رهایی از این محدودیت در مواقع لزوم استفاده می نماید. یک معیار آرمانی ساده این است که ممنوعیت حرکتی که موجب رسیدن به نقطه ای گردد که از تمامی نقاطی که تاکنون بدست آمده است بهتر باشد، در نظر گرفته نمی‌شود
