Biologicky inspirované výpočty: evoluční algoritmy

Biologicky inspirované výpočty: evoluční algoritmy Motivace

P ar

B lo

p ro

a

kov

r lg o

e to

va

é za

h

ic ra n

poj

en í

po ra m . g o A st Hi SOM s u itm

# tu

ep

odl

e

(7 .

,F 13)

ú ní

„Svnoce o d ' te l n oh

#e

lo

,5 . = 0T

f vé

á si

un

gna

kc

e

liz a

V oboru výbušnin jsem vynalézal 2x...

F al s T ru e e F al s T ru e e F al se

ru e

j p ro

ed

no

tl

iv é

p ex

e ri

(a )

me

b)

n ty

av

a il d et

un

aP

a

podle

F al s T ru e e F al se

ov re t

ra uh

ky a m

i( n ic

dvou

ce“ .

# po

tu

o oh

dn

oc

í en

ú#

e lo

f vé

un

kc

e

p ro

je d

n

iv o tl

ée

x

ri pe

me

n ty

prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

m ís tn

%

o &n á c

esta m

ezi p o

#áte#n

ía

Skutečné katastrofy způsobené špatným inženýrským návrhem http://www5.in.tum.de/~huckle/bugse.html


Tak to začíná...


A takhle končí...

Katastrofa č. 1 Výbuch rakety Ariane 5 http://www.ima.umn.edu/~arnold/disasters/ariane.html

4. června 1996 explodovala bezpilotní raketa Ariane 5, vypuštěná Evropskou kosmickou agenturou, jen čtyřicet sekund po odstartování z Kourou, Francouzská Guiana. Raketa byla na své první misi po deseti letech vývoje za 7 miliard dolarů. Zničena raketa a její náklad byly oceněny na 500 milionů dolarů. Ukázalo se, že příčinou selhání byla chyba softwaru v inerciální vztažné soustavy. Navigační systém SRI ale nedokázal konvertovat rychlost měřenou ve formě 64bitového čísla s pohyblivou čárkou do celočíselné 16bitové hodnoty – 16 bitů zkrátka k tomuto účelu nedostačuje. Výsledek: Přeplnění paměti, během kterého byly další hodnoty přepisovány. V případě vážného problému se předpokládalo, že se SRI vypne a budou se používat jen základní data z palubního počítače Ariane. Ten ale informace přijaté od SRI interpretoval jako navigační data (která vypadala, jako kdyby se raketa odchylovala od svého kurzu), a proto provedl fatální opravy kurzu, které nakonec vedly k havárii. Ve své zprávě došla ESA k závěru, že „rozhodující software by měl vždy podstoupit detailní testování“. Konkrétně: I jednoduchý test je dostatečný, aby tyto chyby objevil; SRI v Ariane 5 však „prošel“, aniž by byl i jen jedinkrát otestován.

! prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Katastrofa č. 2 Chybný zásah rakety Patriot http://www.ima.umn.edu/~arnold/disasters/patriot.html http://sydney.edu.au/engineering/it/~alum/patriot_bug.html

Dne 25. února 1991, během války v Perském zálivu, American Patriot Missile baterie v Dharanu, Saúdská Arábie, nedokázala sledovat a zachytit příchozí iráckou raketu Scud, která zasáhla americké armádní kasárna, zabila 28 vojáků a zranila asi 100 dalších lidí. Zpráva General Accounting Office, GAO/IMTEC-92-26, nazvané Patriot protiraketové obrany uvádí: Ukazuje se, že příčinou je nesprávný výpočet času od startu kvůli chybě počítačové aritmetiky. Konkrétně, byl čas v desetinách sekundy, měřen systému vnitřních hodiny a pak vynásoben 1/10 k získání času v sekundách. Tento výpočet byl proveden pomocí 24 bitového registru. Díky použití 24 bitového registru došlo k malé chybce přesnosti. Tato malá chyba se násobením velkého počtu časových jednotek výrazně zvýšila celkem na 0.34s což vypadá sice nevinně, ale vzhledem k rychlosti rakety se Scoud dostala mimo akční rádius rakety Patriot a ... !


Katastrofa č. 3 Potopení plošiny Sleipner http://www.ima.umn.edu/~arnold/disasters/sleipner.html

Plošina Sleipner vyrábí ropu a zemní plyn v Severním moři a je ukotvena na mořském dně v hloubce vody na 82 m. Je plošina typu Condeep s betonovou konstrukcí skládající se z 24 buněk s celkovou základní plochou 16 000 m2. Plošina se potopila při řízeném zatěžování a přípravy na provoz dne 23. srpna 1991. Bezprostředně po nehodě, majitel platformy, Statoil, norská ropná společnost jmenovala vyšetřovací skupinu.Vyšetřování nehody je popsána v 16 zprávách ... Závěr šetření bylo, že potopení bylo způsobeno prasklinou v buněčné stěně, což vedlo k prosakování a čerpadla to nemohla zvládnout. Chyba byla způsobena kombinací vážné chyby v analýze konečných prvků a nedostatečné kotvení výztuže v kritické zóně. Katastrofa znamenala ekonomickou ztrátu 700 milionů USD.


Katastrofa č. 4 Burza ve Vancouveru

V roce 1982 Vancouver Stock Exchange zavedl nový index s nominální hodnotou 1000.000. Index byl aktualizován po každé transakci. O dvacet dva měsíce později spadl na 520. Příčinou bylo, že aktualizovaná hodnota nebyla zaokrouhlována (Round) ale zkrácena (Truncated). Přo zaokrouhlování by výpočet dal hodnotu 1098,892. Zdroje 1.

The Wall Street Journal November 8, 1983, p.37. 2.

The Toronto Star, November 19, 1983. 3.

B.D. McCullough and H.D. Vinod Journal of Economic Literature Vol XXXVII (June 1999), pp. 633-665.


Katastrofa č. 5 Kolaps mostu Tacoma, 1940 http://www5.in.tum.de/~huckle/bugse.html

Dne 7. listopadu 1940, ve vzdálenosti asi 11:00, se zhroutil první visutý most Tacoma Narrows kvůli vibracím vyvolaných mírným větrem. Místo se nachází na Tacoma Narrows v Puget Sound, v blízkosti města Tacoma, Washington, most byl otevřený pro provoz jen několik měsíců.

Viz též YouTube klíčové slovo Tacoma Bridge prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Katastrofa č. 6 Havárie Spanair MD-82, Madrid, 2008

V r. 2008 havaroval Spanair MD-82 při vzletu v Madridu, zahynulo 154 lidí, byla to nejhorší letecké tragédie Španělska za posledních 25 roků. Orgány vyšetřující 2008 havárii letu Spanair 5022 objevili centrálního počítačového systému, sloužícího ke sledování provozu, že technické problémy letadla byly způsobeny škodlivým softwarem. Interní zpráva vydaná leteckou společností odhalila infikovaný počítač který neodhalil tři technické problémy s letadly, která by v případě zjištění, zabránily vzlétnutí letadla - podle zpráv ve španělském deníku El País.

Americká Národní rada pro bezpečnost dopravy ohlásila v předběžném šetření, že letadlo vzlétlo s klapkami a sloty zasunutými - a že žádný zvukový signál na to neupozornil. Malware v počítači Spanair byla identifikován jako typ trojského koně.


Katastrofa č. 7 Mars Americký Mars Climate Orbiter dojel na fakt, že při jeho přípravě pracoval jeden z týmů s anglosaskými jednotkami, zatímco druhý s metrickým systémem. Sonda byla po příletu k Marsu natolik zmatená, že vstoupila do atmosféry, i když něco podobného rozhodně v plánu neměla. Mars Polar Lander měl zkoumat okolí místa přistání. Po průletu atmosférou se však sonda neozvala. Snímky ze sond na oběžné dráze prokázaly, že přistání sondy bylo patrně poněkud tvrdší, zřejmě kvůli chybě softwaru, který vibrace při vysunutí vzpěr interpretoval jako přistání a vypnul brzdicí motory. Sonda se ovšem v té chvíli nacházela desítky metrů nad povrchem rudé planety. Více na: http://magazin.e15.cz/veda-a-technika/pro-rusko-je-mars-proklety-cistestatisticky-718331#utm_medium=selfpromo&utm_source=e15&utm_campaign=copylink


Katastrofa č. 7 Mars


Katastrofa č. 8 Venuse Viz http://en.wikipedia.org/wiki/Venera


Katastrofa č. 9 Venuse

Raketoplán Challenger co: první ze dvou havárií amerických raketoplánů (druhou byla havárie při přistání raketoplánu Columbia v roce 2003) kdy: leden 1986 kde: nad mysem Canaveral na Floridě jak k tomu došlo: Na jedné z pomocných raket bylo vadné těsnění, které nevydrželo žár při startu. Vznikl oheň, který přepálil držák pomocné rakety a ta narazila do hlavní palivové nádrže. Následoval výbuch, který raketoplán rozmetal na kusy. Kabina s posádkou ještě chvíli stoupala a pak se z 20 km výšky zřítila do oceánu. K explozi došlo pouhých 73 vteřin po startu. následky: Všech sedm členů posádky (stejný počet jako později na Columbii) zahynulo.


Katastrofa č. 10 Jaderná válka Vesmírné katastrofy jsou sice okázalé, hororovými se však poruchy softwaru ukázaly během studené války. Obě supervelmoci totiž silně spoléhaly na počítačové analýzy, čímž vznikl velký prostor pro „katastrofické chyby“. Například v listopadu roku 1979 oznámil americký obranný systém NORAD celkem 2 020 současně útočících sovětských raket. Tento scénář byl tak nepravděpodobný, že armáda ihned usoudila, že se jedná o počítačovou chybu. A příčina? V důsledku softwarové chyby propašoval počítač NORAD do vysílaných dat náhodné bity. Chyba poté infiltrovala zprávy, následkem čehož vzniklo „varování před útokem“. Téměř vyhlazením lidstva skončil „špatně vyhodnocený“ signál z ruského satelitního systému. 26. září 1983 v půl jedné ráno signalizoval počítač vypuštění pěti amerických mezikontinentálních raket. Rozhodnutí, zda SSSR opravdu hrozí útok, bylo ponecháno podplukovníkovi Stanislavu Petrovovi, sedícímu v té chvíli asi 50 km jižně od Moskvy v utajeném bunkru „Serpuchov 15“. Jeho radu zvažoval generální štáb jako podklad k zahájení protiútoku. Petrov se ale domníval, že jde o falešný poplach: „Měl jsem divný pocit v žaludku, a navíc – nikdo nezačíná nukleární válku s pouhými pěti raketami.“ Chyba byla detekována ještě ten samý den – satelit interpretoval odrazy slunce od mraků nad základnou vojenského letectva v Malstromu v Montaně (Malstrom Air Force Base) jako start raket.


Katastrofa č. 11 Největší softwarové katastrofy

22 července roku 1962 v 9 hodin 26 minut stiskl bezpečnostní specialista týmu na mysu Canaveral pověstný červený knoflík a zničil raketu Mariner. Tento čin představoval první z mnoha velkých budoucích softwarových katastrof. Raketa Mariner 1 měla být první meziplanetární sondou, která prozkoumá Venuši. Místo toho se její trosky po letu trvajícím 293 sekund zřítily do Karibiku. O týden později objevili experti z NASA příčinu: programátor zapomněl opsat znaménko horního podtržítka (“—“) z ručně psaného vzorce pro řídicí program. Tento symbol byl důležitý: měl zajistit, že počítač propočítá pozici a akceleraci z průměrné rychlosti. Protože tento symbol chyběl, počítač kalkuloval s nepřetržitě se aktualizujícími daty, která se měnila i během výpočtů. Aby se kolísání vyrovnalo, počítač neustále vysílal nové řídicí příkazy, kvůli kterým se však Mariner stále více odchyloval od zamýšlené trajektorie a ve finále musel být zničen. Poučení „z havárie programování“ se později objevilo v interní výzvě NASA: „Žádný detail není natolik malý, aby byl přehlédnut.“


Katastrofa č. 12 Největší softwarové katastrofy - přehled 1962 Mariner 1 Ihned po startu se začala raketa odchylovat od kurzu a musela být zničena. Důvod: Programátoři zapomněli ve vzorci na jediné znaménko. 1971 Eole 1 Francouzský satelit způsobil zničení 71 meteorologických balonů. Důvod: Software nesprávně interpretoval žádost o předání naměřených údajů jako příkaz pro autodestrukci. 1978 Nimbus 7 Satelit selhal při zkoumání ozonové díry nad Antarktidou. Důvod: Program pro analýzu získaných hodnot označoval neobvyklé naměřené hodnoty jako chyby. 1979 Atomové reaktory Pět amerických jaderných reaktorů bylo vypnuto, když jim software pro kontrolu stability při zemětřesení dodal špatné údaje. Důvod: Program počítal místo součtu odmocnin součet mocnin. 1982 Křižník HMS Sheffield Během války o Falklandy byla loď zasažena raketou a potopena. Důvod: Software přepnul zbraňové systémy do „safe“ modu. 1983 Třetí světová válka Sovětský satelit detekoval pět mezikontinentálních raket. Podplukovník Petrov údaj vyhodnotil jako falešný poplach. Důvod: Software interpretoval světelné odrazy jako nepřátelské rakety. 1985-1987 Therac 25 Ozařovací přístroj zabil celou řadu pacientů nadměrnou dávkou radiace. Důvod: Software přístroje dokázal přesně řídit více procesů, pouze pokud byly příkazy zadávány pomalu. 1988 USS Vincennes Americký křižník sestřelil íránský Airbus – výsledkem bylo 290 mrtvých. Důvod: Podle šetření vyhodnotil systém Aegis (za přibližně 400 milionů dolarů) Airbus jako „předpokládaně nepřátelský“. Posádka věřila, že jde o útočící bojový letoun. prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Katastrofa č. 13 Nečastější softwarové chyby

Na softwarové chyby lze narazit i v kvalitně otestovaných a často používaných programech. Během několika let testoval softwarový „provider“ Coverity více než 150 velkých open-source projektů pomocí vlastního nástroje založeného na bázi statické analýzy kódu. Zmiňované projekty byly určeny především pro Linux a server Apache. Celkem software analyzoval více než 55 milionů řádků kódu. Před třemi roky odhalil jednu chybu na 3 300 řádků, v současnosti je tato hranice posunuta až na 4 000 řádků. Mezi nejčastěji detekované chyby patřily tyto: Typ chyby a výskyt v procentech Ukazatel nastavený na null odkazuje do oblasti paměti 27.95 % Použití neschválené oblasti paměti 25.73 % Nepřístupný programový kód 9.76 % Použití netestovaných proměnných 8.30% Přetečení staticky adresované oblasti v paměti 6.14 % Použití již uvolněné paměti 6.46 % Nepovolené počítání s nulou (např. dělení) 5.85 % Proměnným nejsou přiřazeny hodnoty 5.50 % Vypočítané záporné hodnoty jsou použity bez kontroly 3.72 % Ukazatel odkazuje na paměť, která není přístupná 0.62 % Přetečení dynamicky adresované oblasti v paměti 0.31 % ZDROJ: SCAN.COVERTY.COM


Katastrofa č. 14 Blackout http://fyzmatik.pise.cz/21251-co-je-to-blackout.html Výrazný výpadek proudu, který přeruší zásobování rozsáhlého území elektrickou energií se označuje blackout. Existuje mnoho příčin výpadku elektrického proudu v elektrické síti. Mezi hlavní příčiny patří: - extrémní spotřeba energie v létě vlivem stále rostoucího používání klimatizace - zatížení přenosových systémů, jejich následný průhyb a kontakt s okolní vegetací - při bezvětří je minimální produkce větrných elektráren a jejich výkon je nahrazován přenosem elektřiny z jiných zdrojů, často na velké vzdálenosti - chyby v koordinaci při propojení národních energetických soustav - technický stav energetické sítě Plošný výpadek elektřiny na velkém území (blackout) je kritická událost pro celá města, regiony, státy, kontinenty. Zatímco ostatních strategických surovin mají státy zásoby na 90 dní, elektřinu skladovat nelze. Vyrobená energie se musí hned spotřebovat. Co se nevyrobí, nemáme. Blackouty jsou jednou z příčin, proč není takový tlak na důslednou elektrifikaci železnice a proč se stále používají dieselelektrické lokomotivy. Jaké největší blackouty se v nedávné době staly? 20. února 1998 Auckland, Nový Zéland 14. srpna 2003 severovýchod USA a Kanada 23. září 2003 Dánsko a Švédsko 28. září 2003 Itálie 12. července 2004 Řecko 18. srpna 2005, Bali, Indonésie 27. dubna 2007 Kolumbie Výsledky zkoumání příčin blackoutů: - přenos velkých výkonů na hranici zatížitelnosti - nezvládnutá situace při propojení soustav sousedních států - vlivem liberalizace trhu zmizelo tradiční plánování výroby a přenosu elektrické energie - ... prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Katastrofa č. 14 Blackout http://www.nejdelsi.cz/b/blackout-vypadek-proudu/

Rok 1998 nebyl zrovna nejšťastnější pro město Auckland na Novém Zélandu, neb 19. února toho roku zde přišlo o elektřinu na 1700 podniků a domácností. Důsledkem přerušení 4 energetických kabelů vznikly ztráty dosahující 156 miliónů dolarů! Nejdelší blackout tehdy trval neuvěřitelných 66 dnů! Blackout je definován jako výpadek elektřiny ve velmi krátkém čase na větším území, většinou jsou to celá města. Problémy mohou vzniknout jak v elektrárně, tak kdekoliv na vedení, při zkratu nebo přetížení elektrické sítě. Třemi základními druhy výpadků jsou Blackout (totální výpadek), Brownout (pokles napětí způsobí utlumení světel) a Dropout (výpadek v řádu milisekund až sekund). Výpadky sítě a následné okamžité nahrazení jiným zdrojem energie jsou důležité obzvláště pro nemocnice a jiná zařízení. Většina takových zařízení má záložní dieslové generátory, které mohou okamžitě dodávat energii a nepřerušit tak chod strojů, přístrojů a osvětlení.


Katastrofa č. 15 WindUp

Windup je jev narůstání amplitudy kmitů, pozorovatelný u nelineárních (příp. chaotických) systémů. Pokud se provede inženýrský návrh v tomto směru špatně, pak to končí...


Moderní metody řešení inženýrských problémů


1.2 Evolutionary Computation and Selected Examples

BIV - motivace

The application of evolutionary techniques to hardware design (such as electronic devices, chaotic circuits, ... ) is termed evolvable hardware, aiming to replace some traditional design methods with evolutionary techniques forEvouční specified applications hardware that either are not achievable by using traditional methods or can benefit from the evolutionary approach. The development of evolutionary hardware has been inspired by several other fields as illustrated by Fig. 1.1.

1

Computer Science

BioInspired Software Evolvable Hardware

Biology

BioInspired Hardware

Motivation for Application of Evolutionary Computation to Chaotic Systems

7

There are many other examples worthy of mentioning, where evolutionary algorithms find successful applications. Standard evolutionary algorithms “exist” since the first famous seminal paper [23], while evolvable hardware is merely a “product” of later years. Both algorithms and hardware are complementarily joined together to solve various complex and difficult problems. The inter-relationships among various areas of hardware design, synthesis, and evolutionary computation are shown below in Fig. 1.2.

Electronic Engineering

Evolutionary Design Optimization

Fig. 1.1 Evolvable hardware and sciences of computer, biology and electrical engineering

Evolutionary Map. Place Route

Creative Evolutionary Design Evolvable Hardware

Creative Logic Design

Recently, the field of bio-inspired hardware has emerged, based on ideas from biology, to explore methods of fault tolerance and reconfigurability in modern hardHardware Technology Map. Logic ware designs. There are many interchangeable ideas between the fields of evolvable Synthesis Place Route Synthesis hardware and bio-inspired hardware. However the main focus in this paper is on the field of evolvable hardware, which lies in the overlapping zone among basic sciences of computer, biology and electronic engineering. Evolutionary techniques has been in existence for quite a long time, successfully Fig. 1.2 Inter-relational aspects of evolvable hardware solved many complex problems, showing its powerful applications in engineering practice and theory (see Section 1.2.8). The following examples demonstrate the prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu successful applications of evolutionary techniques: The field of evolvable hardware is still in its infancy, and there are many problems

During the course of this competition, a large set of results were obtained from various fields of science. Table 1.1 summarizes some selected and accepted results. A large part of accepted results has been reached in analog circuit design; and results Evouční hardware in other fields like physics and chemistry were also obtained.

BIV - motivace

Table 1.1 An overview of Hummies awards Applications

Number of Awards

Analog circuits Quantum circuits Physics - optical systems Logical circuits Optimization problems Game strategies Chemistry - molecular design Antenna design Applied mathematics


25 8 7 5 5 4 3 2 1

1


2

BIV - motivace 1

Plazmový reaktor


23

Fig. 1.22 Experimental set-up: computer with control software (right), wave synthesizer (bo tom left), and oscilloscope (top left)

Fig. 1.22 Experimental set-up: computer with control software (right), wave synthesizer (bottom left), and oscilloscope (top left)

Fig. 1.23 Experimental set-up: plasma reactor with Langmuir probe prof. Ing. Ivan Zelinka, Ph.D - www.ivanzelinka.eu

Fig. 1.23 Experimental set-up: plasma reactor with Langmuir probe

BIV - motivace Chaos

26

I. Zelinka and G. Chen

Fig. 1.27 Cost-function surface representing problem of synchronization, see Chapter 12

Literatura Prezentace byla udělána na základě této publikace. Více detailů, odkazů na další zdroje a příkladů naleznete v této knize, příp. na www.fai.utb.cz/people/zelinka/evoluce.


Biologicky inspirované výpočty: evoluční algoritmy

Recommend Documents