متن آموزشی: چکیده

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

الگوريتم‌هاي بهينه‌سازي معرفي شده، به طور عمده الهام گرفته از فرايند‌هاي طبيعي مي‌باشند و در ارائه اين الگوريتم‌ها به ساير نمودهاي تکامل انساني توجهي نشده است. در اين نوشتار الگوريتم جديدي براي بهينه‌سازي مطرح مي‌‌شود که نه از يک پديده طبيعي، بلکه از يک پديده اجتماعي – انساني الهام گرفته است. بطور ويژه اين الگوريتم به فرايند استعمار، به عنوان مرحله‌اي از تکامل اجتماعي – سياسي بشر نگريسته و با مدل‌سازي رياضي اين پديده تاريخي، از آن به عنوان منشأ الهام يک الگوريتم قدرتمند در زمينه بهينه‌سازي بهره مي‌گيرد. در مدت کوتاهي که از معرفي اين الگوريتم مي‌گذرد، از آن براي حل مسائل بسياري در حوزه بهينه‌سازي استفاده شده است. طراحي چيدمان بهينه براي واحد‌هاي صنعتي، آنتن‌هاي مخابراتي هوشمند، سيستم‌هاي پيشنهاددهنده هوشمند و نيز طراحي کنترل کننده بهينه براي سيستم‌هاي صنعتي شيميايي تعدادي معدود از کاربردهاي گسترده اين الگوريتم در حل مسائل بهينه‌سازي مي‌باشد.

_______________________________________________
آنچه مطالعه کردید، بخشی از متن آموزشی جامعی در مورد الگوریتم رقابت استعماری بود که بر روی سایت “الگوریتم رقابت استعماری و بهینه سازی تکاملی” قرار گرفته است. این متن آموزشی که توضیحات مفصلی را در مورد لگوریتم رقابت استعماری در اختیار می کذارد، در حقیقت بخشهایی نسبتاً کامل از یک پایان نامه در مورد این الگوریتم می باشد. در ادامه فهرست کامل مطالب این متن آموزشی آمده است. برای مشاهده هر بخش می توانید روی عنوان آن بخش کلیک کنید.

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

چکیده

فصل 1 مقدمه
1-1 هدف و اهميت مسئله
1-2 الگوريتم توسعه داده شده
1-3 مزاياي الگوريتم توسعه داده شده
1-4 ساختار نوشتار

فصل 2 بهينه‌سازي و روشهاي موجود
2-1 انواع مسائل بهينه‌سازي
2-2 روش‌هاي بهينه‌سازي کمينه‌جو
2-2-1 بهينه‌سازي تحليلي
2-2-2 جستجوي خط
2-2-3 روش‌هاي نيوتوني
2-2-4 روش کاهشي نِلدِر ـ ‌ميد با اشکال غير مرکب
2-3 الگوريتم‌ ژنتيک
2-4 الگوريتم بازپخت شبيه‌سازي شده
2-5 بهينه‌سازي گروه ذرات
2-6 کلوني مورچه‌ها
2-7 برنامه‌ريزي ژنتيک

فصل 3 استراتژي بهينه‌سازي مبتني بر تکامل اجتماعي‌ـ‌سياسي
3-1 مقدمه
3-2 مروري تاريخي بر پديده استعمار

3-2-1 هند
3-2-2 مالزي
3-2-3 هندوچين فرانسه
3-2-4 هند شرقي (اندونزي)

3-3 الگوريتم پيشنهادي
3-3-1 شکل دهي امپراطوري‌هاي اوليه
3-3-2 مدل‌سازي سياست جذب: حرکت مستعمره‌ها به سمت امپرياليست
3-3-3 جابجايي موقعيت مستعمره و امپرياليست
3-3-4 قدرت کل يک امپراطوري
3-3-5 رقابت استعماري
3-3-6 سقوط امپراطوري‌هاي ضعيف
3-3-7 همگرايي

3-4 مثال کاربردي
3-5 نتيجه‌گيری
3-6 توابع هزينه مورد استفاده

فصل 4 پياده‌سازي هاي انجام شده
4-1 استفاده از الگوريتم معرفي شده براي طراحي يک کنترل‌کننده PID بهينه
4-1-1 کنترل‌کننده PID
4-1-2 طراحي کنترل‌کننده PID بهينه توسط الگوريتم رقابت استعماري
4-1-3 نتيجه‌گيري
4-2 استفاده از الگوريتم رقابت امپرياليستي براي طراحي کنترل‌کننده PID چند متغيره براي سيستم صنعتي ستون تقطير
4-2-1 مقدمه
4-2-2 کنترل‌کننده PID براي فرايند چند متغيره
4-2-3 نتايج شبيه‌سازي
4-2-4 نتيجه‌گيري

