دانلود ترجمه مقاله بهینه سازی چند هدفه با استفاده از الگوریتم های تکاملی (اسپرینگر ۲۰۰۶)

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

Multiobjective Optimization Using Evolutionary Algorithms A Comparative Case Study

چکیده
۱- مقدمه
۲- الگوریتم‌های تکاملی چندهدفه
۳- مسئله کوله‌پشتی
۴- آزمایش‌ها
۵- نتیجه‌گیری و چشم‌انداز آتی
منابع

چکیده
از سال ۱۹۸۵ چند روش تکاملی برای بهینه‌سازی چندهدفه توسعه یافته است که قادر به یافتن چند راه‌حل در یک دور اجرا (run) هستند. با این حال، اکثر مطالعاتِ مقایسه‌ای که در دسترس هستند، به صورت کیفی بوده و محدود به دو روش اصلی می‌شوند. در این مقاله یک مقایسه گسترده و کمّی عرضه شده است که از ۴ الگوریتم‌ تکاملی چندهدفه برای مسئله ۱/۰ کوله‌پشتی (knapsack problem) استفاده می‌کند.

۲- الگوریتم‌های تکاملی چندهدفه
مروری جامع بر الگوریتم‌های تکاملی در بهینه‌سازی چندهدفه در مقاله‌ای از فونسکا و فلمینگ صورت گرفته‌ است. نویسندگان این مقاله چند روش تکاملی را بررسی کرده‌اند که شامل روش‌های انباشت ساده، روش‌های جمعیتی غیرپارتو و روش‌های مبتنی بر پارتو می‌شود. همچنین روش‌های استفاده از القای همسایگی (niche) نیز آورده شده‌اند.

روش‌های انباشتی به ترکیب‌کردن اهداف درون یک تابع نردبانی بالاتر مشغول‌اند که برای محاسبات شایستگی (fitness) از آنها استفاده می‌شود. این روش‌ها یک راه‌حل منفرد (single) فراهم می‌آورند و نیازمند داشتن دانش عمیقی هستند که معمولاً دردسترس نیست. روش‌های جمعیتی غیرپارتو قادر هستند تا راه‌حل‌های غیرمغلوبی را به صورت موازی پیدا کرده و بنابراین جمعیت اساساً برای راه‌حل‌های غیرمغلوب کنترل می‌شود. اما برعکس روش‌های پارتو، روش‌های جمعیتی غیرپارتو از مفهومِ غلبه (dominance) پارتو به طور مستقیم استفاده نمی‌کنند. الگوریتم‌های تکاملی پارتو، راه‌حل‌ها را بر اساس رابطه > مقایسه می‌کنند تا احتمالِ تولیدمثل هر فرد را محاسبه کنند. اولین بار این نوع مسئله شایستگی را گلدبرگ پیشنهاد داد.

از آنجایی که حفظ‌کردن تنوع موضوع مهمی در حوزه بهینه‌سازی چندحالته است، بسیاری از الگوریتم‌های تکاملی چندهدفه شامل تکنیک‌های نیچینگ (قرارگرفتن در همسایگی) می‌شود و بیش از همه از روشِ اشتراک‌گذاریِ شایستگی استفاده می‌شود. به اشتراک‌گذاشتن شایستگی (Fitness sharing) بر مبنای این ایده است که افراد حاضر در یک محیط خاص، باید منابع دردسترس را با یکدیگر شریک شوند. همانطور که در طبیعت نیز چنین است. بنابراین، شایستگی یک فرد معین به این نحو تعیین می‌شود که هرچه آن فرد بیشتر تضعیف شود، افراد بیشتری در همسایگی او قرار می‌گیرند. همسایگی بر اساس معیار فاصله سنجیده می‌شود و با شعاع همسایگی σshare نشان داده می‌شود. به اشتراک‌گذاشتن هم می‌تواند در فضای ژنوتیپ و هم در فضای فنوتیپ (شرایط محیطی) روی دهد.