Hlavní navigace

Biologické algoritmy (2) - Evoluční algoritmy

V dnešním díle našeho seriálu vyzkoušíme naprogramovat evoluční algoritmus v Javě a vyřešíme jednoduchou optimalizační úlohu. Naučíme se další významnou strategii, používanou v evolučních algoritmech – elitismus. Naším úkolem bude najít tři kružnice, které nejlépe pasují na rozložené body ve 2D.

Na vstupu máme 300 bodů v dvourozměrném prostoru. Tyto body jsou znázorněny na obrázku níže a). Cílem je najít tři kružnice, které nejlépe pasují na tyto body. Každá kružnice je definována třemi parametry – souřadnice x a y a poloměr r. Pro tři kružnice je tak každé řešení dáno 9 parametry. Různá řešení jsou uvedena na obrázku níže b) – e). Některá řešení jsou lepší, jiná horší. Velmi dobré řešení je znázorněno na obrázku e).

Šablona

Programovat začneme z připravené šablony, která obsahuje body v prostoru a umí je vykreslit. Stačí zkopírovat kód níže a spustit kompilátor Javy.

package genetics;

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import javax.swing.BoxLayout;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Genetics extends JFrame{

    double[] ptsX = {127, 41, 54, 76, 82, 125, 30, 128, 68, 34, 29, 95, 30, 34, 128, 93, 45, 29,
    105, 40, 39, 106, 55, 120, 117, 129, 128, 92, 125, 125, 69, 117, 32, 125, 91, 116, 108, 127,
    58, 88, 119, 51, 123, 126, 100, 60, 29, 37, 121, 45, 77, 96, 30, 119, 111, 30, 112, 129, 109,
    108, 84, 130, 54, 127, 65, 47, 30, 79, 121, 92, 101, 92, 111, 45, 129, 128, 107, 52, 116, 54,
    84, 109, 108, 48, 39, 42, 48, 117, 44, 31, 29, 128, 33, 86, 129, 110, 118, 101, 129, 63, 69,
    82, 88, 80, 133, 129, 103, 70, 121, 129, 70, 92, 78, 118, 133, 115, 97, 89, 122, 134, 86, 119,
    71, 93, 125, 135, 107, 75, 127, 79, 135, 108, 70, 68, 103, 73, 70, 83, 95, 135, 100, 73, 134,
    125, 77, 72, 93, 122, 133, 131, 88, 121, 120, 136, 71, 77, 131, 95, 119, 130, 95, 111, 75, 96,
    135, 136, 115, 113, 76, 79, 129, 133, 74, 120, 123, 87, 126, 82, 135, 74, 119, 81, 131, 125, 76,
    124, 132, 71, 92, 122, 136, 132, 129, 120, 113, 136, 136, 70, 69, 99, 31, 82, 153, 125, 23, 47,
    131, 75, 25, 149, 20, 21, 20, 156, 27, 60, 45, 32, 141, 78, 26, 123, 47, 104, 157, 77, 148, 21,
    139, 32, 65, 88, 37, 30, 127, 27, 35, 149, 134, 113, 98, 51, 127, 143, 84, 46, 106, 21, 106, 156,
    137, 130, 156, 21, 116, 64, 25, 65, 126, 26, 27, 89, 122, 21, 84, 122, 19, 39, 157, 29, 139, 80,
    142, 140, 143, 64, 22, 152, 158, 74, 151, 156, 119, 152, 82, 24, 20, 138, 49, 134, 47, 122, 27,
    128, 151, 114, 135, 35, 120, 96};
    double[] ptsY = {89, 67, 141, 50, 149, 81, 92, 110, 149, 120, 104, 146, 89, 77, 90, 148, 63, 105,
    142, 69, 69, 58, 144, 72, 66, 103, 107, 51, 80, 78, 50, 131, 85, 119, 149, 133, 59, 114, 54, 50,
    128, 140, 123, 119, 145, 146, 97, 73, 127, 63, 51, 51, 105, 131, 138, 88, 61, 97, 59, 137, 150,
    95, 57, 87, 54, 62, 92, 150, 128, 148, 54, 51, 138, 135, 109, 92, 141, 142, 134, 142, 50, 60, 58,
    61, 128, 133, 62, 67, 134, 84, 97, 110, 119, 148, 93, 61, 69, 55, 94, 52, 65, 35, 31, 87, 74, 81,
    95, 52, 90, 83, 72, 29, 38, 32, 48, 93, 95, 92, 88, 51, 32, 91, 50, 30, 87, 59, 95, 82, 85, 39, 60,
    29, 55, 59, 28, 45, 70, 34, 29, 58, 27, 45, 53, 38, 84, 47, 95, 89, 76, 45, 92, 89, 33, 57, 51, 39,
    43, 94, 89, 80, 29, 93, 42, 95, 60, 62, 31, 94, 83, 87, 41, 75, 42, 89, 89, 32, 38, 35, 68, 43, 90,
    88, 79, 36, 83, 87, 46, 77, 30, 35, 61, 46, 81, 90, 94, 65, 60, 50, 61, 28, 39, 146, 54, 136, 59,
    131, 24, 10, 106, 46, 64, 59, 88, 66, 49, 16, 130, 39, 122, 145, 47, 136, 134, 144, 68, 144, 112,
    75, 30, 38, 143, 145, 121, 42, 133, 107, 35, 46, 26, 12, 145, 135, 133, 38, 146, 130, 143, 68, 13,
    86, 30, 132, 85, 72, 16, 14, 103, 13, 22, 104, 50, 9, 137, 84, 9, 138, 77, 125, 75, 44, 34, 146, 34,
    123, 36, 142, 91, 53, 74, 11, 51, 91, 138, 50, 145, 52, 86, 30, 133, 28, 131, 16, 47, 22, 105, 141,
    28, 119, 17, 10};

    public class Graph extends JPanel{
        @Override
        public void paintComponent(Graphics g){
            super.paintComponent(g);
            g.setColor(Color.BLACK);
            for(int i=0;i<ptsX.length;i++) g.fillOval((int)ptsX[i], (int)ptsY[i], 3, 3);
        }
    }

    public Genetics(){
        Graph graph = new Graph();
        graph.setBackground(Color.WHITE);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        JPanel panel = new JPanel();

        panel.setLayout(new BoxLayout(panel, BoxLayout.Y_AXIS));
        panel.add(graph);
        setContentPane(panel);

        this.setSize(600, 400);
        this.setVisible(true);

        graph.repaint();
    }

    public static void main(String[] args) {
        Genetics window = new Genetics();
    }
}

