TSP: Ewolucja Drogi (Algorytm Genetyczny)

1. Anatomia Cyfrowej Ewolucji

Algorytm genetyczny nie operuje na jednej trasie. On zarządza całym "społeczeństwem" rozwiązań, które z każdą sekundą staje się mądrzejsze.

2. Wizualizacja: Ewolucja w akcji

Poniżej widzisz symulację GA. Cienkie linie to "duchy" odrzuconych możliwości, a świecąca, neonowa linia to aktualny Lider Populacji (dzięki elityzmowi). Zauważ, jak licznik generacji rośnie, a trasa staje się coraz bardziej logiczna.

3. Implementacja w Pythonie (z Elityzmem)

Poniżej znajdziesz profesjonalną strukturę algorytmu. Zwróć uwagę na funkcję evolve, gdzie elity są traktowane priorytetowo.

import random
import numpy as np

class GeneticTSP:
    def __init__(self, cities, pop_size=100, elite_size=2):
        self.cities = cities
        self.pop_size = pop_size
        self.elite_size = elite_size
        # Populacja to teraz lista par: [trasa, fitness]
        self.population = []
        for _ in range(pop_size):
            tour = random.sample(range(len(cities)), len(cities))
            self.population.append([tour, self.calculate_fitness(tour)])

    def calculate_fitness(self, tour):
        """Oblicza fitness tylko raz dla danej trasy."""
        dist = 0
        for i in range(len(tour)):
            c1 = self.cities[tour[i]]
            c2 = self.cities[tour[(i + 1) % len(tour)]]
            # Formuła euklidesowa: sqrt((x1-x2)^2 + (y1-y2)^2)
            dist += np.sqrt((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2)
        return 1 / dist

    def evolve(self):
        # 1. Sortujemy gotowe wyniki (fitness mamy już policzony)
        self.population.sort(key=lambda x: x[1], reverse=True)
        
        # 2. Elityzm
        new_pop = self.population[:self.elite_size]
        
        # 3. Rozmnażanie
        while len(new_pop) < self.pop_size:
            # Wybieramy rodziców (pobieramy tylko trasy z par [trasa, fitness])
            p1_data, p2_data = random.choices(self.population[:50], k=2)
            parent1, parent2 = p1_data[0], p2_data[0]
            
            child_tour = self.crossover(parent1, parent2)
            
            if random.random() < 0.05: # Zwiększyłem szansę na mutację do 5%
                self.mutate(child_tour)
            
            # Obliczamy fitness dla NOWEGO dziecka raz i zapisujemy w parze
            new_pop.append([child_tour, self.calculate_fitness(child_tour)])
            
        self.population = new_pop

    def crossover(self, p1, p2):
        a, b = sorted(random.sample(range(len(p1)), 2))
        child = [None] * len(p1)
        child[a:b] = p1[a:b]
        
        ptr = 0
        for city in p2:
            if city not in child:
                while child[ptr] is not None: 
                    ptr += 1
                child[ptr] = city
        return child

    def mutate(self, tour):
        i, j = random.sample(range(len(tour)), 2)
        tour[i], tour[j] = tour[j], tour[i]

    def get_best(self):
        # Zwraca najlepszą trasę i jej dystans
        best_tour, best_fitness = self.population[0]
        return best_tour, 1 / best_fitness

4. Matematyka "Przetrwania Najsilniejszych"

Fundamentem jest Funkcja Przystosowania (Fitness Function). Musi ona jednoznacznie premiować krótsze rozwiązania, aby ewolucja wiedziała, w którym kierunku podążać.

5. Zastosowania w przemyśle

Choć nazwa brzmi jak dylemat sprzedawcy, ten algorytm steruje dzisiejszym światem:

• Logistyka: Planowanie tras kurierów DHL czy InPost (oszczędności rzędu milionów litrów paliwa).
• Mikroprocesory: Optymalizacja ścieżek lasera przy wypalaniu obwodów scalonych.
• Astronomia: Planowanie ruchu teleskopów kosmicznych między obserwowanymi obiektami.