4-3 الگوريتم رقابت استعماري؛ ابزاري براي يافتن نقطه تعادل نش
4-3-1 يک بازي غير خطي استاتيک ساده
4-3-2 يک بازي با پيچيدگي بيشتر
4-4 طراحي بهينه آنتهاي آرايه‌اي

4-5 استفاده از الگوريتم رقابت استعماري براي شناسايي ويژگي مواد از آزمون فرورفتگي
4-5-1 مقدمه
4-5-2 توصيف مسئله معکوس
4-5-3 حل مسئله معکوس توسط الگوريتم رقابت استعماري
4-5-4 نتيجه‌گيری

4-6 کنترل فازي اتومبيل
4-6-1 مدل اتومبيل
4-6-2 نتايج

فصل 5 خلاصه، نتيجه‌گيري و پيشنهادات

فصل 6 مراجع

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

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

_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

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

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

رمز فایل ها، عبارت matlabsite.com است.
کدها و برنامه رایگان ارائه شده می توانند به عنوان یک پروژه کامل و مجزا در مورد الگوریتم رقابت استعماری (Imperialist Competitive Algorithm) که به اختصار ICA نامیده می شود، مورد استفاده آموزشی نیز قرار بگیرند.
توجه: به زودی فایل راهنمای استفاده از این برنامه ها، در متلب سایت ارائه خواهد شد. منتظر باشید. البته بر روی “وب سایت الگوریتم رقابت استعماری و بهینه سازی تکاملی” نسخه دیگری از کدها به همراه فایل راهنمای استفاده و نیز فیلم آموزشی نحوه پیاده سازی بر روی مسئله دلخواه موجود می باشد. این لینک را ببینید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.
 
کلمات کلیدی:
Imperialist Competitive Algorithm Codes in C##, Matlab, Free
کدهای الگوریتم رقابت استعماری در C، سی، شارپ، رایگان
_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

فایل راهنمای فارسی الگوریتم رقابت استعماری Imperialist Competitive Algorithm

 

این پست یک فایل آموزشی بسیار مفید راجع به Imperialist Competitive Algorithm یا الگوریتم رقابت استعماری در اختیار علاقه مندان قرار می دهد. این فایل آموزشی در حقیقت متن کامل یک پایان نامه در زمینه بهینه سازی و الگوریتم رقابت استعماری می باشد. در چکیده این فایل 100 صفحه ای می خوانید:

“الگوریتم های بهینه‌سازی الهام گرفته از طبیعت به عنوان روشهای هوشمند بهینه‌سازی در کنار روش‌های کلاسیک موفقیت خوبی از خود نشان داده‌اند. از جمله این روش‌ها می‌توان به الگوریتم‌های ژنتیک (الهام گرفته از تکامل بیولوژیکی انسان و سایر موجودات)، بهینه‌سازی کلونی مورچه‌ها (بر مبنای حرکت بهینه مورچه‌ها) و روش بازپخت شبیه‌سازی شده (با الهام‌گیری از فرایند تبرید فلزات) اشاره نمود. این روش‌ها در حل بسیاری از مسائل بهینه‌سازی در حوزه‌های مختلفی چون تعیین مسیر بهینه عامل‌های خودکار، طراحی بهینه کنترل کننده برای پروسه های صنعتی، حل مسائل عمده مهندسی صنایع همانند طراحی چیدمان بهینه برای واحدهای صنعتی، حل مسائل صف و نیز در طراحی عامل‌های هوشمند استفاده شده‌اند.

الگوریتم‌های بهینه‌سازی معرفی شده، به طور عمده الهام گرفته از فرایند‌های طبیعی می‌باشند و در ارائه این الگوریتم‌ها به سایر نمودهای تکامل انسانی توجهی نشده است. در این نوشتار الگوریتم جدیدی برای بهینه‌سازی مطرح می‌‌شود که نه از یک پدیده طبیعی، بلکه از یک پدیده اجتماعی – انسانی الهام گرفته است. بطور ویژه این الگوریتم به فرایند استعمار، به عنوان مرحله‌ای از تکامل اجتماعی – سیاسی بشر نگریسته و با مدل‌سازی ریاضی این پدیده تاریخی، از آن به عنوان منشأ الهام یک الگوریتم قدرتمند در زمینه بهینه‌سازی بهره می‌گیرد. در مدت کوتاهی که از معرفی این الگوریتم می‌گذرد، از آن برای حل مسائل بسیاری در حوزه بهینه‌سازی استفاده شده است. طراحی چیدمان بهینه برای واحد‌های صنعتی، آنتن‌های مخابراتی هوشمند، سیستم‌های پیشنهاددهنده هوشمند و نیز طراحی کنترل کننده بهینه برای سیستم‌های صنعتی شیمیایی تعدادی معدود از کاربردهای گسترده این الگوریتم در حل مسائل بهینه‌سازی می‌باشد.”