Na začátku třídy Genetics jsou definovány souřadnice bodů. Třída Genetics vytváří okno aplikace. Třída Graph vykresluje body.

Reprezentace řešení

Trojici kružnic můžeme reprezentovat vektorem o devíti hodnotách – viz obrázek níže.

Všechny jedince v populaci lze reprezentovat v 2D poli tak, jak je to uvedeno na obrázku.

Nyní do třídy Genetics doplníme atributy:

public final float CROSS_RATE = 1.0f;
public final float MUTATION_RATE = 0.05f;
public final int POPULATION_SIZE = 80;
public final int GENERATIONS_NUM = 500;
public double[][] population = new double[POPULATION_SIZE][9];
public int[][] zaznam = new int[GENERATIONS_NUM][POPULATION_SIZE];

CROSS_RATE je pravděpodobnost křížení. Většinou tuto hodnotu volíme mezi 0.7  – 1.0. S touto pravděpodobností se dva jedinci zkříží. Dalším parametrem je MUTATION_RATE, který vyjadřuje pravděpodobnost mutace každého genu. Parametr POPULATION_SIZE je počet jedinců v populaci a GENERATIONS_NUM je počet generací (doba, po kterou hledáme řešení). Pole population bude obsahovat všechny jedince v populaci. Pole zaznam bude obsahovat graf, který ukazuje, jak se populace vyvíjí v čase.

Výpočet fitness

Dále potřebujeme umět vyhodnotit kvalitu řešení. K tomuto účelu napíšeme metodu fitness. Tato metoda je definována následujícím kódem.

public double fitness(double[] individuum){
    double d1, d2, d3, dx, dy, x;
    double quality = 0.0f;
    double sigma = 15.0;
    for(int i=0;i<ptsX.length;i++){
        dx = (ptsX[i]-individuum[0]);
        dy = (ptsY[i]-individuum[1]);
        d1 = Math.abs(Math.sqrt(dx*dx + dy*dy) - individuum[2]);
        dx = (ptsX[i]-individuum[3]);
        dy = (ptsY[i]-individuum[4]);
        d2 = Math.abs(Math.sqrt(dx*dx + dy*dy) - individuum[5]);
        dx = (ptsX[i]-individuum[6]);
        dy = (ptsY[i]-individuum[7]);
        d3 = Math.abs(Math.sqrt(dx*dx + dy*dy) - individuum[8]);
        x = Math.min(Math.min(d1,d2),d3);
        quality+= Math.exp(-(x*x)/(2.0*sigma*sigma));
    }
    return quality;
}

