Experiment: spôsoby reprezentácie

Cieľom je porovnať rôzne spôsoby reprezentácie jedincov. Ide o to, ako veľmi jednotlivé reprezentačné schémy napomáhajú alebo prekážajú efektívnemu prehľadávaniu priestoru prehľadávania pri hľadaní riešenia.

Experiment je postavený na úlohe, reprezentovanej typickým kombinatorickým problémom - farbením grafu. Je potrebné vytvoriť politickú mapu Afriky, teda vyfarbiť jednotlivé štáty tak, aby žiadne dva susedné štáty nepoužili rovnakú farbu. Jednotlivé štáty predstavujú uzly grafu, ktorých farbu je potrebné určiť, zatiaľ čo hrany grafu medzi dvojicami uzlov reprezentujú skutočnosť, že štáty, reprezentované týmito uzlami, majú spoločnú hranicu. Každá hrana tak predstavuje ohraničenie, ktoré hľadané riešenie musí spĺňať - uzly spojené hranou musia byť zafarbené rôznymi farbami. Aby farbenie bolo validné, musí spĺňať všetky takéto ohraničenia.

Podstata experimentu

Je daná implementácia algoritmu s jednoduchou realizáciou všetkých typických blokov algoritmu. Je postavená na zvolenom tvare kandidátov na riešenia, spoločne definujúcim priestor kandidátov. Tento tvar využívajú všetky bloky algoritmu, ktoré pracujú s priestorom kandidátov.

Pre definovanie priestoru prehľadávania je použitá reprezentačná schéma, ktorá zrkadlí tvar kandidátov - a teda nie je potrebné dekódovanie reprezentácie kandidáta na samotného kandidáta (aktuálne realizované ako identita). Tvar reprezentácie je zohľadnený všetkými tými blokmi algoritmu, ktoré pracujú s reprezentáciami v priestor prehľadávania.

Výkonnosť algoritmu s použitou reprezentačnou schémou je meraná ako počet generácií, potrebných pre objavenie validného riešenia. Keďže sa jedná o stochastický proces, tak hľadanie riešenia musí byť viackrát opakované pre získanie spoľahlivej vzorky dát. Následne sa určí priemerný počet generácií, ktorý je potrebný pre dosiahnutie riešenia.

Príprava

Pre prípravu experimentu je potrebné nahradiť použitú reprezentačnú schému zvoleným spôsobom reprezentácie. Na základe tohto rozhodnutia je potrebné zmeniť implementáciu všetkých tých blokov algoritmu, ktoré s reprezentáciami pracujú. Je potrebné meniť metódy pre:

1. dekódovanie reprezentácie jedinca na kandidáta (funkcia decode)
2. generovanie jedincov (funkcia generate_individual)
3. mutačné zmeny jedinca (funkcia mutate)
4. kombinovanie jedincov (funkcia cross)

%matplotlib inline

import random
import matplotlib.pyplot as plt

# Štáty a ich susedstvá

states = [
    "Algeria", "Angola", "Benin", "Botswana", "Burkina Faso", "Burundi",
    "Cameroon", "Cape Verde", "Central African Republic", "Chad",
    "Dem. rep. of Congo", "Djibouti", "Egypt", "Equatorial Giunea", "Eritrea",
    "Ethiopia", "Gabon", "Gambia", "Ghana", "Guinea", "Guinea Bissau",
    "Ivory Coast", "Kenya", "Lesotho", "Liberia", "Lybia", "Madagaskar",
    "Malawi", "Mali", "Mauritania", "Mauritius", "Morroco", "Mozambique",
    "Namibia", "Niger", "Nigeria", "Republica of Congo", "Reunion", "Rwanda",
    "Senegal", "Seychelles", "Sierra Leone", "Somalia", "South Africa",
    "Sudan", "Swaziland", "Tanzania", "Togo", "Tunisia", "Uganda",
    "Zambia", "Zanzibar", "Zimbabwe"
]

