ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ЗАДАЧА КОММИВОЯЖЕРА PYTHON

Генетический алгоритм – это эвристический алгоритм поиска, который использует принципы наследственности и естественного отбора для решения задач оптимизации. Одной из таких задач является задача коммивояжера, то есть поиск кратчайшего маршрута, который проходит через все города, при условии, что каждый город посещается только один раз, а маршрут начинается и заканчивается в одном и том же городе.

Для решения задачи коммивояжера с помощью генетического алгоритма нужно определить представление решения (индивида), функцию приспособленности, операторы генетических вариации и штрафные функции для валидации решений.

Пример кода решения задачи коммивояжера на Python:

import numpy as np
from scipy.spatial import distance_matrix

class TSP_GA:
        def __init__(self, coords, pop_size=100, elite_size=20, mutation_rate=0.1, generations=500):
                self.coords = coords
                self.pop_size = pop_size
                self.elite_size = elite_size
                self.mutation_rate = mutation_rate
                self.generations = generations
        
                self.dist_matrix = distance_matrix(coords, coords)
        
                self.best_solution = []
                self.best_distance = np.inf
        
                self.population = self.create_population()
    
        def create_population(self):
        population = []
        for i in range(self.pop_size):
            solution = np.random.permutation(len(self.coords))
            population.append(solution)
        return population

    def rank_routes(self):
        distances = []
        for i in range(len(self.population)):
            dist = self.distance(self.population[i])
            distances.append((i, dist))
        return sorted(distances, key=lambda x: x[1])

    def distance(self, solution):
        route_distance = 0
        for i in range(len(solution)):            
            if i == len(solution)-1:
                from_city = solution[i]
                to_city = solution[0]
            else:
                from_city = solution[i]
                to_city = solution[i+1]
            route_distance += self.dist_matrix[from_city][to_city]
        return route_distance

    def select_parents(self):
        parents = []
        for i in range(self.elite_size):
            parents.append(self.population[self.ranked_routes[i][0]])
        for i in range(len(self.population)-self.elite_size):
            parent1 = self.tournament_selection()
            parent2 = self.tournament_selection()
            parents.append(parent1)
            parents.append(parent2)
        return parents

    def breed_population(self):
        children = []
        parents = self.select_parents()
        num_new = len(self.population) - len(parents)
        for i in range(len(parents)):
            child = self.crossover(parents[i % len(parents)], parents[(i+1) % len(parents)])
            children.append(child)
        for i in range(num_new):
            child = np.random.permutation(len(self.coords))
            children.append(child)
        return children

    def crossover(self, parent1, parent2):
        start = np.random.randint(len(parent1))
        end = np.random.randint(start, len(parent1))
        child = [-1] * len(parent1)
        for i in range(start, end+1):
            child[i] = parent1[i]
        remaining_cities = [x for x in parent2 if x not in child]
        count = 0
        for i in range(len(child)):
            if child[i] == -1:
                child[i] = remaining_cities[count]
                count += 1
        return child

    def mutate_population(self, population):
        for i in range(len(population)):
            if np.random.rand() < self.mutation_rate:
                ind1 = np.random.randint(len(population[i]))
                ind2 = np.random.randint(len(population[i]))
                pop[i][ind1], pop[i][ind2] = pop[i][ind2], pop[i][ind1]
        return population

    def evolve(self):
        for i in range(self.generations):
            self.ranked_routes = self.rank_routes()
            elite = [self.population[x[0]] for x in self.ranked_routes][:self.elite_size]
            self.population = self.breed_population()
            self.population.extend(elite)
            self.population = self.mutate_population(self.population)
            if self.distance(self.population[0]) < self.best_distance:
                self.best_solution = self.population[0]
                self.best_distance = self.distance(self.population[0])
            print(f'Generation: {i}; Best distance: {self.best_distance}')

coords = np.random.random((25,2))
tsp = TSP_GA(coords)
tsp.evolve()

Выполнение данного кода позволит найти кратчайший маршрут для 25 городов, однако алгоритм также работает для меньшего или большего количества городов.