Računala su široko primjenjiva u automatizaciji i računanju ali i ona imaju ograničenja svojih mogućnosti. Jedno od takvih ograničenja jest složenost algoritama s kojima mogu raditi u realnom vremenu. Elektronička računala u većini slučajeva ne mogu potpuno riješiti NP težak problem ali uz pomoć određenih algoritama mogu pronaći skoro optimalna rješenja. Najjednostavniji takav algoritam je pohlepni algoritam. Njegova jednostavnost uzima danak u kvaliteti rješenja; pohlepni algoritam će dati zadovoljavajuće rješenje samo ako je odmah u početku pretpostavljeno rješenje koje je blizu nekog dobrog rješenja.

Mnogi algoritmi nadopunjuju pohlepni algoritam tehnikama bijega iz lokalnog minimuma a među takvim algoritmima je simulirano kaljenje. Simulirano kaljenje se pak nadograđuje paralelnim ispitivanjem više rješenja u genetsko kaljenje, kako bi se još uspješnije pronašlo optimalno rješenje.

Kaljenje je postupak polaganog hlađenja vruće mase (npr. stakla) kako bi se čim pravilnije formirali kristali i time dobio čvršći materijal. Simulirano kaljenje je heuristički algoritam koji oponaša pronalazak stanja minimalne energije u procesu kaljenja metala. To se postiže oponašanjem učinka temperature u gibanju čestica kroz stanja različitih energija i postepenim smanjivanjem te temperature. U simuliranom kaljenju gleda se ponašanje samo jedne čestice (rješenja) u procesu kaljenja.

U svakoj iteraciji, za stanje s iz prethodne iteracije, bira se proizvoljno susjedno stanje s'. Ukoliko je energija stanja s' manja od energije stanja s, čestica prelazi u stanje s'. Ako je stanje s' stanje više energije, s prelazi u s' uz vjerojatnost koja ovisi o temperaturi.

Algoritam kreće od neke zadane "visoke" temperature te ju kroz iteracije smanjuje do "apsolutne nule". Funkcija vjerojatnosti prelaska iz stanja niže u stanje više energije može biti bilo koja funkcija uz ograničenja da je ta funkcija pozitivna te da njena vrijednost opada s padom temperature i porastom razlika energija između stanja. Time se nastoji izbjeći loša karakteristika pohlepnog algoritma: zaustavljanje u lokalnom minimumu koji je puno lošiji od globalnog minimuma.

Slika 2.1 Pseudokod algoritma

Kod pretraživanja simuliranim kaljenjem, nerijetko se prakticira višestruko ponavljanje postupka kako bi se dobilo što bolje riješenje. Algoritam genetskog kaljenja kojeg je Kennet V. Price 1994. objavio u časopisu "Dr. Dobb's Journal" proširuje simulirano kaljenje upravo s tom idejom. Umjesto da se rješenja simuliranog kaljenja generiraju nezavisno jedno od drugog, generiraju se paralelno i u istom sustavu. Čestice, kao i u simuliranom kaljenju, nezavisno traže stanje minimalne energije ali razmjenjuju energiju koja omogućava prelazak u stanja više energije. Ukoliko neka čestica prijeđe u povoljnije stanje (stanje manje energije), ona emitira energiju u sustav i tu energiju ostale čestice mogu iskoristiti za prelazak u nepovoljnija stanja. Hlađenje se ostvaruje tako da se nakon svake iteracije dio slobodne energije, energije koja ne pripada niti jednoj čestici, izgubi (emitira van sustava). Na taj način se još bolje imitira stvarno kaljenje.

Genetsko kaljenje na jednostavniji način može odlučiti da li čestica može preći u nepovoljnije stanje. Metoda koju je Price predložio je da se prije svake iteracije slobodna energija E jednoliko rasporedi po česticama tako da svaka može preći u stanje koje ima maksimalno za E/N (N je broj čestica) veću energiju od početne čestice.

Slika 2.2 Pseudo kod algoritma

Genetsko kaljenje se može primjenjivati u rješavanju velikog broja NP teških problema. Svoju široku primjenjivost zahvaljuje svojom jednostavnošću zahtjeva. Praktički svi heuristički i metaheuristički algoritmi zahtijevaju da se za dani problem definira kako će se kodirati riješenje (struktura čestice) te da se definira funkcija dobrote rješenja. Genetsko kaljenje uz te dvije definicije još zahtjeva definiciju funkcije mutacije a ona se često može lako izvesti iz strukture čestice.

U slijedećim poglavljima su opisani problem trgovačkog putnika i problem podijele grafa. Oba problema su statički problemi (problem se ne mijenja tokom vremena) no i dinamički problemi, kao što je problem mrežnog usmjeravanja, rješivi su genetskim kaljenjem.

Problem trgovačkog putnika (engl. travelling salesman problem u daljnjem u TSP) je problem pronalaska najkraćeg puta tako da se obiđu svi unaprijed zadani gradovi. Matematički, taj se problem svodi na problem pronalaska najkraćeg Hamiltonovskog puta u težinskom grafu. Graf se načini tako da vrhovi predstavljaju gradove, bridovi veze između gradova a težina brida cijenu puta između povezanih gradova. Put koji je riješenje takvog problema može se definirati kao uređena n-torka (n = |V|, broj vrhova) koja predstavlja raspored kojim se gradovi/vrhovi posjećuju.

Egzaktno rješavanje problema bi zahtjevalo da se ispitaju sve moguće rute, odnosno sve permutacije rasporeda (n-torke) a složenost takvog postupka je O(n!). Pomoću tzv. dinamičkog rješavanja, ta složenost se može smanjiti na O(n²2ⁿ) odnosno na eksponencijalnu složenost. Oba pristupa bi na suvremenim računalima već za 45 gradova zahtijevala preko godine dana računanja.

Problem dijeljenja grafa (engl. graph partitioning problem, u daljnjem u GPP) je problem podjele vrhova grafa u m skupova tako da su ti skupovi otprilike jednake veličine i da minimalan broj bridova veže vrhove u različitim skupovima. Praktični primjer tog problema je podjela n komponenti na m čipova, tako da su čipovi minimalno povezani.

Egzaktno rješavanje i ovog problema bi u općem slučaju zahtjevalo ispitivanje svih kombinacija. Kako je ukupan broj tih kombinacija mⁿ algoritam koji ispituje te kombinacije bi imao eksponencijalnu složenost.

Mnogi NP teški problemi nisu rješivi egzaktnim postupcima i zbog toga su razvijeni brojni algoritmi koji na pametan način pokušavaju pogoditi rješenje. Jedan od jednostavnijih je genetsko kaljenje. Zbog svoje jednostavnosti ono možda ima lošije performanse do složenijih algoritma ali zato se može primijeniti na velikom broju problema. U usporedbi s algoritmima iz kojeg se razvilo (pohlepni algoritam i simulirano kaljenje), genetsko kaljenje za isti broj operacija pronalazi bolje rješenje.

[1]Dr. Dobb's Algorithm Alley, october 1st 1994, http://www.ddj.com/architect/184409333?pgno=10, 17. 12. 2008.
[2]Evolutionary algorithm, http://en.wikipedia.org/wiki/Evolutionary_algorithm, 17. 12. 2008.
[3]Simulated annealing, http://en.wikipedia.org/wiki/Simulated_annealing, 17. 12. 2008.
[4]NP-complete, http://en.wikipedia.org/wiki/NP-complete,17. 12. 2008.