در ادمه لینک دانلود این کتاب قرار داده شده است:
اگر در هر مرحله ای، فایلها نیاز به پسورد داشتند، پسورد matlabsite.com را وارد کنید.
فایل راهنمای فارسی و انگلیسی در فرمت Word نیز در این لینک موجود می باشد.

 


صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

 

نحوه مواجهه با قید ها در بهینه سازی مقید

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

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

لینک های دانلود

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

پیاده سازی متنی فایل صوتی

متن فوق به صورت متنی در آمده است که در ادامه متن پیاده سازی شده را می بینیم. البته توصیه ما استفاده از فایال های صوتی است برای درک بهتر موضوع. در هر صورت، متن زیر نیز در عین اشکالات کوچک پیاده سازی شاید مفید باشد.

با سلام
در مورد مدیریت قیدها در الگوریتم های تکاملی از جمله الگوریتیم ژنتیک، الگوریتم پرندگان، زنبور عسل و الگوریتم رقابت استعماری و کلاً مسأله ای که مطرح است این است که روش هایی که موجود هستند و ما از آن ها استفاده می کنیم مستقل از نوع الگوریتم هستند. یعنی این، این طور نیستند که بگوییم روش هندل کردن قید در فلان جا. معمولاً روشی مدیریت قیود (Constraint Handling) که برای یک الگوریتم استفاده می شود برای یک الگوریتم دیگر هم قابل استفاده است. ما خود را محدود به هیچ الگوریتمی نمی کنیم و کلاً بازی کردن با قیدها مبحث جداگانه و تخصص جداگانه ای از کارکردن با خود فقط الگوریتم است.

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

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

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

حالا برویم سراغ های پیشگیری. روش های پیشگیری می گویند که اگر آن چیزی که اسمش را می گذاریم مجرم، در جامعه سعی کنیم نگذاریم متولد بشود. اگر مجرم متولد شد پانیش (تنبیه) کنیم. مثلاً یک قانون می تواند این باشد که هر کسی که پایش را فراتر از حدودی که تعیین شده گذاشت، اعدامش کنیم. این ساده ترین و کم پیچیده ترین قانونی است که می شود تصویب کرد. چه کار می کنیم؟ در الگوریتم ژنتیک می آییم پنالتی می گذاریم. مثلاً ما می دانیم که هزینه هایمان چه هستند.

به عبارت دیگر، خوب ما می خوایم مسأله مینیمم سازی حل کنیم یعنی هر چه کمتر باشد بهتر است ما می دانیم که هزینه هایمان بین منفی 10 تا 100 است یهو می آییم به آن جواب هایی که خیلی از قیود ما بیرون رفتند چه کار می کنیم؟ یهو یه پنالتی می دیم. مثلاً صد میلیون. یعنی چی؟ یعنی این می رود تو ته لیست جمعیت قرار می گیرد. خوب اعدام می شود یعنی می رود ته جمعیت ته لیست جمعیت و از جمعیت بیرون انداخته می شود. یعنی ما کافیه که در تابع هزینه مون که گفتیم به صورت جداگانه ما این رو نوشتیم یک تابع هزینه داریم f(x). داخل اون می نویسم f،x ؟؟ مثلاً اگر gx که هزینه ما هست کوچکتر از صفر شد همیشه می شود الگویش را می شود به این صورت نوشت. حالا بزرگ تر شد هر چی شد یعنی اگر عدول کرد، هزینه اش را بالا می گذاریم. مثلاً صد میلیارد. خوب این هم پس، آن یکی روش. روش اول که پیشگیری بود. روش درمان اولیه و سطحی که به ذهن می رسد همین است. این هم اگر جواب داد، ساده ترین کاری است که می شود انجام داد یعنی ما اگر بتوانیم با این روش کار را جلو ببریم می توانیم تا حدی خودمان را از پیچیدگی روشهای دیگر که در ادامه می گوییم رها کنیم. خوب ادامه را در بخش دوم ببینید.

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

