Avagy miért kell néha rossz irányba menni?

Szeretném ma bemutatni, hogy az evolúció miért jó algoritmus, és hogyan működik.

Középiskolában részt vetem egy országos informatikaversenyen. Nem tudom, miért, de élénken emlékszem az egyik feladatra. Mutattak egy algoritmust, ami azt csinálta, hogy egy térképen a közepén állsz kezdetben, majd minden irányba (a feladatban nyilván mátrix volt a térkép, és a minden irány az 8 volt) szétnézel és ellenőrzöd, hogy hol a legnagyobb a tengerszint feletti magasság, majd oda lépsz, és kezded elölről a folyamatot. Ha nem találsz a jelenlegi helyednél magasabb pontot, akkor vége. A térkép legmagasabb pontját akarta megtalálni ez az algoritmus, és a kérdés az volt, hogy mit talál meg.

Akkor még nem tudtam, hogy ennek a neve a falánk algoritmus (vagy stratégia): mindig az abban a pillanatban elérhető legnagyobb eredményre törekszik. És nem is találja meg a maximumot. Ugye eléggé egyszerűen belátható, hogy ha mindig a legnagyobb meredekség irányába vezető úton haladunk, akkor nem a legmagasabb pontot találjuk meg, hanem azt a pontot, ahová a LEGMEREDEKEBB út vezet.

Hogy jobban megvilágítsam, képzeljük el, hogy valahol a Kékes alatt lakunk, és az udvarunkból egy darab lépcsőn kell lefelé lépnünk, hogy az úthoz érjünk, ami a Kékesre vezet (a Kékestető a Kékes melletti település neve, sokan tévedésből Kékestetőnek nevezik a hegycsúcsot). Ha fel akarunk jutni a hegyre, akkor először nyilván LEFELÉ kell lépnünk majd a lépcsőn, és utána fel. De ha elindulunk a falánk stratégiával, akkor sosem fogunk lefelé lépni, így a legvalószínűbb, hogy az udvarunkon lévő vakondtúrást fogjuk megtalálni.

Szerintem eléggé látható és szemléletes, hogy a falánk algoritmus céljaink elérésére alkalmatlan (röviden: szar). Sokszor írtam itt a blogon pl. a magyar parasztokról, akik hihetetlen akaraterővel, küzdelemmel kioptimalizálták, hogy hogyan legyen a legtöbb földjük, a legtöbb tehenük, de arra nem gondoltak, hogy ha egyszer majd nem a föld lesz a minden, vagy nem tudják megvédeni a földet, akkor mi lesz. Vagy a németek, akik nagyon nagy hatékonysággal tudnak menni egy irányba, még ha az rossz is. Láttuk a világháborúkban.

Na jó, ez nem alkalmas, de mi akkor a jó megoldás? A legjobb nyilván az, hogy ismerjük az egész térképet, és az alapján megkeressük a legmagasabb csúcsot, megtervezzük az utat, és készen vagyunk. Ezt lehetne isteni algoritmusnak is nevezni, mivel MINDEN információnak a birtokában kell lennünk. Tehát ezzel megtaláljuk az utat, ha tudjuk, hogy hová kell menni. De nyilván az ember (meg a kecske meg a giliszta) nincs ennek a tudásnak a birtokában, de mégis szeretne "győzni". Ezt azért tettem idézőjelbe, mert nem igazán tudja a szarvasbika, ami párosodni akar, hogy ő hová tart (és az ember sem tudja), de valami maximális pont felé. A térképen a legmagasabb pontot akarja megtalálni. Most ezt nem részletezem, hogy miért meg mi az, csak annyit, hogy hogyan lehet oda eljutni.

Szóval a Kékes alatt lakunk, nincs meg az isteni térkép, de mi mégis meg akarjuk találni az ország legmagasabb pontját. Mi tudunk tenni? A másik megoldás az, hogy egyszerre több küldöncöt is elindítunk, ami véletlenszerűen össze-vissza lépeget, és mindig jelenti nekünk, hogy milyen magasan tart. Egy idő után azt mondjuk, hogy az eddigi legmagasabb pontot kinevezzük az ország tetejének. Ezzel a megoldással az a baj, hogy egyáltalán nem hatékony, rengeteg erőforrást használ el, sőt még az is simán lehet, hogy nem találja meg a tetőre vezető utat végül.

Valahogy ötvöznünk kellene a falánk és a véletlenszerű algoritmust! És valójában az evolúció ezt teszi. De hogyan?

Nézzük meg a hátizsákfeladatot!

