Performance and Scalability of Genetic Algorithms on NK-Landscapes Export

@incollection{citeulike:4313326, abstract = {This work studies the working principles, performance, and scalability of genetic algorithms on NK-landscapes varying the degree of epistasis interactions. Previous works that have focused mostly on recombination have shown that simple genetic algorithms, and some improved ones, perform worse than random bit climbers and not better than random search on landscapes of increased epistasis. In our work, in addition to recombination, we also study the effects on performance of selection, mutation, and drift. We show that an appropriate selection pressure and postponing drift make genetic algorithms quite robust on NK-landscapes, outperforming random bit climber on a broad range of classes of problems. We also show that the interaction of parallel varying-mutation with crossover improves further the reliability of the genetic algorithm.}, author = {Aguirre, Hern\'{a}n and Tanaka, Kiyoshi}, citeulike-article-id = {4313326}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-70807-0_3}, citeulike-linkout-1 = {http://www.springerlink.com/content/00g20g72m6818u3t}, doi = {10.1007/978-3-540-70807-0_3}, journal = {Recent Advances in Evolutionary Computation for Combinatorial Optimization}, keywords = {crossover, drift, evolutionary-computation, genetic-algorithm, metaheuristic, mutation, nk-landscapes, parameter-setting, performance-assessment, selection}, pages = {37--52}, posted-at = {2009-04-15 14:34:25}, priority = {5}, title = {Performance and Scalability of Genetic Algorithms on NK-Landscapes}, url = {http://dx.doi.org/10.1007/978-3-540-70807-0_3}, year = {2008} }

TY - CHAP ID - citeulike:4313326 L3 - citeulike-article-id:4313326 N2 - This work studies the working principles, performance, and scalability of genetic algorithms on NK-landscapes varying the degree of epistasis interactions. Previous works that have focused mostly on recombination have shown that simple genetic algorithms, and some improved ones, perform worse than random bit climbers and not better than random search on landscapes of increased epistasis. In our work, in addition to recombination, we also study the effects on performance of selection, mutation, and drift. We show that an appropriate selection pressure and postponing drift make genetic algorithms quite robust on NK-landscapes, outperforming random bit climber on a broad range of classes of problems. We also show that the interaction of parallel varying-mutation with crossover improves further the reliability of the genetic algorithm. JF - Recent Advances in Evolutionary Computation for Combinatorial Optimization EP - 52 TI - Performance and Scalability of Genetic Algorithms on NK-Landscapes SP - 37 KW - crossover KW - drift KW - evolutionary-computation KW - genetic-algorithm KW - metaheuristic KW - mutation KW - nk-landscapes KW - parameter-setting KW - performance-assessment KW - selection AU - Aguirre, Hernán AU - Tanaka, Kiyoshi PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-70807-0_3 ER -