خوب در مواردی که ناحیه در دسترس ما خیلی نسبت به فضای جستجوی اصلی که ما جستجو را باهاش شروع کردیم، کوچک هست، روش تنبیه مساوی و بزرگ برای کل جمعیت روش مناسبی نیست. خوب این را می توانیم خیلی ساده تست کنیم. می آییم چه کار می کنیم؟ می آییم پاپیولیشن (جمعیت) مثلاً هزارتایی را در نظر می گیرم. بعد این ها را به صورت تصادفی تولید می کنیم در آن فضای اولیه حدس. خوب این ها را پخش می کنیم بعد قیود را در نظر می گیریم اگر دیدیم مثلاً از این هزارتا فقط20 تا 50 تا فوقش 100 تا یعنی ده درصد قیود را رد کردند و بقیه در فضای اصلی هستند، همون تنبیه ساده کافیه. منتها یهو دیدیم از آن هزارتایی که ما تولید کردیم دو تا فقط هست یا حتی یک دانه و یا حتی اصلاً نیست در قیود ما صدق کند این روش دیگه جواب نمی دهد می پره این ور و آن ور.

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

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

روش سوم این است که ما بیاییم متناسب با عدول از قیود، پانیشمنت در نظر بگیریم. این به چه صورت است؟ می آییم می گویم مثلاً اگر قرار بود که x2 +x1 کوچکتر از 10 باشد و حالا، بزرگتر از 10 شده، نیائیم هر کروموزمی که x1+x2 برای آن؛ بزرگتر از 10 هست، پانیش کنیم. بیاییم چه کار کنیم؟ بیائیم میزان تنبیه رو برابر با میزان عدول در نظر بگیریم.

مثلاً به چه میزان از x1+x2 که باید 10 می شد بزرگتر است. اگه 11 هست یک واحد پانیش کنیم اگر 15 هست 5 واحد پانیش کنیم اگه 20 هست 10 واحد پانیش کنیم . این یعنی به اصطلاح متناسب با آن میزان عدول از قیود آن ها را پانیش کنیم. این یکی از روشهاست. پس میزان پانیش منت مساوی است با فاصله ای که از قیود می گیرند. مثلاً می توانیم، مثلاً اگر 5 تا قید داریم می گوییم مجموع فواصل از قیود را کمینه کنید.

یک روش هم این است که در کنار این که این ها را در نظر بگیریم تعداد عدول از قیود را هم در نظر می گیریم. معمولاً بعضی روش ها مثلاً اگه 7 یا 8 تا قید داریم می گوییم نه تنها میزان عدولشان بلکه تعداد عدولشان را هم در نظر بگیر. این چیزهایی که گفته می شود این جا، این جا روش استاندارد و کلاسیکی وجود ندارد گفته بشود بله ، این روش کار ماست. نه! این ها آن قدر باید باهاشون بازی بشود تا مناسب ترین روش اصلاح برای آن مسأله به دست بیاید. یعنی این طور نیست که ما قانونی را برای یک کشور تصویب کنیم و همان قانون برای کشور همسایه بتواند آن کشور را اصلاح کند. منتها خوب می شود قانون هایی را بهشون رسید که در میانگین، بهتر از قوانین دیگر جواب می دهند. منتها باید توجه کرد که این یک اکسیر یا کیور آل (cure-all) برای تمام مسائل نیست.

خوب پس چه کار می کنیم؟ یه پنالتی فاکتور در نظر می گیرم. پنالت فاکتور را همیشه می توان با میزان هزینه آن کروموزم جمع کرد یا همیشه درش ضرب کرد. مثلاً می گوییم که کاست (هزینه) هر کروموزم برابر است با کاست اصلیش یعنی میزان تابع هزینه آن به اضافه مثلاً صد برابر، ده برابر یا هر چیزی از عدول از هزینه.

فقط یک مسأله را در نظر داشته باشید که باید خیلی حرفه ای با این مسأله برخورد شود. بعضی وقت ها، مثلاً پنالتی ها به گونه ای هستند که اول کار، خوب جواب می دهند، وسط ها مثلاً یهو می بینی که مسأله، بهینه سازی می شود؛ منتها در نهایت جواب می دهد که باز خارج از قیود ما هست. ریشه کار به چی بر می گردد؟ ریشه کار به این برمی گردد که شما اگر با موبایل داخل ماشین نشسته و صحبت کنید، جریمه اش مثلاً 10 هزار تومان است. منتها خیلی از افراد یک معامله مثلاً یک میلیونی را با همان مکالمه 5 دقیقه ای که اگه بگیرنش 10 هزار تومان جریمه اش باشد؛ انجام می دهند. یعنی پاپیولیشن ها (اعضای جمعیت) ما هم بعضی وقت ها می روند، قیدها را زیر پا می گذارند. منتها از این طرف، توی تابع هزینه یه جاهایی را پیدا می کنند که هزینه آن قدر کم می شود که شما اگر هزینه تمام قیود را جمع کنید و در نهایت باز جبران آن عدول از قیود نمی شود. یعنی در حقیقت می شود گفت پانیش منت (تنبیه) ما خیلی شُل هست. یعنی جامعه را خیلی شُل گرفتیم. این به این معنی نیست که بیاییم پانیش منت را بگیریم هر چی شد تابع به اضافه صد برابر عدول از قیود. نه! پانیش منت را باید در طی مسأله باید کم کنیم، زیاد کنیم، این ها چیزهایی که باید باهاشون مدتی بازی بشود که دستتون کاملاً بیاد.

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

