جستجوی ممنوعه Tabu Search یاTS انجام پروژه های دانشجویی برنامه نویسی کدنویسی متلب matlab مطلب

انجام پروژه های دانشجویی برنامه نویسی کدنویسی

متلب matlab مطلب

الگوریتم های بهینه سازی فرا ابتکاری 

Email : matlab_net@yahoo.com

Phone : 09190090258 

گروه آموزشی متلب نت

1-معرفی

جستجوي تابو به تابع جستجو اجازه مي‌دهد تا راه‌حلهايي را بررسي نمايد كه كاهش دهنده ارزش تابع هدف نمي‌باشند، البته در صورتي كه اين راه‌حلها بصورت ممنوعه نباشند. اين الگوريتم مشخصه‌اش اين است كه از حافظه منعطفي استفاده مي‌كند. اين الگوريتم قادر به حذف كمينه محلي است تا در فضاي جستجو به بهينه سراسري برسد. بنابراين اين الگوريتم قادر به يافتن كمينه سراسريِ يك فضاي چند قيدي است. و اين كمينه را با توجه به تابع ارزيابي محاسبه مي‌كندكه در هر تكرار بيشترين مقدار جواب را انتخاب مي‌كند. و در هر مرحله با توجه به مقداري كه از فضا حذف مي‌شود، جواب را به سمت نقطه‌اي كه بر اساس تابع ارزيابي و محدوديت‌هاي تابو پديد آمده حركت مي‌دهد.تابع ارزيابي حركتي كه بيشترين پيشرفت يا حداقل بدترشدن را در تابع هدف داشته انتخاب مي‌كند. فهرست تابو براي ذخيره كردن مشخصه‌هاي انتقالِ قابل قبول به كار گرفته مي‌شود، بنابراين اين در هر تكرار مشخصه‌ها مي‌توانند در دسته‌بندي انتقال‌ها به عنوان تابو ( يعني با يد از آن حذر كرد) در نظر گرفته شوند. به عبارت ديگر، فهرست تابو تعيين مي‌كند كه توسط انتقال از جواب فعلي به كداميك از جوابها برسيم. از آنجايي كه انتقال در بهبود جوابي كه پذيرفته مي‌شود نقشي ندارد، ممكن است به جوابي كه هم اكنون در آن است بازگردد و اين باعث چرخه تكرار شود. استراتژي‌اي كه استراتژي منع كردن ناميده مي‌شود فهرست تابو را كنترل و بروز مي‌كند تا اين مشكل برطرف شود.

2- استراتژي‌ها

الگوريتم تابو شامل سه استراتژي مهم است: استراتژي منع‌كنندگي[3] ، استراتژي ترخيص[4] و استراتژي كوتاه مدت (Glover 1989, Glover 1990).

     استراتژي منع‌كنندگي آنچه را كه در فهرست تابو وارد مي‌شود را كنترل مي‌كند. استراتژي ترخيص انچه كه از فهرست تابو خارج مي‌شود و اينكه چه موقع خارج مي‌شود را كنترل مي‌كند. استراتژي كوتاه‌مدت فعل و انفعالي كه بين استراتژي منع‌كننده و استراتژي ترخيص براي انتخاب جواب نامزد وجود دارد را مديريت مي‌كند. مجزا از اين استراتژي‌ها، استراتژي يادگيري وجود دارد كه در موقع استفاده از توابع حافظه ميان‌مدت و بلند‌مدت به كار گرفته مي‌شود. اين استراتژي اطلاعات را در طول اجراي جستجوي تابو جمع‌آوري مي‌كند و اين اطلاعات به طور مستقيم در اجراي  جستجوي توالي هاي بعدي استفاده مي‌شود.

1-2-استراتژي‌ منع‌كنندگي.

