Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
A genetikus algoritmus, mint a részletes modell többszempontú és többérdeku˝ "optimálásának" általános és robosztus módszere Balogh Sándor Kaposvári Egyetem, Informatika Tanszék
I. Kaposvári Gazdaságtudományi Konferencia
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
Modellezés és szimuláció Modellezés „A tudomány nem próbál végso˝ magyarázatot adni, fogalmakat értelmezni is alig. A természettudomány modelleket alkot. Modell alatt egy olyan matematikai ˝ amelyik – bizonyos szóbeli interpretáció struktúra értendo, hozzáfuzésével ˝ – leírja a jelenséget. Egy ilyen matematikai struktúra létjogosultságát egyedül az adja, hogy sikeresen ˝ elorelátja a jelenségeket, tehát muködik.” ˝ (Neumann János) Szimuláció „A szimuláció egy rendszer modelljének a megfelelo˝ bemenetekkel (inputokkal) történo˝ ellátása, muködtetése ˝ (driving) és a kimenetek (outputok) megfigyelése”. (Bratley). Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
Modellezés és szimuláció Modellezés „A tudomány nem próbál végso˝ magyarázatot adni, fogalmakat értelmezni is alig. A természettudomány modelleket alkot. Modell alatt egy olyan matematikai ˝ amelyik – bizonyos szóbeli interpretáció struktúra értendo, hozzáfuzésével ˝ – leírja a jelenséget. Egy ilyen matematikai struktúra létjogosultságát egyedül az adja, hogy sikeresen ˝ elorelátja a jelenségeket, tehát muködik.” ˝ (Neumann János) Szimuláció „A szimuláció egy rendszer modelljének a megfelelo˝ bemenetekkel (inputokkal) történo˝ ellátása, muködtetése ˝ (driving) és a kimenetek (outputok) megfigyelése”. (Bratley). Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
˝ A hardver környezet fejlodése
16 bites architektúrák (i186,i286,..)
32 bites architektúrák (i386,pentium4,..)
64 bites architektúrák (opteron,core 2 duo,..)
Szuperszámítógépek, klaszterek... Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
A szoftver környezet változása
Zárt forráskódú DOS Windows 95/98 Windows NT/XP
Nyílt forráskódú Linux Slackware/Debian/Ubuntu/OpenSSI BSD OpenBSD/NetBSD/FreeBSD
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
Modellek fejlesztése
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Evolúció a természetben Az élo˝ sejtekben a kromoszómák tárolják az egyedek felépítéséhez szükséges információt
˝ „Változatos” élolények jönnek a kromoszómák keresztezése, mutálódása miatt
A természetes szelekció az „életképesebb” egyedek túlélését segíti Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
A genetikus algoritmus folyamatábrája
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
A feladat genetikus kódolása A genetikus ABC meghatározása Gének és alléljeik valós értéku˝ diszkrét
Kromoszóma struktúrája „sztring” típusú fa típusú
Értékelési szempontok kiválasztása egyszempontú többszempontú
A kezdeti populáció létrehozása véletlenszeruen ˝ és/vagy meglévo˝ megoldásokat felhasználva Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
A feladat genetikus kódolása A genetikus ABC meghatározása Gének és alléljeik valós értéku˝ diszkrét
Kromoszóma struktúrája „sztring” típusú fa típusú
Értékelési szempontok kiválasztása egyszempontú többszempontú
A kezdeti populáció létrehozása véletlenszeruen ˝ és/vagy meglévo˝ megoldásokat felhasználva Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
A feladat genetikus kódolása A genetikus ABC meghatározása Gének és alléljeik valós értéku˝ diszkrét
Kromoszóma struktúrája „sztring” típusú fa típusú
Értékelési szempontok kiválasztása egyszempontú többszempontú
A kezdeti populáció létrehozása véletlenszeruen ˝ és/vagy meglévo˝ megoldásokat felhasználva Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Genetikus operátorok Szelekció rulett kerék versengéses stb.
Keresztezés n-pontú permutációs ˝ ol ˝ stb. több szülob
Mutáció inverziós stb.
Kicserélés Elitizmus ˝ Szüloket cserélem stb. Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Genetikus operátorok Szelekció rulett kerék versengéses stb.
Keresztezés n-pontú permutációs ˝ ol ˝ stb. több szülob
Mutáció inverziós stb.
Kicserélés Elitizmus ˝ Szüloket cserélem stb. Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Genetikus operátorok Szelekció rulett kerék versengéses stb.
Keresztezés n-pontú permutációs ˝ ol ˝ stb. több szülob
Mutáció inverziós stb.
Kicserélés Elitizmus ˝ Szüloket cserélem stb. Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Genetikus operátorok Szelekció rulett kerék versengéses stb.
Keresztezés n-pontú permutációs ˝ ol ˝ stb. több szülob
Mutáció inverziós stb.
Kicserélés Elitizmus ˝ Szüloket cserélem stb. Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Szimulációs specialitások Egy megoldás értékelése egy részletes dinamikus szimuláció ˝ nagy az eroforrás igénye, ezért korlátozott számú szimuláció ˝ végezheto párhuzamosíthatóság, skálázhatóság ˝ ˝ minden értékelt megoldás megorzésének lehetosége kis populáció méret, korai konvergencia elkerülése szülo˝ cserével
˝ ˝ épülnek a modellek Folytonos és diszkrét építoelemekb ol „vegyes” kromoszómák használata ˝ lebegopontos gének (paraméterek) ˝ tulajdonság osztályok elemei (strukturális éptoelemek)
Több értékelési szempont többszempontú genetikus algoritmusok dominancia bázisú Pareto optimálás legtöbbször a Pareto front felderítése nem cél Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Szimulációs specialitások Egy megoldás értékelése egy részletes dinamikus szimuláció ˝ nagy az eroforrás igénye, ezért korlátozott számú szimuláció ˝ végezheto párhuzamosíthatóság, skálázhatóság ˝ ˝ minden értékelt megoldás megorzésének lehetosége kis populáció méret, korai konvergencia elkerülése szülo˝ cserével
˝ ˝ épülnek a modellek Folytonos és diszkrét építoelemekb ol „vegyes” kromoszómák használata ˝ lebegopontos gének (paraméterek) ˝ tulajdonság osztályok elemei (strukturális éptoelemek)
Több értékelési szempont többszempontú genetikus algoritmusok dominancia bázisú Pareto optimálás legtöbbször a Pareto front felderítése nem cél Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Szimulációs specialitások Egy megoldás értékelése egy részletes dinamikus szimuláció ˝ nagy az eroforrás igénye, ezért korlátozott számú szimuláció ˝ végezheto párhuzamosíthatóság, skálázhatóság ˝ ˝ minden értékelt megoldás megorzésének lehetosége kis populáció méret, korai konvergencia elkerülése szülo˝ cserével
˝ ˝ épülnek a modellek Folytonos és diszkrét építoelemekb ol „vegyes” kromoszómák használata ˝ lebegopontos gének (paraméterek) ˝ tulajdonság osztályok elemei (strukturális éptoelemek)
Több értékelési szempont többszempontú genetikus algoritmusok dominancia bázisú Pareto optimálás legtöbbször a Pareto front felderítése nem cél Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
A módszer szoftveres megvalósítása
A program c++ nyelven készült FOX grafikus könyvtár LGPL Plplot könyvtár LGPL
Támogatott platformok Windows 95/98/2000/XP Linux/XFree86 UNIX/X11 munkaállomások (IRIX, Solaris, Tru64, AIX, HP-UX, FreeBSD, SGI, stb.)
Multiprocesszoros környezetben jól skálázódik
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Genetikus futás 1 szempontú futás
9 szempontú futás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Windows 2003 szerver
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Linux (Ubuntu)
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
OpenSSI Cluster
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
˝ Az eloadás vázlata 1
Részletes modell és szimuláció Definíciók ˝ Számítástechnika fejlodése Modellek kezelése
2
Genetikus algoritmusok Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
3
Összefoglalás
Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Az algoritmus lényege Szimulációs sajátosságok Implementáció Gyakorlati alkalmazások
Befejezett és folyamatban lévo˝ projektek
Szakaszos polimerizáció modellezése és tervezése Szimulált mozgóágyas kromatográfia modellezése Baromfi telep modellezése Családi gazdaság modellezése Kvalitatív egészségügyi kockázatelemzés Metabolikus folyamatok modellezése Balogh Sándor
Genetikus algoritmus
Részletes modell és szimuláció Genetikus algoritmusok Összefoglalás
Összefoglalás
˝ Az általunk használt genetikus algoritmus elosegítette a gyakorlati problémák megoldását A kidolgozott kódolás és a genetikus operátorok változtatás nélkül alkalmazhatók voltak a feladatok széles spektrumára Természetesen még további fejlesztések szükségesek az új kihívásoknak való megfeleléshez
Balogh Sándor
Genetikus algoritmus