حالا باز همانگونه که عرض کردم خدمتتون، هیچ تفاوتی بین الگوریتم ژنتیک و دیگر الگوریتم ها نیست. مثلاً خیلی وقت ها من ایمیل دریافت می کنم که من الگوریتم رقابت استعماری را که الگوریتم جدید و کارایی در حوزه بهینه سازی هست را دارم استفاده می کنم. در مورد این الگوریتم، قیود را چه کار کنیم؟ جوابشون را من معمولاً این طور می دهم که همان کاری را که با ژنتیک می کنیم با همین هم بکنید. منتها اگر ژنتیک را بلد نیستید این یک بحث مجزاست. یعنی همان قیود را که در مورد ژنتیک کار می کنید، همان کار تکرار می شود برای الگوریتم پرندگان، الگوریتم مورچگان، برای الگوریتم رقابت استعماری. همشون تکراری، همین موارد هستند. امیدوارم این توضیحات تا حدی توانسته باشد بعضی از سؤالات را جواب بدهد، بقیه اش هم که دیگه تجربه شخصی است. باید با برنامه نویسی و … این ها به دست بیاید. موفق باشید و خدا نگهدار.

در ضمن نگاهی به مقالات منتشر شده در مورد الگوریتم رقابت استعماری در بخش مقالات و پایان نامه ها در سایت داشته باشید. مقالات خوبی در زمینه مدیریت قیود را خواهید دید.

_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

کدهای الگوریتم رقابت استعماری و فیلم آموزش استفاده از آنها

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

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

 

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

مشاهده فیلم در یوتیوب
فیلم مذکور را در صورت دسترسی به یوتیوب می توانید در این لینک ببینید.

 

توضیحات مربوط به توابع موجود در کنار کدهای آماده:

شبه کد الگوریتم رقابت استعماری همانگونه که در فایل راهنمای فارسی آن بطور مفصل توضیح داده شده است، به صورت زیر است.
  1. چند نقطه تصادفي روي تابع انتخاب کرده و امپراطوري‌هاي اوليه را تشکيل بده.
  2. مستعمرات را به سمت کشور امپرياليست حرکت بده (سياست همسان‌سازي یا جذب).
  3. عملگر انقلاب (Revolution) را اعمال کن.
  4. اگر مستعمره‌اي در يک امپراطوري‌، وجود داشته باشد که هزينه‌اي کمتر از امپرياليست داشته باشد؛ جاي مستعمره و امپرياليست را با هم عوض کن.
  5. هزينه‌ي کل يک امپراطوري را حساب کن (با در نظر گرفتن هزينه‌ي امپرياليست و مستعمراتشان).
  6. يک (یا چند) ستعمره از ضعيف‌ترين امپراطوري انتخاب کرده و آن را به امپراطوري‌اي که بيشترين احتمال تصاحب را دارد، بده.
  7. امپراطوري‌هاي ضعيف را حذف کن.
  8. اگر تنها يک امپراطوري باقي‌ مانده باشد، توقف کن وگرنه به 2 برو.
نکته مهم: شبه کد فوق مربوط به نسخه اولیه معرفی شده از الگوریتم است. نسخه های جدید تر الگوریتم در بندهایی از این شبه کد ممکن است با آنچه در بالا آمد، متفاوت باشند.

 

در فایل زیپ شده کدها چندین تابع وجود دارند که به ترتیب الفبا در زیر مرتب شده اند. در ادامه در کنار هر تابع ارتباط آن با بخشی از الگوریتم رقابت استعماری نوشته شده است.

AssimilateColonies
این تابع بخش آسیمیلاسیون (Assimilation) یا به عبارت دیگر سیاست جذب را پیاده سازی می کند.

BenchmarkFunction

