Algorytmy genetyczne

9.1 Wprowadzenie do algorytmów genetycznych.

Algorytmy genetyczne (GA) to metoda optymalizacji i wyszukiwania inspirowana procesem doboru naturalnego, która imituje biologiczne procesy ewolucyjne.

Algorytmy genetyczne stosuje się do rozwiązywania złożonych zadań, gdzie tradycyjne metody mogą być nieskuteczne. Te algorytmy wykorzystują mechanizmy selekcji, krzyżowania (crossover) i mutacji do ewolucji rozwiązań.

Zasady działania:

1. Inicjalizacja:

Tworzona jest początkowa populacja możliwych rozwiązań (chromosomów). Każde rozwiązanie jest kodowane w postaci ciągu (ciąg bitowy, ciąg znaków lub inne struktury).

2. Funkcja dopasowania (fitness function):

Ocena jakości każdego rozwiązania w populacji.

3. Ocena:

Każde rozwiązanie (osobnik) jest oceniane przy pomocy funkcji dopasowania (fitness function), która określa, jak dobrze rozwiązanie rozwiązuje problem.

4. Selekcja:

Rozwiązania z lepszym dopasowaniem mają większe szanse na wybór do reprodukcji. Często stosowane są metody takie jak selekcja ruletkowa (roulette wheel selection), selekcja turniejowa (tournament selection) i selekcja rankingowa (rank selection).

5. Krzyżowanie (crossover):

Wybrane rozwiązania (rodzice) są łączone w celu stworzenia nowych rozwiązań (potomków). Krzyżowanie może być jedno-, dwu- lub wielopunktowe.

6. Mutacja:

Losowe zmiany w nowych rozwiązaniach (mutacje) są stosowane do wprowadzenia różnorodności. Pomaga to algorytmowi unikać lokalnych minimów.

7. Wymiana:

Nowa populacja zastępuje starą, a proces powtarza się, aż do spełnienia warunku zatrzymania (np. osiągnięcie określonej liczby pokoleń lub osiągnięcie określonego dopasowania).

Zalety i wady

Zalety:

• Szerokie zastosowanie: Mogą być stosowane do rozwiązywania różnych zadań, w tym takich, gdzie analityczne metody nie działają.
• Globalna optymalizacja: Są w stanie znaleźć globalne optimum w wielowymiarowych i złożonych przestrzeniach.
• Elastyczność: Mogą być używane z dowolną funkcją dopasowania.

Wady:

• Wysokie koszty obliczeniowe: Wymagają znaczących zasobów obliczeniowych, szczególnie dla dużych populacji i złożonych zadań.
• Trudności z ustawieniem parametrów: Dobór parametrów (rozmiar populacji, prawdopodobieństwo mutacji i krzyżowania) może być trudny i mocno wpływać na wydajność.
• Brak gwarancji optymalnego rozwiązania: Nie ma gwarancji, że znalezione rozwiązanie będzie globalnie optymalne.

Faktycznie algorytm genetyczny jest wysoce efektywną heurystyką. Nie gwarantuje, że znajdzie najlepsze rozwiązanie, nawet jeśli ma dostęp do pełnych danych. Ale dla skomplikowanych sytuacji i ogromnych ilości danych bardzo szybko generuje rozwiązanie zbliżone do idealnego.

9.2 Przykład zastosowania

Rozważ przykład zastosowania algorytmu genetycznego do optymalizacji funkcji.

import random

# Parametry algorytmu genetycznego
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Definicja funkcji dopasowania
def fitness_function(x):
    return -x**2 + 10*x
            
# Inicjalizacja populacji
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Selekcja (turniejowa)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Krzyżowanie (jednopunktowe)
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Mutacja
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Główna pętla algorytmu genetycznego
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Wypisanie najlepszego rozwiązania
best_individual = max(population, key=fitness_function)
print("Najlepsze rozwiązanie:", best_individual)
print("Wartość funkcji:", fitness_function(best_individual))
            
        

Zalety i wady

9.3 Optymalizacja funkcji wielowymiarowej

Zadanie:

Znajdź minimalną wartość funkcji wielowymiarowej.

Rozwiązanie:

Bierzemy poprzedni szablon

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Przykład użycia:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Najlepsze rozwiązanie: {best_solution}")