اين استراتژي براي جلوگيري از چرخه تكرار توسط انتقال‌هاي ممنوع يا به عبارت ديگر دسته‌بندي آنها به عنوان يك منع‌شده استفاده مي‌شود. در جهت جلوگيري از چرخه تكرار، كافي است چك كند آيا جواب‌هاي قبلي مشاهده شده مجدداً ملاقات مي‌شود. كمال مطلوب اينكه فهرست تابو بايدتمام جواب‌هايي كه قبلاً مشاهده شده را ذخيره كند و قبل از هر انتقال جديد فهرست چك شود. به هر حال اين عمل نياز به حافظه بالا و محاسبات زيادي دارد. قاعده ساده‌اي براي جلوگيري از چرخه تكرار اين است كه جوابي كه در آخرين تكرار بدست آمده ، مجدداً انتخاب نشود. بديهي است اين روش از به وقوع پيوستن چرخه تكرار جلوگيري نمي‌كند. راهي ديگر اين است كه جواب‌هايي كه در طولِ دور آخر مشاهده شده Ts را انتخاب نكند(اين جواب‌ها را درون فهرست ممنوعه قرار دهد). بنابراين، با جلوگيري نقصي كه  انتخاب جوابهاي قبلي در طولِ اين تكرارها داشته است، جستجوي بصورت بهبود بخشي حركت مي‌كند. در اينجا Ts فهرست ممنوعه  يا اندازه فهرست ممنوعه است. با كمك از مقادير درخورِ اندازه فهرست ممنوعه (Ts)، احتمالِ اينكه چرخه تكرار رخ دهد ضعيف مي‌شود. اگر اين مقدار خيلي كوچك باشد، احتمال چرخه تكرار بالا است. و اگر خيلي زياد باشد ممكن است قبل از اينكه به اكتشاف فضاي‌هاي جديد بپردازد، جستجو در حولِ همسايگي جواب خوبي كه تا كنون بدست آمده انجام پذيرد.

     فهرست جستجو يكي از توابع حافظه كوتاه‌مدت اوليه‌ي جستجوي ممنوعه را دربردارد. همان طوري كه در بالا شرح داده شد، فهرست ممنوعه تنها آخرين انتقال‌ها را ثبت مي‌كند. زمانيكه فهرست ممنوعه پر شد، هر جوابي كه برگزيده مي‌شود جايگزين قديمي ترين عنصر اين فهرست مي‌شود. اين اعمال بر طبقِ اولين وارده-اولين صادره[5] انجام مي‌شود.

معيار هدف و محدوديت‌هاي ممنوعه. با معيار هدف، يك جواب با اينكه در فهرست ممنوعه قرار دارد را انتخاب مي‌شود اگر كيفيت كافي را داشته باشد و از چرخه تكرار جلوگيري كند. معيار هدف در هدايت فرايند جستجو نقش دارد و محدوديت‌هاي ممنوعه در ساختن فضاي جستجو. جوابي قابل قبول مي‌شود كه محدوديت‌هاي ممنوعه ارضا شود. در مورد يك جواب ممنوعه اگر معيار هدف به كار گرفته شود صرفنظر از شرايط ممنوع بودنش قابل قبول فرض مي‌شود. مشخصه‌هاي انتقال، در جستجوي ممنوعه ثبت و استفاده مي‌شود تا محدوديت‌هايي را كه جلوي انتخاب را مي‌گرفتند بي اثر كند. محدوديت‌هاي ممنوعه براي جلوگيري از تكرار استفاده مي‌شوند. نقش جلوگيري از تكرار مسيري براي جستجوي جواب باز مي‌كند. محدوديت ممنوعه تنها زماني فعال‌ مي‌شود كه مشخصه‌هايش در تعدادي محدود تكرار كه مقدم بر تكرار فعلي است رخ دهد (محدوديت بر پايه جديدترين تكرار[6]) و يا با فراواني معلومي از بين تعداد زيادي تكرار (محدوديت برپايه فراواني[7]) رخ مي‌دهد.

     در محدوديت بر پايه جديدترين تكرار، توزيع ممنوعه تعيين مي‌شود و جواب ممنوعه به عنوان ممنوعه از درون مدت ممنوعه باقي‌مي‌ماند. نقش تعيين كردنِ مدت ممنوعه به دو گروه ايستا و پويا دسته‌بندي مي‌شود. قواعد ايستا از مدتي كه درون جستجو ثابت مانده، مقداري انتخاب مي‌كند. قواعد پويا به مقدار اجازه تغيير كردن را مي‌دهد.

     در محدوديت‌هاي بر پايه فراواني، اندازه فراواني استفاده مي‌شود. اين اندازه نسبتي است كه صورت كسر، شمارش تعدادِ وقايع يك رويداد خاص و مخرج كسر يكي از مقادير زير مي‌باشد(Reeves 1995):

الف) جمع صورت

ب) بيشترين مقدار صورت

ج) ميانيگين مقادير صورت

استفاده مناسبِ معيار هدف براي قادرساختن جستجوي ممنوعه در رسيدن به بهترين عملكرد بسيار مهم است. معيار هدف مي‌تواند هم وابسته به زمان و يا مستقل از زمان باشد. كاربردهاي اخير جستجوي ممنوعه تنها از يك نوع سادة معيار هدف استفاده مي‌كند كه داراي معيارمستقل از زمان است. اين معيار هدف شامل حذف دسته‌بندي ممنوعه از يك جواب آزمايشي است زماني كه جواب عملكرد بهتري را از بهترين جواب تاكنون نشان مي‌دهد. اين روش به طور گسترده‌اي كاربرد دارد. روش ديگري كه زياد استفاده مي‌شود، هدف بطور پيش‌فرض[8]  نام دارد. با اين معيار، اگر تمام انتقال‌هاي دردسترس به عنوان يك ممنوعه دسته‌بندي شود، در اين حالت با معيارهاي ديگر انتخاب قابل قبولي وجود ندارد ولي با اين معيار، جوابي كه در فهرست ممنوعه كمترين است انتخاب مي‌شود. اين مي‌تواند جوابي باشد كه با كمترين افزايشي در مقدار جاري اين تعداد تكرارِ الگوريتم  داشته، دسته‌بندي ممنوعه‌اش را از دست داده است. به غير از اين دو معياري كه گفته شد، معيارهاي زيادي وجود دارد از قبيل هدف بوسيله هدف[9]، هدف بوسيله جستجوي مستقيم و هدف به وسيله تاثير(Reeves 1995).

