NAUKOWIEC AMATOR

Shawn Carlson

krzepnà w skomplikowanà gmatwani-

Algorytm bogów

n´. Lecz jeÊli spadek ten jest powolny, tworzà one wysoce uporzàdkowany

Zwyk∏em sp´dzaç dnie, polujàc nierozwiàzywalnych na pierwszy rzut kryszta∏, czasami miliardy razy wi´k-na supernowe. Wraz z grupà

oka zagadnieƒ. Ten zdumiewajàcy al-szy od pojedynczej czàsteczki.

astrofizyków odkurzyliÊmy sta-

gorytm pozwala nawet zwyk∏ym lap-

Je˝eli ka˝da czàsteczka zostanie unie-ry 76-centymetrowy teleskop, u˝ywa-topom uporaç siź tym problemem za-ruchomiona w stanie o mo˝liwie najni˝-

ny dotychczas jedynie do nauczania, ledwie w kilka minut, co czyni z algo-szej energii, to taki kryszta∏ znajduje sií przekszta∏ciliÊmy go w ca∏kowicie rytmu pot´˝ne narz´dzie w zestawie w minimum energii. (W moim proble-zautomatyzowany instrument badaw-

Êrodków naukowca amatora.

mie odpowiada to takiemu uszeregoczy. Gdy nadchodzi∏a noc, sterowane Algorytm ten, zwany symulowanym

waniu galaktyk, które wymaga od tele-komputerowo cudo budzi∏o si´, spraw-odpr´˝aniem, to znakomite po∏àczenie skopu najmniej ruchów.) Uk∏ad zbli˝a dza∏o swoje uk∏ady i zabiera∏o si´ do pomys∏owoÊci ludzkiej ze skuteczno-si´ do tego minimum w sposób natural-robienia odkryç. W bezchmurne noce Êcià przyrody. Nicholas Metropolis za-ny po raczej nieoczekiwanej i specyficz-teleskop ten potrafi∏ przebadaç setki ga-jmujàcy si´ fizykà matematycznà roz-nej drodze. Czàsteczki majà z natury laktyk w poszukiwaniu obiektów wy-winà∏ t´ procedur´ wraz ze wspó∏pra-energi´ kinetycznà roz∏o˝onà w pew-glàdajàcych jak jasne gwiazdy nie wy-cownikami ju˝ w 1953 roku, ale do po-nym zakresie. Gdy temperatura spada, kryte na wczeÊniejszych zdjćiach.

wszechnego u˝ytku wesz∏a ona dopie-

Êrednia energia kinetyczna siźmniej-Czasami je znajdowa∏.

ro niedawno. Procedur´ Metropolisa sza. Lecz niektóre z czàsteczek pozosta-To by∏o wspania∏e! Nie czu∏em wy-

stosowano ostatnio do znajdowania jà w stanach o wysokiej energii nawet rzutów sumienia, ˝e nie marznća∏ymi u˝ytecznych rozwiàzaƒ problemów ty-wtedy, gdy wi´kszoÊç porusza sińa nocami w odleg∏ym obserwatorium. Za pu komiwoja˝era; komputer naÊlado-tyle powoli, by ulec zwiàzaniu w

to miesiàcami harowa∏em w cyberpie-kle, starajàc sińauczyç teleskopowy komputer, którym galaktykom powi-nien robiç zdjćia i w jakiej kolejnoÊci je obserwowaç. Poniewa˝ dalekie wyciecz-ki od horyzontu do horyzontu wywo-

∏ywa∏y w 40-letnim uk∏adzie naprowa-dzania teleskopu szok, istotne by∏o, by ten wys∏u˝ony weteran rusza∏ si´ mo˝-

liwie jak najmniej. Oznacza∏o to takie ustawienie kolejnoÊci galaktyk, by kàt ruchu teleskopu zsumowany w ciàgu nocy by∏ mo˝liwie najmniejszy. Kom-puterowi zapaleƒcy rozpoznajà w mo-jej galaktycznej zagadce odmian´ pro-blemu komiwoja˝era, w którym hand-larz poszukuje marszruty pozwalajàcej na obejÊcie najkrótszà drogà wszystkich miast na jego liÊcie.

Problem minimalizacji ruchu teleskopu wydawa∏ si´ bardzo trudny. Posor-SLIM FILMS

towaç 200 galaktyk – typowe zadanie

PRZESZUKIWANIE GALAKTYKI sta∏o si´ mo˝liwe dzi´ki boskiemu algorytmowi.

dla naszego teleskopu na jednà noc –

mo˝na na 10375 ró˝nych sposobów. (Dla fanów matematyki: 10375 jest to 200 sil-wa∏ naturalne procesy, które powodujà, kryszta∏. Gdy moleku∏y o ni˝szej ener-nia.) Aby znaleêç ten jedyny sposób

