Inšpirácia pre evolučné algoritmy

Zjednodušená história výpočtov ukazuje, že zatiaí čo výpočty boli v 19. storočí považované za mentálny proces


Zjednodušená história výpočtov ukazuje, že zatiaí čo výpočty boli v 19. storočí
považované za mentálny proces íudí, v 20. storočí už boli prevažne pokladané za
proces strojov; všetko nasvedčuje tomu, že v 21. storočí budú výpočty procesy
prislúchajúce prírode.
Kvantové počítače boli navrhnuté na začiatku 80. rokov 20. storočia a koncom
tejto dekády bol ich návrh tiež formalizovaný. Výskum spájajúci evolučné
algoritmy a kvantové výpočty začal na konci 90. rokov. Vyvinuté algoritmy mÖžu
byť rozdelené do dvoch skupín. V prvej skupine sú algoritmy pre kvantové
počítače, zatiaí čo v druhej skupine sú algoritmy pre klasické počítače, ktoré
sú inšpirované kvantovými princípmi, ako sú interferencia, superpozícia a
pozorovania kvantových stavov.

Optimalizačné algoritmy
Kvantovo inšpirované evolučné algoritmy (skratkou QEA, z anglického
qunatum-inspired evolutionary algorithms) patria práve do druhej zo spomínaných
skupín. Sú to stochastické optimalizačné algoritmy, ktoré sa inšpirujú
kvantovými javmi: superpozíciou stavov a reprezentáciou jednotky informácie
pomocou kvantových bitov. Práve reprezentácia informácie je kíúčovým faktorom,
na ktorom kvantovo inšpirované evolučné algoritmy stoja.
Zatiaí čo v doteraz známych evolučných technikách (respektíve všeobecne v
stochastických optimalizačných technikách, kam QEA patria) sa používalo
kódovanie informácie binárnymi hodnotami, reálnymi číslami alebo symbolmi,
kvantovo inšpirované evolučné algoritmy používajú pravdepodobnostné kódovanie.
Najmenšou jednotkou informácie uloženej v dvojstavovom kvantovom počítači je
kvantový bit (qbit). Qbit mÖže byť v stave 0, v stave 1, ale na rozdiel od
klasického bitu mÖže byť aj v íubovoínej superpozícii týchto stavov. Konkrétny
stav qbitu sa reprezentuje dvojicou dvoch komplexných čísel, ktorých druhá
mocnina modulu dáva pravdepodobnosti, že kvantový bit bude pozorovaný v stave 0
alebo v stave 1.

Princíp neurčitosti
V reprezentácii informácii pomocou kvantových bitov sa Heinsenbergov princíp
neurčitosti prejavuje tak, že zatiaí čo qbit mÖže byť v íubovoínej superpozícii
stavov 0 a 1, t.j. mÖže sa nachádzať v jednom z nekonečného množstva možných
stavov, v momente, keď je kvantový bit pozorovaný, skolabuje do jedného zo
stavov 0 a 1. Qbit, hoci sa nachádza v jednom z nekonečného množstva stavov, je
pozorovaný iba v jednom konkrétnom stave. Tento stav však nie je možné
predvídať pred pozorovaním; jediný spÖsob, ako ho zistiť, je pozorovanie
vykonať.
V klasických evolučných optimalizačných technikách sa používajú variačné
operátory mutácie a kríženia. Variačné operátory v kvantovo inšpirovaných
evolučných algoritmoch musia byť vzhíadom na reprezentáciu jednotky informácie
pomocou qbitov iné. I tieto operátory sú prebrané z kvantových výpočtov. Jedná
sa o takzvané kvantové hradlá (anglicky quantum gates).
Hoci existuje viacero kvantových hradiel používaných alebo uvažovaných v
kvantových počítačoch, v kvantovo inšpirovaných evolučných algoritmoch sa
používa iba operátor NOT (ktorý si možno predstaviť ako negáciu kvantového
stavu qbitu, kedy sa vymenia pravdepodobnosti jeho pozorovania v stave 1 a v
stave 0), a takzvané rotačné hradlo (anglicky rotation gate). Práve rotačnému
hradlu vďačia kvantovo inšpirované evolučné algoritmy za svoje optimalizačné
schopnosti. Mení totiž pravdepodobnosti pozorovania qbitu v stave 0 alebo 1
takým spÖsobom, aby s väčšou pravdepodobnosťou bol tento kvantový bit
pozorovaný práve v tom stave, ktorý sa javí ako výhodnejší, t.j. je ohodnotený
lepšou hodnotou funkcie vhodnosti.

Alokácia disku
Kvantovo inšpirované evolučné algoritmy boli úspešne použité na riešenie
ťažkých kombinatorických úloh. Za zmienku stojí napríklad alokácia miesta na
disku na uloženie súborov. Pravdepodobnostná reprezentácia informácie v QEA
však nie je úplne nová myšlienka, ako to prezentujú autori QEA profesor
Jong-Hwan Kim a jeho študent Kuk-Hyun Han. Rovnakú pravdepodobnostnú
reprezentáciu jedinca i narábanie s touto reprezentáciou používa už mnoho rokov
jeden známy stochastický optimalizačný algoritmus (horolezecký algoritmus s
učením anglicky hillclimbing with learnig, HCwL).
Tento algoritmus vzišiel z úplne opačného konca stochastických optimalizačných
techník, dá sa povedať, že s toho najprimitívnejšieho. Jeho znovuobjavenie
úplne inou cestou od zložitých a vysoko sofistikovaných evolučných techník a
kvantových výpočtov potvrdzuje jeho použiteínosť pre technické problémy.
Určite bude zaujímavé sledovať, aká budúcnosť postretne kvantovo inšpirované
evolučné algoritmy; možno sa dočkajú slávy najskÖr v akademickej obci a neskÖr
aj v praktickom nasadení, alebo sa stanú len jedným z mnohých pokusov "robiť
veci inak". Pre druhú z načrtnutých verzií vývoja hovorí skutočnosť, že
technická prax potrebuje dobre fungujúce a jasne formalizovateíné nástroje, nie
zložité metafory.
text ON-LINE
Kompletní podobu tohoto článku najdete na portálu Science World (www.scien
ceworld.cz) s datem 19. 11. 2004.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.