Difference between exploration and exploitation in genetic algorithm

Question

In evolutionary algorithms two main abilities maintained which are Exploration and Exploitation.

In Exploration the algorithm searching for new solutions in new regions, while Exploitation means using already exist solutions and make refinement to it so it's fitness will improve.

In my case I am concern about genetic algorithm,and my question is I read many different article and I figured out three different explanation for the exploration and exploitation these views are as follow:

1. in one article it talks that exploration is done by crossover and exploitation done by mutation

2. in one article the inverse of first one, exploration by mutation and exploitation by crossover

3. and in last one which is a paper "On Evolutionary Exploration and Exploitation" (1998) by A. E. Eiben and C.A. Schippers, it says that exploitation is done through selection process, while exploration is done by operator whatever it is crossover or mutation

I see from my little point of view that both crossover and mutation gives us a new solution which was not there in the population which is the random part of the algorithm so it's exploration process ,and when selecting individuals for mating or reproduction I select from already existed solutions and according to it fitness which is the heuristic part so it exploitation.

Which is the correct one? Which step or operator responsible for exploration and which responsible of exploitation?

Please I need reasoning logical answer for that.

Blanks

Answer 1

Number 3 appears to be the correct explanation.

Crossover and mutation are both methods of exploring the problem space. Selection is used to exploit the 'good' genetic material in the current set.

However I think you are suggesting that these are two separate and diverse concepts when they are not. They are both methods of traversing the problem space, both are almost always used in conjunction. An algorithm should explore the problem space through crossover and mutation but it should do so by preferencing solutions near to other good solutions.

The trick is always in finding the right balance. Go too far into exploitation and you will get stuck in local maxima, go too far to exploration and you will waste time on solutions that are less likely to be good and ignore the information you have already gathered.

Fumikofumitory

i agree,and i understand the second half but i need explanation about "Go too far into exploitation and you will get stuck in local maxima" ,so if i can balance exploration by the crossover or mutation rate,so how i control exploitation as you mentioned in selection so not stuck in local maxima. – Blanks

in other word how to set the selection pressure. – Blanks

Usually you would balance it by altering the crossover and mutation rates but there are changes that you can make to the selection process. Use of different selection processes such as roulette wheel and tournament selection will give different amounts of selection pressure. Also eliminating the X lowest % of population is a common method of increasing exploitation (or conversely guaranteed selection for the best candidates). – Fumikofumitory

Answer 2

Crossover operator implements a depth search or exploitation, leaving the breadth search or exploration for the mutation operator:

(Source: https://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node1.html)

Crossover -> Exploitation (depth search but not breadth)

Mutation -> Exploration (Breadth search)

Suppose a genetic algorithm uses chromosomes of the form x = abcdefgh
with a fixed length of eight genes. Each gene can be any digit between 0
and 9. Let the fitness of individual x be calculated as:

f(x) = (a + b) − (c + d) + (e + f) − (g + h) 

and let the initial population consist of four individuals with the following
chromosomes:
x1 = 6 5 4 1 3 5 3 2
x2 = 8 7 1 2 6 6 0 1
x3 = 2 3 9 2 1 2 8 5
x4 = 4 1 8 5 2 0 9 4

The algorithm will never reach the optimal solution without mutation. Suppose, the optimal solution is x = 9 9 0 0 9 9 0 0. If mutation does not occur, then the only way to change genes is by applying the crossover operator. Regardless of the way crossover is performed, its only outcome is an exchange of genes of parents at certain positions in the chromosome. This means that the first gene in the chromosomes of children can only be either 6, 8, 2 or 4 (i.e. first genes of x1, x2, x3and x4 optimal), and because none of the individuals in the initial population begins with gene 9, the crossover operator alone will never be able to produce an offspring with gene 9 in the beginning.

(Source: http://www.eis.mdx.ac.uk/staffpages/rvb/teaching/BIS3226/sol15.pdf)

Marte

Answer 3

• Exploration – the want for a search method to find new areas of the search space which have not been visited yet
• Exploitation – the want for a search method to locally search about the best known areas in the space in order to refine these current solutions
• All search algorithms will have some mix of both properties
• Note that if we only have a limited number of objective tests available, then we have a zero-sum game – we can explore or we can search with a test

Vancouver