Write an evolutionary algorithm to solve the Eight Queen puzzle.

FILL IN THE MISSING CODE in Python.

# initialization.py-Complete this method that generates a population of permutations # evaluation.py-Complete this method that evaluates the fitness of a permutation # mutation.py-Complete this method that implements the swap mutation for a permutation. # recombination.py-Complete this method that implements the cut-and-crossfill recombination for two chosen permutations

*************************** *****initialization.py*****

# initialize a population of permutation def permutation (pop_size, chrom_length): population = [] # code begin

# code end return population

*********************** *****evaluation.py***** # compute fitness of an invidual for the 8-queen puzzle def fitness_8queen (individual): # maximization M = 28 check = 0 # code begin

# code end return M - check

********************* *****mutation.py*****

# mutate a permutation def permutation_swap (individual): mutant = individual.copy() # code begin

# code end return mutant

************************** *****recombination.py*****

# cut-and-crossfill crossover for permutations def permutation_cut_and_crossfill (parent1, parent2): offspring1 = [] offspring2 = [] # code begin

# code end return offspring1, offspring2

***************** *****main.py*****

# A genetic algorithm for Eight Queen puzzle # representation, fitness evalution, mutation, and crossover

import random import numpy

import initialization import evaluation import recombination import mutation

def main(): # random.seed(0) # numpy.random.seed(0)

string_length = 8 popsize = 4 mating_pool_size = int(popsize*0.5) # has to be even mut_rate = 1 xover_rate = 0.9

# initialize population population = initialization.permutation(popsize, string_length) fitness = [] print("Initial population:") for i in range (0, popsize): fitness.append(evaluation.fitness_8queen(population[i])) print(i, ":", population[i],"fitness:", fitness[i])

# pick parents parents_index = random.sample(range(0,popsize), mating_pool_size) print("Parents:") for i in range (0, len(parents_index)): print(parents_index[i], ":", population[parents_index[i]]) # reproduction offspring =[] i=0 # offspring are generated using selected parents in the mating pool while len(offspring) < mating_pool_size: # recombination if random.random() < xover_rate: off1,off2 = recombination.permutation_cut_and_crossfill(population[parents_index[i]], population[parents_index[i+1]]) else: off1 = population[parents_index[i]].copy() off2 = population[parents_index[i+1]].copy()

# print offspring after recombination print("After xover:") print(off1,"fitness:", evaluation.fitness_8queen(off1)) print(off2,"fitness:", evaluation.fitness_8queen(off2)) if random.random() < mut_rate: off1 = mutation.permutation_swap(off1) if random.random() < mut_rate: off2 = mutation.permutation_swap(off2) # print offspring after mutation print("After mutation:") print(off1,"fitness:", evaluation.fitness_8queen(off1)) print(off2,"fitness:", evaluation.fitness_8queen(off2))

offspring.append(off1) offspring.append(off2)

# end of main

main()