روش کلی ایجاد نسخه های گسسته الگوریتم رقابت استعماری - Artificial Intelligence

**Astaraki** · ۱۰-۲۱-۱۳۸۹, ۰۸:۱۸ قبل از ظهر

روش کلی ایجاد نسخه های گسسته الگوریتم رقابت استعماری

با اینکه الگوریتم رقابت استعماری، در نسخه های اولیه آن برای حل مسائل بهینه سازی پیوسته معرفی شد، اما از همان ابتدای معرفی در کار های پژوهشی متنوعی در حل مسائل گسسته نیز به کار رفته است. در این پست می خواهیم نحوه ایجاد تغییرات در کدهای پیوسته الگوریتم رقابت استعماری را جهت تبدیل آن به روش حل مسائل گسسته بررسی کنیم.

در الگوریتم رقابت استعماری دو دسته از پارامترها را می توان تقسیم بندی نمود.
عملگر های ساختاری و مستقل از مسئله: عملگرهایی هستند که به نوع کد کردن مسئله وابسته نیستند و ساختار تقریباً معین و ثابتی دارند. مثلاً بخش رقابت استعماری، کل تصمیم گیری را از روی هزینه کشورها و امپراطوری ها انجام می دهد و نوع کد شدن و شیوه نمایش کشورها را در فرایند خود دخالت نمی دهد.

عملگرهای وابسته به مسئله: این عملگر ها، باید وابسته به مسئله طراحی شوند. مثلاً عملگر جذب (Assimilation) را در نظر بگیرید. جذب در مسائل پیوسته به این صورت است که کشور مستعمره در راستای برداری ازخود به سمت استعمارگر با روند خاصی (+)، حرکت می کند. این حرکت باعث نزدیکی اقلیدسی مستعمره به استعمارگر می شود. اما در یک مسئله گسسته نزدیکی اقلیدسی، لزوماً معنی نزدیکی و نزدیک شدن را نمی دهد و حتی بعضی وقتها، نزدیکی اقلیدسی فاقد هرگونه معنی خاصی می باشد. مثلاً نزدیک شدن شهر شماره 12 به شهر شماره 17 و مثلا رسیدن به شهر شماره 14.75 معنی ندارد.

در استفاده از الگوریتم رقابت استعماری در حل مسائل گسسته، تنها بخش هایی که باید تغییر داده شوند، عملگرها و بخش های وابسته به مسئله هستند. این بخش ها عبارتند از:
ایجاد جمعیت اولیه (Initial Countries)
عملگر جذب (Assimilation)
عملگر انقلاب (Revolution)

ایجاد جمعیت اولیه (Initial Countries)
تابع ایجاد جمعیت اولیه باید کمی دست کاری شود. این تابع را در این لینک (+) ببینید. نوع دستکاری این تابع بستگی به نوع مسئله گسسته دارد. می توان چند دسته از مسائل گسسته را طبقه بندی کرد. سه دسته مهم و شاید تنها دسته ها، عبارتند از:
مسائل گسسته با ماهیت پیوسته: مسائلی که ذاتاً پیوسته اند، اما به دلیل کوانتیزیشن (Quantization) تبدیل به گسسته شده اند. مثلاً انتخاب درصدی از سهام را در نظر بگیرید که عددی بین 0 تا 100 درصد را دارد و در مسئله معینی درصدهای میانی معنی ندارد. بنابراین 101 درصد قابل انتخاب وجود دارد. بنابراین مسئله از این لحاظ گسسته است و متغیر ما بصورت پیوسته تغییر نمی کند. اما این پارامتر ذاتاً پیوسته است. به این معنی که مثلاً به راحتی قابل درک است که 35 درصد به 40 درصد نزدیک است، اما 5 درصد با 40 درصد فاصله نسبتاً زیادی دارد. یعنی نزدیکی متغیرهای گسسته به هم (از نوع اقلیدسی)، واقعاً معنی دار است و "نزدیک"، "دور" و "خیلی نزدیک" و "خیلی دور"، در این مورد عبارات کاملاً معنی داری هستند.
مسائل گسسته جایگشتی: مسئله فروشنده دوره گرد، مثال واضح این دسته است. در این حالت به جوابهای مسئله اعدادی اختصاص داده می شوند که فقط یک کد برای شناختن آنها هستند و نزدیکی آن کدها به هم هیچ نشانی از نزدیکی واقعی و اقلیدسی ندارد. سپس ترتیبی از این کدها جواب مسئله را تشکیل می دهند.
مسائل گسسته باینری: این مسائل هم مسائلی از نوع صفر و یکی هستند و در برخی موارد نوع نمایش باینری از یک مسئله پیوسته هستند. در برخی موارد هم ترتیب بودن و نبودن دسته ای فعالیت ها هستند.
شناخت هر کدام از این انواع، کمک شایانی به حل مسئله می کند. در حقیقت بدون شناخت مناسب مسئله، امکان حل درست آن وجود ندارد. مسائل گسسته با ماهیت پیوسته، مشابه مسائل پیوسته حل می شوند. مثالی از حل این مسئله مقاله زیر می باشد (قابل دسترسی در بخش مقالات سایت).

