Classic Computer Science Problems in Python – GeneticAlgorithm – SimpleEquation

main.py

from __future__ import annotations
from copy import deepcopy
from enum import Enum
from functools import reduce
from heapq import nsmallest
from itertools import tee
from math import radians, sqrt, sin, cos, atan2
from random import choices, random, shuffle, randrange
from statistics import mean
from operator import add


class GeneticAlgorithm:

    SelectionType = Enum('SelectionType', 'ROULETTE TOURNAMENT')

    def __init__(self,
                 initial_population,
                 threshold,
                 max_generations=100,
                 mutation_chance=0.01,
                 crossover_chance=0.7,
                 selection_type=SelectionType.ROULETTE):
        self._population = initial_population
        self._threshold = threshold
        self._max_generations = max_generations
        self._mutation_chance = mutation_chance
        self._crossover_chance = crossover_chance
        self._selection_type = selection_type
        self._fitness_key = type(self._population[0]).fitness

    def _pick_roulette(self, wheel):
        return tuple(choices(self._population, weights=wheel, k=2))

    def _pick_tournament(self, num_participants):
        participants = choices(self._population, k=num_participants)
        return tuple(nsmallest(2, participants, key=self._fitness_key))

    def _reproduce_and_replace(self):
        new_population = []
        while len(new_population) < len(self._population):
            if self._selection_type == GeneticAlgorithm.SelectionType.ROULETTE:
                parents = self._pick_roulette(
                    [individual.fitness() for individual in self._population])
            else:
                parents = self._pick_tournament(len(self._population) // 2)
            if random() < self._crossover_chance:
                new_population.extend(parents[0].crossover(parents[1]))
            else:
                new_population.extend(parents)
        if len(new_population) > len(self._population):
            new_population.pop()
        self._population = new_population

    def _mutate(self):
        for individual in self._population:
            if random() < self._mutation_chance:
                individual.mutate()

    def perform(self):
        best = min(self._population, key=self._fitness_key)
        for generation in range(self._max_generations):
            if best.fitness() <= self._threshold:
                return best
            print(f'[{generation}] Best {best.fitness()} Avg {mean(map(self._fitness_key, self._population))}')
            self._reproduce_and_replace()
            self._mutate()
            lower = min(self._population, key=self._fitness_key)
            if lower.fitness() < best.fitness():
                best = lower
        return best


class Point:
    def __init__(self, name, latitude, longitude):
        self._name = name
        self._latitude = latitude
        self._longitude = longitude

    def coordinates(self):
        return self._latitude, self._longitude

    def __eq__(self, other):
        if isinstance(other, Point):
            return self.__dict__ == other.__dict__
        return False

    def __hash__(self):
        return hash(frozenset(self.__dict__.items()))

    def __repr__(self):
        return self._name.split(' - ')[1]


class Route:
    def __init__(self, route):
        self._route = route

    def fitness(self):
        edges_distances_in_km = map(self._distance,
                                    self._pairwise(self._route))
        return reduce(add, edges_distances_in_km)

    def _pairwise(self, route):
        origin, destination = tee(route)
        next(destination, None)
        return zip(origin, destination)

    def _distance(self, edge):
        origin, destination = edge
        origin_latitude, origin_longitude = origin.coordinates()
        destination_latitude, destination_longitude = destination.coordinates()
        earth_radius_in_km = 6371

        delta_latitude = radians(destination_latitude - origin_latitude)
        delta_longitude = radians(destination_longitude - origin_longitude)
        delta_arch = (sin(delta_latitude / 2) * sin(delta_latitude / 2) +
                      cos(radians(origin_latitude)) *
                      cos(radians(destination_latitude)) *
                      sin(delta_longitude / 2) * sin(delta_longitude / 2))
        return earth_radius_in_km * 2 * atan2(sqrt(delta_arch),
                                              sqrt(1 - delta_arch))

    @classmethod
    def random_instance(cls, points):
        route = deepcopy(points)
        shuffle(route)
        return Route(route)

    def crossover(self, other):
        child1 = deepcopy(self)
        child2 = deepcopy(other)
        index_cut = randrange(len(self._route))
        child1._route = list(dict.fromkeys(self._route[:index_cut] + other._route))
        child2._route = list(dict.fromkeys(other._route[:index_cut] + self._route))
        return child1, child2

    def mutate(self):
        shuffle(self._route)

    def __repr__(self):
        return ', '.join(map(str, self._route))

BRAZIL_CAPITALS = [
    Point('Aracaju - SE', -10.9095, -37.0748),
    Point('Belém - PA', -1.45502, -48.5024),
    Point('Belo Horizonte - MG', -19.8157, -43.9542),
    Point('Boa Vista - RR', 2.81954, -60.6714),
    Point('Brasília - DF', -15.7801, -47.9292),
    Point('Campo Grande - MS', -20.4435, -54.6478),
    Point('Cuiabá - MT', -15.5989, -56.0949),
    Point('Curitiba - PR', -25.4284, -49.2733),
    Point('Florianópolis - SC', -27.5969, -48.5495),
    Point('Fortaleza - CE', -3.71839, -38.5434),
    Point('Goiânia - GO', -16.6799, -49.255),
    Point('João Pessoa - PB', -7.11532, -34.861),
    Point('Macapá - AP', 0.0344566, -51.0666),
    Point('Maceió - AL', -9.66625, -35.7351),
    Point('Manaus - AM', -3.10719, -60.0261),
    Point('Natal - RN', -5.79448, -35.211),
    Point('Palmas - TO', -10.1689, -48.3317),
    Point('Porto Alegre - RS', -30.0277, -51.2287),
    Point('Porto Velho - RO', -8.76183, -63.902),
    Point('Recife - PE', -8.05428, -34.8813),
    Point('Rio Branco - AC', -9.974, -67.8076),
    Point('Rio de Janeiro - RJ', -22.9035, -43.2096),
    Point('Salvador - BA', -12.9704, -38.5124),
    Point('São Luís - MA', -2.53073, -44.3068),
    Point('São Paulo - SP', -23.5489, -46.6388),
    Point('Teresina - PI', -5.08921, -42.8016),
    Point('Vitória - ES', -20.3222, -40.3381)
]

if __name__ == '__main__':
    initial_population = [
        Route.random_instance(BRAZIL_CAPITALS) for _ in range(20)
    ]
    algorithm = GeneticAlgorithm(initial_population=initial_population,
                                 threshold=25000.0,
                                 max_generations=100,
                                 mutation_chance=0.2,
                                 crossover_chance=0.7,
                                 selection_type=GeneticAlgorithm.SelectionType.ROULETTE)
    route = algorithm.perform()
    print(route, route.fitness())