Astaraki

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

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


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



برای فهم مشکل موجود در تحلیل زمانی الگوریتم ها در مواجهه با مسائل 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 مثلاً 10000 باشد (که مثلاً در یک الگوریتم ژنتیک با 100 جمعیت اولیه و 100 نسل اتفاق می افتد)، Tc برابر با 10000*1=10000 دقیقه خواهد بود. در کنار این 10000 دقیقه زمان Ta برای یک الگوریتم سریع حدود 10 ثانیه و برای یک الگوریتم کند حدود یک دقیقه خواهد بود. در نتیجه زمان کل تاثیر چندانی از سرعت خود الگوریتم (محاسبات عملگرهای آن) نخواهد پذیرفت (10000 دقیقه و 10 ثانیه در مقایسه با 10001 دقیقه) و بخش عمده آن از زمان Tc تشکیل خواهد شد که برای دو الگوریتم با Nc یکسان، یکی خواهد بود. بنابراین نتیجه به دست آمده از تحلیل زمانی الگوریتم بر روی مسائل استاندارد در تعمیم آن به مسائل عملی، ارزش علمی خود را از دست خواهند داد.

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

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

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

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

rasoul_cold

امکان اینکه این دو الگوریتم را ترکیب کرد وجود داره؟

nahiyd

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

__________________