Na vstupu je vektor (pole) individuum o 9 hodnotách, který obsahuje genotyp jedince. Výstupem je kvalita jedince. Pro každý bod se vypočte vzdálenost od 1. kružnice d1, vzdálenost od 2. kružnice d2 a vzdálenost od 3. kružnice d3. Z těchto vzdáleností se vybere nejnižší. Najdeme tak ke každému bodu vzdálenost od nejbližší kružnice. Potom přičteme ke kvalitě hodnotu danou normálním rozdělením. Je-li vzdálenost od kružnice nulová, přičte se hodnota 1.0, se zvyšující se vzdáleností se bude přičítat nižší hodnota. V ideálním případě – když všech 300 bodů bude ležet na kružnicích – bude mít fitness svoji maximální hodnotu  300.0.

Vykreslování řešení

Nyní upravíme vykreslovací třídu Graph následujícím způsobem, aby vykreslila kružnice v populaci:

public class Graph extends JPanel{
    @Override
    public void paintComponent(Graphics g){
        super.paintComponent(g);
        // vykreslime vsechny kruznice v populaci
        g.setColor(Color.LIGHT_GRAY);
        for(int i=1;i<POPULATION_SIZE;i++){
            g.drawOval((int)(population[i][0]-population[i][2]), (int)(population[i][1]-population[i][2]), (int)(population[i][2]*2), (int)(population[i][2]*2));
            g.drawOval((int)(population[i][3]-population[i][5]), (int)(population[i][4]-population[i][5]), (int)(population[i][5]*2), (int)(population[i][5]*2));
            g.drawOval((int)(population[i][6]-population[i][8]), (int)(population[i][7]-population[i][8]), (int)(population[i][8]*2), (int)(population[i][8]*2));
        }
        // vykreslime nejlepsi reseni v populaci
        g.setColor(Color.RED);
        Graphics2D g2D = (Graphics2D) g;
        g2D.setStroke(new BasicStroke(2F));
        g2D.drawOval((int)(population[0][0]-population[0][2]), (int)(population[0][1]-population[0][2]), (int)(population[0][2]*2), (int)(population[0][2]*2));
        g2D.drawOval((int)(population[0][3]-population[0][5]), (int)(population[0][4]-population[0][5]), (int)(population[0][5]*2), (int)(population[0][5]*2));
        g2D.drawOval((int)(population[0][6]-population[0][8]), (int)(population[0][7]-population[0][8]), (int)(population[0][8]*2), (int)(population[0][8]*2));
        // vykreslime body
        g.setColor(Color.BLACK);
        for(int i=0;i<ptsX.length;i++) g.fillOval((int)ptsX[i], (int)ptsY[i], 3, 3);
        // vykreslime graf vyvoje populace v case
        for(int i=0;i<GENERATIONS_NUM;i++){
            g.setColor(Color.LIGHT_GRAY);
            for(int j=1;j<POPULATION_SIZE;j++){
                if(zaznam[i][j] > 0) g.fillOval(i, 400-zaznam[i][j], 3, 3);
            }
            if(zaznam[i][0] > 0){
                g.setColor(Color.RED);
                g.fillOval(i, 400-zaznam[i][0], 3, 3);
            }
        }
    }
}

Nejprve se šedou barvou vykreslí všechny kružnice všech řešení. Potom se červenou barvou vykreslí z nich nejlepší řešení, které je uloženo v populaci jako první řádek 2D pole. Dále se vykreslí černou barvou všech 300 bodů a nakonec graf vývoje populace v čase. V průběhu evolučního algoritmu by se nyní mělo řešení vykreslovat následujícím způsobem:

Selekce

Nyní napíšeme metodu, která vybere náhodného jedince na základě jeho fitness. Jedinci s vyšší fitness budou mít vyšší šanci, že budou vybráni. Níže uvedená metoda provádí tzv. „Roulette selection“.