˝e w siatkach krystalicznych szk∏a lub gii „zastygnà”, czśto zwiàzane sà w sta-uszeregowania galaktyk, najmniej for-metalu napr´˝enia wewn´trzne zmniej-nach o wy˝szej energii, ni˝ powinny.

sujàcy dla naszego teleskopu, powinni-szajà si´ w czasie ogrzewania. Proces Czàsteczki o wy˝szych energiach mo-

Êmy byli sprawdziç ka˝de mo˝liwe

ten nazywa siódpr´˝aniem.

gà jednak˝e „wbijaç” z∏apane moleku∏y ustawienie. Niestety, nie wykonajà te-Chocia˝ procedura opiera sińa mo-

ze stanów zwiàzanych o nadmiarze

go nawet wszystkie komputery Êwiata delu odpr´˝ania, jej istotne podstawy energii do stanów o energii ni˝szej. Ta-pracujàce dzieƒ i noc przez tryliardy lat.

fizyczne sà takie same jak w procesie kie przekazywanie energii od czàstecz-Dla wi´kszoÊci rzeczywistych proble-wzrostu kryszta∏u, a byç mo˝e troch´

ki do czàsteczki pozwala im podczas mów wynik ró˝niàcy sió kilka procent

∏atwiejsze do wyt∏umaczenia. Czàstecz-och∏adzania cieczy na wzajemnà re-od idealnego jest w zasadzie akcep-ki w roztworze cukru w goràcej wodzie dystrybucjénergii przez tràcanie wzra-towalny. Na szcz´Êcie informatycy poruszajà si´ we wszystkie strony stajàcych kraw´dzi kryszta∏u w taki wymyÊlili algorytm, dzi´ki któremu w sposób przypadkowy. JeÊli tempera-sposób, ˝e usadawiajàce sińa nich czà-

mo˝na znaleêç rozwiàzanie wielu

tura szybko spada, czàsteczki cukru steczki trafiajà do stanu o minimalnej ÂWIAT NAUKI Maj 1997 99

energii. Ten uporzàdkowany wzrost Algorytm bogów ujawniony

kryszta∏u wyst´puje jedynie podczas powolnego ch∏odzenia, poniewa˝ na Oto procedura stosujàca symulowane odpr´˝anie znalezienie stanu o najni˝szej energii PSEUDOKOD

UWAGI

potrzeba czàsteczkom du˝o czasu.

Lecz co to wszystko ma wspólnego

Podstawowy algorytm programu

z problemem komiwoja˝era? By zasto-

{

Setup()

Utwórz poczàtkowà listí ustaw potrzebne zmienne sowaç procedur´ Metropolisa, musicie opisaç wasz problem jako poszukiwa-for (i = 1; i <= 100; i = i + 1) Wypróbuj do 100 ró˝nych temperatur nie porzàdku. W problemie komiwoja-

{ numSuc=Anneal()

Odpr´˝aj list´ w tej temperaturze;

˝era na przyk∏ad nale˝y okreÊliç najlep-zwróç liczbúdanych zmian

szà kolejnoÊç odwiedzania miejscowoÊci if (numSuc==0) break

JeÊli nie zosta∏y znalezione ˝adne poprawki, z listy. Przy odrobinie sprytu w ten spo-program si´ koƒczy

sób mo˝na sformu∏owaç bardzo wiele temperature=temperature *0.9

Obni˝ temperaturó 10%

problemów. Konieczne jest tak˝e wyge-

}

nerowanie liczby okreÊlajàcej, jak dale-PrintResults()

ce dobre jest aktualne uporzàdkowanie.

}

Im lepsze rozwiàzanie, tym mniejsza b´dzie ta liczba. Jej wartoÊç jest analo-Algorytm inicjujàcy (tworzy poczàtkowà listí ustawia temperatur´ poczàtkowà) giczna do energii kryszta∏u w przyk∏a-

{

dzie procesu jego wzrostu. W moim CreateInitialList (list)

problemie poszukiwania supernowych energy = GetEnergy (list)

porzàdkiem by∏a kolejnoÊç przeszuki-temperature = energy/liczba pozycji na liÊcie wania galaktyk, a wielkoÊcià analogicz-runLimit = 100 * liczba pozycji na liÊcie sucLimit = 10 * liczba pozycji na liÊcie nà do energii by∏ ca∏kowity kàt, o jaki

}

musia∏ obróciç si´ teleskop.

W ramce obok przedstawi∏em szkic

Algorytm odpr´˝ania (odpr´˝a list´ w jednej temperaturze w celu znalezienia najlepszego rozwiàzania) algorytmu. Dzia∏a on na zasadzie obli-

