[go: up one dir, main page]
Scribd
Upload
27 views3 pages

GA Example

The document outlines a genetic algorithm (GA) approach to solving the 8-Queen problem and maximizing a function. It details the steps of initialization, selection, crossover, mutation, and survival, including specific examples of chromosomes and their fitness calculations. The process is iterative, aiming to evolve solutions until a valid configuration with no attacking pairs is found for the 8-Queen problem and optimal values for the function are achieved.

Uploaded by

grabby173041
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
27 views3 pages

GA Example

The document outlines a genetic algorithm (GA) approach to solving the 8-Queen problem and maximizing a function. It details the steps of initialization, selection, crossover, mutation, and survival, including specific examples of chromosomes and their fitness calculations. The process is iterative, aiming to evolve solutions until a valid configuration with no attacking pairs is found for the 8-Queen problem and optimal values for the function are achieved.

Uploaded by

grabby173041
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

1.

Initialization of Population
2. Selection
3. Crossover/Recombination
4. Mutation
5. Survival/Accept

1. Solving 8-Queen Using GA


Place 8 queens on an 8×8 chessboard so that no two queens attack each other.

A) Initial Population (Chromosomes)

Each chromosome is an array where the index is the column (1–8) and the value is the row (1–8).

Chromosome (state) Representation Attacking Pairs Non-Attacking (max 28)


Chromosome 1 1 6 2 5 7 4 8 3 4 24
Chromosome 2 2 4 7 3 6 8 5 1 5 23
Chromosome 3 5 3 1 6 8 4 2 7 8 20
Chromosome 4 6 1 3 2 8 7 5 4 17 11
Step 1: Fitness Calculation

Total fitness sum = 24 + 23 + 20 + 11 = 78

Fitness Probabilities:

 Chromosome 1: 24/78 = 31%


 Chromosome 2: 23/78 ≈ 29%
 Chromosome 3: 20/78 ≈ 26%
 Chromosome 4: 11/78 ≈ 14%

Step 2: Selection

Randomly select 2 parents, say:

 Parent 1 = 1 6 2 5 7 4 8 3
 Parent 2 = 2 4 7 3 6 8 5 1
Step 3: Crossover

Suppose crossover happens at position 4.

 Offspring = First 4 genes from Parent 1 + last 4 from Parent 2


 Child = 1 6 2 5 | 6 8 5 1

Step 4: Mutation

Mutation might occur in 1 gene. Suppose column 6 (value = 8) mutates to row = 7.

 Mutated Child = 1 6 2 5 6 7 5 1

Step 5: Repeat

This new child is evaluated, added to the next generation, and the process repeats.

Final Goal:

Eventually, a chromosome like 1 5 8 6 3 7 2 4 appears, with:

 0 Attacking Pairs
 Fitness = 28

Valid 8-Queen solution found!

2
x
2. Maximize f ( x )= −3 x , when x in [0 to 31]
2

Binary Encoding – 5 digits


1. Initialization of Population
2. Selection
3. Crossover/Recombination
4. Mutation
5. Survival/Accept

Update Population

1. Selection (Let us take 6 chromosomes in initial population)

String Initial x 2 Probability Bin


x
No Population f ( x )= −3 x
2
1 [1,0,0,1,0] 18 108 0.211 0.001-0.211
2 [1,0,0,1,1] 19 123.5 0.242 0.212-0.453
3 [1,0,1,1,1] 23 195.5 0.383 0.454-0.836
4 [0,1,1,1,0] 14 56 0.110 0.837-0.946
5 [0,0,1,0,1] 5 0 [if negative] 0 ---
6 [0,1,0,1,1] 11 27.5 0.054 0.947-1.00
Total 510.5 1.00

Let us select 4 parents and perform 2. crossover and 3. mutation

Random Selected Chosen Offspring after Offspring after


Number Bin No. Parent Crossover at random point Mutation (1% chance)
0.54 3 [1,0,1,1,1] [1,0,1,1,0] [1,1,1,1,0]
0.88 4 [0,1,1,1,0] [0,1,1,1,1] [0,1,1,1,1]
0.45 2 [1,0,0,1,1] [1,0,0,1,0] [1,0,0,1,0]
0.20 1 [1,0,0,1,0] [1,0,0,1,1] [1,0,0,1,1]
4. Accept/Survival

Offspring x Fitness, f(x)


[1,1,1,1,0] 30 360
[0,1,1,1,1] 15 67.5
[1,0,0,1,0] 18 108
[1,0,0,1,1] 19 123.5

[Select survivors and add to population]

Updated Population:

String Initial
No Population
1 [1,0,0,1,0]
2 [1,0,0,1,1]
3 [1,0,1,1,1]
4 [0,1,1,1,0]
5 [0,0,1,0,1]
6 [0,1,0,1,1]
7 [1,1,1,1,0]

Check termination [Condition]

New Cycle:

You might also like