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

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

Tt = Ta + 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 ها با هم مقایسه شوند. بنابراین یکبار اجرای یک الگوریتم و گزارش برتری آن نسبت به یک بار اجرای الگوریتم دیگری صحیح نمی باشد.

_____________________________________________

صرف زمان برای یادگیری اتلاف زمان نیست. سرمایه گذاری زمانی است.