Podręcznik

Operatory selekcji w algorytmach genetycznych

Selekcja to kluczowy etap algorytmu genetycznego, w którym wybierane są osobniki do reprodukcji – czyli do krzyżowania i/lub mutacji. Celem selekcji jest premiowanie lepiej przystosowanych jednostek, a zarazem zachowanie pewnej różnorodności genetycznej w populacji. Istnieje wiele technik selekcji, z których każda ma inne właściwości pod względem presji selekcyjnej i zbieżności.

Selekcja ruletkowa (proporcjonalna)

Selekcja ruletkowa (ang. "roulette wheel selection") jest jedną z najprostszych i najbardziej intuicyjnych metod. Każdemu osobnikowi przypisywany jest wycinek koła proporcjonalny do jego wartości funkcji przystosowania (fitness). Im lepszy osobnik, tym większe ma szanse na wybór. Wyobrażamy to sobie jak koło fortuny, w którym sektory odpowiadają poszczególnym osobnikom – im większy sektor, tym większe prawdopodobieństwo trafienia.

Z matematycznego punktu widzenia, prawdopodobieństwo selekcji osobnika wyraża się jako:

$P(i) = \frac{f_i}{\sum_{j=1}^{N} f_j}$

gdzie:

• $f_i$ to wartość funkcji przystosowania osobnika $i$,
• $N$ to liczba osobników w populacji.

Selekcja ruletkowa jest szybka i prosta, ale ma kilka wad. Przede wszystkim, jeśli w populacji znajduje się jeden bardzo dobrze przystosowany osobnik, to dominuje on selekcję – co może prowadzić do przedwczesnej zbieżności. Z drugiej strony, gdy wartości funkcji przystosowania są zbliżone, presja selekcyjna spada, a algorytm „drepcze w miejscu”.

Selekcja rankingowa

W selekcji rankingowej osobniki są najpierw sortowane według przystosowania (od najlepszego do najgorszego), a następnie każdemu przypisywana jest wartość selekcyjna zależna od jego pozycji (rangi), a nie od bezwzględnej wartości funkcji celu. Dzięki temu unika się problemów związanych z dużymi różnicami w wartościach funkcji przystosowania.

Presję selekcyjną można regulować poprzez funkcję przekształcającą rangę na prawdopodobieństwo – np. liniowo, wykładniczo lub z wykorzystaniem rozkładów losowych. Rankingowa metoda zapewnia bardziej kontrolowaną presję selekcyjną i pozwala uniknąć dominacji pojedynczych osobników, ale kosztem większej złożoności obliczeniowej (sortowanie).

Selekcja turniejowa

W selekcji turniejowej tworzy się losowo grupy (turnieje) złożone z osobników (zwykle lub ). W każdej grupie wygrywa najlepszy osobnik, który trafia do puli reprodukcyjnej. Metoda ta jest prosta do zaimplementowania i nie wymaga znajomości wartości funkcji przystosowania całej populacji.

Presję selekcyjną reguluje się wielkością turnieju – większe oznacza silniejszą presję. Przykładowo, turniej zachowuje sporo losowości, natomiast może szybko prowadzić do utraty różnorodności. Istnieją też warianty turnieju probabilistycznego, w którym zwycięzca wybierany jest z prawdopodobieństwem zależnym od jego jakości.

Porównanie technik

• Ruletka – szybka, ale wrażliwa na rozkład przystosowań; może prowadzić do dominacji jednego osobnika.
• Ranking – stabilna i odporna na ekstremalne wartości funkcji celu; presja zależna od rangi.
• Turniej – bardzo elastyczny, szybki i łatwy do równoleglenia; dobrze sprawdza się w praktyce.

Dobór operatora selekcji ma istotny wpływ na zachowanie algorytmu – jego zbieżność, eksplorację i eksploatację przestrzeni. W praktyce często testuje się różne metody dla konkretnego problemu, by dobrać najbardziej efektywną konfigurację.

Ciekawostka: Uruchamiając poniższy program możecie zobaczyć / testować jak działają omówione operatory selekcji:

import numpy as np
import matplotlib.pyplot as plt

# Generowanie populacji i przypisanie funkcji przystosowania
np.random.seed(42)
population_size = 20
fitness = np.sort(np.random.rand(population_size))[::-1]  # Posortowane od najlepszego

# Selekcja ruletkowa
def roulette_selection(fitness, num_selected):
    probabilities = fitness / fitness.sum()
    return np.random.choice(len(fitness), size=num_selected, p=probabilities)

# Selekcja rankingowa (liniowa)
def ranking_selection(fitness, num_selected):
    ranks = np.argsort(np.argsort(-fitness))  # 0 - najlepszy
    rank_weights = (len(fitness) - ranks)
    probabilities = rank_weights / rank_weights.sum()
    return np.random.choice(len(fitness), size=num_selected, p=probabilities)

# Selekcja turniejowa
def tournament_selection(fitness, num_selected, tournament_size=3):
    selected = []
    for _ in range(num_selected):
        participants = np.random.choice(len(fitness), tournament_size, replace=False)
        winner = participants[np.argmax(fitness[participants])]
        selected.append(winner)
    return np.array(selected)

# Zastosowanie selekcji
num_selected = 1000
roulette_counts = np.bincount(roulette_selection(fitness, num_selected), minlength=population_size)
ranking_counts = np.bincount(ranking_selection(fitness, num_selected), minlength=population_size)
tournament_counts = np.bincount(tournament_selection(fitness, num_selected), minlength=population_size)

# Wizualizacja
plt.figure(figsize=(12, 6))
plt.plot(roulette_counts, label='Ruletkowa', marker='o')
plt.plot(ranking_counts, label='Rankingowa', marker='s')
plt.plot(tournament_counts, label='Turniejowa (k=3)', marker='^')
plt.title("Porównanie technik selekcji w algorytmie genetycznym")
plt.xlabel("Indeks osobnika (0 = najlepszy)")
plt.ylabel("Liczba wybrań w selekcji (z 1000 prób)")
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.show()