کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
377358 658409 2006 30 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Backward-chaining evolutionary algorithms
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Backward-chaining evolutionary algorithms
چکیده انگلیسی

Starting from some simple observations on a popular selection method in Evolutionary Algorithms (EAs)—tournament selection—we highlight a previously-unknown source of inefficiency. This leads us to rethink the order in which operations are performed within EAs, and to suggest an algorithm—the EA with efficient macro-selection—that avoids the inefficiencies associated with tournament selection. This algorithm has the same expected behaviour as the standard EA but yields considerable savings in terms of fitness evaluations. Since fitness evaluation typically dominates the resources needed to solve any non-trivial problem, these savings translate into a reduction in computer time. Noting the connection between the algorithm and rule-based systems, we then further modify the order of operations in the EA, effectively turning the evolutionary search into an inference process operating in backward-chaining mode. The resulting backward-chaining EA creates and evaluates individuals recursively, backward from the last generation to the first, using depth-first search and backtracking. It is even more powerful than the EA with efficient macro-selection in that it shares all its benefits, but it also provably finds fitter solutions sooner, i.e., it is a faster algorithm. These algorithms can be applied to any form of population based search, any representation, fitness function, crossover and mutation, provided they use tournament selection. We analyse their behaviour and benefits both theoretically, using Markov chain theory and space/time complexity analysis, and empirically, by performing a variety of experiments with standard and back-ward chaining versions of genetic algorithms and genetic programming.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 170, Issue 11, August 2006, Pages 953-982