--Notebook.html---

import random #geneating random chromosomes def random_chromosome(size): return [ random.randint(1, nq) for _ in range(nq) ] #fitness function, calculating number of queen pairs not attacking each other. def fitness(chromosome): horizontal_collisions = sum([chromosome.count(queen)-1 for queen in chromosome])/2 diagonal_collisions = 0 n = len(chromosome) left_diagonal = [0] * 2*n right_diagonal = [0] * 2*n for i in range(n): left_diagonal[i + chromosome[i] - 1] += 1 right_diagonal[len(chromosome) - i + chromosome[i] - 2] += 1 diagonal_collisions = 0 for i in range(2*n-1): counter = 0 if left_diagonal[i] > 1: counter += left_diagonal[i]-1 if right_diagonal[i] > 1: counter += right_diagonal[i]-1 diagonal_collisions += counter / (n-abs(i-n+1)) return int(maxFitness - (horizontal_collisions + diagonal_collisions)) #28-(2+3)=23 def probability(chromosome, fitness): return fitness(chromosome) / maxFitness def random_pick(population, probabilities): populationWithProbabilty = zip(population, probabilities) total = sum(w for c, w in populationWithProbabilty) r = random.uniform(0, total) upto = 0 for c, w in zip(population, probabilities): if upto + w >= r: return c upto += w assert False, "Shouldn't get here" def reproduce(x, y): #doing cross_over between two chromosomes n = len(x) c = random.randint(0, n - 1) return x[0:c] + y[c:n] def mutate(x): #randomly changing the value of a random index of a chromosome n = len(x) c = random.randint(0, n - 1) m = random.randint(1, n) x[c] = m return x def genetic_queen(population, fitness): mutation_probability = 0.05 new_population = [] probabilities = [probability(n, fitness) for n in population] for i in range(len(population)): x = random_pick(population, probabilities) #best chromosome 1 y = random_pick(population, probabilities) #best chromosome 2 child = reproduce(x, y) #creating two new chromosomes from the best 2 chromosomes if random.random()   10. [1 pt] The Genetic Algorithm N Queens [Notebook, html] posted on Canvas shows example of using genetic algorithm to solve N-Queens problem. Use Notebook as the selection code, answer following questions, and implement respective tasks. a. For the same number of Queens (E.g., N=16 ), comparing speed between hill-climbing vs. genetic algorithm, explain why genetic algorithm is much slower than hill-climbing algorithm [0.25pt] b. One problem of genetic algorithm is that the cross-over and mutation process may generate off-spring whose genetic code is not a permutation (i.e., a clear attack case to the N-Queens) problem. For example, genetic code "23813754" is not a permutation, because there are two queens in a row (or column) [there are two "3"], and it also misses 8. Propose a solution to generate off-spring whose genetic code is a permutation [0.25] c. Implement your algorithm and compare its performance vs. the original genetic algorithm to solve N=16 queens problem (repeat 5 times and report average runtime). [0.5pt]