notification icon
Ne maradj le semmiről! Iratkozz fel értesítéseinkre!
Máté Balázs online marketing asztali

Genetikus algoritmusok

Genetikus algoritmusok

hirdetes

Iratkozz fel Te is Youtube csatornánkra, kattints az alábbi YOUTUBE ikonra! 

 

 

 

A genetikus algoritmusok olyan, az informatikában használatos alternatív keresési technológiák, amelyekkel többek között közelítõ becsléseket, határértékeket tudunk számoltatni anélkül, hogy ismernénk a probléma megoldásához vezetõ pontos matematikai modellt. Tipikus felhasználási eset még az is, ha egy feladat megoldásához esetleg több, nagy erõforrás igényû út tartozik, és ezek közül szeretnénk kiválasztani az optimálisat.

Honlapkészítés online marketing tanácsadó segítéségvel? A hatékony honlapkészítés titka az online marketing tanácsadás alapján készülõ honlap!

Kérje ajánlatunkat itt!

Genetikus algoritmusok

A genetikus algoritmusok elmélete sokan kölcsönzött a Darwin-féle evolúcióelmélet alapvetõ mechanizmusaiból. A folyamat lényege az, hogy egy létrehozunk egy populációt, amely egyedei génekkel rendelkeznek - a gének a probléma megoldásának atomi részeit alkotják -, és az egyedek célzott "tenyésztésével" megpróbáljuk a megoldást megtalálni.

Az alappopuláció meghatározása

A könnyebb érthetõség kedvéért tegyük fel, hogy egy hatodfokú, hatismeretlenes egyenletet szeretnénk megoldani ilyen módszerrel. Ekkor egy egyed hat génnel rendelkezik, amelyek az egyenlet hat ismeretlenét képezik le. A populáció mérete kezdetben legyen pl. százezer egyed, amelyeknek génjeit véletlenszerûen feltöltjük egy-egy tetszõleges számmal.

Következõ lépésben meg kell határoznunk az egyes egyedek életképességét. Ekkor behelyettesítjük minden egyes egyed génjeit az egyenletbe, és megnézzük, hogy az egyenlet két oldala megegyezik-e. Ha igen, akkor megtaláltuk a megoldást (a véletlenszámok kezdeti felírásánál ennek esélye természetesen elhanyagolható), ha nem, akkor megnézzük, hogy mekkora az eltérés a kívánt értéktõl. Minél kisebb ez a differencia, annál életképesebbnek vesszük azt az egyedet.

Kiválasztás

Ezek után a kiválasztás történik - meg kell határoznunk, hogy mely egyedek maradnak meg és örökítik génjeiket a következõ generáció számára. Általában azokat az egyedeket célszerû kiválasztani, amelyek életképessége kedvezõbb, azonban nem szabad hagyni azt sem, hogy a gyengébb egyedek nyom nélkül eltûnjenek a populációból - késõbb még hasznos információt nyerhetünk ki belõlük.

hirdetes
Nagyon sok kiválasztási szabály létezik, az egyik leggyakrabban alkalmazott az ún. rulett-kerék szabály. Ekkor a rulett keréken olyan az egyedek életképességével egyenes arányban határozunk meg körcikkeket. Mivel a jobb egyedek területe nagyobb, az esélyük is nagyobb, hogy a rulett-golyó ott álljon meg, így biztosítva az egyed túlélését, de így a gyengébbek is kapnak esélyt, ha kisebbet is.

Reprodukció

Két olyan egyed, amely a kiválasztás után megmaradt, gyermeket "hoz világra". A gyermek tulajdonságait a két szülõ adottságai határozzák meg, az utód egy adott génjét ugyanis véletlenszerûen vagy az egyik, vagy a másik szülõ megfelelõ génje határozza meg.
A rendszer nem biztos hogy megoldásra fog vezetni, ha nem alkalmazunk mutációt is. Ennek mértékének azonban megfelelõen alacsonynak kell lennie, hogy ne zilálja szét a teljes populációt. Ha mutáció lép fel, akkor a gyermek egyed egyik génje nem az egyik szülõtõl származik, hanem véletlenszerûen jön létre.
A szülõk a reprodukció után megszûnnek, példánkban tehát a populáció egyedszámának fenntartásához két utódot hoznak létre. Az új egyedeknek ismételten kiszámoljuk az életképességét, aztán újra a kiválasztásra kerül sor.

hirdetes

Megoldás

Néhány százezer generáció után azt vehetjük észre, hogy az egyedek "jósága" egyre nõ, tehát egyre közelebb kerülünk a megoldáshoz. Amennyiben elértünk egy elõre meghatározott határértéket, akkor a számítást befejezzük.
A megoldása gyorsasága - és gyakran annak megléte is - függ egyrészt attól, hogy jól választjuk-e meg az alappopulációt, értve ezt mind az egyedszámra, mind a kezdeti génállományra (ennél az egyenletnél tehát "meg kell sejtenünk", hogy az egyenlet gyökei kb. milyen tartományban lehetnek), másrészt a kiválasztási szabálytól.

Természetesen a fent említett példa nem ideális, nem tükrözi a genetikus algoritmusok használhatóságát, hiszen az egyenlet megoldásait nagy valószínûséggel a matematikai analízis módszereivel is meghatározhatjuk, azonban ez egy olyan egyszerû esetet eredményezett, amelyen könnyen meg lehet mutatni ezen eljárás sajátosságait.
Az elõnyök olyan esetekben jelentkeznek, amelyeknél a megoldás egyéb módokon túl sokáig tartana - elég pl. az utazó ügynök (http://www.agent.ai/?folderID=168&articleID=862) problémájára gondolni.

Honlapkészítés online marketing tanácsadó segítéségvel? A hatékony honlapkészítés titka az online marketing tanácsadás alapján készülõ honlap!

Kérje ajánlatunkat itt!

Forrás:

hirdetes

Ha tetszett ez a cikk, oszd meg ismerőseiddel, kattints ide:

MEGOSZTÁS MEGOSZTÁS MEGOSZTÁS MEGOSZTÁS

Ezek is érdekelhetnek

hirdetes
hirdetes

Hasznos volt számodra ez a cikk?

Mondd el mennyire!

Szavazatok száma: 143

Átlagos értékelés: 5.0

Szótár

minõségfejlesztés

a minõségirányításnak az a része, amely a minõségi követelmények teljesítési... Tovább

auditcsoport

egy, vagy több auditor , aki auditot végez 1. MEGJEGYZÉS: Az... Tovább

Tovább a lexikonra