public int pickRandomIndividuum(double[] arFitness, double sumFitness){
    double sum = 0.0;
    double fitnessPoint = Math.random()*sumFitness;
    for(int i=0;i<POPULATION_SIZE;i++){
        sum+= arFitness[i];
        if(sum > fitnessPoint) return i;
    }
    return 0;
}

Tato funkce dostane na vstup pole arFitness, které obsahuje fitness všech jedinců v populaci, a proměnnou sumFitness, která obsahuje sumu fitness od všech jedinců. Náhodné se vybere hodnota mezi nulou a hodnotou sumFitness a potom se vyhledá jedinec, který „padne“ na tuto vybranou hodnotu. Lepší jedinci tak budou mít vyšší šanci, že budou vybráni.

Průběh algoritmu, křížení a mutace

Nyní upravíme poslední metodu Genetics(), která udělá zbytek.

public Genetics(){
    Graph graph = new Graph();
    graph.setBackground(Color.WHITE);
    setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    JPanel panel = new JPanel();

    panel.setLayout(new BoxLayout(panel, BoxLayout.Y_AXIS));
    panel.add(graph);
    setContentPane(panel);

    this.setSize(600, 400);
    this.setVisible(true);

    // inicializujeme populaci
    for(int i=0;i<POPULATION_SIZE;i++){
        for(int j=0;j<9;j++) population[i][j] = 100.0*Math.random();
    }
    graph.repaint();

    double[] arFitness = new double[POPULATION_SIZE];
    for(int iGeneration=0;iGeneration<GENERATIONS_NUM;iGeneration++){
        double bestFitness = 0.0f;
        int bestFitnessIdx = 0;
        double[][] newPopulation = new double[POPULATION_SIZE][9];
        double minFitness = Double.MAX_VALUE;
        // vypocteme fitness vsech jedincu v populaci
        for(int i=0;i<POPULATION_SIZE;i++){
            arFitness[i] = fitness(population[i]);
            if(arFitness[i] > bestFitness){
                bestFitness = arFitness[i];
                bestFitnessIdx = i;
            }
            if(arFitness[i] < minFitness) minFitness = arFitness[i];
            zaznam[iGeneration][i] = (int)Math.round(arFitness[i]*0.66);
        }
        // upravime hodnoty fitness pro lepsi selekci od 0 do bestFitness-minFitness
        double sumFitness = 0.0;
        for(int i=0;i<POPULATION_SIZE;i++){
            arFitness[i]-= minFitness;
            sumFitness+= arFitness[i];
        }
        // vytvoreni nove populace, ktera nahradi stavajici
        for(int iIndividuum=0;iIndividuum < POPULATION_SIZE; iIndividuum+=2){
            // prirozeny vyber
            int individuumIdx1 = pickRandomIndividuum(arFitness, sumFitness);
            int individuumIdx2 = pickRandomIndividuum(arFitness, sumFitness);
            if(Math.random() < CROSS_RATE){
                for(int i=0;i<9;i++){
                    if(Math.random() < 0.5){
                        newPopulation[iIndividuum][i] = population[individuumIdx1][i];
                        newPopulation[iIndividuum+1][i] = population[individuumIdx2][i];
                    }
                    else{
                        newPopulation[iIndividuum][i] = population[individuumIdx2][i];
                        newPopulation[iIndividuum+1][i] = population[individuumIdx1][i];
                    }
                }
                // mutace
                for(int child=0;child<2;child++){
                    for(int i=0;i<9;i++){
                        if(Math.random() < MUTATION_RATE){
                            double randomValue = 8.0*Math.sqrt(-2*Math.log(Math.random()))*Math.sin(2*Math.PI*Math.random());
                            newPopulation[iIndividuum+child][i]+= randomValue;
                            if(newPopulation[iIndividuum+child][i] < 0) newPopulation[iIndividuum+child][i] = 0;
                            else if(newPopulation[iIndividuum+child][i] > 100) newPopulation[iIndividuum+child][i] = 100;
                        }
                    }
                }
            }
            else{ // neni krizeni
                for(int i=0;i<9;i++){
                    newPopulation[iIndividuum][i] = population[individuumIdx1][i];
                    newPopulation[iIndividuum+1][i] = population[individuumIdx2][i];
                }
            }
        }
        // elitismus - zachovani nejlepsiho
        for(int i=0;i<9;i++) newPopulation[0][i] = population[bestFitnessIdx][i];
        population = newPopulation;
        System.out.println("Generation "+iGeneration+", Fitness: "+bestFitness);
        graph.repaint();
        try{
            Thread.sleep((int)(2000.0/Math.sqrt(iGeneration+1)));
        } catch (InterruptedException ex){
        }
    }
}

