کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876098 | 690214 | 2015 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
From black-box complexity to designing new genetic algorithms
ترجمه فارسی عنوان
از پیچیدگی جعبه به طراحی الگوریتم ژنتیک جدید
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جستجوی اکتشافی، تئوری اکتشافات جستجوی تصادفی، الگوریتم ژنتیک، تجزیه و تحلیل زمان اجرا، پیچیدگی جعبه سیاه،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Black-box complexity theory recently produced several surprisingly fast black-box optimization algorithms. In this work, we exhibit one possible reason: These black-box algorithms often profit from solutions inferior to the previous-best. In contrast, evolutionary approaches guided by the “survival of the fittest” paradigm often ignore such solutions. We use this insight to design a new crossover-based genetic algorithm. It uses mutation with a higher-than-usual mutation probability to increase the exploration speed and crossover with the parent to repair losses incurred by the more aggressive mutation. A rigorous runtime analysis proves that our algorithm for many parameter settings is asymptotically faster on the OneMax test function class than all what is known for classic evolutionary algorithms. A fitness-dependent choice of the offspring population size provably reduces the expected runtime further to linear in the dimension. Our experimental analysis on several test function classes shows advantages already for small problem sizes and broad parameter ranges. Also, a simple self-adaptive choice of these parameters gives surprisingly good results.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 567, 16 February 2015, Pages 87-104
Journal: Theoretical Computer Science - Volume 567, 16 February 2015, Pages 87-104
نویسندگان
Benjamin Doerr, Carola Doerr, Franziska Ebel,