در این برنامه تعداد زیادی از توابع مطرح استاندارد بهینه سازی قرار داده شده اند. از این توابع می توان جهت تست روشهای مختلف بهینه سازی استفاده نمود. در کنار این توابع، یک مثال عملی از حل یک مسئله کنترل برای طراحی کنترل کننده PID نیز وجود دارد. به احتمال زیاد این بخش مربوط به کار انجام شده در مقاله به عنوان زیر است که در بخش مقالات انگلیسی فایل کامل آن قابل دانلود است.
Esmaeil Atashpaz Gargari & Caro Lucas, “Designing an optimal PID controller using Colonial Competitive Algorithm”, First Iranian Joint Congress on Intelligent and Fuzzy Systems, September 2007, Mashhad, Iran.

CreateInitialEmpires

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

DisplayEmpires

اگر توجه کرده باشید، در فایل راهنمای فارسی الگوریتم رقابت استعماری و نیز در بسیاری از مقالات فارسی و انگلیسی شکلهایی برای نشان دادن محل امپراطوری ها وجود دارند. در این شکلها معمولاً هر رنگ نشان دهنده یک امپراطوری است. در هر امپراطوری نیز کشور مرکزی (امپریالیست) با علامت ستاره و مستعمرات با علامت دایره نشان داده می شوند. تابع DisplayEmpires مسئول انجام چنین ترسیماتی است. لازم به ذکر است که این نوع ترسیمات برای برای بهینه سازی های با بعد کمتر یا مساوی 3 معنا دارد. برای ابعاد با تعداد بیشتر این ترسیم را متوقف می کنیم.

GenerateNewCountry

این تابع که بیش از چند خط نیست، یک کشور را با موقعیت تصادفی خلق می کند. کشور با موقعیت تصادفی در بازه ای که قبلاً به عنوان قیود بهینه سازی در برنامه اصلی Main_ImperialistCompetitveAlgorithm داده شده است، ایجاد می شود.

ImperialisticCompetition

انجام رقابت استعماری میان امپراطوری ها جهت جذب مستعمرات همدیگر، توسط این تابع انجام می پذیرد. حذف امپراطوری های ضعیف (از بین رفته) نیز در این تابع گنجانده شده است.

Main_ImperialistCompetitveAlgorithm

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

در این بخش از برنامه تنظیمات مرتبط با مسئله، همانند نام تابع هزینه، تعداد متغیرها (بعد مسئله بهینه سازی)، تعداد کشور های اولیه، تعداد دهه ها و … صورت می پذیرد. توجه شود که برنامه تابع هزینه با آوردن نام آن، شناخته می شود. در حالت پیشفرض، توابع استاندارد موجود همراه فایل ها برای تست اجرای برنامه تنظیم شده اند. پارامتر Costfunction.ExtraPrams شماره تابع استاندارد موجود را تعیین می کند. توجه شود که این پارامتر برای کاربردهای آتی پیش بینی شده است و در حالت استفاده عادی برای اتصال به توابع هزینه نوشته شده توسط شما، باید خالی (تهی []) باشد. راهنمای موجود در مقابل این عبارت که به صورت کامنت نوشته شده است نیز، به خوبی به این موضوع اشاره دارد.

PossesEmpire

تعویض جای مستعمره و استعمارگر در این تابع انجام می پذیرد. اگر مستعمره ای به جای بهتری نسبت به استعمارگر رسید، فوراً کنترل امپراطوری را در دست گرفته و کار را با اعمال سیاست جذب بر روی آنها ادامه می دهد.

RevolveColonies

انقلاب که وزنه اصلی توازن Exploration و Exploitation و به نفع Exploration است، در این تابع انجام می شود. تغییراتی ناگهانی در برخی کشور ها اتفاق افتاده و در برخی موارد به کشف نقاط ناپیدای مینیمم در تابع منجر می شود. لازم به ذکر است که این بخش مهم از الگوریتم رقابت استعماری که از اولین نسخه های این الگوریتم با آن بوده است، متاسفانه در هیچ یک از مستندات آن از جمله در فایل راهنمای فارسی و مقالات اولیه مرتبط با الگوریتم مورد بررسی قرار نگرفته است. در نهایت برای اولین بار توضیحات مرتبط با این بخش مهم از الگوریتم در مقاله با عنوان زیر که در بخش مقالات انگلیسی فایل کامل آن قابل دانلود است، ارائه شده است.
“Solving the Integrated Product Mix-Outsourcing Problem by a Novel Meta-Heuristic Algorithm: Imperialist Competitive Algorithm”, Expert Systems with Application, Elsevier

UniteSimilarEmpires

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

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

Myrandint