Van egy kofa, aki minden héten a piacra megy árulni, de a zsákjába meghatározott mennyiségű áru fér be. Nem tudja, hogy melyikre lesz azon a héten kereslet, nem tudja, hogy az alku közben melyiken éri el a legnagyobb hasznot. És nyilván a legnagyobb profitot szeretné hazavinni. Mit csinál ilyenkor? Megpróbál több kombinációt is elkészíteni a zsák tartalmára. Kiviszi őket a piacra,és felírja, hogy mikor melyiknél mennyi volt a haszon. Tudja, hogy a falánk algoritmus nem vezet sikerre, ezért nem mindig ugyanazt viszi ki, egy idő után a két legnagyobb haszonnal eladott kombinációt egyesíti: véletlenszerűen kidob csomagokat az egyikből, és a másikból kitölti a zsákot. Majd megint elviszi őket a piacra. Olyat is csinál, hogy néha a kidobott helyre nem a másikból választ, hanem véletlenszerűen egy teljesen új csomagot. És persze mindig írja a hasznot. Az így létrehozott csomagok nem mindig lesznek jobbak az eredeti (szülő) csomagoknál. Sőt sokszor kisebb lesz a  haszon. De nem fog egy lokális maximumon megrekedni sem a vakondtúrásnál, és nem lesz végtelen hosszúságú véletlenszerű tapogatózás sem.

Azt hiszem, nagyjából sikerült is megvilágítanom az evolúció három fő alapszabályát: szelekció, kombináció, mutáció. És persze az iteráció.

1. Jutalmazás: mindig figyelem a megoldásokat, hogy melyik jobb a többinél. És ha az, akkor azt előnyben részesítem.

2. Kombináció: nem véletlenszerűen pakolom össze a csomagot, hanem a már jól működő megoldásokból válogatom össze őket.

3. Változtatás: néha behozok teljesen ismeretlen eddigi árufajtát is. Nagy hülyeségnek tűnik, és sokszor kisebb hasznot is jelent. De ha ezt nem tenném, akkor sokkal nagyobb valószínűséggel ragadnék bele egy lokálisan jó, de globálisan rossz megoldásba.

4. Ismétlés: nyilván nagyon sokszor meg kell ismételnem az előbbi szabályokat, hogy közelítsek a jó megoldáshoz.

Ugye a való életben a szelekció az, mikor az életképesebb marad életben, a kombináció a párosodás, a mutáció a külső környezeti hatások miatt kialakuló génhibák.

És az a jó ebben a felismerésben, hogy ez egy általános megoldási lehetőség arra az esetre, mikor nem tudjuk, hogy mi a jó, a legjobb megoldás, és szép lassan szeretnénk megtalálni. Az általános lehetőség itt azt jelenti, hogy ehhez nem kell biológiai rendszer. Bármilyen elméleti, fizikai, matematikai, kémiai modellben működőképes.

Azonban itt felhívnám a figyelmet arra, hogy ebben a négy lépésben rengeteg további paraméter van. Mikor azt mondom, hogy szelekció, akkor azon belül ezerféle megoldás létezik, mint ahogy a kombinációnál is. A mutációnál pl. nem mindegy, hogy milyen gyakran alkalmazzuk. Ha nagyon sokszor, akkor lerontja a hatékonyságunkat, ha túl kevésszer, akkor meg beleragadunk a lokális maximumba (vakondtúrás). Tehát ez egy nagyon általános modell, ha konkrét feladatot szeretnénk megoldani, akkor bizony nagy tere van a kísérletezésnek.

Ami viszont jó benne, hogy a világegyetem másik felén is működik. Ha eltekintünk ugye attól az esettől, hogy tudjuk a megoldást, akkor ez a legjobb "bolyongási" algoritmus, amivel megkereshetjük azt. De ami biztos: nem vezet egyenes út a megoldáshoz, néha rossz irányba is kell menni. Mondhatjuk, hogy ez a természet parancsa.

És itt kapcsolódunk is a mai liberális világfelfogáshoz, ami azt mondja, hogy azért kell védeni a kisebbségeket, mert az ugyan sok esetben nem hatékony, azonban ha mindig elnyomjuk őket, akkor beleragadunk a lokális maximum csapdájába. És ez tényleg igaz, de azt is láttuk, hogy a rossz irányba tett lépéseknek gátat kell szabni. Ha túl sokszor alkalmazzuk, akkor sokkal többször mehetünk rossz irányba, mint hogy az áldásos lenne. Nem tudjuk kiszámolni, hogy mennyi mutáció a hasznos, de az biztos, hogy nem a nulla és nem a sok.

A kultúrák általában a nullát szeretik. Suba subához, guba gubához, ahogy nagyanyám mondta. És láttuk abban a zsákutcát. Pl. a fehér ember általában lenézi a feketéket. Az igaz, hogy innen nézve "visszalépés" az IQ-juk. A feketék is biztos lenézik a fehéreket, hogy gyengék és nem szaporodnak. Onnan nézve nekik is igazuk van. Az ázsiaiak biztos lenézik a lusta fehéreket stb. De lehetséges, hogy a több jó megoldási mód közül (onnan tudjuk, hogy jó, hogy mindegyik létezik, van létjogosultsága) mindegyik zsákutcába jutna önmagában, de a különböző életstratégiák keveredésével majd kialakul egy jobb megoldás. Persze még egyszer mondom: a mutációk és  a rosszabb megoldásokkal történő kombináció általában rosszabb eredményre vezet,csak hosszú időtávon és ritkán lesz jobb a kialakult új megoldási mód.

(Ha még sok ilyen hülyeséget :-) akarsz hallani, akkor én innen vettem: https://www.libri.hu/konyv/kit_yates.ne-hidd-el-az-igazsagot.html )