موضوع مقاله: الگوریتم جستجوی ممنوعه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم جستجوی ممنوعه | مقدمه: در سال ۱۹۹۷، اولین کتابی که کاملاً به جستجوی ممنوعه اختصاص داشت توسط گلووِر و لاگونا منتشر شد.Glover F. | ## بخش 1: الگوریتم جستجوی ممنوعه | بر اساس واژه‌نامهٔ وِبستر، امروزه این واژه در معنای «ممنوعیت ایجاد شده به دلیل فرهنگ اجتماعی برای ایجاد اقدام حفاظتی» یا «ممنوعیت چیزی که دارای ریسک است»، به کار می‌رود.Merriam-Webster. ریسکی که در الگوریتم جستجوی ممنوعه از آن اجتناب می‌شود، خطر مسیرهای نامناسب است. چپ|10px|قاب|نمودار جریان الگوریتم جستجوی ممنوعه ساختار کلی جستجوی ممنوعه برای رسیدن به جواب بهینه در یک مسئله بهینه‌سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می‌کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می‌کند؛ در غیراین‌صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می‌شود؛ به این معنا که حرکت قبل که بوسیلهٔ آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می‌شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود. | ## بخش 2: الگوریتم جستجوی ممنوعه | در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه‌است که توسط آن از قرار گرفتن الگوریتم در بهینهٔ محلی جلوگیری می‌شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت‌هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می‌شوند. به‌طور مثال محدودیت تعداد حرکت به جواب همسایه می‌تواند یک شرط خاتمه باشد.الگوریتم‌های بهینه‌سازی فراابتکاری/تالیف مسعود یقینی، محمد رحیم اخوان کاظم‌زاده. جهاد دانشگاهی واحد صنعتی امیر کبیر استراتژی‌های پیشرفتهٔ جستجوی ممنوعه ساختار کلی جستجوی ممنوعه اغلب جوابگوی مسائل بزرگ نیست؛ بنابراین به منظور افزایش قدرت الگوریتم از استراتژی‌های زیر که معروف به استراتژی‌های پیشرفته جستجوی ممنوعه هستند استفاده می‌شود:Gendreau, M. روشی دیگر، این است که به جای آن که تمامی همسایه‌ها بررسی شود، تنها یک زیرمجموعهٔ تصادفی از همسایه‌ها در نظر گرفته شود، که در نتیجه هزینهٔ محاسباتی به‌طور قابل ملاحظه‌ای کاهش می‌یابد. انتخاب زیرمجموعه‌ای از جوابهای همسایه به صورت تصادفی، می‌تواند به عنوان یک مکانیزم ضد چرخه عمل کند؛ این کار اجازه می‌دهد که از فهرست ممنوعهٔ کوچکتری نسبت به کل همسایگی، استفاده شود. | ## بخش 3: الگوریتم جستجوی ممنوعه | البته باید در نظر داشت که این کار یک عیب مهم دارد و آن احتمال از دست دادن جوابهای خوب است، بنابراین احتمال‌هایی را نیز می‌توان به کار برد تا معیارهای ممنوعه فعال شود. تقویت، در بسیاری از پیاده‌سازی‌های TS استفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در آن‌ها جستجوی معمولی کفایت می‌کند. نتیجه‌ای که از این واقعیت می‌توان گرفت، این است که هر چند جواب‌های خوبی به وسیلهٔ این روشها به دست می‌آید، اما ممکن است جستجو از اکتشاف مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. برای انجام این کار، تنوع‌بخشی، جستجو را مجبور می‌کند به سوی مناطقی که تا کنون کشف نشده، حرکت کند. مجوز دادن به جوابهای نشدنی: در حالت‌هایی که محدودیت‌های مسئله بسیار محدودکننده باشند و از جستجوی مؤثر فضای جواب جلوگیری کنند از این استراتژی استفاده می‌شود. | ## جمع‌بندی | طی این استراتژی محدودیت‌های مسئله آزاد شده و بجای آن‌ها یک مقدار جریمه به تابع هدف اضافه می‌شود.