This is an old revision of the document!
Table of Contents
Genetikus algoritmus – Limonádérecept optimalizálása
Egy büfé szeretné megtalálni a vásárlók számára legfinomabb limonádé receptjét.
Egy recept három összetevő mennyiségével adható meg:
- citromlé: ml
- cukor: g
- víz: ml
1. Reprezentáció
Egy kromoszóma tehát három számból áll:
\[ [\text{citromlé}, \text{cukor}, \text{víz}] \]
Például:
\[ [100,40,800] \]
jelentése:
- 100 ml citromlé,
- 40 g cukor,
- 800 ml víz.
Ez valós/egész értékű kódolás, nem bináris reprezentáció.
2. Kezdeti populáció
Négy receptet próbáltunk ki. A kóstolók minden receptet 1-től 10-ig értékeltek.
| Egyed | Citromlé (ml) | Cukor (g) | Víz (ml) | Értékelés |
| A | 100 | 40 | 800 | 6 |
| B | 150 | 50 | 750 | 9 |
| C | 80 | 60 | 850 | 5 |
| D | 120 | 30 | 800 | 7 |
A kromoszómák:
\[ A=[100,40,800] \]
\[ B=[150,50,750] \]
\[ C=[80,60,850] \]
\[ D=[120,30,800] \]
A fitnesszérték a kóstolók által adott pontszám.
Minél magasabb ez az érték, annál jobb az egyed.
3. Szelekció
Használjunk tornaszelekciót.
Két-két recept versenyez egymással.
Első torna
A és B:
\[ A=6 \]
\[ B=9 \]
A kiválasztott egyed:
\[ \boxed{B=[150,50,750]} \]
Második torna
C és D:
\[ C=5 \]
\[ D=7 \]
A kiválasztott egyed:
\[ \boxed{D=[120,30,800]} \]
A következő lépésben tehát B és D lesznek a szülők.
4. Keresztezés
A szülők:
| Szülő | Citromlé | Cukor | Víz |
| B | 150 | 50 | 750 |
| D | 120 | 30 | 800 |
Alkalmazzunk számtani keresztezést.
Az utód minden génje legyen a két szülő megfelelő génjének átlaga.
Citromlé
\[ \frac{150+120}{2}=135 \]
Cukor
\[ \frac{50+30}{2}=40 \]
Víz
\[ \frac{750+800}{2}=775 \]
Így az új kromoszóma:
\[ \boxed{[135,40,775]} \]
Az új recept tehát:
- 135 ml citromlé,
- 40 g cukor,
- 775 ml víz.
5. Mutáció
A genetikus algoritmusban időnként véletlenszerű módosítást végzünk az egyedeken.
Tegyük fel, hogy az új egyed cukormennyisége mutálódik, és 5 grammal növekszik:
\[ 40\rightarrow45 \]
A mutáció előtti egyed:
\[ [135,40,775] \]
A mutáció utáni egyed:
\[ \boxed{[135,45,775]} \]
Tehát az új kipróbálandó recept:
- 135 ml citromlé
- 45 g cukor
- 775 ml víz
6. Az új egyed kiértékelése
Az új receptet is meg kell kóstoltatni.
Tegyük fel, hogy az értékelése:
\[ \boxed{9,5} \]
A mutációval létrejött egyed tehát jobb lett, mint a korábbi populáció legjobb receptje:
\[ 9,5>9 \]
Ezért érdemes lehet az új egyedet megtartani a következő generációban.
Fontos: a mutáció nem garantálja a javulást. Elképzelhető, hogy a mutációval létrejövő recept rosszabb értékelést kap.
Új populáció kiválasztása
A keresztezés és a mutáció után el kell döntenünk, hogy mely egyedek kerüljenek be a következő generációba.
A genetikus algoritmusban általában a populáció méretét állandó értéken tartjuk. Ha tehát az eredeti populáció 4 egyedből állt, akkor a következő generáció is 4 egyedből fog állni.
Jelöltek:
| Szülő | Citromlé | Cukor | Víz | Értékelés |
| A | 100 | 40 | 800 | 6 |
| B | 150 | 50 | 750 | 9 |
| C | 80 | 60 | 850 | 5 |
| D | 120 | 30 | 800 | 7 |
| E | 135 | 45 | 775 | 9.5 |
Új populáció kiválasztása elitizmussal
Az elitizmus lényege, hogy a korábbi populáció egy vagy több legjobb egyedét automatikusan megtartjuk.
Ezzel elkerülhetjük, hogy egy már megtalált jó megoldás véletlenül eltűnjön a következő generációból.
Tegyük fel, hogy 1 egyedes elitizmust alkalmazunk.
A jelenlegi populáció legjobb egyede:
\[ E=[135,45,775], \qquad f(B)=9.5 \]
Ez automatikusan bekerül az új populációba.
Az új populáció többi helyét további, valamilyen stratégia szerint kiválasztott egyedekkel töltjük fel.
A következő iterációban már ebből a populációból indulunk ki.