Genetické algoritmy

“Evoluce je fakt hustá” – Darwin 1939


Pro začátek řekněme něco k evoluci, jež je klíčovou inspirací, a z jejíž terminologie evoluční algoritmy nemálo přejímají. Na počátku 19. století Jean B. Lamarck ve své knize Philosophie zoologue popisuje první ucelenou teorii o vývoji druhů. Tvrdí, že jedinec mění své predispozice cíleně během života, což se průběhem času ukázalo jako mylné. V druhé polovině 19. století vychází slavná Darwinova kniha O původu druhů, jež pojednává o principu přírodního výběru. Nedlouho poté je popsána mutace dědičné informace. Dalekosáhlý význam měl také Mendelův spis O křížení rostlin. Ústředním tématem této knihy je gen, jenž dostal tento název až o něco později. Gen můžeme chápat jako jednotku dědičnosti, úsek DNA kódující určitý znak (například barvu očí). Ve spisu jsou popsány princip segregace alel, kombinace vloh, formuluje zákony dědičnosti, definuje dominantní a recesívní znaky. Dále rozděluje genetickou informaci na interpretovanou a neinterpretovanou, jíž nazývá genotypem (dnešní definice by mohla znít soubor pokynů kódovaných v souhrnu genetických informací uložených v sekvenci DNA) a fenotypem ( můžeme chápat jako genotyp ovlivněný vnějšími faktory, mutacemi a podobně). Z významných tváří moderní biologie, které se zajímají i o umělý život, mohu uvést Daniela  Dennetta, Richarda Dawkinse, Humberta Maturana, Francisca Varela. K historii genetiky v počítačových vědách. Uvedu vždy jméno autora, název přístupu a rok publikace.

  • 1962 – Evoluční programování – L. Fogel [9]
  • 1962 – Evoluční strategie – P. Schwefel, Refenberg [10]
  • 1975 – Genetické algoritmy – J. Holland [11]
  • 1989 – Moderní genetické algoritmy – D. E. Goldberg[12]
  • 1992 – Genetické programování – J. Koza [13]

Z výše uvedených přístupů bude řeč pouze o tom nejpoužívanějším. Genetické algoritmy, dále jen GA, jsou podmnožinou algoritmů evolučních. Můžeme na ně nahlížet jako na populaci možných kandidátů řešení. Takové řešení, jedince, nazáváme fenotypem. Jedinec obsahuje určité genetické informace (například ve formě binárního řetězce, datového stromu, datového pole), těm říkáme genotyp nebo také chromosom. GA fungují zhruba na takovémto principu. “Z populace se (kvazi)náhodně vyberou dva chromozomy, které si křížením vymění opět (kvazi)náhodně vybranou část řetězců. Výsledné chromozómy se pak ještě podrobí mutaci, která překlopí náhodně zvolené bity. Takto nově vytvořená dvojice se vrací do populace, kde vytěsní dvojici kvazináhodně vybraných chromozómů s malou silou”.

Genetické operátory, jiným slovem evoluční mechanismy, které GA používají jsou například :

Rekombinace – Jiným názvem také křížení, je u lidí vznik nové kombinace genů při pohlavním rozmnožování. U GA je postup obdobný. Stačí si místo řetězce nukleových bázi představit například řetězec nul a jedniček. Grafické znázornění viz Obrázek 2.


Mutace –  U lidí spontánní změna genotypu vzniklá chybou v replikačním a reparačním mechanismu DNA. V umělém prostředí spočívá v inverzi každého bitu řetězce s předem určenou pravděpodobností. Například z (1, 1, 0, 1, 0) na (1, 1, 0, 0, 0). Koluje názor, že u lidí se jedná  o jedniný zdroj nové genetické informace.

Inicializace– Operátor náhodně nastavuje jednotlivé bity binárního řetězce. Zpravidla na začátku procesu.

Inverze – Operátor provádí binární inverzi řetězce.

