FazBrowse Wikipedia Viewer | Main Page |
Search Wikipedia:
|
Viewing: https://en.wikipedia.org/wiki/Memetic_algorithm

Memetic algorithm

Contents
    Choice of Lamarckian or Baldwinian learning
Applications
Recent activities in memetic algorithms

Part of a series on the
Evolutionary algorithm
Genetic algorithm (GA)
Genetic programming (GP)
Differential evolution
Evolution strategy
Evolutionary programming
Related topics
Select the subset of individuals, Ωil do Perform individual learning using meme(s) f_{il}</math>"}},"i":0}}]}'>with frequency or probability of til. Proceed with Lamarckian or Baldwinian learning. end for end while

Lamarckian learning in this context means to update the chromosome according to the improved solution found by the individual learning step, while Baldwinian learning leaves the chromosome unchanged and uses only the improved fitness. This pseudo code leaves open which steps are based on the fitness of the individuals and which are not. In question are the evolving of the new population and the selection of P(t); Compute the fitness f(p) choose a subset of Offspring: Recombine and mutate individuals Learning: Improve Evaluation: Compute the fitness p′ according to improvement P(t+1) by selecting some individuals from t=t+1; // Increment the generation counter end while Return best individual til, is the amount of computational budget allocated to an iteration of individual learning; i.e., the maximum computational budget allowable for individual learning to expend on improving a single solution.

Choice of Lamarckian or Baldwinian learning

edit

It is to be decided whether a found improvement is to work only by the better fitness (Baldwinian learning) or whether also the individual is adapted accordingly (lamarckian learning). In the case of an EA, this would mean an adjustment of the genotype. This question has been controversially discussed for EAs in the literature already in the 1990s, stating that the specific use case plays a major role. The background of the debate is that genome adaptation may promote premature convergence. This risk can be effectively mitigated by other measures to better balance breadth and depth searches, such as the use of structured populations.

Applications

edit

Memetic algorithms have been successfully applied to a multitude of real-world problems. Although many people employ techniques closely related to memetic algorithms, alternative names such as hybrid genetic algorithms are also employed.

Researchers have used memetic algorithms to tackle many classical NP problems. To cite some of them: graph partitioning, multidimensional knapsack, travelling salesman problem, quadratic assignment problem, set cover problem, minimal graph coloring, max independent set problem, bin packing problem, and generalized assignment problem.

More recent applications include (but are not limited to) business analytics and data science, training of artificial neural networks, pattern recognition, robotic motion planning, beam orientation, circuit design, electric service restoration, medical expert systems, single machine scheduling, automatic timetabling (notably, the timetable for the NHL), manpower scheduling, nurse rostering optimisation, processor allocation, maintenance scheduling (for example, of an electric distribution network), scheduling of multiple workflows to constrained heterogeneous resources, multidimensional knapsack problem, VLSI design, clustering of gene expression profiles, feature/gene selection and multi-class, multi-objective feature selection.

Recent activities in memetic algorithms

edit