کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876007 | 689663 | 2015 | 21 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved time complexity analysis of the Simple Genetic Algorithm
ترجمه فارسی عنوان
تجزیه و تحلیل پیچیدگی زمان بهبود الگوریتم ژنتیک ساده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم ژنتیک ساده، متقاطع، تجزیه و تحلیل زمان اجرا،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A runtime analysis of the Simple Genetic Algorithm (SGA) for the OneMax problem has recently been presented proving that the algorithm with population size μâ¤n1/8âε requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to μâ¤n1/4âε which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 605, 9 November 2015, Pages 21-41
Journal: Theoretical Computer Science - Volume 605, 9 November 2015, Pages 21-41
نویسندگان
Pietro S. Oliveto, Carsten Witt,