بخشی از مقاله
بهینه سازي حل مسأله هشت وزیر به روش الگوریتم ممتیک
چکیده:
مسأله هشت وزیر، از جمله مسائل NP Hard میباشد. با توجه به اینکه الگوریتمهاي ممتیک از جمله الگوریتمهاي تکاملی است، میتواند براي حل این مسائل مورد استفاده قرار گیرد. در این مقاله به حل مسأله پیچیده هشت وزیر با استفاده از الگوریتم ممتیک میپردازیم و سپس الگوریتم جستجوي محلی جدیدي معرفی میگردد که باعث هوشمندي بیشتر و افزایش سرعت الگوریتم ممتیک شده و منجر به یافتن پاسخ بهتر براي این مسأله میشود. الگوریتم ممتیک با جستجوي محلی راه حلهاي بهینه در مسائل بهینه سازي ارائه میدهد. این الگوریتمها با استفاده از یک تکنیک جستجوي محلی پایداري الگوریتم را افزایش داده و با اجتناب از همگرایی زود رس صحت همگرایی در الگوریتم را بهبود میبخشد.
کلید واژه: الگوریتم ممتیک (Memetic Algorithm)، مسأله NP Hard، تابع شایستگی (Fitness)، جستجوي محلی (Local Search)
-1 مقدمه
پیچیدگی مسائل و توجه بیشتر به سرعت حل مسائل، موجب شده که روشهاي کلاسیک و سنتی چندان پاسخگوي مناسبی نباشند لذا امروزه از الگوریتمهاي جستجوي تصادفی در برابر روشهاي جستجوي همه جانبه فضاي مسأله استقبال بیشتري میشود. در این بین در سالهاي اخیر استفاده از الگوریتمهاي جستجوي هیوریستیک (شهودي) همچون الگوریتم ژنتیک GA) )، الگوریتم کلونی مورچهها (ACO)، الگوریتم پرندگان (PSO) و الگوریتمهاي ممتیک ... (MA) رشد چشمگیري داشته است.
الگوریتمهاي ژنتیک کلاسیک در یافتن نواحی جواب با سرعت خوبی عمل میکنند اما در به دست آوردن جواب با دقت مورد نظر زمان زیادي را صرف میکنند. این نقص را میتوان تا حدودي با بکارگیري دانش موجود از مساله و یا اضافه کردن فاز جستجوي محلی به چرخهي تکاملی بهبود بخشید. محققان با الهام گرفتن از ایدهي »مم«که توسط ریچارد داوکینز1 مطرح شد[1] الگوریتمهایی پیشنهاد کردهاند که ممها به عنوان جستجوگرهاي محلی جوابهاي بدست آمده را بهبود میدهند تا فرآیند جستجو سریع تر و کاراتر شود. به این گونهروشها
الگوریتمهاي ممتیک یا دورگه گفته میشود. این الگوریتمها از نظر تطبیق پذیري به 3 دسته ي ایستا، تطبیقی و خودتطبیقی تقسیم می شوند. در دوستهي اول ممها در فرآیند جستجو تغییر نمیکنند و فقط انتخاب بهترین مم مطرح است ولی در دستهي سوم مم ها در جمعیتی جداگانه تکامل پیدا کرده و به صورت تکاملی با مساله تطبیق پیدا میکنند.
در ادامه مقاله در بخش دوم روش الگوریتم ممتیک بیان میشود. سپس در بخش بعد تشریح مساله 8 وزیر ارائه شده و در بخش چهارم نیز روش حل مسأله شرح داده میشود. در بخش پنجم روش پیشنهادي پیادهسازي شده است و نتایج بدست آمده با روش الگوریتم ژنتیک مقایسه گردیده است. در پایان نیز نتیجهگیري مقاله آورده شده است.
-2 روش الگوریتم ممتیک
در طی سالهاي گذشته، دانشمندان به هنگام حل مسائل پیچیده، در طبیعت به دنبال روشهاي طبیعی جستجو نموده که الگوریتمهاي تکامل یافته2، گروهی از مجموعه راهکارهاي بهینهسازي میباشند. در این روشها از تکنیک انتخاب برتر استفاده میشود که بر اساس روشهاي طبیعی استفاده شده و
پس از شبیهسازي در نرمافزار، کروموزومهاي برتر انتخاب میگردند.
الگوریتمهاي تکامل یافته به تنهایی در مسائل پیچیده و داراي چندین نقطه بهینه کارایی مناسبی نداشته لذا روشهاي برپایه تکنینکهاي جدید پیشنهاد و اجرا میشوند. در مسائلی که داراي چندین نقطه بهینه میباشند، میبایست از جستجوهاي محلی استفاده نمود که بهترین نقطه بهینه یافته شود. به این روش، یعنی ترکیب الگوریتمهاي تکامل یافته و جستجوگرهاي محلی، الگوریتم ممتیک3 گویند .[2]
الگوریتم ممتیک بر اثر یک مقایسه ژنی در زمینه تکامل فرهنگی توسط شخصی به نام Dawkins معرفی گردید و اصطلاح memetic از واژه meme برداشت شده است. مم یک عنصر فرهنگی یا رفتاري است که به وسیله عوامل غیر ژنتیکی از نسلی به نسل دیگر منتقل میشود. ساختار کلی آن بصورت زیر است:
شکل (1) ساختار کلی الگوریتم ممتیک
جستجوي محلی موجب میشود تابع هدف در اطراف نقطه بهینه نیز جستجو شود تا حتی الامکان مسأله در یک نقطه بهینه نسبی به پایان نرسد. بدین ترتیب جستجوي محلی و سراسري به خوبی در این الگوریتم ترکیب میشوند. جستجوي محلی امکان انتقال مم را میان افراد ممکن سازدمی و استراتژيِ ترکیب امکان انتقال مم را میان کل جمعیت ممکن میسازد. این روش قابلیت بالایی براي جستجوي سراسري دارد.
مراجع [3,4] برتري روشهاي مبتنی بر الگوریتم ممتیک بر الگوریتمهاي تکاملی را نشان میدهد. در مرجع [5] نیز مقایسهاي میان الگوریتم ممتیک (MA) و الگوریتم فرایند گروهی (TPA) انجام شده است و نشان داده شده که الگوریتم ممتیک اثر بخشتر است و جوابهاي بهتري را نسبت به الگوریتم فرایند گروهی مییابد. همچنین در مرجع [6] نیز برتري روش ممتیک بر الگوریتم ژنتیک بیان شده است.
-3 مساله هشت وزیر
مسأله هشت وزیر از جمله مسائل NP Hard4 میباشد که در سال 1841 توسط شطرنجبازي به نام Max Bezzal بیان شد. هدف از این مسأله مشخص کردن چیدمانی از 8 وزیر در یک صفحه شطرنج (صفحه 8 در (8 به گونهاي میباشد که هیچکدام از مهرهها یکدیگر را تهدید نکنند (هیچ دو مهرهاي در یک ردیف افقی، عمودي و یا مورب نباشند) و همچنین در چیدمان مهرهها رعایت محدودیتها الزامی است به طور کلی محدودیتها به دو دسته تقسیم می شوند: محدودیت هاي سخت که باید در پاسخ ارایه شده لزوما رعایت شوند و محدودیت هاي نرم که بهتر است در پاسخ رعایت شوند اما رعایت آنها الزامی نیست.
در مسأله 8 وزیر بررسی شده در این مقاله فقط محدودیت سخت یعنی عدم تهدید وزیران رعایت میگردد. در این مسأله مهمترین بخش، تابع شایستگی5 میباشد که در حالت ایده آل و بدون برخورد برابر صفر بوده و به ازاي هر برخورد یک پله یک واحدي افزایش مییابد. هدف این مسأله مینیممسازي تابع شایستگی (fitness) میباشد که با توجه به تعریف مسأله و چیدمان مهرهها رسیدن به بهترین نقطه بهینه بسیار پیچیده میباشد. روشهاي متعدد با تکنیکهاي خاص از جمله جستجوي تابو[7] 6، الگوریتم تکاملی چند مرحلهاي[8] و جستجوي محلی[9] و . . .
براي حل این مسأله بکار رفتهاند که البته بدلایلی از جمله وجود چندین نقطه بهینه در مسأله، به پاسخ مناسبی دست نیافته اند.
[10]
از آنجاییکه جستجوي محلی نقش بسیار موثري در کارآیی و سرعت اجراي الگوریتمهاي محلی دارد در این مقاله نیز سعی بر این است که جستجوي محلی جدیدي براي مسأله 8 وزیر ارائه شود که هم در افزایش سرعت اجراي الگوریتم و هم در دستیابی به نتایج بهتر براي مسأله تاثیر بسزایی دارد.
-4 الگوریتم ممتیک پیشنهادي
-1-4 جمعیت اولیه7 و نمایش کروموزوم
در الگوریتم ممتیک هر کروموزوم یک پاسخ منحصر به فرد براي مساله است. هر کروموزوم یک راه حل است که بصورت تصادفی پر شده است کروموزوم بصورت یک آرایه یک بعدي (یک سطر و هشت ستون) نمایش داده میشود که محتواي هر خانه معادل سطري است که وزیر در آن قرار دارد. در الگوریتم پیشنهادي
یک ژن معادل یک خانه از آرایه است نمونه کروموزوم در شکل (2) آمده است.
شکل (2) نمایش یک کروموزوم با توجه به چیدمان مهرهها
براي ایجاد جمعیت اولیه باید آرایه اي از کروموزوم پیشنهادي تعریف نمود. در الگوریتم پیشنهادي کروموزومها کاملا هوشمندانه تولید میشوند.
-2-4 تابع شایستگی
تابع شایستگی از مهمترین قسمتهاي یک الگوریتم تکاملی است که سهم عمدهاي از زمان اجراي الگوریتم را به خود اختصاص میدهد. این تابع شاخصی جهت تعیین تابع هدف است و وظیفه این تابع یافتن میزان تفاوت بین پاسخها براي یافتن بهترین حالت است.
شکل (3) محاسبه تابع شایستگی در یک حالت نمونه
محاسبه این تابع مبتنی بر رعایت محدودیت سخت است یعنی در محاسبه تابع شایستگی براي هر راه حل (کروموزوم) به ازاي هر برخوردي که وزیرها دارند تابع یک واحد افزایش مییابد.
-3-4 جستجوي محلی
یک الگوریتم جستجوي محلی همانند شکل (4) از یک حالت S0 (که میتواند از بعضی تکنیکهاي دیگر و یا بصورت تصادفی تولید شود) آغاز شده و وارد حلقه اي میشود که فضاي جستجو را که همان حوزه همسایگی N(s0) یک کروموزوم است، پیمایش مینماید. جستجو در هر بار، تکرار حلقه از یک حالت Si به یک حالت همسایه Si+1 آن است. [11,12]
جستجو در هر مرحله، توسط تابع شایستگی کیفیت هر حالت را تخمین میزند و کار را ادامه میدهد تا بهترین کروموزوم را در همسایگی کروموزوم ورودي بیابد. سه جستجوي محلی اصلی به نامهاي تپه نوردي8، شبیه سازي گداختگی9 و جستجوي تابو10 وجود دارند [11]
شکل (4) الگوریتم جستجوي محلی
شکل فوق نمونه اي از همسایگی نقاط واقع بر منحنی یک تابع در الگوریتمهاي ممتیک مختلف که درباره مسائل بهینه سازي متفاوت ارائه شده اند را نمایش میدهد که از این سه روش و یا در بعضی موارد از روشی حاصل از ترکیب آنها استفاده شده است. جستجوهاي محلی سنتی مذکور، براي اجرا نیازمند زمان بسیاري هستند زیرا باید تمام نقاط واقع در همسایگی کروموزوم را بررسی کرده و براي هر کدام یک بار تابع شایستگی را فراخوانی کنند تا بهترین نقطه را بیابند.
جستجوي محلی مورد استفاده در الگوریتم پیشنهادي در مقایسه با روشهاي پیشنهادي داراي کارآیی بهتري است. این روش نیازمند زمان بسیار کمتري است و میتواند منجر به دستیابی به
