نحوه مقایسه کارکرد دو الگوریتم بهینه سازی
 
بچه های مهندسی فناوری اطلاعات ورودی 87
نمونه سوال-کتاب-مقاله و...
 
سه شنبه 10 اسفند 1389برچسب:, :: 21:33 ::  نويسنده : hanieh.daneshgar

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

 

 

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

[تصویر: fig_4_12_l.png]
شکل: مقایسه دو الگوریتم بهینه سازی؛ در این شکل الگوریتم یک (A1) نسبت به الگوریتم دو (A2) کارایی مطلقاً بهتری نشان می دهد. برای رسیدن به هزینه معین، الگوریتم یک زمان کمتری نسبت به الگوریتم دو نیاز دارد. از سوی دیگر در زمان ثابت نیز الگوریتم یک به هزینه کمتری می رسد. در ادامه خواهیم دید که اگر محور افقی زمان واقعی باشد، این تحلیل می تواند کمی اشکال داشته باشد. ولی اگر محور افقی تعداد فراخوانی تابع هزینه هزینه باشد، می توان تا حد زیادی نتیجه به دست آمده را به مسائل واقعی نیز تعمیم داد.

شاید با در نظر گرفتن تعریف فوق، به این نتیجه برسیم که زمان (CPU time) رسیدن به جواب ملاک خوبی برای مقایسه دو الگوریتم است. یعنی با استفاده از تایمر کامپیوتر، دو الگوریتم را اجرا کرده و هدف را مثلاً مقدار بهینه صفر قرار می دهیم و با رسیدن هر الگوریتم به این مقدار بهینه، تایمر را متوقف کرده و نتیجه زمانی را گزارش می کنیم و در نتیجه هر الگوریتمی که با این تایمر سریعتر بود، بهتر است. این روشی است که در خیلی از مقالات انتشار یافته مشاهده می کنیم و با استناد به چندین اندازه گیری زمانی (تایمر) نویسندگان مقاله ادعا می کنند که روش ارائه شده توسط آنها، بهتر است و یا اینکه تغییری که آنها در بخشی از الگوریتم ژنتیک، PSO و یا الگوریتم رقابت استعماری (ICA) داده اند، این روشها را بهبود داده است. در چنین مواردی معمولاً مولفین از توابعی استفاده می کنند که به عنوان توابع استاندارد یا Benchmark شناخته می شوند. شکل زیر یک مورد از توابع استاندارد را نشان می دهد. تعدادی بیشتری از این توابع در این لینک در بخشی از فایل راهنمای الگوریتم رقابت استعماری قابل ملاحظه هستند. همچنین بخش پیوست کتاب الگوریتم ژنتیک عملی (در این لینک)، برخی از این توابع را لیست کرده است.

[تصویر: image576.png]
[تصویر: chart?cht=tx&chs=1x0&chf...20%282y%29]
[تصویر: chart?cht=tx&chs=1x0&chf...%2018.5547]
شکل: یک مورد از توابع استاندارد مورد استفاده در تست روشهای بهینه سازی

برای فهم مشکل موجود در تحلیل زمانی الگوریتم ها در مواجهه با مسائل Benchmark باید به این نکته توجه کرد که مسائل مذکور، مسائل استانداردی هستند که بصورت بسیار ساده و کاملاً ریاضی مطرح شده اند و زمان مورد نیاز برای محاسبه خود این توابع بسیار ناچیز می باشد. مثلاً تابع کروی دو بعدی به صورت x1^2 + x2^2 در کسری از ثانیه به ازای هر x1 و x2 محاسبه می شود. بنابراین محاسبات تابع هزینه در مسائل استاندارد زمان بسیار ناچیزی را در مقایسه با محاسبات مربوط به خود الگوریتم (مثلاً جذب و انقلاب در الگوریتم رقابت استعماری و یا تزویج و میوتیشن در الگوریتم ژنتیک) به خود اختصاص می دهند. برای بررسی دقیقتر موضوع زمان کل رسیدن الگوریتم به جواب را Tt در نظر می گیریم. Tt می تواند به صورت زیر به دو بخش شکسته شود.

