Oppiskele Valinta, Risteytys ja Mutaatiot

Valintastrategiat

Valinta on keskeinen prosessi geneettisissä algoritmeissa; se määrittää, mitkä yksilöt osallistuvat seuraavaan sukupolveen, tasapainottaen kelpoisuutta ja monimuotoisuutta. Käytössä on useita yleisiä valintastrategioita:

Rulettipyörävalinta: Jokaiselle yksilölle annetaan valintatodennäköisyys, joka on verrannollinen sen kelpoisuuteen. Kuvittele pyörä, jossa jokaisen siivun koko vastaa kelpoisuutta; korkeamman kelpoisuuden omaavilla yksilöillä on suurempi mahdollisuus tulla valituksi;
Turnausvalinta: Satunnaisesti valitaan ryhmä (turnaus) yksilöitä ja paras heistä valitaan vanhemmaksi. Tämä menetelmä on yksinkertainen ja tehokas, ja turnauksen koko voi säädellä valintapainetta;
Sijoitusperusteinen valinta: Yksilöt järjestetään kelpoisuuden mukaan ja valintatodennäköisyydet määräytyvät sijoituksen, eivät absoluuttisen kelpoisuuden perusteella. Tämä auttaa estämään muutaman korkean kelpoisuuden yksilön hallinnan, erityisesti ongelmissa, joissa kelpoisuuserot ovat suuria.


              1234567891011121314151617
            
import random

def tournament_selection(population, fitnesses, tournament_size=3):
    """
    Selects one individual from the population using tournament selection.
    """
    # Randomly pick tournament_size individuals
    selected_indices = random.sample(range(len(population)), tournament_size)
    # Find the one with the highest fitness
    best_index = max(selected_indices, key=lambda idx: fitnesses[idx])
    return population[best_index]

# Example usage
population = [[0,1,1,0], [1,0,0,1], [1,1,0,0], [0,0,1,1]]
fitnesses = [3, 2, 5, 4]
parent = tournament_selection(population, fitnesses, tournament_size=2)
print("Selected parent:", parent)

Risteytysoperaattorit

Valinnan jälkeen geneettiset algoritmit käyttävät risteytystä uusien yksilöiden luomiseen yhdistämällä tietoa kahdesta vanhemmasta. Risteytys tuo vaihtelua ja mahdollistaa algoritmin tutkia uusia ominaisuusyhdistelmiä populaatiossa.

Yleisiä risteytystyyppejä:

Yksipisteristeytys: Risteytyspiste valitaan satunnaisesti. Toisen vanhemman alkuosa yhdistetään toisen loppuosaan.
Kaksipisteristeytys: Kaksi pistettä valitaan satunnaisesti. Niiden välinen osuus vaihdetaan vanhempien välillä jälkeläisten tuottamiseksi.
Uniformi risteytys: Jokainen geeni jälkeläisessä valitaan satunnaisesti jommankumman vanhemman geenistä yhtä suurella todennäköisyydellä.


              12345678910111213141516171819
            
import random

def single_point_crossover(parent1, parent2):
    """
    Performs single-point crossover between two parents.
    """
    if len(parent1) != len(parent2):
        raise ValueError("Parents must be of the same length")
    point = random.randint(1, len(parent1) - 1)
    child1 = parent1[:point] + parent2[point:]
    child2 = parent2[:point] + parent1[point:]
    return child1, child2

# Example usage
p1 = [1, 0, 1, 0, 1]
p2 = [0, 1, 0, 1, 0]
offspring1, offspring2 = single_point_crossover(p1, p2)
print("Offspring 1:", offspring1)
print("Offspring 2:", offspring2)

Mutaatioiden rooli

Mutaatio on yksi geneettisten algoritmien keskeisistä mekanismeista. Se tuo uutta geneettistä materiaalia populaatioon, mikä auttaa algoritmia välttämään pysähtymistä ja jatkamaan uusien ratkaisujen etsimistä. Ilman mutaatiota populaatio voi muuttua liian samankaltaiseksi, jolloin haku voi jumittua paikallisiin optimeihin.

Miksi mutaatio on tärkeää

Estää ennenaikaisen konvergenssin: mutaatio varmistaa, ettei populaatiosta tule liian yhtenäistä, mikä ehkäisee epäoptimaalista konvergenssia;
Ylläpitää monimuotoisuutta: satunnaisten muutosten avulla mutaatio säilyttää laajan geneettisen vaihtelun tuleville sukupolville;
Mahdollistaa paikallisista optimeista irtautumisen: pienet satunnaiset muutokset mahdollistavat algoritmin tutkia uusia hakutilan alueita, jotka voivat johtaa parempiin ratkaisuihin;
Tasapainottaa risteytystä: kun risteytys yhdistää olemassa olevia ominaisuuksia, mutaatio tuo uusia, varmistaen että algoritmi tuottaa jatkuvasti uusia mahdollisuuksia.

Nämä ominaisuudet tekevät mutaatiosta olennaisen osan vankkaa ja sopeutuvaa hakuprosessia.

Yleiset mutaatio-operaattorit

Eri ongelmaesitykset vaativat erilaisia mutaatiotekniikoita. Kaksi yleisintä operaattoria ovat:

Bitin kääntö -mutaatio: binääriesityksille — kääntää bitin arvosta 0 arvoon 1 tai päinvastoin, tuoden pieniä, hallittuja muutoksia;
Vaihtomutaatio: permutaatioihin perustuville esityksille (esim. järjestysongelmat) — vaihtaa kahden yksilön alkion paikkaa muodostaen uuden konfiguraation.


              1234567891011121314151617181920
            
import random

def bit_flip_mutation(individual, mutation_rate=0.1):
    """
    Performs bit-flip mutation on a binary list.
    """
    mutated = []
    for gene in individual:
        if random.random() < mutation_rate:
            mutated.append(1 - gene)  # Flip bit
        else:
            mutated.append(gene)
    return mutated

# Example usage
original = [1, 0, 1, 1, 0]
mutated = bit_flip_mutation(original, mutation_rate=0.5)
print("Original:", original)
print("Mutated:", mutated)

Oliko kaikki selvää?

Kiitos palautteestasi!

Osio 2. Luku 2

Kysy tekoälyä

Kysy mitä tahansa tai kokeile jotakin ehdotetuista kysymyksistä aloittaaksesi keskustelumme

Suggested prompts:

Can you explain how tournament size affects selection pressure?

What are the advantages and disadvantages of each selection strategy?

How do I choose the right selection strategy for my problem?

Awesome!

Completion rate improved to 6.25

Pyyhkäise näyttääksesi valikon