Genetic Algorithm for solving 8 queens problem in Python

g8.py

# Code by Farooq Karimi Zadeh under MIT/X11


import random
from typing import List, Tuple


Fitness = float

class Chromosome:
    possible_rows = tuple(2**i for i in range(8))
    def __init__(self, r: str):
        if len(r) != 64:
            raise ValueError("r must be a string of length 64 exactly")
        if r.replace("0", "").replace("1", "") != "":
            raise ValueError("r must be a binary string having only 1 or 0")

        self._board: List[int] = list()
        while len(r):
            self._board.append(int(r[:8], 2))
            r = r[8:]

    def fitness(self) -> Fitness:
        max_collisions: int = 64
        collisions: int = 0

        for i, row_a in enumerate(self._board):
            for j, row_b in enumerate(self._board):
                if row_a == row_b and i != j:
                    collisions += 1
        
        for i, row_a in enumerate(self._board):
            for j, row_b in enumerate(self._board):
                if i == j:
                    continue
                row_p1 = row_a << abs(i-j)
                row_p2 = row_a >> abs(i-j)
                if row_b == row_p1:
                    collisions += 1
                if row_b == row_p2:
                    collisions += 1

        return (max_collisions - collisions) / max_collisions

            
    def __add__(self, other):
        r0 = repr(self)
        r1 = repr(other)
        def cut(r: str, i: int) -> Tuple[str, str]:
            return r[:i], r[i:]
        
        cross_point: int = random.randrange(8, len(r0) - 1, 8)
        r0_left, r0_right = cut(r0, cross_point)
        r1_left, r1_right = cut(r1, cross_point)
        C = Chromosome
        return C(r0_left + r1_right), C(r1_left + r0_right)


    def __repr__(self) -> str:
        return "".join(bin(r).replace("0b", "").zfill(8) for r in self._board)
    
    def mutate(self):
        i = random.choice(self.possible_rows)
        j = random.randint(0, len(self._board) - 1)
        self._board[j] = i

    @staticmethod
    def rand():
        ch = Chromosome("0"*64)
        ch._board = list()
        for _ in range(8):
            ch._board.append(random.choice(Chromosome.possible_rows))
        return ch


class GA8:
    def __init__(self, pop_size: int, max_gen: int, mutation_rate: float):
        self._population: List[Chromosome] = []
        self.max_gen: int = max_gen
        self.mutation_rate: float = mutation_rate
        
        for _ in range(pop_size):
            self._population.append(Chromosome.rand())

    def run(self):
        for generation in range(self.max_gen):
            print("Gen:", generation)
            evaled: List[Tuple[Chromosome, Fitness]] = [(C, C.fitness()) for C in self._population]
            offsprings: List[Tuple[Chromosome, Fitness]] = list()
            for index, ch_ft in enumerate(evaled[:-1]):
                next_ch, _ = evaled[index+1]
                ch = ch_ft[0]
                of0, of1 = ch + next_ch
                of0_ft = of0.fitness()
                of1_ft = of1.fitness()
                offsprings.append((of0, of0_ft))
                offsprings.append((of1, of1_ft))

            total: list = evaled + offsprings
            total.sort(key=lambda e: e[1], reverse=True)
            total = total[:len(self._population)]
            total = [ch[0] for ch in total]
            self._population = total[:len(self._population)]
            for ch in self._population:
                if random.random() <= self.mutation_rate:
                    ch.mutate()
            if self._population[0].fitness() == 1.0:
                break
            print("Best ft:", self._population[0].fitness())

    def best(self):
        return max(self._population, key=lambda ch: ch.fitness())