Question

Artificial Intelligence homework. Please answer correctly.

3. Assume you were asked to place 8 queens on an 8x8 chessboard such that no two queens can attack each other (i.e. share the same row, column, or diagonal). Please introduce a solution to use genetic algorithm to solve the game. Please explain the encoding of the state for genetic algorithm (i.e., the representation of the chromosome), the fitness function, the cross over, and the mutation process. [1 pt].

Answer 1

• Initialization : The initialization contains of the randomly distributed population that is generated. Lower population size will lead to lots of time in computation of approximate solution. And higher value will cause internal iterations to increase. Therefore choose population size carefully. In this example we have tried with population size of 100 , 500 and 1000
• Selection of parents: Just as evolutionary biology requires two parents to undergo meiosis, so does GA. Therefore there is need to select two parents which determine a child. The calculation in determining the parents is elaborated later
• CrossOver / Reproduction : Once parents having high fitness are selected, crossover essentially marks the recombining of genetic materials / chromosomes to produce a healthy offspring
• Mutation : Mutation may or maynot occur. In case mutation occurs, it forces a random value of child to change , thereby shifting the algorithm in either a positive or negative route
• Generation of new population : For all population, a child must be computed. Therefore, the new population can be said to be a list dynamically populated by the children computed.

Solution to use genetic algorithm to solve the game:

function Genetic-Algorithm( population, Fitness-fn) returns an individual
    inputs: population -> set of individuals
            Fitness-fn -> a function that measures the fitness of an individual

    repeat
        parents <-- Select parents from Population
        population <-- Offsprings created by parents

    repeat until desired fit individual is obtained

return the best individual in the population

Fitness fn : The fitness fn is proportional to the number of clashes amongst the queens. If seen, there are 28 clashes possible in an 8 x 8 chessboard. Therefore, if an individual has high fitness, I can say that it will have lower number of clashes.

Let clashes=number of clashing queensLet clashes=number of clashing queens

∴fitness=28−clashes∴fitness=28−clashes

Then, any individual with the maximum fitness will be having least number of clashes.