neighbours = [
    ("Morroco","Mauritania"), ("Morroco","Algeria"), ("Tunisia","Algeria"),
    ("Tunisia","Lybia"), ("Egypt","Lybia"), ("Egypt","Sudan"),
    ("Algeria","Mauritania"), ("Algeria","Mali"), ("Algeria","Niger"),
    ("Algeria","Lybia"), ("Lybia","Niger"), ("Lybia","Chad"),
    ("Lybia","Sudan"), ("Gambia","Senegal"), ("Mauritania","Senegal"),
    ("Mauritania","Mali"), ("Mali","Senegal"), ("Mali","Guinea"),
    ("Mali","Ivory Coast"), ("Mali","Burkina Faso"), ("Mali","Niger"),
    ("Niger","Burkina Faso"), ("Niger","Benin"), ("Niger","Nigeria"),
    ("Niger","Chad"), ("Chad","Nigeria"), ("Chad","Cameroon"),
    ("Chad","Central African Republic"), ("Sudan","Central African Republic"),
    ("Chad","Sudan"), ("Sudan","Dem. rep. of Congo"), ("Sudan","Uganda"),
    ("Sudan","Kenya"), ("Sudan","Ethiopia"), ("Sudan","Eritrea"),
    ("Eritrea","Ethiopia"), ("Eritrea","Djibouti"), ("Senegal","Guinea Bissau"),
    ("Senegal","Guinea"), ("Guinea","Guinea Bissau"), ("Guinea","Sierra Leone"),
    ("Guinea","Liberia"), ("Sierra Leone","Liberia"), ("Ivory Coast","Liberia"),
    ("Guinea","Ivory Coast"), ("Ivory Coast","Burkina Faso"),
    ("Ivory Coast","Ghana"), ("Burkina Faso","Ghana"), ("Ghana","Togo"),
    ("Burkina Faso","Togo"), ("Burkina Faso","Benin"), ("Benin","Togo"),
    ("Benin","Nigeria"), ("Nigeria","Cameroon"),
    ("Cameroon","Equatorial Giunea"), ("Cameroon","Central African Republic"),
    ("Cameroon","Gabon"), ("Cameroon","Republica of Congo"),
    ("Dem. rep. of Congo","Central African Republic"),
    ("Dem. rep. of Congo","Republica of Congo"), ("Djibouti","Somalia"),
    ("Dem. rep. of Congo","Angola"), ("Republica of Congo","Angola"),
    ("Dem. rep. of Congo","Zambia"), ("Dem. rep. of Congo","Burundi"),
    ("Dem. rep. of Congo","Rwanda"), ("Dem. rep. of Congo","Uganda"),
    ("Uganda","Rwanda"), ("Uganda","Tanzania"), ("Uganda","Kenya"),
    ("Ethiopia","Kenya"), ("Kenya","Somalia"), ("Ethiopia","Somalia"),
    ("Ethiopia","Djibouti"), ("Dem. rep. of Congo","Tanzania"),
    ("Equatorial Giunea","Gabon"), ("Republica of Congo","Gabon"),
    ("Central African Republic","Republica of Congo"), ("Rwanda","Burundi"),
    ("Tanzania","Burundi"), ("Rwanda","Tanzania"), ("Kenya","Tanzania"),
    ("Angola","Namibia"), ("Angola","Zambia"), ("Tanzania","Zambia"),
    ("Zambia","Malawi"), ("Tanzania","Malawi"), ("Tanzania","Mozambique"),
    ("Zambia","Namibia"), ("Zambia","Botswana"), ("Namibia","South Africa"),
    ("Zambia","Mozambique"), ("Malawi","Mozambique"), ("Zambia","Zimbabwe"),
    ("Namibia","Botswana"), ("Zimbabwe","Botswana"), ("Zimbabwe","Mozambique"),
    ("Botswana","South Africa"), ("Zimbabwe","South Africa"),
    ("Mozambique","South Africa"), ("Mozambique","Swaziland"),
    ("South Africa","Lesotho"), ("South Africa","Swaziland"),
]

# Parametre algoritmu

μ = 10                   # veľkosť populácie
max_generation = 1000    # maximálne povolený počet generácií

# dostupné farby - vybrať jednu z možností
colours = ["yellow", "green", "blue", "red"]
#colours = ["yellow", "green", "blue", "red", "black"]

# Dekódovanie reprezentácie jedinca na kandidáta - Potrebné prispôsobiť reprezentácii

def decode(individual):
    return individual

# Určenie vhodnosti kandidátov

def evaluate(individual):
    candidate = decode(individual)
    return sum(
        [ 1 if candidate[state1] != candidate[state2] else 0 
         for state1, state2 in neighbours ]
    )

# Generovanie reprezentácie jedincov - Potrebné prispôsobiť reprezentácii

def generate_individual():
    return { state : random.choice(colours) for state in states }

# Inicializácia počiatočnej generácie jedincov

def initialize():
    population = [ generate_individual() for _ in range(μ) ]
    return [ (individual, evaluate(individual)) for individual in population ]

# Ukončenie behu algoritmu

def end_condition(population, generation):
    max_fitness = len(neighbours)
    solutions = [ "." for _, fitness in population if fitness == max_fitness ]
    return solutions != [] or generation == max_generation

# Selekcia rodičov

def select(population):
    parents = population
    return parents

# Genetické operátory - Potrebné prispôsobiť reprezentácii

def mutate(individual):
    state = random.choice(states)
    individual[state] = random.choice(colours)

def cross(individual1, individual2):
    state = random.choice(states)
    individual1[state] = individual2[state]

# Vytvorenie nových potomkov

def reproduce(population):
    parents = select(population)
    
    offsprings = [ individual.copy() for individual, _ in population ]
    idx1, idx2 = list(range(len(offsprings))), list(range(len(offsprings)))
    random.shuffle(idx1)
    random.shuffle(idx2)
    for i, j in zip(idx1,idx2):
        cross(offsprings[i], offsprings[j])
        mutate(offsprings[j])
        
    new_population = [ (individual, evaluate(individual)) for individual in offsprings ]
    
    return new_population

# Vytvorenie novej generácie jedincov

def replace(population, offsprings):
    pool = population + offsprings
    random.shuffle(pool)
    return [x if x[1] > y[1] else y for x, y in zip(pool[0::2],pool[1::2])]

# Experiment - jeden beh

def best(population):
    best = max([ fit for _, fit in population ])
    avg =  sum([ fit for _, fit in population ]) / len(population)
    return best, avg

def print_graph(data):
    plt.xlabel("generation")
    plt.ylabel("fitness")
    plt.plot([x[0] for x in data], label="best_fitness")
    plt.plot([x[1] for x in data], label="avg. fitness")
    plt.legend(loc="lower right")
    plt.show()

def ea():
    fitness = []
    gen = 0
    population = initialize()
    fitness.append(best(population))
    while not end_condition(population, gen):
        offsprings = reproduce(population)
        population = replace(population, offsprings)
        fitness.append(best(population))
        gen += 1
    print_graph(fitness)

ea()

# Experiment - opakovane hľadanie riešenia

repetitions = 1000

def ea_repeated():
    num_gen = []
    for _ in range(repetitions):
        gen = 0
        population = initialize()
        while not end_condition(population, gen):
            offsprings = reproduce(population)
            population = replace(population, offsprings)
            gen += 1
        num_gen.append(gen)
    avg_gen = sum(num_gen) / len(num_gen)
    print(f"Average number of generations: {avg_gen}")

ea_repeated()

Average number of generations: 585.476