این تابع یک یا تعدادی عدد رندم صحیح در بازه دلخواه داده شده به آن ایجاد می کند. در حقیقت متلب تابعی با نام randint دارد که مربوطه به یکی از تولباکس های آن (به احتمال زیاد Communications Toolbox) می باشد. چون ممکن است این تولباکس بر روی خیلی از کامپیوتر ها نباشد (به ویژه خارج از ایران که هزینه تهیه و نصب برنامه متلب بسیار بالا است!!!)، این تابع به عنوان جایگزینی برای آن نوشته شده است.

چگونه ترسیم شکل ها را کنترل کنیم؟

دو نوع ترسیم در کدهای موجود پیش بینی شده اند. ترسیم اول، رسم نمودار موقعیت امپراطوری ها است. این ترسیم تنها برای مسائل با بعد دو یا سه معنی دار می باشد. زیر در این حالت امکان نمایش امپراطوری ها (کشور مرکزی به همراه مستعمرات هر یک) وجود دارد. برای فعال کردن و یا غیر فعال کردن این ترسیم، خط کد زیر را در میان کدها بیابید.
DisplayParams.PlotEmpires = true;    % “true” to plot. “false” to cancel ploting.
 
اگر به جای true در خط کد فوق، عبارت false بنویسید، ترسیم موقعیت امپراطوری ها غیر فعال خواهد شد. true بودن ترسیم امپراطوری ها را فعال می کند.
 
نوع دوم شکل و ترسیم در این کدها، ترسیم نمودارهای همگرایی تابع هزینه است. از جهت نوع کنترل، ترسیم نمودار های همگرایی هزینه نیز داستان مشابهی دارند، با این تفاوت که این نمودار، هیچ محدودیتی در ابعاد ندارد و برای تمام مسائل قابل ترسیم است و حتی رسم آن توصیه نیز می شود. ترسیم این نمودار را نیز به همان ترتیب بالا با ایجاد تغییر در خط کد زیر در میان کدها می توانید کنترل نمایید.
DisplayParams.PlotCost = true;    % “true” to plot. “false”
 
توجه: در متلب، به جای true و false عددهای 1 و 0 را می توانید به ترتیب استفاده نمایید.

________________________________
در ضمن نسخه های دیگری از الگوریتم رقابت استعماری به ویژه در زبانهای برنامه نویسی دیگر در حال تهیه بوده و به زودی منتشر می شوند. همچنین کدهای مربوط به روشهای دیگر بهینه سازی همانند الگوریتم های ژنتیک (Genetic Algorithms)، الگوریتم پرندگان (Particle Swarm Optimization) و بهینه سازی کلونی موچگان (Ant Colony Optimization) نیز به مرور زمان بر روی سایت قرار خواهند گرفت. البته متلبسایت مرجع کاربران و برنامه نویسان متلب و هوش مصنوعی ایران تا به حال مطالب بسیاری را در این موضوعات منتشر کرده است.

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

تولباکس گرافیکی

در بخش از متن پایان نامه منشتر شده بر روی وبسایت به یک تولباکس گرافیکی اشاره شده است که کدهای متلب آن را می توانید در لینک زیر دانلود نمایید.

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

نکته جهت اجرا: پس از دانلود فایل زیپ شده، برنامه  FirstPage.m را باز کرده و آنرا (مثلاً با فشار دکمه F5) اجرا نمایید.

_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.

 

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.

انتخاب ورودی و ویژگی توسط الگوریتم رقابت استعماری

سوال مطرح شده: سوال دریافتی از طریق بخش تماس با ما در سایت: “آیا با استفاده از الگوریتم رقابت استعماری می شود دیسکریپتور (Descriptor) انتخاب کرد؟ (دسکریپتر‌های برنامه SPSS). من قبلاً به روش استپوایز (Stepwize) اینکار رو در برنامه SPSS انجام میدادم. حالا می‌خواهم بدونم که آیا با الگوریتم ICA هم می‌شه این کارو کرد؟”

جواب: بله می شود.

در حقیقت انتخاب دیسکریپتور و به طور کلی انتخاب ورودی های موثر در خروجی یک سیستم (یا همان انتخاب ویژگی ها در مسائل طبقه بندی {1}) یک مسئله بهینه سازی گسسته می باشد که بسته به تعداد کاندیداهای موجود برای انتخاب و نیز تعداد انتخاب های مورد نیاز می تواند مسئله بسیار پیچیده ای باشد. البته پیچیدگی ارتباط میان ورودی و خروجی سیستم نیز در پیچیدگی این مسئله تاثیر دارد. در حالتی که ما می خواهیم تعداد کمی از ورودی ها یا همان دیسکریپتورها را انتخاب کنیم، این مسئله می تواند با یک جستجوی جامع انجام شود. فرض کنیم که 70 مورد دیسکریپتور داریم و می خواهیم از میان آنها n موردی را که بیشترین اثر را در روی خروجی سیتم دارند انتخاب کنیم. همیشه معیاری برای این انتخاب وجود دارد. مثلاً در مسائل طبقه بندی (Classification) در حوزه بازشناسی الگو (Pattern Recognition) ، خطای طبقه بندی معیار انتخاب ما می باشد. در مسائل رگرسیون و تقریب تابع، این معیار می تواند میانگین مربعات خطای میان خروجی واقعی و خروجی حاصل از رابطه باشد. در هر صورت ما این معیار را داریم و می خواهیم بدانیم که با در نظر گرفتن این معیار چه دسته ای ورودی های خوب هستند!!؟

حال فرض کنید، ما بخواهیم یک دسته 3 تایی از آن 70 تا انتخاب ممکن را داشته باشیم. تعداد انتخاب های ممکن تعداد انتخاب 3 از 70 است. یعنی:

70! / (3! * 67!) = 70*69*68 / 6 = 54,740
اگر فرض کنیم که هر 100 بار ارزیابی تابع معیار انتخاب ما یک ثانیه برای کامپیوتر طول بکشد، تقریباً 9 دقیقه طول می کشد که جواب مسئله (بهترین دسته سه تایی از ورودی ها) را پیدا کنیم. این امر امکان پذیر است.حال فرض کنید، ما بخواهیم یک دسته 8 تایی از آن 70 تا انتخاب ممکن را داشته باشیم. تعداد انتخاب های ممکن تعداد انتخاب 8 از 70 است. یعنی:
70! / (8! * 62!) = 9.4404e+009

یعنی تقریباً 9 میلیارد انتخاب ممکن وجود دارد. باز اگر فرض کنیم که هر 100 بار ارزیابی تابع معیار انتخاب ما یک ثانیه برای کامپیوتر طول بکشد، تقریباً یک هزار و نود و دو (1092) روز یعنی تقریباً 3 سال طول می کشد که جواب مسئله (بهترین دسته 8 تایی از ورودی ها) را پیدا کنیم. 3 سال برای این انتخاب زمان کمی به نظر نمی رسد. به سادگی می تواد حدس زد که انتخاب 9، 10 و حتی 20 ویژگی چقدر طول می کشد.

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

شکل زیر انتخاب 8 ویژگی با الگوریتم رقابت استعماری را نشان می دهد. روش انتخاب مستقیم، به میزان خطای 0.0167 در زمان حدود 10 دقیقه رسیده است. در مقابل الگوریتم رقابت استعماری در حدود 30 دقیقه (نه سه سال!!) توانسته دسته از ورودی ها را پیدا کند که به خطای صفر می رسند!

 

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

… میخواستم بدونم که چگونه از الگوریتم استعماری میتونم در زمینه انتخاب اسلاید های مناسب زمانی (در مسئله پیش بینی سری های زمانی) یا همان روزهای قبل که در قسمت پیش بینی مثلا مصرف برق یا هر سری زمانی (بحث انتخاب ویژگی) استفاده کنم …

پاسخ:

با سلام.

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

لینک زیر کمی توضیح در این مورد می دهد.

http://www.icasite.info/2010/05/blog-post.html

نسخه های گسسته و باینری این الگوریتم را نیز می توانید به راحتی پیدا و یا ایجاد (با تغییر در کدهای اولیه) نمایید.

فیلم زیر نیز شاید مفید باشد.

http://www.icasite.info/2010/11/feature-selection.html

لینک زیر طبقه بندی مسائل بهینه سازی را ارائه می کند (تا حدی پاسخ سوال دوم شما).

http://www.icasite.info/2010/05/blog-post_31.html

پاسخ زیر را نیز به یک سوال مطرح شده دیگر ببینید.
پرسش:

آیا می توان از آی سی ای برای انتخاب ویژگی استفاده نمود؟ قدم های لازم چه هستند؟

پاسخ:

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

—————————————————————————————————————————————-
{1} برای انتخاب ورودی و ویژگی و دیسکریپتور عناوین مشابه زیر نیز در حوزه های مختلف به کار میرود:

Feature Selection
Input Selection
Descriptor Selection

_____________________________________________
نظرات شما در انتهای این پست برای سایر خوانندگان، بسیار مفید خواهد بود. می توانید نظر خود را با اکانت سرویس های مختلف و یا به عنوان ناشناس در این پست درج نمائید.
صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.