Selekce – U lidí hledání partnera s vhodným genotypem pro zajištění nejschopnějšího potomka. V umělém prostředí vyhledávání takvových kombinací, při kterých se dobereme nejlepšího výsledku.  Ten zahrnuje dva protichůdné požadavky :

  • požadavek na co nejrychlejší konvergenci a nalezení řešeni (můžeme nazvat selekčním tlakem)
  • požadavek na prohledání co největšího podprostoru stavového prostoru úlohy a tím minimalizaci rizika na uváznutí v lokálním extrému

Klademe-li důraz na první, hrozí nám, že uvízneme pouze v lokálním maximu. Klademe-li důraz na druhý, budou se prodlužovat výpočetní časy. Sílu jedince (vhodnost pro řešení), popisuje hodnotící funkce fitness. Čím větší hodnota, tím kvalitnější jedninec je, naopak jedinci s fitness pod určitou úrovní hynou. Je to stěžejní hodnota, jelikož má asi největší vliv na konečné řešení. Jak funcki nastavit záleží na konrétní úloze.

Darwin

Typickým znakem evoluce je adaptace, přizpůsobení měnícímu se prostředí, vývoj směřující k dokonalejšímu jedinci i celku. GA směřuje k lepšímu a lepšímu řešení zadaného úkolu. Jde o heuristický přístup, pracující s populací jedinců (jedinec Je reprezentován datovou strukturou), na kterou jsou aplikovány genetické operátory, čímž dochází k evoluci. Co je tedy jedinec? Například instrukce programu, parametr výpočtu….. prostě řešení dané úlohy. Datovou strukturou může být binární řetězec pevné délky, datový strom nebo datové pole.  Můžeme  brát každého jedince jako stav určitého stavového prostoru, a protože se jedinec neustále proměňuje, můžeme na situaci pohlížet jako na prohledávání stavového prostoru, stálé přibližování k řešení zadaného problému. Reprodukce se zaměřuje na nejlepší jedince v populaci. Jejich vhodnost pro dané prostředí je určena již popsanou  funkcí fitness. Můžeme určit dvě vývojové strategie.

  • Generační – V nové generaci jsou pouze noví jedinci (jako příklad vezměme jednoleté rostliny)
  • Postupné – Rodiče a potomci koexitsují

Selekce je určená pravidlem rulety. Uveďme příklad. Máme 4 jedince : A, B, C, D s hodnotami fitness [1, 2, 3, 4] Nyní si představme ruletu v níž jedinec A má jeden jamku, zatímco jedinec D jamky 4, tudíž 4 krát větší pravděpodobnost, že přežije do další generace.

Matematicky vyjádřeno

\mathbit{p}_\mathbit{i}=\frac{\mathbit{f}_\mathbit{i}}{\sum_{\mathbit{l}}^{\mathbit{N}}\mathbit{f}_\mathbit{i}}

  • pi pravděpodovnost, s jakou bude i-tý jedinec vybrán
  • fi fitness hodnota i-tého jedince
  • N počet jedinců v populaci

Je důležité si uvědomit, že když simulujeme nějakou úlohu, již za pár generací budeme mít jiné výsledky, než v té samé simulaci s těmi samými vstupními hodnotami, právě díky nahodilým faktorům jako je mutace.

Budeme li chtít řešit nějakou úlohu, můžeme použít tento postup [16]

  • Najít vhodnou reprezentaci potenciálních řešení problému (vhodně zvolit „formát“ chromozomu)
  • Najít způsob, jak vytvořit počáteční populaci chromozomů tak, aby představovaly přípustná řešení
  • Sestavit účelovou funkci, díky níž budeme schopni rozhodnout, který jedinec je „lepší“ a který „horší“
  • Zvolit nebo vytvořit vhodné genetické operátory, které ovlivňují tvorbu nových potomků
  • Vhodně nastavit různé parametry používané v GA (velikost populace, pravděpodobnosti uplatnění genetických operátorů, apod.)

