الگوریتم جستجوی ممنوعه ( Tabu Search ) ( TS ) یک الگوریتم بهینه سازی فراابتکاری است که برای اولین بار در سال ۱۹۸۶ توسط گلووِر Glover معرفی شد. [ ۱] در سال ۱۹۹۷، اولین کتابی که کاملاً به جستجوی ممنوعه اختصاص داشت توسط گلووِر و لاگونا منتشر شد. [ ۲] واژهٔ تابو از تُنگان زبان مردم جزایر پلینزی در اقیانوس آرام گرفته شده است. این واژه به معنای شیء مقدسی است که به دلیل قداست نباید آن را لمس کرد. [ ۳] بر اساس واژه نامهٔ وِبستر، امروزه این واژه در معنای «ممنوعیت ایجاد شده به دلیل فرهنگ اجتماعی برای ایجاد اقدام حفاظتی» یا «ممنوعیت چیزی که دارای ریسک است»، به کار می رود. [ ۴] معنای اخیر واژهٔ تابو، با تکنیک جستجوی ممنوعه کاملاً سازگار است. ریسکی که در الگوریتم جستجوی ممنوعه از آن اجتناب می شود، خطر مسیرهای نامناسب است. [ ۳]
برای رسیدن به جواب بهینه در یک مسئله بهینه سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می کند. سپس الگوریتم بهترین جواب همسایه را از میان همسایه های جواب فعلی انتخاب می کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می کند؛ در غیراین صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می شود؛ به این معنا که حرکت قبل که بوسیلهٔ آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود. در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه است که توسط آن از قرار گرفتن الگوریتم در بهینهٔ محلی جلوگیری می شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می شوند. مدت زمانی که حرکت ها در فهرست ممنوعه قرار می گیرند توسط یک پارامتر که زمان ممنوعه ( tabu tenure ) نام دارد تعیین می شود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می یابد که شرط خاتمه دیده شود. شرط های خاتمه متفاوتی می توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می تواند یک شرط خاتمه باشد. [ ۵]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفبرای رسیدن به جواب بهینه در یک مسئله بهینه سازی، الگوریتم جستجوی ممنوعه ابتدا از یک جواب اولیه شروع به حرکت می کند. سپس الگوریتم بهترین جواب همسایه را از میان همسایه های جواب فعلی انتخاب می کند. در صورتی که این جواب در فهرست ممنوعه قرار نداشته باشد، الگوریتم به جواب همسایه حرکت می کند؛ در غیراین صورت الگوریتم معیاری به نام معیار تنفس را چک خواهد کرد. بر اساس معیار تنفس اگر جواب همسایه از بهترین جواب یافت شده تا کنون بهتر باشد، الگوریتم به آن حرکت خواهد کرد، حتی اگر آن جواب در فهرست ممنوعه باشد. پس از حرکت الگوریتم به جواب همسایه، فهرست ممنوعه بروزرسانی می شود؛ به این معنا که حرکت قبل که بوسیلهٔ آن به جواب همسایه حرکت کردیم در فهرست ممنوعه قرار داده می شود تا از بازگشت مجدد الگوریتم به آن جواب و ایجاد سیکل جلوگیری شود. در واقع فهرست ممنوعه ابزاری در الگوریتم جستجوی ممنوعه است که توسط آن از قرار گرفتن الگوریتم در بهینهٔ محلی جلوگیری می شود. پس از قرار دادن حرکت قبلی در فهرست ممنوعه، تعدادی از حرکت هایی که قبلاً در فهرست ممنوعه قرار گرفته بودند از فهرست خارج می شوند. مدت زمانی که حرکت ها در فهرست ممنوعه قرار می گیرند توسط یک پارامتر که زمان ممنوعه ( tabu tenure ) نام دارد تعیین می شود. حرکت از جواب فعلی به جواب همسایه تا جایی ادامه می یابد که شرط خاتمه دیده شود. شرط های خاتمه متفاوتی می توان برای الگوریتم در نظر گرفت. به طور مثال محدودیت تعداد حرکت به جواب همسایه می تواند یک شرط خاتمه باشد. [ ۵]
wiki: الگوریتم جستجوی ممنوعه