{

czania poziomów energii reprezento-numSuc = 0

Liczba udanych zmian listy

wanych przez ró˝ne sekwencje, inaczej

„Êcie˝ki”. Program zawsze przyjmuje for (I = 0; i <= runLimit; i = i + 1){

Zrób do „runLimit” prób w aktualnej nowe uporzàdkowanie, je˝eli ma ono temperaturze

ni˝szà energińi˝ poprzednie. Wróçmy GetSegment (start,end,insertPoint) Wybierz losowo segment listy do zmiany do przyk∏adu ze wzrostem kryszta∏u; alteration = PickAlteration()

Zadecyduj losowo o odwróceniu kolejnoÊci Êcie˝ka o ni˝szej energii odpowiada jed-w segmencie lub przerzuceniu go w inne nej lub kilku czàsteczkom znajdujàcym miejsce listy

swà drog´ do po∏o˝enia o ni˝szej ener-Edif = EnergyDif (alteration)

Wylicz zmianénergii przy dokonanym gii w sieci krystalicznej. Lecz co ze Êcie˝-

przekszta∏ceniu

kami o energiach wy˝szych? Tutaj rzecz answer = Oracle (Edif, temperature) Zdecyduj, czy zastàpiç aktualnà listńowà ca∏a staje siínteresujàca. Program nie if (answer == YES){

JeÊli Algorytm Wyroczni zadecyduje odrzuca od razu Êcie˝ek o wy˝szych przekszta∏ciç list´...

energiach. Mimo wszystko przemiesz-AlterList ()

...zmieƒ listńa sta∏e

czenie moleku∏y uwiźionej w stanie numSuc = numSuc + 1

Jeszcze jeden sukces!

o wy˝szej energii w sieci jest przyk∏a-

}

dem Êcie˝ki o wy˝szej energii, a takie zdarzenia stanowià sedno procedury.

if (numSuc > = sucLimit) break JeÊli by∏o dostatecznie du˝o prób udanych, Jednak nie ze wszystkich Êcie˝ek

wyjdê z tej p´tli, by móc obni˝yç temperaturó wy˝szych energiach mo˝na stràciç uk∏ad do stanu o energii ni˝szej. Dla

}

okreÊlenia tych, z których mo˝na to zro-return numSuc

biç, stosuje si´ w procedurze tzw. roz-

}

k∏ad prawdopodobieƒstwa Boltzmanna.

Parametr ten okreÊla prawdopodobieƒ-

Algorytm Wyroczni (decyduje, czy zaakceptowaç zaproponowanà nowà list´) stwo znalezienia siúk∏adu, takiego jak

{

czàsteczka lub ich grupa, o ustalonej if (Edif < 0) return YES

Zawsze zachowuj nowà list´, jeÊli ma ni˝szà energii E w danej temperaturze T. W za-energiód starej

stosowaniu do symulowanego odpr´˝ania prawdopodobieƒstwo to wyra˝a siíf (random() < exp(-Edif/temperature)) Nast´pnie u˝yj wspó∏czynnika Boltzmanna liczbà e (sta∏à równà oko∏o 2.7183, która return YES

do zdecydowania, czy powinna zostaç pojawia sićzśto w fizyce i innych dzie-zachowana lista o wy˝szej energii dzinach) podniesionà do pot´gi (-D E/ kT), Uwaga, random() zwraca liczbĺosowà o wartoÊci pomi´dzy zerem a jedynkà gdzie k jest sta∏à Boltzmanna wià˝àcà temperaturź energià, a D E ró˝nicà ener-return NO

JeÊli wszystko inne zawiedzie, odrzuç list´

gii pomi´dzy dwiema Êcie˝kami.

}

Pomys∏owy trik pozwala przetwarzaç list´ bez potrzeby przeliczania za ka˝dym 100 ÂWIAT NAUKI Maj 1997

razem energii od poczàtku. Przetwarza-nie rozpoczyna siód losowego wybra-

W majowym numerze

nia pewnego segmentu listy. Nast´pnie albo odwracany jest porzàdek elementów

mi´dzy innymi:

segmentu, albo ca∏y segment przemiesz-czany i wstawiany ponownie w losowe

■ SUKCES

miejsce listy. W obu wypadkach energia zwiàzana z segmentem sińie zmienia.

W OWCZEJ SKÓRZE

Energia zmienia si´ jedynie w punkcie, Sklonowanie owcy

w którym segment ∏àczy siź resztà listy.

porównano do z∏amania

Ramka na sàsiedniej stronie zawiera kodu genetycznego, pierwszego

pseudokod szkicujàcy niezb´dne procedury. Równowa˝ny kod w jźyku C mo˝-

lotu w Kosmos lub wynalezienia

na skopiowaç z sieci WWW ze strony To-komputera osobistego.

warzystwa Naukowca Amatora.

Co tak naprawdśi´ wydarzy∏o