Nejlepší asi bude ukázat praktickou ukázku, totiž řešení problému obchodního cestujícího. Kód pochází odtud. To o co nám jde, lze viděl na následujícím obrázku, kde jsou vykresleny jednotlivé generace a kde je krásně vidět, jak se výsledek zlepšuje.

import numpy as np, random, operator, pandas as pd, matplotlib.pyplot as plt

class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def distance(self, city):
        xDis = abs(self.x - city.x)
        yDis = abs(self.y - city.y)
        distance = np.sqrt((xDis ** 2) + (yDis ** 2))
        return distance


class Fitness:
    def __init__(self, route):
        self.route = route
        self.distance = 0
        self.fitness= 0.0
    
    def routeDistance(self):
        if self.distance ==0:
            pathDistance = 0
            for i in range(0, len(self.route)):
                fromCity = self.route[i]
                toCity = None
                if i + 1 < len(self.route):
                    toCity = self.route[i + 1]
                else:
                    toCity = self.route[0]
                pathDistance += fromCity.distance(toCity)
            self.distance = pathDistance
        return self.distance
    
    def routeFitness(self):
        if self.fitness == 0:
            self.fitness = 1 / float(self.routeDistance())
        return self.fitness

def createRoute(cityList):
    route = random.sample(cityList, len(cityList))
    return route

def initialPopulation(popSize, cityList):
    population = []

    for i in range(0, popSize):
        population.append(createRoute(cityList))
    return population

def rankRoutes(population):
    fitnessResults = {}
    for i in range(0,len(population)):
        fitnessResults[i] = Fitness(population[i]).routeFitness()
    return sorted(fitnessResults.items(), key = operator.itemgetter(1), reverse = True)

def selection(popRanked, eliteSize):
    selectionResults = []
    df = pd.DataFrame(np.array(popRanked), columns=["Index","Fitness"])
    df['cum_sum'] = df.Fitness.cumsum()
    df['cum_perc'] = 100*df.cum_sum/df.Fitness.sum()
    
    for i in range(0, eliteSize):
        selectionResults.append(popRanked[i][0])
    for i in range(0, len(popRanked) - eliteSize):
        pick = 100*random.random()
        for i in range(0, len(popRanked)):
            if pick <= df.iat[i,3]:
                selectionResults.append(popRanked[i][0])
                break
    return selectionResults

def matingPool(population, selectionResults):
    matingpool = []
    for i in range(0, len(selectionResults)):
        index = selectionResults[i]
        matingpool.append(population[index])
    return matingpool


def breed(parent1, parent2):
    child = []
    childP1 = []
    childP2 = []
    
    geneA = int(random.random() * len(parent1))
    geneB = int(random.random() * len(parent1))
    
    startGene = min(geneA, geneB)
    endGene = max(geneA, geneB)

    for i in range(startGene, endGene):
        childP1.append(parent1[i])
        
    childP2 = [item for item in parent2 if item not in childP1]

    child = childP1 + childP2
    return child


def breedPopulation(matingpool, eliteSize):
    children = []
    length = len(matingpool) - eliteSize
    pool = random.sample(matingpool, len(matingpool))

    for i in range(0,eliteSize):
        children.append(matingpool[i])
    
    for i in range(0, length):
        child = breed(pool[i], pool[len(matingpool)-i-1])
        children.append(child)
    return children


def mutate(individual, mutationRate):
    for swapped in range(len(individual)):
        if(random.random() < mutationRate):
            swapWith = int(random.random() * len(individual))
            
            city1 = individual[swapped]
            city2 = individual[swapWith]
            
            individual[swapped] = city2
            individual[swapWith] = city1
    return individual


def mutatePopulation(population, mutationRate):
    mutatedPop = []
    
    for ind in range(0, len(population)):
        mutatedInd = mutate(population[ind], mutationRate)
        mutatedPop.append(mutatedInd)
    return mutatedPop


