Complex networks in spatially structured genetic algorithms: a robotics perspective
Andrea Gasparri, Stefano Panzieri, Federica Pascucci · Iris (Roma Tre University) · 2007
Evolutionary algorithms have been widely applied in several research fields to solve optimization problems, due to their effectiveness to cope with nonlinear problems [1]. These algorithms use a population of encoded strings (chromosomes) as candidate solutions to explore the search space. The candidate are evaluated by an objective function (fitness function) and the populations evolves at each iteration (epoch) applying reproduction operators such as crossover and mutation. In this work a cellular evolutionary algorithm is proposed using complex network theory to build the structure of the population. The idea is to take advantage of the good properties of some complex networks models, such as the Watts-Strogats model or the Barabasi-Albert model [2], to improve the algorithm performances. From a technical point of view, some differentiations have been introduced regarding to the selection and mating methods. In particular, the selection step simply considers all pairs of elements that, based on the incidence matrix M , are linked. Afterward, for each individual a rank (high or low) is obtained by a comparison with the average fitness over the whole population. Finally, for each pair, the reproduction operators are selected and applied according to the particular mating rules. Extensive simulations has been carried out in a robotic context in order to test the algorithm under different conditions. Videos of such simulations can be reached at http://www.dia.uniroma3.it/labrob/papers/eccs07 showing the improved exploration capability of the algorithm as well as an interesting ability to identify the optimal solution subspace.