Nejprve se populace inicializuje náhodnými hodnotami od 0 do 100. Potom vytvoříme pole arFitness, do kterého se budou ukládat fitness všech jedinců v populaci.

V cyklu procházíme všechny generace. V každém cyklu vytvoříme pole newPopulation, které ke konci cyklu nahradí stávající populaci. Pro všechny jedince vypočteme jejich fitness a uložíme do pole arFitness, přitom si pamatujeme jedince s minimálním fitness a jedince s maximálním fitness.

Dále všechny zjištěné hodnoty fitness upravíme tak, že odečteme minimální fitness. Tím kvalitu jedinců dostaneme do rozsahu od 0 do bestFitness-minFitness. Tím se zlepší selekce – je zaručeno, že nejhorší jedinec nebude nikdy vybrán ke křížení.

V dalším cyklu budeme vytvářet novou populaci, která nahradí stávající. Cyklus opakujeme POPULATION_SIZE/2 krát. V každé iteraci vybereme náhodné 2 jedince ke křížení a vytvoříme místo nich 2 potomky, které uložíme do nové populace  newPopulation.

S pravděpodobností CROSS_RATE provedeme křížení, jinak pouze zkopírujeme do nové populace již existující vybrané jedince. Křížení provedeme tak, že každou hodnotu genotypu potomka vybereme náhodně buď z prvního rodiče nebo druhého rodiče. Vzniknou tak dva potomci newPopulation[iIndividuum]newPopulation[iIndividuum+1].

Po křížení se provede mutace obou potomků. V každém ze dvou potomků procházíme jejich genotyp (9 hodnot) a s pravděpodobností MUTATION_RATE hodnotu v genotypu změníme tak, že přičteme náhodnou hodnotu dánou normálním rozdělením. S vyšší pravděpodobností dojde k malé změně hodnoty a s nižší pravděpodobností dojde k vyšší změně hodnoty. Nakonec zkontrolujeme, že hodnota v genotypu je v přípustném rozsahu od 0 do  100.

Po vytvoření nové populace se provede operace, která se v evolučních algoritmech označuje jako elitismus. Je to umělé zachování nejlepších jedinců. Zaručuje, že nejlepší jedinec se v populaci zachová. To umožňuje rychleji nalézt optimální řešení. Do nové populace na první řádek zkopírujeme nejlepšího jedince v minulé generaci.

Nakonec vypíšeme číslo generace a nejlepší známé fitness a pomocí timeru počkáme, aby bylo při vykreslování okna vidět vývoj algoritmu.

Výsledek

Výsledek, který dostanete je uveden na následujícím obrázku.

Jak je z obrázku vidět, kružnice byly nalezeny správně. Velmi rychle (během pár generací) bylo dosaženo dobrého řešení, které se postupem času ještě zpřesňovalo. Kompletní kód v Javě si můžete stáhnout.

V příštím díle

Příště se podíváme na další možnosti evolučních algoritmů. Seznámíme se s některými strategiemi, které zabraňují uvíznutí v lokálním extrému a tak umožňuji rychleji nalézt globální optimum. Seznámíme se také s různými možnostmi selekce, mutace a křížení a tím dokončíme část zabývající se evolučními algortimy.

Ohodnoťte jako ve škole:
Průměrná známka 1,38

Školení: Úvod do PHP

  • Základní syntaxe, vkládání do HTML, komentáře, operátory.
  • Vestavěné a vlastní funkce, třídy a objekty, řídící struktury.
  • Práce s databází MySQL, knihovny PECL a PEAR.
´

Zjistěte více informací o školení>>

       
27 názorů Vstoupit do diskuse
poslední názor přidán 25. 8. 2013 22:02

Tento text je již více než dva měsíce starý. Chcete-li na něj reagovat v diskusi, pravděpodobně vám již nikdo neodpoví. Pro řešení aktuálních problémů doporučujeme využít naše diskusní fórum.

Zasílat nově přidané příspěvky e-mailem