Intelligens Rendszerek Elmélete dr. Kutor László
Párhuzamos keresés genetikus algoritmusokkal http://mobil.nik.bmf.hu/tantargyak/ire.html login: ire jelszó: IRE07 2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/1
A természet általános kereső algoritmusa: a genetikus algoritmus
Természetes és mesterséges genetikus terminológia Természetes
Mesterséges
Kromoszóma Karakterfüzér (sztring) (a sejtek örökletes tulajdonságokat hordozó anyaga) Gén Jellemző, karakter (az öröklődő tulajdonságokkat hordozó kromoszóma egy része, (nukleinsav molekula)) Allél A karakter (jellemző) értéke Lókusz Karakter pozíció Genotípus Karakterfüzér szerkezet (az örökletes tulajdonságok összessége) Fenotípus Paraméter készlet (az élőlény alaktani és élettani sajátosságainak összessége. Az örökletes és a környezet együttes hatására létrejött megjelenési alak) IRE 5/4 2008. ősz BMF NIK, dr. Kutor László
A genetikus algoritmus működése 1. Az optimalizálandó rendszer leírása (mesterséges kromoszómába) A rendszerre jellemző változók 2. Kezdeti generáció
GA 2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/2
2008. ősz
egymást követő generációk
GA BMF NIK,
GA dr. Kutor László
GA IRE 5/5
A genetikus algoritmus alkalmazásának feltételei
Az élet információ tárolói
1. Egyértelmű rendszerleírás egy rendszerváltozókat tartalmazó karakterfüzérbe az un. mesterséges kromoszómába. 2. Reprezentatív populáció, ami azonos formában különböző jellemzőkkel bíró egyedek (rendszerek) leírását tartalmazza. 3. Alkalmas mérési módszer, mellyel a vizsgált rendszerek jóságát meg lehet határozni. 2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/3
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/6
A genetikus algoritmusok operátorai Andrew Z. Fire Szelekció Craig C. Mello Kereszteződés Orvosi Nobel díj Mutáció 2006. 10. 2. Alacsony szintű operátorok: Mario Capecchi Dominancia Oliver Smithies Inverzió Martin Evans Törlődés 2007. 10. 08 Halkítás (erősítés) Kikapcsolás „knock out” Populációra vonatkozó operátorok: Migráció Alap operátorok:
„Házassági” korlátozás Jóság transzformáló függvények 2008. ősz
BMF NIK,
IRE 5/7
dr. Kutor László
A relatív jósággal (fitness) arányos un. rulettkerék algoritmus 1. Az egyedek jóságának meghatározása: Fi=f(Ii) 2. A populáció összes tagja jóságának meghatározása: S = ∑F 3. Az egyedek relatív jóságának kiszámítása: n
i =1
2008. ősz
BMF NIK,
Kiválasztási mechanizmusok Paraméterek:
kereszteződési pontok száma kereszteződési pontok helye
S =
n
∑F i =1
i
kiinduló sztringek: X
X 1
X 2
X 3
X 4
X 5
X 6
X X 7 8
Y
Y 1
Y 2
Y 3
Y 4
Y 5
Y 6
Y Y 7 8
X’
X 1
X 2
X 3
X 4
Y 5
Y 6
Y 7
Y 8
Y’
Y 1
Y 2
Y 3
Y 4
X 5
X 6
X 7
X 8
új sztringek:
Paraméterek: populáció méret, Reprodukciós arány (állandó, csökkenő, bővülő,..) 2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/8
2008. ősz
BMF NIK,
A genetikus algoritmus alkalmazásának menete
1. A mesterséges kromoszóma (leíró adatfüzér) 2. 3. 4. 5.
szerkezetének kidolgozása (változók és jellemzői) Kezdeti populáció létrehozása A populációt alkotó egyedek értékelése, az abszolút- majd a relatív jóság meghatározása A genetikus operátorok alkalmazásával új populáció létrehozása (pl.:szelekció, keresztezés, mutáció, stb…) A 3.-ik és a 4.-ik lépés ismétlése, amíg a megállási feltétel nem teljesül.
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/10
dr. Kutor László
Kereszteződés
A relatív jósággal (fitness) arányos un. rulettkerék algoritmus Csak a legjobbakat kiválasztó algoritmus „ elicista”
i
(Teljes Relatív Fitness TRF=1): 4. 1 és 100 közötti szám hozzárendelése a populáció minden tagjához a relatív jóságuknak megfelelően. (n = a jelenlegi populáció mérete) 5. Egy „m” véletlen szám generálása 1 és 100 között (m: az új populáció mérete) 6. m egyed (génstruktúrájának) másolása az új generációba,
IRE 5/9
IRE 5/11
dr. Kutor László
Mutáció Paraméterek:
mutációs helyek száma mutációs változás tartománya
2008. ősz
kiinduló sztring:
X
X 1
X 2
X 3
X 4
X 5
új sztring:
X’
X 1
M X 2 3
X 4
M M X 5 6 7
BMF NIK,
dr. Kutor László
X 6
X X 7 8
M 8
IRE 5/12
A genetikus algoritmus előnyei a hagyományos kereső algoritmusokhoz képest A keresési tér több pontját vizsgálja egyszerre (párhuzamosság)
Az elektronikus kereskedelmi rendszerek sikerének kiemelkedő tényezői: AAA
• Authentication:
személy-, és eszköz azonosítás Mobil IP cím menedzsment
• Authorization:
hozzáférési jogok hozzárendelése a hálózati eszközökhöz, és szolgáltatásokhoz
• Accounting:
számlázás (forgalom nyilvántartás, személyreszabott szolgáltatás kezelés)
Csak jellemzőket tartalmazó sztringgel dolgozik, a változók értelmezésétől függetlenül, ezért általános keresési algoritmus A véletlenszerű változók használata miatt a lokális minimumokra kevésbé érzékeny. Mivel a keresési szabályok nem determinisztikusak, hanem valószínűségi szabályokat alkalmaznak, így az NP teljes jellegű problémákra is megközelítést adhat. 2008. ősz
BMF NIK,
IRE 5/13
dr. Kutor László
A genetikus algoritmusok korlátai Túlságosan nagy jóságú egyedek eluralhatják a populációt Ha csak minimális különbségek vannak az egyedek között akkor nincs javulás Részleges megoldások: Különböző jóság transzformáló eljárások a keresés előrehaladtával (pl. nagy különbségek kiegyenlítése a keresés elején, kis különbségek felnagyítása a keresés vége felé)
(pl. hozzáférési időszak, sávszélesség)
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/16
Automatikus azonosítási lehetőségek 1. Saját belső, elválaszthatatlan tulajdonságok alapján 2. Hozzárendelt azonosítók alapján Tipikus hozzárendelt azonosítók, kódok:
Vonalkód Rádiófrekvenciás azonosító (RFID) Rendszám (járműveknél) Téri koordináták (GPS)
fg(xi) = αg + βg f(xi) 2008. ősz
BMF NIK,
IRE 5/14
dr. Kutor László
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/17
Automatikus személyazonosító rendszerek
Példa a GA alkalmazására 5
x2 f(x) = 3x12 + 2x22 + 3.5x32 +4x42 + 2.7x52e –Σ i=1 i
xi értelmezési tartománya -10-től +10-ig Kezdeti populáció száma: 20 Megállási feltétel: f(x) >=1.1471, vagy 105 generáció Eredmények: x1, x2, x3, x4, x5 elért generációk száma
Példa megoldás:
x1= 0.0000005267=0, x2= 0.000000015805=0, x3= 0.000000542=0, x4= 1.0.000002049=-1, x5=0.0000005267=0, g= 78967 IRE 5/15 2008. ősz BMF NIK, dr. Kutor László
Hozzárendelt információ alapú Tárgy alapú
Tudás alapú
• kulcs • jelszó, kulcsszó (mechanikus. (PIN, PUK) elektronikus) • azonosító kód • igazolvány (elektronikus • jelvény, kitűző aláírás) • azonosító kártya (mechanikus, elektronikus) • rádiófrekvenciás azonosító (RFID, NFC) 2008. ősz
BMF NIK,
Személyes jellemző alapú „Biometrikus” Biológiai
Viselkedéses
• kézírás • bőrmintázat (ujjnyomat, kéznyomat) (íráskép, dinamika) • arc • beszédhang (kép, termogramm) • gépelési ritmus • kéz • járási mód (geometria, erezet) • szem (írisz, retina) • illat • DNS dr. Kutor László
IRE 5/18
Bőrmintázat (ujj, tenyér) azonosítás • lenyomat, • nyomat, • nyom
2008. ősz
BMF NIK,
Ujjnyomat vétel a reptéren az USAban
?
IRE 5/19
dr. Kutor László
2008. ősz
Azonosító pontok (minuciák) keresése a bőrmintázaton Binarizálás
Vékonyítás 2008. ősz
BMF NIK,
BMF NIK,
dr. Kutor László
IRE 5/22
Arc azonosítás
Orientáció
Minutia keresés dr. Kutor László
IRE 5/20
dr. Kutor László
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/23
Az arc termogrammja (1)
A személyazonosítás a reptéren
2008. ősz
BMF NIK,
IRE 5/21
IRE 5/24
Az arc termogrammja (3)
Az automatikus azonosítás folyamata 1 Jellemzők mérése Azonosító jegyek számítása
2
Referencia Referencia létrehozása
Referencia-Vizsgálat Vizsgálat
3 4 IRE 5/25
Íriszkód előállítása
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/26
Beszédhang (beszélő) azonosítás
2008. ősz
BMF NIK,
dr. Kutor László
IRE 5/27
Összevetés
Azonosítás Keresés
Vizsgálati mód
Hitelesítés
IRE 5/28