استراتژي‌ ترخيص. استراتژي ترخيص براي تصميم گيري اينكه كداميك از فهرست ممنوعه خارج شود استفاده مي‌شود. اين استراتژي محدوديت‌هاي ممنوعه را حذف مي‌كند بنابراين جوابي كه تاكنون نمي‌توانست انتخاب شود در تكرار‌هاي بعدي در نظر گرفته مي‌شود. مشخصه‌هاي يك جواب ممنوعه در طول تكرارهاي اين فهرست، روي فهرست ممنوعه اثر مي‌گذارد. يك جواب زماني قابل قبول است كه مشخصه‌هاي آن ممنوعه نباشد يا اينكه تست معيار هدف را گذرانده باشد.


                         

استراتژي‌هاي متوسط و بلند مدت. اين استراتژي‌ها توابع بلند مدت و متوسط را به كار مي‌گيرند. تابع متوسط عنصر تشديد را ايجاد مي‌كند. اين تابع بدين شكل عمل مي‌كند كه در طول اجراي الگوريتم تعدادي جواب انتخاب شدة خوب كه  توليد انتقال كرده‌اند را ثبت مي‌كند. اين عمل مي‌تواند به عنوان استراتژيِ يادگيري در نظر گرفته شود كه مانند جواب‌هايي كه  درگذشته ثبت ‌شده بود بدنبال يافتن جواب‌هاي جديدي است. اين عمل توسط انتقال‌هاي محدود شده‌اي بدست مي‌آيد كه اجازه رسيدن به جواب‌هاي موردنظر را نداده بودند.

استراتژي كوتاه مدت (استراتژي سرتاسري). اين استراتژي تقابل بين دو استراتژي كه در بالا گفته شد را مديريت مي‌كند. استراتژي سرتاسري در شكل(2-4) نشان داده شده است. فهرست نامزد[10] ، زير مجموعه‌اي از انتقال‌هاي ممكن است. استراتژي‌هاي فهرست نامزد، معمولاً وابسته به مسأله‌اند  و مي‌توانند توسط روش‌هاي گوناگوني از قبيل نمونه‌گيري ساده بدست‌آيد.

     استراتژي‌هاي انتخابِ بهترين جواب، جوابي قابل قبول را از جواب‌هاي جاري انتخاب مي‌كنند كه همچنان بيشترين بهبود يا كمترين بدتر شدن را در تابع هدف داشته باشند به طوري كه محدوديت‌هاي ممنوعه و معيار هدف را ارضا كنند. اين عمل يك معيار تهاجمي است و بر پايه فرضي است كه جواب‌هاي با سنجش بالا، احتمال بالايي  دارد كه به نزديك‌ترين جواب بهينه يا يك جواب خوب در در كمترين تعداد تكرار، هدايت شود. اگر يك جواب معيار هدف را ارضا كند، در انتخاب آن ممنوع يا ناممنوع بودنش نقشي ندارد ولي اگر اين جواب معيار هدف را ارضا نكند براي اينكه قابل قبول شود با ممنوعه نباشد.

     معيار توقف، بعد از تعداد تكرار مشخصي كه در مجموع رسيد يا از موقعي كه بهترين مقدار را يافت رويه جستجوي ممنوعه را متوقف مي‌كند.

[1] Glover

[2] Hansen

[3] Forbidding Strategy

[4] Freeing Strategy

[5]  fist-in-first-out (FIFO)

[6]  recency-based restriction

[7]  frequently-based restriction

[8]  aspiration by default

[9] aspiration by objective

تعریف آرایه های توسعه یافته با container map در matlab,تعریف آرایه های توسعه یافته با container map در متلب,تعریف آرایه های توسعه یافته با container map در مطلب,تعریف بهینه سازی,تعریف بهینه یابی,تعریف تایمرها در matlab,تعریف تایمرها در متلب,تعریف تایمرها در مطلب,تعریف تخطی,تعریف قیدهای موجود در سبد سهام,تعریف و استفاده از توابع در matlab,تعریف و استفاده از توابع در متلب,تعریف و استفاده از توابع در مطلب,تعریف و تحلیل نرخ های بهره,تعریفی از بهینه سازی,تعریفی از بهینه یابی,تعقیب تصویری یا video tracking,تعمیم pca,تعمیم روش های td با معیارهای شایستگی,تعمیم روش های یادگیری تقویتی به فضای پیوسته,تعیین ساختار شبکه,تعیین ضرایب بهینه