Wyniki wyszukiwania - BazTech

1

A study on meme propagation in multimemetic algorithms

Nogueras R., Cotta C.

International Journal of Applied Mathematics and Computer Science

|

2015

|

Vol. 25, no. 3

499--512

EN

Multimemetic algorithms (MMAs) are a subclass of memetic algorithms in which memes are explicitly attached to genotypes and evolve alongside them. We analyze the propagation of memes in MMAs with a spatial structure. For this purpose we propose an idealized selecto-Lamarckian model that only features selection and local improvement, and study under which conditions good, high-potential memes can proliferate. We compare population models with panmictic and toroidal grid topologies. We show that the increased takeover time induced by the latter is essential for improving the chances for good memes to express themselves in the population by improving their hosts, hence enhancing their survival rates. Experiments realized with an actual MMA on three different complex pseudo-Boolean functions are consistent with these findings, indicating that memes are more successful in a spatially structured MMA, rather than in a panmictic MMA, and that the performance of the former is significantly better than that of its panmictic counterpart.

2

Asymptotic guarantee of success for multi-agent memetic systems

Byrski A., Schaefer R., Smołka M., Cotta C.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2013

|

Vol. 61, nr 1

257-278

EN

The paper introduces a stochastic model for a class of population-based global optimization meta-heuristics, that generalizes existing models in the following ways. First of all, an individual becomes an active software agent characterized by the constant genotype and the meme that may change during the optimization process. Second, the model embraces the asynchronous processing of agent’s actions. Third, we consider a vast variety of possible actions that include the conventional mixing operations (e.g. mutation, cloning, crossover) as well as migrations among demes and local optimization methods. Despite the fact that the model fits many popular algorithms and strategies (e.g. genetic algorithms with tournament selection) it is mainly devoted to study memetic algorithms. The model is composed of two parts: EMAS architecture (data structures and management strategies) allowing to define the space of states and the framework for stochastic agent actions and the stationary Markov chain described in terms of this architecture. The probability transition function has been obtained and the Markov kernels for sample actions have been computed. The obtained theoretical results are helpful for studying metaheuristics conforming to the EMAS architecture. The designed synchronization allows the safe, coarse-grained parallel implementation and its effective, sub-optimal scheduling in a distributed computer environment. The proved strong ergodicity of the finite state Markov chain results in the asymptotic stochastic guarantee of success, which in turn imposes the liveness of a studied metaheuristic. The Markov chain delivers the sampling measure at an arbitrary step of computations, which allows further asymptotic studies, e.g. on various kinds of the stochastic convergence.

3

From Genes to Memes: Optimization by Problem-aware Evolutionary Algorithms

Cotta C.

Schedae Informaticae

|

2006

|

Vol. 15

127-150

EN

Memetic algorithms are population-based metaheuristics aimed to solve hard optimization problems. These techniques are explicitly concerned with exploiting available knowledge in order to achieve the most effective resolution of the target problem. The rationale behind this optimization philosophy, namely the intrinsic theoretical limitations of problem-unaware optimization techniques, is presented in this work. A glimpse of the main features of memetic algorithms, and a brief overview of the numerous applications of these techniques is provided as well.