کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475974 | 699403 | 2008 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Evolutionary algorithms are randomized search heuristics, which are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. They have successfully been applied to different kinds of arc routing problems. To start the analysis of evolutionary algorithms with respect to the expected optimization time on these problems, we consider the Eulerian cycle problem. We show that a variant of the well-known (1+1)(1+1) EA working on the important encoding of permutations is able to find an Eulerian tour of an Eulerian graph in expected polynomial time. Altering the operator used for mutation in the considered algorithm, the expected optimization time changes from polynomial to exponential.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 35, Issue 9, September 2008, Pages 2750–2759
Journal: Computers & Operations Research - Volume 35, Issue 9, September 2008, Pages 2750–2759
نویسندگان
Frank Neumann,