Institute of Information Science - University of Miskolc

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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(E)=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.