Symulowane odpr´˝anie nie jest jedy-w Szkocji i jakie to b´dzie mia∏o nym algorytmem naÊladujàcym natur´

w rozwiàzywaniu z∏o˝onych proble-

implikacje?

mów. Tzw. algorytmy genetyczne sy-

■ UCIECZKA

mulujà ewolucjńa poziomie genetycz-

PRZED AIDS

nym dla cyberorganizmów, które same z siebie sà rozwiàzaniem problemów ba-O wirusie nabytego niedoboru

dawczych [patrz: NAUKOWIEC AMA-

odpornoÊci wielokrotnie pisano

TOR; Âwiat Nauki, wrzesieƒ 1992]. Sieci na pierwszych stronach gazet,

neuropodobne – symulujàce czynnoÊci ale dopiero niedawno zacz´to

neuronów w mózgu potrzebne do prze-chowywania informacji, uczenia sićz´Êciej mówiç o nadziei przez doÊwiadczenie i przeprowadza-na jego pokonanie.

nia obliczeƒ – stanowià oddzielne pole

■ WOLTER POPULARYZATOREM NAUKI

intensywnych badaƒ.

Autor Traktatu o tolerancji, Kandyda, ulubieniec francuskich Wszystko to prowadzi do fascynujàce-go wniosku. Przyroda jest o wiele bardziej salonów by∏ równie˝ niez∏omnym propagatorem nauki.

pomys∏owa, ni˝ kiedykolwiek b´dà lu-

■ PTASIE DZIECI¡STWO

dzie. Komputerowa symulacja natural-Dooko∏a wiosna. W∏aÊnie teraz w wi´kszoÊci ptasich gniazd nych metod organizacji i tworzenia do-prowadzi∏a do powstania niezwykle wykluwajà si´ piskl´ta. Jedne zaraz opuszczajà gniazdo, inne pot´˝nych narz´dzi przydatnych do upo-pozostajà w nim i z otwartymi dziobami czekajà na pokarm.

rania siź niektórymi z naszych najbar-

■ SKAZANI NA STAROÂå

dziej dokuczliwych problemów. Pomimo to dotàd uda∏o si´ powieliç na komputerze M∏odoÊç ma nieodparty urok. Nie da si´ jednak jej przed∏u˝aç, gdy˝

jedynie garstkŕozwiàzaƒ natury. Jeszcze mimo post´pu medycyny nadal jesteÊmy skazani na staroÊç.

wiele mo˝emy siód niej nauczyç. Naj-

■ ÂWIAT DèWI¢KÓW

trudniejszà sprawà jest rozeznanie, które uk∏ady warto modelowaç, i zrozumienie, To pierwszy artyku∏ z cyklu „Od Platona i Newtona...”. Pod tym jaki rodzaj problemów nasze symulacje samym tytu∏em Telewizja Polska emituje programy poÊwićone potrafià rozwiàzaç.

fizyce. Ich autorami sà prof. dr hab. Jan Gaj i Ma∏gorzata Uberna.

Tak wić miej oczy otwarte! Byç mo-

˝e podczas kontemplacji turbulentnych zmarszczek w dymie papierosowym, ob-DODATEK HUMANISTYCZNY

serwacji, jak pszczo∏y organizujà si´

■

w rój, czy badania jednoczesnych zwro-

RODZINA I WOLNOÂå

tów klucza ptaków dostrze˝esz szans´

Jednà z nielicznych instytucji spo∏ecznych, których nie zdo∏a∏

na kolejnà istotnà innowacj´ kompute-zniszczyç socjalizm, jest rodzina. Obecna odnowa cywilizacyjna rowego rozwiàzywania problemów.

w Polsce nie mo˝e si´ dokonaç bez jej udzia∏u.

T∏umaczy∏

Zbigniew Loska

■ GEOPOLITYCZNY PRZYPIS?

Czy Timor Wschodni ma szansńa niepodleg∏oÊç? Czy ubieg∏oroczna Chcàc skopiowaç ca∏oÊç kodu w jźyku Pokojowa Nagroda Nobla dla dwóch wybitnych przedstawicieli C potrzebnà do zrealizowania algorytmu symulowanego odpr´˝ania, odwiedê interne-narodu timorskiego mo˝e odmieniç jego los?

towà stronŚociety for Amateur Scientist

■ ˚YWA DEMOKRACJA

http://www.thesphere.com/SAS/

Nie ma demokracji tam, gdzie si´ jej nie praktykuje na co dzieƒ, gdzie Wićej informacji o innych amatorskich projektach naukowych znajdziesz tam˝e lub obywatele nie majà wp∏ywu na urzàdzenia publiczne, a kapita∏ spo-pod numerami telefonów [phone] lub

∏ecznego zaufania nie jest stale odnawiany.

[phone].

ÂWIAT NAUKI Maj 1997 101