def nextGeneration(currentGen, eliteSize, mutationRate):
    popRanked = rankRoutes(currentGen)
    selectionResults = selection(popRanked, eliteSize)
    matingpool = matingPool(currentGen, selectionResults)
    children = breedPopulation(matingpool, eliteSize)
    nextGeneration = mutatePopulation(children, mutationRate)
    return nextGeneration


def geneticAlgorithm(population, popSize, eliteSize, mutationRate, generations):
    pop = initialPopulation(popSize, population)
    print("Initial distance: " + str(1 / rankRoutes(pop)[0][1]))
    
    for i in range(0, generations):
        pop = nextGeneration(pop, eliteSize, mutationRate)
    
    print("Final distance: " + str(1 / rankRoutes(pop)[0][1]))
    bestRouteIndex = rankRoutes(pop)[0][0]
    bestRoute = pop[bestRouteIndex]
    return bestRoute


cityList = []

for i in range(0,25):
    cityList.append(City(x=int(random.random() * 200), y=int(random.random() * 200)))

geneticAlgorithm(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)


def geneticAlgorithmPlot(population, popSize, eliteSize, mutationRate, generations):
    pop = initialPopulation(popSize, population)
    progress = []
    progress.append(1 / rankRoutes(pop)[0][1])
    
    for i in range(0, generations):
        pop = nextGeneration(pop, eliteSize, mutationRate)
        progress.append(1 / rankRoutes(pop)[0][1])
    
    plt.plot(progress)
    plt.ylabel('Distance')
    plt.xlabel('Generation')
    plt.show()

geneticAlgorithmPlot(population=cityList, popSize=100, eliteSize=20, mutationRate=0.01, generations=500)

A takový je výsledek

Initial distance: 2090.2684140881915
Final distance: 797.0592530678264

Občas je důležité nastavit zastavovací pravidlo. Ne vždy další a další generace spějí k lepšímu výsledku. Může dojít k homogenizaci populace, což znamená, že genetické operátory již nemohou přinést žádnou novou změnu. Takové zastavovací pravidlo může znít : nedošlo-li za posledních dvacet generací ke zlepšení výsledků, zastav. Nebo také : zítra ráno v 9 zastav.

Genetické algoritmy prošly řadou modifikací, jež odstraňují některé jeho nedostatky. Například: je možné, že ze souboru jedinců eliminujeme toho nejlepšího. Řešení je takové, že vedle vyvíjejících se populací máme ještě jednu pomocnou paměťovou pozici, v níž uchováme dosud nejlepší nalezené řešení, a v každém kroku testujeme, zda nebylo nalezeno řešení kvalitnější. Další inovací, je tzv. Turnajová selekce, kde namísto toho, abych nechal všechny jedince s nedostatečným fitnessem rovnou zemřít, rozdělím celou populaci do dvojic, které svedou souboj, zbytek jedinců opět rozdělím do dvojic, kde opět zůstane ten s vyšším fitness, a to až do doby, kdy bude námi požadovaný počet jedinců.

V čem jsou GA, než běžné prohledávací algoritmy, jako je třeba metoda gradientu nebo metoda slepého horolezce? Jsou nedeterministické, pracují s náhodou, nedokážeme dopředu říci, jak výsledek dopadne. Jsou paralelní, nezpracovávají tudíž jen jednu informaci najednou. Jedná se o globální, nikoliv lokální prohledávání. Výhody z toho vyplývající jsou například větší univerzálnost, v určitých oblastech rychlost. Mezi nevýhody patří dejme tomu potřeba nastavit hodnoty jako jsou pravděpodobost mutace, křížení. Tyto parametry není jednoduché zjistit a většinou je získáváme empiricky. Jako praktické využití, můžeme uvést například řízení robotů, návrh rozpoznávacích systémů, simulaci umělého života, nebo vytváření rozvrhu práce v továrnách. Kupříkladu tvar tzv. evolved antény byl vytvořen právě prostřednictvím GA.

Darwin

Napsat komentář

Vaše emailová adresa nebude zveřejněna.