N-Queens Problem

 1from deap_er import creator
 2from deap_er import tools
 3from deap_er import base
 4import random
 5import numpy
 6
 7
 8random.seed(1234)  # disables randomization
 9
10BOARD_SIZE = 20
11
12
13def evaluate(individual):
14    size = len(individual)
15    left_diagonal = [0] * (2 * size - 1)
16    right_diagonal = [0] * (2 * size - 1)
17
18    for i in range(size):
19        l_idx = i + individual[i]
20        left_diagonal[l_idx] += 1
21        r_idx = size - 1 - i + individual[i]
22        right_diagonal[r_idx] += 1
23
24    sum_ = 0
25    for i in range(2*size-1):
26        if left_diagonal[i] > 1:
27            sum_ += left_diagonal[i] - 1
28        if right_diagonal[i] > 1:
29            sum_ += right_diagonal[i] - 1
30
31    return sum_,  # The comma is essential here.
32
33
34def setup():
35    creator.create("FitnessMin", base.Fitness, weights=(-1.0,))
36    creator.create("Individual", list, fitness=creator.FitnessMin)
37
38    toolbox = base.Toolbox()
39    toolbox.register("permutation", random.sample, range(BOARD_SIZE), BOARD_SIZE)
40    toolbox.register("individual", tools.init_iterate, creator.Individual, toolbox.permutation)
41    toolbox.register("population", tools.init_repeat, list, toolbox.individual)
42    toolbox.register("mate", tools.cx_partially_matched)
43    toolbox.register("mutate", tools.mut_shuffle_indexes, mut_prob=2.0 / BOARD_SIZE)
44    toolbox.register("select", tools.sel_tournament, contestants=3)
45    toolbox.register("evaluate", evaluate)
46
47    stats = tools.Statistics(lambda ind: ind.fitness.values)
48    stats.register("Avg", numpy.mean)
49    stats.register("Std", numpy.std)
50    stats.register("Min", numpy.min)
51    stats.register("Max", numpy.max)
52
53    return toolbox, stats
54
55
56def print_results(best_ind):
57    if not best_ind.fitness.values == (0.0,):
58        raise RuntimeError('Evolution failed to converge.')
59    print(f'\nRow numbers for each queen on each column of the chessboard: \n{best_ind}')
60    print(f'\nEvolution converged correctly.')
61
62
63def main():
64    toolbox, stats = setup()
65    pop = toolbox.population(size=300)
66    hof = tools.HallOfFame(1)
67    args = dict(
68        toolbox=toolbox,
69        population=pop,
70        generations=400,
71        cx_prob=0.6,
72        mut_prob=0.3,
73        hof=hof,
74        stats=stats,
75        verbose=True  # prints stats
76    )
77    tools.ea_simple(**args)
78    print_results(hof[0])
79
80
81if __name__ == "__main__":
82    main()