استراتژی جامع حل مسائل بهینه سازی - Artificial Intelligence

**Astaraki** · ۰۳-۹-۱۳۸۹, ۰۱:۳۸ بعد از ظهر

استراتژی جامع حل مسائل بهینه سازی

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

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

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 باید باشد؟

پاسخ: بله! شما پس از جدا کردن و تعریف کردن متغیرهای بهینه سازی خود، یک تابع هزینه می نویسید که با دریافت این متغیرها ، خروجی هزینه را بدهد. در این مورد فیلم آموزشی کوتاهی بر روی سایت الگوریتم استعماری (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 این نوشتار با عنوان بهینه سازی چیست، به همراه تصویر موجود در این بخش برداشتی از کار ارزشمند جناب آقای مهندسی سید مصطفی کلامی هریس با کسب اجازه از ایشان بوده است.

منبع : استراتژی جامع حل مسائل بهینه سازی

vatanparast · ۰۳-۱۷-۱۳۹۰, ۰۵:۲۰ بعد از ظهر

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

icasite.info · ۰۳-۲۷-۱۳۹۰, ۰۸:۲۸ قبل از ظهر

دوست عزیز، برای اینکه در کدنویسی ها اشتباه نشه، میتونی کدهای آماده استفاده ICA رو به همراه فیلم آموزشی نحوه استفاده از لینک زیر دریافت کنی. به همراه کدها، مثال های متنوعی وجود دارند.

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

noshiiin · ۰۹-۲۴-۱۳۹۲, ۱۰:۲۸ بعد از ظهر

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

noshiiin · ۰۹-۲۴-۱۳۹۲, ۱۰:۳۰ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله noshiiin

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

اگه بشه سریع پاسخ بدین ممنون میشم

sadegh.ebrahimi · ۰۳-۱۷-۱۳۹۵, ۰۳:۵۹ بعد از ظهر

سلام دوستان
کسی هست بتونه این مساله مدل سازی رو حل کنه ؟

‌در یک سرمایه گذاری باید در مورد تقسیم سرمایه در میان 4 انتخاب مختلف تصمیم گیری به عمل آید . این سرمایه گذاری سه نتیجه دارد . جدول زیر سود یا زیان متناظر با هر هزار تومانی را که در هر یک از چهار انتخاب گذاشته شود برای هر یک از سه نتیجه را نشان می دهد .
سود یا زیانی که برای هر هزار تومانی که در انتخاب مفروض است
نتیجه 1 2 3 4
1 -3 4 -7 15
2 5 -3 9 4
3 3 -9 10 -8

فرض کنید سرمایه گذاری جمعا 500 هزار تومان دارد که با آن می تواند تنها یک بار سرمایه گذاری کند . نتیجه دقیق سرمایه گذاری مشخص نیست و به علت همین نا معلومی ٫ سرمایه گذار تصمیم گرفته پولش ر به طوری تقسیم کند که کمینه درآمدش بیشینه شود . مسله را به صورت یک مدل برنامه ریزی خطی فرمول بندی نمایید ؟ ( درآمد سرمایه گذاری می تواند - ٫ + ویا صفر باشد )