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] a 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.
