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

۵ خرداد ۱۳۸۹ توسط eag مجموعه: بهینه سازی

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

 

 

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

 

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

 

 

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

۱) بهینه سازی چیست؟

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



شکل: فرایند یا تابعی که بهینه‌سازی می‌شود. در بهینه‌سازی ورودی‌ها یا متغیرها به نحوی تغییر داده می‌شوند که خروجی مطلوب به دست بیاید.

مراحل حل یک مسئله بهینه سازی

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

  • آهان همین زاویه رو نگه دار
  • یکم برگرد عقب تر
  • نه الان خیلی بد شد
  • و ….

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

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

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

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

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

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

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

Image Quality = function(Antenna Angle , Antenna Height)

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

IQ = f(x1 , x2)

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

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

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

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

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

x1 = 0;
x2 = 5;

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

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

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

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

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

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

Cost = function(X)

 

Cost = f(X);

 

end

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

پاسخ: ظاهراً تابع هزینه شما باید بهترین مقادیر (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. سلام و وقت بخیر خدمت شما
    اگر در این زمینه (بهینه سازی خطی و غیر خطی در محیط متلب در زمینه مکانیک یا هوافضا۹دارید ممنون میشم برام بفرستید
    خیلی نیاز دارم
    تشکر

    پاسخ

    1. در پاسخ به samad:
      با سلام؛

      در لیست آموزش های فرادرس تنها آموزشی که می تواند مرتبط با بهینه سازی خطی باشد در ادامه معرفی شده است:

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

      یکی از سرفصل های این آموزش «آموزش طراحی انواع کنترل بهینه خطی درجه دو یا LQR در متلب» می باشد؛ امیدواریم در راستای هدف شما باشد.

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

      پاسخ

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *