Solving N-Queen Problem Using Genetic Algorithm

Solving the N-Queen problem involves placing queens on a chessboard in such a way that they cannot check each other. The genetic algorithm approach addresses this problem through representations like phenotype and genotype, fitness evaluation based on queen penalties, mutations involving permutations, recombination to create new permutations, and selection of parents and survivors. This method provides a systematic and efficient way to solve the 8-queens problem.

• Genetic Algorithm
• N-Queens
• Chessboard
• Fitness Evaluation
• Problem Solving

darasmo Follow

Uploaded on Sep 22, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. N-Queen Problem Solving By Genetic Algorithm

2. Example: the 8 queens problem Place 8 queens on an 8x8 chessboard in such a way that they cannot check each other

3. The 8 queens problem: representation Phenotype: a board configuration Genotype: a permutation of the numbers 1 - 8 Obvious mapping 1 3 5 2 6 4 7 8

4. 8 Queens Problem: Fitness evaluation Penalty of one queen: the number of queens she can check. Penalty of a configuration: the sum of the penalties of all queens. Note: penalty is to be minimized Fitness of a configuration: inverse penalty to be maximized

5. The 8 queens problem: Mutation Small variation in one permutation, e.g.: swapping values of two randomly chosen positions, 1 3 5 2 6 4 7 8 1 3 7 2 6 4 5 8

6. The 8 queens problem: Recombination Combining two permutations into two new permutations: choose random crossover point copy first parts into children create second part by inserting values from other parent: in the order they appear there beginning after crossover point skipping values already in child 4 8 1 3 5 2 6 7 8 1 3 5 4 2 7 6 2 1 8 7 6 5 4 3 1 8 7 6 2 4 3 5

7. The 8 queens problem: Selection Parent selection: Pick 5 parents and take best two to undergo crossover Survivor selection (replacement) When inserting a new child into the population, choose an existing member to replace by: sorting the whole population by decreasing fitness enumerating this list from high to low replacing the first with a fitness lower than the given child

8. 8 Queens Problem: summary Note that this is only one possible set of choices of operators and parameters