József Attila Tudományegyetem, Informatikai Intézet

http://www.inf.u-szeged.hu/~csendes

Az előadás áttekintést nyújt a kemometriában, és tágabb értelemben a kísérletes természettudományban használatos egyes nagyobb optimalizálási módszerosztályokról. Tárgyaljuk az egyes eljárás-fajták előnyeit és hátrányait, a hatékony és hatásos használatuk feltételeit.

A kevésbé ismert intervallum aritmetikán alapuló algoritmusok a kerekítési hibákat is figyelembe véve garantált megbízhatóságú eredményeket tudnak adni, és így akár matematikai bizonyítások részei is lehetnek (lásd például a négyszín sejtést, illetve a Kepler-sejtés bizonyítását). Az algoritmusok részleteinek ismertetésén túl bemutatunk egy vegyipari rendszertervezési feladatot is, amelynek megoldásában intervallumos optimalizálási eszközök elengedhetetlenek voltak annak igazolásában, hogy a szűkebb szakmát is meglepő módon szeparátor-hálozatokban az optimális költségű berendezésben is lehetséges a redundancia, a reciklizálás.

Az evolúciós, és azon belül a genetikus algoritmusok olyan esetben előnyösek, amikor a feladat célfüggvényének ismeretlen szerkezetét nem lehet kihasználni, amikor a megoldások lehetséges elhelyezkedéséről semmilyen információval sem rendelkezünk. Ezek az eljárások ilyen esetben hatásosak lehetnek, bár hatékonyságuk rendszerint elmarad a hasonló, sztochasztikus algoritmusokétól, ha az azok használatához szükséges derivált és egyéb információk rendelkezésre állnak. A genetikus algoritmusok olyankor használhatók sikeresen, ha a mutáció, rekombináció és a szelekció eszközei az adott feladat szerkezete miatt találóak. Az evolúciós módszerek új osztálya az ún. multiágens eljárásoké, ezek hatékonyan párhuzamosíthatók.

A szimulált hőkezelés (simulated annealing) eljárások hasonló módon olyan feladatokhoz jelenthetnek megoldást, amelyek esetén a kifinomultabb algoritmusok a feladatra vonatkozó többletinformációk (az első, vagy a második derivált, a Lipschitz konstans stb.) hiányoznak. A szimulált hőkezelési eljárások egy új osztályát képezik a tabusearch jellegű algoritmusok, amelyeknek egy érdekes alkalmazását bemutatjuk a körpakolási feladatokon. Ugyan a konvergencia-eredmények rendelkezésre állnak, az evolúciós és a szimulált hőkezelésen alapuló módszerek sebessége nehéz feladatokon rendkívül lassú lehet. Ismertetjük még a klaszterezési technikán alapuló hatékony, deriváltakat nem igénylő sztochasztikus optimalizálási módszerünket is, amely akadémiai célra letölthető a következő címről:

ftp://ftp.jate.u-szeged.hu/pub/math/optimization/index.html

A kapcsolódó kutatásokat az OTKA T 017241, az FKFP 0739/97 és 0449/99 pályázatok támogatták.