الگوریتم های فراابتکاری و ارزیابی عملکرد

دانلود پایان نامه
کارایی الگوریتم های فرا ابتکاری ارتباط مستقیمی با تنظیم پارامترهای آن دارد و کالیبراسیون الگوریتم یکی از مهمترین مراحل طراحی الگوریتم های فراابتکاری در دستیابی به جواب های بهینه و یا نزدیک به بهینه می باشد. از آنجاییکه مقادیر مختلف پارامترهای کنترل کننده این الگوریتم ها ممکن است شاخص های محاسباتی شامل کیفیت جواب ها و زمان محاسباتی را تحت تاثیر قرار دهند، معمولاً مجموعه ای از آزمایشات کالیبراسیون به منظور یافتن ترکیب بهینه مقادیر متفاوت پارامترهای کنترل کننده الگوریتم صورت میپذیرد. روشهای آماری متنوعی برای طراحی آزمایشات مطرح شده است، اما استفاده از رویکرد جامعی مثل آزمایشات عاملی کامل همواره کارایی لازم را ندارند، به این دلیل که با افزایش تعداد عامل های مورد بررسی انجام آزمایشات پیچیده و فوق العاده زمانبر میشود. تاگوچی [93] دسته ای از آزمایشات عاملی کسری را معرفی کرد که بطور قابل توجهی تعداد آزمایشات مورد نیاز بررسی را با حفظ اطلاعات مورد نیاز برای نمایش کاهش می دهد.
4-4-1- طراحی آزمایشات چند عاملی
از اولین مراحل اجرای طراحی آزمایشات چند عاملی میتوان به تعیین پارمترهای کنترلی و سطوح مختلف آنها برای هر یک از الگوریتمهای فراابتکاری اشاره کرد. پارامترهای کنترلی الگوریتم NSGA- شامل حداکثر تعداد تکرار (MaxIt)، اندازه جمعیت اولیه (Npop)، نرخ تقاطع (Cr) و نرخ جهش (Mr) می باشد. پارامتر های کنترلی الگوریتم MOACOشامل حداکثر تعداد تکرار (MaxIt)، اندازه جمعیت اولیه (NAnt)، میزان فرومون اولیه، نرخ تبخیر ، بازه تغییرات وزن دهی به اهداف و نرخ بهره برداری می باشد. همان طور که میدانید هر دو الگوریتم پیشنهادی در این پایان نامه از نوع الگوریتمهای فراابتکاری جمعیت محور و تکرار شونده میباشند و این پارامترها ( یعنی تعداد تکرار و اندازه جمعیت اولیه) ارتباط مستقیمی با کیفیت جوابهای بدست آمده با توجه به زمان محاسباتی انجام شده دارند. معمولاً میزان این دو نوع پارامتر ارتباط مستقیمی با ابعاد مسئله مورد بررسی دارند بطوریکه تعیین مقادیر کوچک برای این دو پارامتر جستجوی موثر فضاهای جواب را محدود میسازد در حالیکه اندازههای بزرگ کارایی الگوریتم را در دستیابی به جوابهای بهینه در زمانهای محاسباتی معقول کاهش میدهد. پس تعیین مقدار این دو پارامتر وابسته به سایز مسئله و همچنین میزان وقت و هزینهای است که کاربر حاضر به صرف آنها دارد. از طرفی چون در این پایاننامه برای ارزیابی عملکرد الگوریتم ها سه گروه از مسائل آزمایشی با ابعاد کوچک، متوسط و بزرگ طراحی شده است و انجام طراحی آزمایشات برای هر سه این گروه ها برای هر الگوریتم فراابتکاری کاری وقتگیر و از حوصلهی این تحقیق خارج است و تنها تفاوت سطوح پارامترهای موجود در این سه گروه از مسائل تنها در تعداد تکرار و میزان جمعیت اولیه می باشد، از این رو ما در این پایان نامه بر اساس آزمایش بصورت سعی وخطا برای هر گروه از این مسائل آزمایشی و وابسته به نوع الگوریتم، مقادیری ثابت و معقول را برای دو پارامتر تعداد تکرار و اندازه جمعیت اولیه در نظر می گیریم. از این رو با انجام یک آزمایش چند عاملی ترکیبی میتوان به سطوح مطلوب برای سایر پارامترهای الگوریتم رسید. در این آزمایش ما یک مسئله با ابعاد کوچک و یک مسئله با ابعاد بزرگ و همچنین یک مسئله با ابعاد متوسط را برای انجام هر آزمایش در نظر میگیریم و خروجی نهایی برای هر آزمایش متوسط نتایج این سه مسئله خواهد بود. در جدول (4-1) مقادیر پارامترهای تعداد تکرار و اندازه جمعیت اولیه برای هر الگوریتم در هر گروه از مسائل آزمایشی و در جدول (4-2) فاکتورها و سطوح مختلف پارامتر های مورد بررسی برای هر الگوریتم نشان داده شده است.
MOACO
NSGA-
(NAnt , MaxIt)
Size
(Npop , MaxIt)
Size
(20,150)
Small
(30,100)
Small
(30,300)
Medium
(40,200)
Medium
(40,300)
Large
(50,250)
Large
جدول (4-1)- سطوح مربوط به پارامترهای تعداد تکرار و اندازه جمعیت اولیه