Podręcznik

W przypadku algorytmów genetycznych - to co Wam pokażę to rozwiązanie problemu dyskretnego - problemu komiwojażera. Zaczniemy od definicji problemu:

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_points = 50

points_coordinate = np.random.rand(num_points, 2)
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')

def cal_total_distance(routine):
    '''Funkcja celu. Parametrem wejściowym jest trasa, zwracana jest jej długość
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
    

W następnym kroku uruchamiany jest algorytm genetyczny. My stosujemy wersję dedykowaną do optymalizacji permutyzacyjnej - kiedy genom jest zakodowany w formie listy.

• func - funkcja celu 
• n_dim - liczba wymiarów funkcji celu
• size_pop - wielkość populacji
• max_iter - liczba iteracji 
•  prob_mut - prawdopodobieństwo mutacji

from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=1000, prob_mut=1)
best_points, best_distance = ga_tsp.run()

Pozostaje nam narysowanie wyników

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()