Tt = Ta + Tc

که در آن Ta زمان کل مربوط به عملیات خود الگوریتم تا رسیدن به جواب و Tc زمان کل صرف شده برای محاسبه تابع هزینه است. اگر الگوریتم تا رسیدن به جواب Nc بار تابع هزینه را فراخوانی کند و هر بار محاسبه تابع هزینه به زمان tc نیاز داشته باشد، می توان نوشت:

Tt = Ta + Tc = Ta + Nc * tc

در مسائل Benchmark که به آنها اشاره شد، tc زمان بسیار ناچیزی است و Nc * tc زمانی قابل مقایسه با ta می باشد. بنابراین زمان کل Tt بسیار متاثر از Ta خواهد بود. بنابراین از دیدگاه این نوع توابع، الگوریتمی بهتر است که در عین داشتن کارایی نسبتاً مناسب، دارای Ta کمتری باشد و به عبارت دیگر تا حد امکان ساده بود و عملگر های پیچیده ای نداشته باشد. شاید در نگاه اول این نوع دیگاه غیرمنطقی نباشد، ولی مسئله زمانی پیچیده می شود که می خواهیم از یک الگوریتم بهینه سازی در حل یک مسئله عملی استفاده کنیم. به عنوان مثال، الگوریتم رقابت استعماری دارای Ta به نسبت بیشتری نسبت به PSO و GA می باشد. بنابراین با وجود اینکه این الگوریتم در حل بسیاری از مسائل ساده و استاندارد نیز کارایی بهتری نسبت به PSO و GA نشان داده است، ولی در حل مسائل بیش از حد ساده ممکن است به این نتیجه برسیم که این الگوریتم کمی کند است. مثلاً به جای یک ثانیه (در مورد الگوریتم ژنتیک)، این الگوریتم در یک و نیم ثانیه جواب را پیدا می کند. اما باید این نکته را در نظر بگیریم که در یک مسئله عملی زمان tc زمان کوچک و قابل صرفنظری نیست. در برخی موارد هر بار فراخوانی و محاسبه تابع هزینه چندین دقیقه زمان می برد. بنابراین اگر Nc مثلاً ۱۰۰۰۰ باشد (که مثلاً در یک الگوریتم ژنتیک با ۱۰۰ جمعیت اولیه و ۱۰۰ نسل اتفاق می افتد)، Tc برابر با ۱۰۰۰۰*۱=۱۰۰۰۰ دقیقه خواهد بود. در کنار این ۱۰۰۰۰ دقیقه زمان Ta برای یک الگوریتم سریع حدود ۱۰ ثانیه و برای یک الگوریتم کند حدود یک دقیقه خواهد بود. در نتیجه زمان کل تاثیر چندانی از سرعت خود الگوریتم (محاسبات عملگرهای آن) نخواهد پذیرفت (۱۰۰۰۰ دقیقه و ۱۰ ثانیه در مقایسه با ۱۰۰۰۱ دقیقه) و بخش عمده آن از زمان Tc تشکیل خواهد شد که برای دو الگوریتم با Nc یکسان، یکی خواهد بود. بنابراین نتیجه به دست آمده از تحلیل زمانی الگوریتم بر روی مسائل استاندارد در تعمیم آن به مسائل عملی، ارزش علمی خود را از دست خواهند داد.