كد:

S. Nazari-Shirkouhi, H. Eivazy, R. Ghodsi, K. Rezaie, E. Atashpaz-Gargari, "Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm", Expert Systems with Applications, Volume 37, Issue 12, December 2010, Pages 7615-7626.

در این نوع مسائل، در غالب اوقات کافی است که متغیر بهینه سازی را تنها در مرحله ارسال به تابع هزینه، کوانتیزه کنیم. بنابراین کدها را دستکاری نمی کنیم و فرض می کنیم با یک مسئله پیوسته سرو کار داریم و تمام عملیات، برای مسئله پیوسته انجام می شوند. تنها کاری که می کنیم این است که یک تابع واسط میان تابع هزینه اصلی و برنامه الگوریتم رقابت استعماری قرار می دهیم. این تابع متغیر پیوسته را در هنگام ارزیابی میزان هزینه، پیوسته کرده و به تابع هزینه مسئله بهینه سازی ارسال کرده و میزان هزینه آن را دریافت می کند. سپس این مقدار هزینه را به الگوریتم، جهت ادامه عملیات برمی گرداند. الگوریتم بدون اینکه متوجه شود که مشغول حل یک مسئله گسسته است، کار خود را ادامه داده و به پایان می رسد. در نهایت مقادیر بهینه ای را که الگوریتم داده است و پیوسته هستند، با همان تابع کوانتیزه کننده، گسسته می کنیم و به عنوان جواب اصلی مسئله گسسته بر می گردانیم.

بنابراین در مسائل گسسته با ماهیت پیوسته، نیاز به تغییر چندانی در الگوریتم نیست. در مورد مسائل دو دسته دیگر ، ما باید چندین تابع را دستکاری کنیم. در این حالت، تابع تولید کننده جمعیت اولیه، باید به گونه ای دستکاری شود که کشور های اولیه ایجاد شده، مطابق کدینگ مطلوب ما از مسئله گسسته باشند. مثلاً اگر هدف حل مسئله TSP، باشد، این تابع باید، دنباله ای از شماره شهر ها را ایجاد کند. یا در یک مسئله باینری باید، دنباله ای از صفر و یک ها ایجاد شوند. در ادامه، تغییرات لازم در عملگر جذب را برای دو دسته دیگر بررسی می کنیم. همانگونه که بیان شد، برای دسته مسائل گسسته با ماهیت پیوسته، نیاز به هیچ گونه تغییری نمی باشد در عملگرها نمی باشد.

عملگر جذب (Assimilation)
پس از تعریف مناسب کشورها، با تعریف کدینگ مناسب برای آنها، باید عملگر جذب را تعریف کنیم. مثال مسئله فروشنده دوره گرد (Traveling Salesman Problem - TSP) را با 5 شهر در نظر بگیریم. فرض کنیم دو کشور زیر را داریم که هر کشور دنباله ای از مسیر طی شده توسط فروشنده است که باید از تمام شهر ها عبور کند و کمترین فاصله را نیز طی نماید.

كد:

country1 = [1 2 3 4 5];
country2 = [3 4 5 1 2];

این دو کشور با در نظر گرفتن فاصله اقلیدسی، از هم فاصله دارند. در حالی که از دید مسئله TSP، این دو مسیر دقیقاً یکی هستند! فقط، نقطه شروع آنها با هم متفاوت است. بنابراین می بینیم که اطلاعات کشور ها نه در خود شماره شهرها، بلکه در ترتیب قرار گرفتن آنها، نهفته است و دو کشور زمانی به هم نزدیک هستند، که دنباله های یکسانی از ترتیب شهرها داشته باشند. بنابراین نوع نزدیکی ای که تعریف می شود باید این را لحاظ کند. مثلاً یک راه برای نزدیک کردن کشور مستعمره به امپریالیست (جذب)، می تواند این باشد، که ترتیب های تصادفی ای از کشور استعمارگر (مثلاً رنگ قرمر در پایین) را برداشته و در دنباله کشور مستعمره قرار دهیم. مثلاً

كد:

colony = [1 2 3 4 5 6 7];
imperialist = [3 1 2 5 4 7 6];

مثلاً دنباله های رفتن از 3 به 1 و نیز رفتن از 5 به 4 را از imperialist، برداشته و در colony قرار می دهیم و colony جدید بصورت زیر تشکیل می شود.

كد:

new_colony = [3 1 5 4 2 7 6];

