استراتژی حل مسائل بهینه سازی با استفاده از الگوریتم رقابت استعماری

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

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

“این پست اختصاصی وبسایت محاسبات تکاملی و الگوریتم رقابت استعماری تهیه شده است و درج آن در رسانه های چاپی و یا مجازی فقط با کسب اجازه از وبسایت مذکور، مجاز می باشد.”
1) بهینه سازی چیست؟
بهينه‌سازي، تغيير دادن ورودي‌ها و خصوصيات يک دستگاه، فرايند رياضي و يا آزمايش تجربي است، به نحوي که بهترين خروجي يا نتيجه به دست بيايد (شکل زیر). ورودي‌ها، متغيرهاي فرايند يا تابع مورد بررسي هستند که با نام‌هاي تابع هدف (Objective Function)، تابع هزينه (Cost Function) و يا تابع برازندگي (Fitness Function) ناميده مي‌شود. خروجي‌ نيز به صورت هزينه، سود و يا برازندگي تعريف مي‌شود. غالب مسائل بهينه‌سازي به صورت کمينه‌سازي مقدار يک تابع هزينه در نظر گرفته شده‌اند. به راحتي مي‌توان نشان داد که هر نوع مسأله‌ي بهينه‌سازي را مي‌توان در قالب يک مسأله‌ي کمينه‌سازي تعريف نمود.

شكل: فرايند يا تابعي که بهينه‌سازي مي‌شود. در بهينه‌سازي ورودي‌ها يا متغيرها به نحوي تغيير داده مي‌شوند که خروجي مطلوب به دست بيايد.
مراحل حل یک مسئله بهینه سازی
مهمترین قدم در حل یک مسئله بهینه سازی با استفاده از الگوریتم رقابت استعماری و هر روش دیگری، تعریف متغیرهای بهینه سازی و در کنار آن اهداف بهینه سازی می باشد. فرض کنید که می خواهیم آنتن تلویزیون را به گونه ای تنظیم کنیم که بیشترین کیفیت تصویر دریافتی را داشته باشد. عبارت “تنظیم آنتن تلویزیون برای داشتن بیشترین کیفیت تصویر دریافتی” یک بیان کیفی از یک مسئله بهینه سازی است. در بعضی موارد روشهای سعی و خطا برای یافتن جواب بهینه استفاده می شود. بدین ترتیب که در این مثال نوعی، یک نفر به پشت بام رفته و شروع به جابجا کردن آنتن تلویزیون می کند و یک نفر دیگر نیز پشت تلویزیون نشسته و با عبارتهایی نظیر:
  • آهان همین زاویه رو نگه دار
  • یکم برگرد عقب تر
  • نه الان خیلی بد شد
  • و ….
با صدای بلند میزان کیفیت هر یک از موقعیت های آنتن را به گوش تنظیم کننده آنتن می رساند. معمولاً کسی که بالا رفته و آنتن را جابجا می کند، حرفه ای تر از فردی هست که پایین پشت تلویزیون نشسته و داد می زند.فرد بالای پشت بام (فرد حرفه ای تر) نقش الگوریتم بهینه سازی و فردی که کیفیت تصویر را داد میزند، نقش تابع هزینه را بازی می کند.در موارد زیادی حل مسئله بهینه سازی با سعی و خطا امکن پذیر نیست! یک دلیل برای این کار این است که فضای جستجوی مسئله بسیار بزرگ است. دلیل دیگر این است که نمی توان هر بار سیستم را اجرا کرده و نتیجه آن را مشاهده کرد. فرض کنیم که برای قرار گرفتن یک ماهواره در مدار زمین باید، بهینه ترین سرعت و زاویه پرتاب و بهینه ترین مسیر حرکت باید تعیین شوند. نمی توان برای تعیین جواب مسئله هر بار ماهواره ارسال کرد و با همان عبارتهای مشابه ” آهان همین رو نگه دار”، “یکم برگرد عقب تر” و “نه الان خیلی بد شد” (مشابه روش تعیین مسیر بهینه شلیک گلوله توپ به هدف) بهترین روش پرتاب ماهواره را تعیین نمود.

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

2) هدف چیست (بیان کیفی هدف)؟

در مثال مطرح شده هدف رسیدن به بیشترین کیفیت تصویر دریافتی از تلویزیون است.

3) متغیرهای بهینه سازی چه هستند؟

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

Image Quality = function(Antenna Angle , Antenna Height)

و به طور خلاصه داریم:

IQ = f(x1 , x2)

که در آن x1، میزان زاویه آنتن و x2 میزان ارتفاع آنتن است.

4) ارتباط میان هدف بهینه سازی و متغیرهای بهینه سازی به صورت ریاضی چیست؟

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

IQ = 100 – x1^2 – (x2-5)^2

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

x1 = 0;
x2 = 5;

که با مقادیر فوق به کیفیت تصویر 100 می رسیم.

5) حال اگر رابطه فوق کمی پیچیده تر باشد، چه باید کرد؟ مثال زیر را در نظر می گیریم.

IQ = -20 – x1^2 + x2^2 + 10 * (cos(2*pi*x1) + cos(2*pi*x2));

این رابطه دارای تعداد زیادی نقاط اکسترمم محلی و یک نقطه اکسترمم مطلق در نقطه (0,0) می باشد. برای حل چنین مسائل بهینه سازی، از روش های دیگر بهینه سازی همچون بهینه سازی تکاملی و در میان آنها از می توان از الگوریتم رقابت استعماری استفاده کرد.

6) پس از تعریف ارتباط ریاضی تابع هزینه و متغیرهای بهینه سازی چه باید کرد؟