چاره چیست؟ پاسخ دادن به این سوال ساده نیست. هر نوع تحلیلی از سرعت مشکل خاص خود را خواهد داشت. اما تا کنون با توجه به اینکه اغلب مسائل عملی Tc بالایی دارند، بهترین کار در نظر گرفتن Nc (تعداد فراخوانی کل تابع هزینه) می باشد. بدین ترتیب اگر در مواجهه با یک مسئله بهینه سازی (حتی در مسائل Benchmark) الگوریتم “الف” نسبت به الگوریتم “ب” با تعداد فراخوانی تابع هزینه (Nc) یکسان به جواب بهتری رسید، الگوریتم “الف” بهتر است. به عبارت دیگر اگر برای رسیدن به جواب معین و یکسان، الگوریتم “الف” تعداد فراخوانی تابع هزینه کمتری نسبت به الگوریتم “ب” نیاز داشت، الگوریتم “الف” بهتر است. جایگزینی زمان CPU با تعداد فراخوانی تابع هزینه تا حد زیادی مشکل مربوط به تعمیم نتایج به مسائل عملی را حل می کند. به این ترتیب ممکن است الگوریتمی مثل الگوریتم رقابت استعماری زمان Ta بیشتری داشته باشد (به عبارت دیگر چند ثانیه زمان بیشتری را به فکر کردن و هوشمندی بگذراند) ولی در نهایت به خاطر اینکه مثلاً به تعداد ۱۰۰۰ بار کمتر فراخوانی تابع هزینه انجام داده است، ۱۰۰۰ دقیقه زودتر ما را به جواب برساند که در مقایسه با چندین ثانیه زمان بیشتری که برای عملگرهای خود صرف می کند، صرفه جویی بسیاری در زمان می باشد.

نکته مهم دیگر این است که دو الگوریتم باید به تعداد زیادی اجرا شده و در میانگین و واریانس و سایر Statistic ها با هم مقایسه شوند. بنابراین یکبار اجرای یک الگوریتم و گزارش برتری آن نسبت به یک بار اجرای الگوریتم دیگری صحیح نمی باشد.

منبع

http://forum.matlabsite.com/showthread.php?tid=53&pid=81#pid81


نظرات شما عزیزان:

hosein888
ساعت21:39---10 اسفند 1389
سلام داش خوبی
یه سری به من بزن
فقط یه خواهش اومدی تو وبم روب نر تبلیلغاتی اول وبلاگم کلیک کن
خیلی ممنون
حسین


نام :
آدرس ایمیل:
وب سایت/بلاگ :
متن پیام:
:) :( ;) :D
;)) :X :? :P
:* =(( :O };-
:B /:) =DD :S
-) :-(( :-| :-))
نظر خصوصی

 کد را وارد نمایید:

 

 

 

عکس شما

آپلود عکس دلخواه:





درباره وبلاگ

این وبلاگ برای همه بچه های مهندسی فناوری اطلاعات ورودی 87 زده شده اما همه دوستان میتونن از این وبلاگ استفاده کنن امیدوارم از مطالب بهترین استفاده رو ببرید پیشنهاد و یا انتقادی بود حتما در نظرات بفرمایید اگر مطلب خاصی خواستید در نظرات بفرمایید تاقرار داده بشه آرزوی بهترین ها برای شما دوست عزیز موفق باشید
آخرین مطالب
پيوندها

تبادل لینک هوشمند
برای تبادل لینک  ابتدا ما را با عنوان بچه های مهندسی فناوری اطلاعات ورودی 87 و آدرس itgroup-1387.LoxBlog.ir لینک نمایید سپس مشخصات لینک خود را در زیر نوشته . در صورت وجود لینک ما در سایت شما لینکتان به طور خودکار در سایت ما قرار میگیرد.





نويسندگان



نام :
وب :
پیام :
2+2=:
(Refresh)

<-PollName->

<-PollItems->

خبرنامه وب سایت:

برای ثبت نام در خبرنامه ایمیل خود را وارد نمایید




آمار وب سایت:
 

بازدید امروز : 6
بازدید دیروز : 0
بازدید هفته : 70
بازدید ماه : 794
بازدید کل : 50061
تعداد مطالب : 259
تعداد نظرات : 71
تعداد آنلاین : 1



<-PollName->

<-PollItems->

وب سایت ختم قرآن مجید



Top Blog
وبلاگ برتر در تاپ بلاگر

كد موسيقي براي وبلاگ

كد تغيير شكل موس