کشور جدید، ترکیبی از موقعیت مستعمره قبلی است که در راستای نزدیکی (نه لزوماً نزدیکی اقلیدسی) به سمت کشور استعمارگر حرکت کرده است. بخش قرمز از امپریالیست، گرفته شده است و بخش آبی بخش هایی است که به ترتیب از کلونی آمده اند که در بخش گرفته شده از امپریالیست نبوده اند.

روش بیان شده، لزماً بهترین روش برای حل مسئله فروشنده دوره گرد توسط الگوریتم رقابت استعماری نیست، اما به عنوان یک روش عمومی می تواند در مسائل گسسته جایگشتی، همچون مسائل فروشنده دوره گرد، برنامه ریزی تولید، Job Scheduling و Job-Shop Scheduling استفاده شود.

خلاصه بحث این است که با در نظر گرفتن ماهیت مسئله و شیوه مورد استفاده برای کدینگ آن ،باید روش مناسبی برای نزدیک کردن مستعمره در نظر گرفته شود. این روش باید به گونه ای روی مستعمره عمل کند که مستعمره جدید، حالتی میانی، بین مستعمره قبلی و استعمارگر داشته باشد. از دیدگاه اطلاعاتی، موقعیت جدید باید هم اطلاعات قبلی خود را داشته باشد، هم بخشی از اطلاعات استعمارگر را.

در مورد مسئله باینری هم، مشابه همین کار را باید انجام داد. شاید ساده ترین کار در این بخش، استفاده از عملگر تقاطع (Crossover) از الگوریتم ژنتیک در بخش جذب است. بدین ترتیب در یک الگوریتم مرکب "استعماری - ژنتیک"، ساختار کل مسئله و سایر عملگرهای الگوریتم رقابت استعماری حفظ می شود. ولی در بخش جذب، عملگر تقاطع از الگوریتم ژنتیک استفاده می شود. این مورد در برخی از مقالات، با موفقیت مورد استفاده قرار گرفته است. البته کارهای بسیار متنوعی را در این بخش می توان انجام داده و به نسخه های متفاوتی از الگوریتم رسید (همانگونه که در برخی مقالات انجام شده است). هدف این پست، لیست کردن همه این تغییرات نیست. هدف بیان حالت کلی ایجاد این روند بوده است که به نظر می رسد با توضیحات کافی، به سادگی قابل پیاده سازی شده است.

عملگر انقلاب (Revolution)
عملگر انقلاب، نیاز به توضیحات زیادی ندارد. اگر بخش "ایجاد جمعیت اولیه"، به خوبی پیاده سازی شده باشد، معمولاً در کدهای آماده موجود بر روی همین سایت، این عملگر، بعضی از کشورهای تصادفی را انتخاب می کند و آنها را به صورت تصادفی با موقعیت جدید، جایگزین می نماید. جهت ایجاد موقعیت جدید، از همان تابع ایجاد کننده جمعیت اولیه استفاده می شود. بنابراین اگر مقصود استفاده از همان عملگر انقلاب موجود در نسخه استاندارد الگوریتم باشد، عموماً نیازی به انجام تغییرات عمده در تابع مربوطه نیست.

در هر صورت می توان بسته به مسئله تغییرات تصادفی جدیدی را در کشورها تعریف کرده و عملگرهای انقلاب متفاوتی را ایجاد نمود. نکته اصلی این است که در نتیجه انقلاب، کشور جدید حاصل از این عملگر، باید تا حد زیادی و به صورت تصادفی و خارج از قاعده (نه لزوماً به معنی کاملاً خارج از قائده)، با کشور اولیه متفاوت باشد.

پیشنهاد پایانی
نسخه های گسسته الگوریتم رقابت استعماری (Discrete Imperialist Competitive Algorithm)، در مقالات و کارهای پژوهشی بسیار زیادی مورد استفاده عملی قرار گرفته اند. با مراجعه به بخش مقالات منتشر شده الگوریتم رقابت استعماری (+)، آنها را مطالعه کرده و با نویسندگان آنها جهت کسب اطلاعات بیشتر در مورد روش مورد استفاده شان، مکاتبه نمایید.

نکته: در لحظه نگارش این پست، هیچ کد و برنامه آماده و مستقلی برای نسخه گسسته الگوریتم بر روی این سایت قرار نگرفته است. ممکن است، زمانی که شما این پست را مطالعه می کنید، کدهایی با توضیحات بیشتر بر روی همین سایت منتشر شده باشند. از طریق بخش جستجو، مطالب مرتبط را جستجو کرده و کلیه مطالب مربوط به الگوریتم رقابت استعماری را نیز در این لینک (+) مشاهده نمایید.

منبع : روش کلی ایجاد نسخه های گسسته الگوریتم رقابت استعماری