1 10-Hybridization

1.1 Hybridization with Other Techniques

1.2 Memetic Algorithms

2 Why Hybridize

Might want to put in EA as part of larger system

Might be looking to improve on existing techniques but not re-invent wheel

Might be looking to improve EA search for good solutions

3 Why Hybridize Michalewicz’s view on EAs in context


4 What is a Memetic Algorithm?

The combination of Evolutionary Algorithms with Local Search Operators that work within the EA loop has been termed “Memetic Algorithms”

Term also applies to EAs that use instance-specific knowledge in operators

Memetic Algorithms have been shown to be orders of magnitude faster and more accurate than EAs on some problems, and are the “state of the art” on many problems

5 Where to Hybridize:

A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing 2014, Chapter 7

6 Incorporating good solutions: Heuristics for Initialising Population

7 Incorporating good solutions: Initialisation Issues

8 Incorporating good solutions: “Intelligent” Operators

9 Incorporating good solutions Local Search Acting on Offspring

Can be viewed as a sort of “lifetime learning”

Lots of early research done using EAs to evolve the structure of Artificial Neural Networks and then Back-propagation to learn connection weights

Often used to speed-up the “endgame” of an EA by making the search in the vicinity of good solutions more systematic than mutation alone

10 Local Search and graphs: Local Search

11 Local Search and graphs: Landscapes & Graphs

12 Local Search and graphs: Example Graphs for Binary Problems

13 Local Search and graphs: Graphs

14 Local Search and graphs: Pivot Rules

Is the neighbourhood searched randomly, systematically or exhaustively ?

does the search stop as soon as a fitter neighbour is found ( Greedy Ascent )

or is the whole set of neighbours examined and the best chosen ( Steepest Ascent )

of course there is no one best answer, but some are quicker than others to run ……..

15 Local Search and graphs: Variations of Local Search

16 Local Search and graphs: Two Models of Lifetime Adaptation

17 Local Search and graphs: The Baldwin effect

18 Local Search and graphs: Induced landscapes

Baldwin landscape

19 Local Search and graphs: Information Use in Local Search

20 Diversity

21 Diversity: Boltzman MAs: acceptance criteria (1/2)

22 Choice of Operators

There are theoretical advantages to using a local search with a move operator that is DIFFERENT to the move operators used by mutation and crossover cf. Krasnogor (2002)

Can be helpful since local optimum on one landscape might be point on a slope on another

Easy implementation is to use a range of local search operators, with mechanism for choosing which to use. (Similar to Variable Neighbourhood Search)

This could be learned & adapted on-line (e.g. Krasnogor & Smith 2001)

23 Hybrid Algorithms Summary

It is common practice to hybridize EA’s when using them in a real world context.

This may involve the use of operators from other algorithms which have already been used on the problem (e.g. 2-opt for TSP), or the incorporation of domain-specific knowledge (e.g. PSP operators)

Memetic algorithms have been shown to be orders of magnitude faster and more accurate than GAs on some problems, and are the “state of the art” on many problems

24 Adaptive Memetic Algorithm

25 Adaptive Memetic Algorithm MA generations

26 Warning: Memetic Overkill