در این مرحله پیاده سازی عملی کار شروع می شود. در مراجع مختلف و به ویژه در اینترنت، کدهای رایگان بسیاری از الگوریتم های بهینه سازی تکاملی وجود دارند. کدهای رایگان الگوریتم رقابت استعماری نیز به سادگی با جستجوی عبارت “کدهای رایگان الگوریتم رقابت استعماری” و یا “Imperialist Competitive Algorithm Code” به زبانهای مختلف قابل تهیه هستند. نکته مشترک میان همه این کدها این هست که این کدها، تابع هزینه مسئله شما را گرفته و پس از جستجو با استراتژی های مختلف، جواب مسئله را به شما می دهند. برای استفاده از همه کدهای موجود بر روی وب باید تابع هزینه خود را به صورت یک تابع جداگانه بنویسید. البته میان نحوه تعریف تابع هزینه در کدهای مختلف شاید ، اندکی تفاوت موجود باشد. منتها روند کلی به صورت زیر است.

Cost = function(X)
Cost = f(X);
end

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

7) آیا تابع هزینه مسئله همیشه به صورت یک برنامه ساده و یک رابطه ریاضی مشخص است؟

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

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

8) مسئله بهینه سازی من پارامتهای دیگری دارد که متغیر بهینه سازی نیستند ولی در بهینه سازی تاثیر دارند، چه کنم؟

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

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

—————————————————————–

قسمتی از پروژه ی پایان نامه ی من به این شکل تعریف شده است:انجام آزمایشات (32 موردآزمایش) با استفاده از دستگاه WEDM: در طول انجام این آزمایشات که بر حسب روش طراحی آزمایش تاگوچی طرح ریزی شده اند، 5 فاکتور ورودی سیستم یعنی W (تغذیه ی سیم)، P (توان)، V (ولتاژ)، S (سر) و زمان تغییر می کند تا از این طریق اثر تغییر این پارامترها روی خروجی و یا کارایی سیستم بررسی شود. خروجی های سیستم هم حجم برداشته شده از سطح قطعه کار (MRR) و صافی سطح (SR) است.برای بهینه سازی خروجی فرایند، تصمیم گرفتم که از الگوریتم استعماری استفاده کنم. ولی مشکلی که دارم این است که نمی دانم به چه شکل می توانم تابع هزینه متناسب با این فرایند را تعریف کنم؟ یکی از توابع هزینه که درفرایند های ماشینکاری مطرح میشود به شکل زیر است

L(w,p,s,v,t) = MRR + 1/SR

به این مفهوم که با تغییر ورودی ها به ماکزیمم مقدار برداشت مواد از سطح و کمترین پستی و بلندی که با SR نمایش داده می شود برسیم.

—————————————————————–

سوالاتی زیر برای من مطرح است:

سوال 1: برای استفاده از الگوریتم رقابت استعماری، چه تعداد تابع هزینه بایستی تعریف شود؟

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

function Y = f(x)

Y = f1(x) + f2(x)

end

function Y = f1(x)

Y = sin(x)

end

function Y = f1(x)

Y = cos(x)

end
فراخوانی تابع f برای هر مقدار x به عبارت sin(x)+coss(x) خواهد رسید. بنابراین تعداد اهداف مسئله بهینه سازی (که در اکثر کاربردها یک می باشد)، لزوماً تعداد توابع مورد استفاده برای کد نویسی آن را نشان نمی دهد.

سوال 2: تابع هزینه به صورت FUNCTION باید باشد؟

پاسخ: بله! شما پس از جدا کردن و تعریف کردن متغیرهای بهینه سازی خود، یک تابع هزینه می نویسید که با دریافت این متغیرها ، خروجی هزینه را بدهد. در این مورد فیلم آموزشی کوتاهی بر روی سایت الگوریتم استعماری (www.icasite.info) وجود دارد. موارد آموزشی تکمیلی به زودی بر روی سایت قرار خواهد گرفت.

سوال 3: تابع هزینه باید رابطه ای بین ورودی ها باشد ویا خروجی ها؟

پاسخ: ظاهراً تابع هزینه شما باید بهترین مقادیر (w,p,s,v,t) را بدهد. بنابراین شما باید تابعی بنویسید که این مقادیر را گرفته وMRRوSRاز روی آنها تعیین شوند و در نهایتLبه دست آید. در حقیقت داریم.

MRR = MRR(w,p,s,v,t)
SR = SR(w,p,s,v,t)
L = L(w,p,s,v,t) = MRR + 1/SR = MRR(w,p,s,v,t) + 1/SR(w,p,s,v,t)

اگر بخواهیم تا حدی یک شبه کد برای این مسئله بنویسیم خواهیم داشت.

Function L = L_Fcn(w,p,s,v,t)
L = MRR_Fcn(w,p,s,v,t) + 1/ SR_Fcn(w,p,s,v,t)
end
Function MRR = MRR_Fcn(w,p,s,v,t)
{Required Calculations}
end
Function SR = SR_Fcn(w,p,s,v,t)
{Required Calculations}
end

الگوریتم رقابت استعماری فقط با تابع L_Fcn کار خواهد کرد و با بقیه تابع ها کاری نخواهد داشت.

پایان متن
————————————————————————–

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

 

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

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

یکی از دوستان سوالی در مورد نحوه برخورد با قید ها (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 های کانسرنت هندلنگ (مدیریت قیود) خیلی زیاد هستند. در مورد این ها می توانیم مجزا مطالعه کنیم. منتها این روش هایی که گفتم، روش های عام این قضیه هستند و می توانیم با مقداری بازی کردن باهاشون، کار کنید.

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

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

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

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

سوال مطرح شده: سوال دریافتی از طریق بخش تماس با ما در سایت: “آیا با استفاده از الگوریتم رقابت استعماری می شود دیسکریپتور (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

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