Novinky zeměměřické knihovny č. 4/2006

Klíčová slova: GPS, sítě, optimalizace, metaheuristika, genetický algoritmus, umělá inteligance

       Abstrakt: Genetické algoritmy (GA), založené na biologické evoluci, se jeví jako účinný prostředek pro řešení mnoha komplexních problémů reálného světa - např. pro optimalizaci observačního plánu zaměřování GPS sítě. Náhodné „genetické operátory“ selekce                       a rekombinace (která zahrnuje mutaci a crossover) se v modelech GA uplatňují pro modifikaci „populace“, načež se hodnotí její „úspěšnost“ z daných hledisek. V článku se navrhuje modifikovaná GPS-GA technika pro plánování měření GPS. Počítačový model GPS-GA náhodně modifikuje a rekombinuje „populaci“ možných programů zaměření, a po hodnocení se nová generace buď uchová pro další vývoj, nebo zavrhne („vyhyne“). Nakonec se z ní vybere podle zvolených kritérií nejlepší observační plán. Je naznačen logický algoritmus GPS-GA, jeho funkce (vše v genetických termínech) a uvedeny výsledky numerických experimentů se sítěmi na Maltě (redukce nákladů o 3,10 %) a na Seychelách (redukce „jen“ o 1,78 %).

       Poznámka: Originál článku obsahuje řadu obrázků a schémat, vysvětlujících chování genomu, formalizovaným jazykem popisujících funkci genetických algoritmů (GA) i modelu GPS-GA pro optimalizaci zaměřování GPS sítě, a ilustrujících jeho aplikaci na malou modelovou        a dvě konkrétní sítě. V tomto zkráceném překladu (aby takovým byl) je všechny vypouštím            a omezuji se na slovní výklad základních myšlenek pojednání, v podobě místy upraveného textu článku, s kurzívou psanými poznámkami, příp. souhrny větších pasáží textu.

Úvod

       Pro uplatnění kosmických technologií v běžném životě bylo vykonáno mnoho práce výzkumné, při polních zkouškách i v průmyslovém rozvoji. Toto pojednání se zabývá využitím GPS při budování geodetických sítí. V současné době vstupuje do kosmické technologie jako inovace umělá inteligence (AI - Artificial Intelligence), která již přechází z výzkumu do aplikací. Genetické algoritmy (GA), založené na biologické evoluci, se staly zajímavým prostředkem pro optimalizaci řady komplexních problémů reálného světa. K pochopení významu GA pro satelitní zaměřování si představíme síť bodů, které všechny se mají navštívit s přijímači GPS. Zeměměřič zná doby přesunu mezi jednotlivými body a chce minimalizovat celkový potřebný čas. Úkol zní: „V jakém efektivním pořadí se mají dané body navštívit?“ Vyzkoušet všechny možné varianty cesty může být proveditelné pro malé sítě, ale velmi vyčerpávající v sítích velkých. Pak metaheuristická technika GA může dát lepší výsledky v podstatně kratším čase. Všeobecně řečeno, metaheuristická technika je iterační procedura pro rychlé a efektivní vyhledání optimálního řešení v diskrétním souboru možných, tedy nejlepší hodnoty jednoduché funkce (času, ceny, přesnosti apod.). V tomto článku se GA metaheuristická technika aplikuje na minimalizaci času pro zaměření GPS sítě, a i když pravděpodobně nenalezne to doslova optimální řešení, přesto dá v krátkém čase řešení „téměř“ optimální, vyhovující podstatným požadavkům na průběh zaměřování.

       Genetické algoritmy (GA) byly navrženy pro simulaci procesů v přírodních systémech, podstatných v evoluci - sledují zejména Charlese Darwina princip „přežívá nejzdatnější“. Je to soupeření jedinců v prostředí omezených zdrojů, kdy zdatnější jedinci převládají nad slabšími. Pro efektivní užití GA je potřebné „biologické“ znázornění optimalizovaného řešení (jako genomu či chromozomů). Pak  GA vytvářejí „populaci“ řešení, a aplikují genetické operátory (např. mutace a crossover) pro vývoj nových úspěšnějších generací, za účelem nalezení nejúspěšnější(ch). (Slova crossover, crossing-over, v češtině překřížení, znamenají náhodné výměny částí genetické informace v chromozomech.) Toto pojednání zavádí GA a navrhuje modifikovaný přístup, založený na genetickém chování, pro vyhledání nejlepšího plánu zaměřování geodetické GPS sítě.

Formulace problému

       V tomto článku modifikovaná GPS-GA technika vytváří od začátku prvotní observační plán a zlepšuje jeho kvalitu redukcí jeho celkových nákladů postupnými iteracemi. Tyto celkové náklady jsou dány sumou nákladů na přepravu přijímačů mezi stanicemi. Na začátku jsou           (v uváděném příkladu s obrázkem jednoduché sítě 4 bodů, zaměřované dvojicí přijímačů) oba přijímače (X a Y) na výchozích (zvolených) bodech. Pak se Y přemístí na jiný bod, čímž vzniknou první přepravní náklady, načež putuje na další bod s dalšími náklady a opět na zbývající bod, zatímco přijímač X zůstává bez pohybu. Mají-li se zaměřit všechny strany, musí se přemisťovat i přijímač X, a v některých krocích (kroku) oba současně. Pak se spočtou výsledné náklady a může se vyzkoušet jiná varianta pořadí přemisťování obou přijímačů i jejich počátečních poloh. Obecně lze problém zaměřování GPS sítě formulovat následujícím způsobem. Jistý počet přijímačů (X, Y, atd.) se má umístit na stanicích (a, b, c, d, atd.) pro koordinované zaměření seancí („sessions“ ab, ac, dc, atd.) mezi těmito stanicemi. Úkolem je najít nejlepší pořadí měření pro minimální celkové náklady na zaměření sítě. (Můžeme ovšem myslet i na přesnost zaměření, na skutečnou nutnost měření všech spojnic, na náklady vlastní observace apod.)

Reálné chování lidských genů

       Všechny živé organizmy jsou složeny z buněk, z nichž každá obsahuje stejnou sadu chromozomů (neboli genom). Chromozomy jsou řetězce genů, které definují druh a jsou modelem celého organizmu. Jsou to bloky molekul DNA (deoxyribonukleová kyselina / „acid“), řídících dědičnou informaci. Forma této biologické informace se musí kopírovat do veškerého potomstva buňky. Soubor všech alel (forem genů) celé sady chromozomů určuje genotyp (znaky, charakteristické rysy, např. barvu očí atd.) jedince, v jejich množině pak genofond určité populace. Jednotlivé geny si lze představit jako binárně kódované znaky. Přirozený vývoj pak se děje rekombinací dvou originálních genotypů do nových směšováním jejich genů. Vývojový proces lze popsat takto: je dána výchozí generace; pak z ní nastává výběr jedinců; jejich páření; mutace jejich genů genetickými operátory; vložení těchto genů do nové generace. A všechno to lze popsat formálním jazykem nebo v podobě diagramů, což nalezneme v originálu článku.

Genetické operátory (selekce a rekombinace) se užijí pro obměnu složení populace. Selekce se děje na základě relativní zdatnosti a pravděpodobnostním způsobem vyřazuje relativně slabší jedince. Rekombinace, tvořená mutací a crossoverem, imituje pohlavní reprodukci dvou existujících chromozomů (rodičů) do dvou nových chromozomů (dětí), majících s vyšší pravděpodobností lepší zdatnost, než jejich rodiče. Crossover, jako třídící operátor, se s vysokou pravděpodobností uplatňuje pro výměnu informací mezi tvořenými řešeními (biologicky: „překřižení“, výměna částí v páru chromozomů). Naproti tomu mutace, stejně jako v přírodních systémech, je velmi málo pravděpodobný operátor, který mění (přepíná) určitý bit ve vlastním (výsledném) řešení, což umožňuje využít nové oblasti pro vyhledávání řešení (tady se patrně míní už aplikace na náš problém).

       Shrnuto: selekce zaměřuje vyhledávací proces na nadějné oblasti v prostoru (hotových) řešení, zatímco crossover a mutace vytvářejí nové výchozí body v tomto prostoru pro příští řešení (s dalším zlepšováním). Technika GA bude pomocí genetických operací konvergovat úspěšnými iteracemi ke globálními (nebo téměř globálnímu) optimu. Uchovává populaci chromozomů (tj. řešení) s přiřazenými hodnotami zdatnosti. Rodiče pro páření se vybírají na základě jejich zdatnosti a produkují potomstvo podle reprodukčního plánu. V důsledku toho, zdatnější řešení (tj. „rodiče“) mají více příležitostí k reprodukci, takže jejich potomstvo zdědí vlastnosti obou rodičů. Každá nová úspěšná generace ponese lepší geny „parciálních řešení“ než předchozí generace. V dalším oddílu budou tyto koncepce GA modifikovány na GPS zaměřování k vyhledání optimálního observačního plánu (nebo blízkého k němu).

Jak pracuje vyvinutá technika GPS-GA?

       Využití idejí genetiky v satelitním vyměřování má tři nejdůležitější stránky: definici              a implementaci genetického znázornění, definici cílové funkce, definici a implementaci gene­tic­kých operátorů. Navrhovaná technika GPS-GA je počítačový model, v němž populace „kandidujících“ observačních plánů pro GPS síť se stochasticky selektuje, rekombinuje a mutuje, a poté se buď eliminuje, nebo uchovává v závislosti na relativní vhodnosti („zdatnosti“ - „fitness“).

       V prvním kroku („Initialization“) se podle návrhu generuje počáteční populace „chromozomů“ (tj. observačních plánů) buď náhodně, nebo změnami obměňováním vstupních dat chromozomů. Druhý krok („Evaluation“) počítá hodnoty „fitness“ (zde náklady). Realizace cílové funkce přirozeného výběru je obsahem třetího kroku („Exploitation / diversification“).      V něm se vybrané chromozomy s nejlepšími výsledky „fitness“ zařazují „polonáhodně“ jednou nebo vícekrát do podskupiny pro množení, zatímco chromozomy s nízkými výsledky se z po-pulace vyřazují. Konečně čtvrtým krokem („Exploration / intensification“) jsou operátory rekombinace a mutace (uplatněné na výsledky třetího kroku). - Poznamenejme, že slovníkový překlad anglických označení kroků, zde daných v závorkách, neodpovídá dobře logice věci.

       Následuje podrobnější popis těchto kroků v „observační“ představě. Dva chromozomy (observační plány s definovaným počtem seancí) se z původní populace náhodně vybírají pro reprodukci („páření“). Pravděpodobnost že k tomu dojde je volitelná a zpravidla se nastavuje na vysokou hodnotu (např. 0,90). Přitom se uplatní rekombinační operátor pro výměnu genů (seancí) mezi dvojicí „rodičů“ (starých plánů), aby vznikly dvě „děti“ (nové kvalitnější observační plány). „Rodiče“ neurčení pro reprodukci přejdou do další generace beze změny. Při reprodukci se ještě volí (jak?) bod crossoveru, nad nímž se překříží geny rodičů (tj. přehodí se blízké seance), načež děti nahradí rodiče v další generaci. Pro zvýšení diverzity v populaci se s obvykle jen malou, rovněž volitelnou pravděpodobností (např. 0,01) uplatní operátor mutační, takže dobré chromozomy se nepoškozují. Po čtvrtém kroku se populace zaplňuje nově vzniklými chromozomy, a cyklus se opakuje do stanoveného počtu generací (iterací).

       Jedním z charakteristických rysů, který odlišuje GA od jiných optimalizačních přístupů, je skutečnost, že se optimalizují zobrazení proměnných (parametrů) a nikoliv samotné proměnné. To činí techniku GA velmi flexibilní a vhodnou pro situace, kde jsou proměnné velmi rozdílné.

       Mnozí výzkumníci však konstatovali, že nejběžnější důvod proč technika GA v některých aplikacích nepracuje dobře, spočívá ve špatné volbě zobrazení proměnných k optimalizaci.

       Genetické zobrazení problému měřických sítí GPS je obtížný úkol, a komplikovanost spočívá v tom, jak zakódovat observační plány v souladu se strategií GA. To nemůže být prostě seznam seancí (sessions) v pořadí, jak se mají měřit. Musí se užít sofistikovaná forma kódování pro vygenerování potenciálního observačního plánu.

       V článku nyní následuje podrobnější popis funkce algoritmu textem a poté zápisem sledu logických operací, který zde přepíšeme ve zkrácené podobě (zejména bez symbolů proměnných, které dále nepoužijeme).

[I]      Inicializace & reprezentace :

(A)   Formulace výchozí hodnotové matice (časy přesunů mezi stanicemi):

·  Vložení celkového počtu stanic a odhadu nákladů na pohyb každého přijímače.

(B)   Vytvoření aktuální hodnotové matice (časy přesunů přijímačů mezi seancemi):

·  Vložení počtu přijímačů a definice seancí (sessions), které se mají měřit.

(C)   Vyjádření potenciálního řešení pro měřenou síť:

·  Zakódování řešení v podobě řetězců znaků konečné abecedy.

·  Každý řetězec musí představovat kompletní řešení měřené sítě.

(D)   Definice hodnotové funkce.

(E)    Stanovení strukturálních prvků:

·  Nastavení velikosti populace;

·  Volba dvou výchozích populací (tj. množiny možných observačních plánů) pro dva časy t a t+1;

·  Zavedení nejnižší hodnoty nákladů pro první z těchto populací;

·  Určení observačního plánu, který má tuto nejnižší hodnotu nákladů.

(F)    Inicializace řídících parametrů:

·  Volba pravděpodobnosti crossoveru;

·  Volba pravděpodobnosti mutací;

·  Volba zákona poklesu pravděpodobnosti mutací;

·  Volba kritéria pro ukončení.

[II]   Generování počáteční populace a strategie přijetí                                                     Zde probíhají dva na sebe navazující cykly:

(A)   Diverzifikace  pro novou generaci se provádí selekce dvojic, crossover a mutace, dokud není naplněna nová populace (množina observačních plánů);

(B)   Intenzifikace druhou optimalizační procedurou „2nd opt.“ - generování všech možných observačních plánů přehazováním blízkých seancí.

[III]  Pravidla ukončení

(A)   Ukončení vyhledávacího procesu:

·  Dosažení stanoveného počtu iterací;

·  Dosažení stanoveného počtu iterací bez dalšího zlepšení nejlepšího observačního plánu;

·  Jiné důvody.

(B)   Vyhlášení výsledku

·  Nejlepší observační plán;

·  Čas výpočtu.

·  Konec

Výsledky výpočtů

       Právě podané logické schéma aplikace genetických algoritmů (GA), resp. GPS-GA, jen naznačuje některé souvislosti - ani v originálním článku nejsou dány všechny podrobnosti stochastických řešení, ale spíše odkazy na řadu dřívějších publikací. V tomto oddílu autoři ilustrují funkci GPS-GA na příkladu malé hypotetické sítě o čtyřech bodech, s požadavkem zaměření všech spojnic (6 seancí) dvojicí přijímačů. „Hodnoty“ pro jednotlivé přesuny mezi body (tj. časy přesunů) jsou zadány od 1 do 6 jednotek (minut). Se třemi obrázky a šesti tabulkami pak ukazují postup řešení a výsledky jeho jednotlivých (výše naznačených) kroků. Zkrácený překlad zde pro podrobnosti realizace naznačeného algoritmu odkazuje na originál; v něm jsou probírány i detaily dosti významných crossoveru a mutací. My budeme jen konstatovat, že v prů-běhu řešení se „cena“ observačních plánů (tj. součet „hodnot“ pro přesuny) od výchozího, náhodně vybraného plánu se 17 minutami, dostala až na 27 minut, přičemž pro nejlepší plán (tj. pořadí seancí - zaměřovaných spojnic bodů) byla „cena“ jen 13 minut.

Velké sítě

       Pro zobecnění vyvinuté techniky a práci s většími sítěmi byly užity dvě GPS sítě různé velikosti a typu. První byla triangulační síť na Maltě, kde 38 seancí spojilo 25 bodů. Výchozí observační plán měl hodnotu 1405 minut, a byl generován manuálně na základě intuice a zku-šeností měřičů. Aplikace GPS-GA techniky zredukovala tento čas na 940 minut po 20 sekundách výpočtu (v tabulce je 10 s ???). Druhá síť byla liniová na Seychelách. Ta má 71 seancí a 57 bodů, manuálně generované časy 994 minut snížila po 80 sekundách výpočtu technika GPA-GA na 857 minut (což neudivuje, u liniové sítě se dá méně manipulovat s přehazováním pořadí měřených vektorů). V těchto řešeních byla nastavena pravděpodobnost crossoveru na 0,9 a počáteční pravděpodobnost mutací 0,85 (???); velikost počáteční populace byla 30 jedinců (plánů).           V následující tabulce jsou dány výsledky obou výpočtů.

V tabulce je N počet stanic, S počet seancí, V0 „cena“ podle počátečního plánu (minuty), V GA „cena“ podle optimálního plánu z GPS-GA, ET výpočetní čas (sekundy) a RRC% relativní redukce ceny v procentech. Poznamenejme k časům výpočtu: není uvedena velikost programů, počty iterací (populací), ani parametry užitého počítače.

Závěry a další práce

       Metaheuristika GA je univerzální metoda optimalizace, pro kterou není potřeba mnoho vědět  o řešeném problému. Z tohoto pohledu byly zkoumány a vyvíjeny techniky GPS-GA, určené pro řešení a optimalizaci problému měřických sítí GPS (statického typu).

     Budoucí výzkumy předpokládají dynamický rozvoj tohoto modelu do flexibilních počítačových procedur, které by dávaly velmi přesné modely o vysokém rozlišení i pro jiné geomatické aplikace (např. pro modelování atmosférických efektů, globálních, velmi přesných modelů tíhového pole, geografických informačních systémů atd.).

       Úsilí o optimalizaci těchto důležitých aplikací je zaměřeno na zvýšení funkčnosti zavedených technologií pro práci s jejich reálnějšími prvky, jako jsou časové a metrické možnosti, se směsí spojitých proměnných a diskrétních výběrů, atd. Například, tento model pomůže při zkoumání různě integrovaných interních a externích dynamických jevů, vyžadovaném pro plánování, vývoj a otevření kosmického letu „Mise k Marsu...“

Poznámka pro hlubší zájemce

       Zájemci o podrobnosti si mohou článek přečíst nejen v „papírové“ podobě (např. knihovna VÚGTK - ODIS, sign. 49 533), ale i na webu, kde je ve formátu html i pdf. Hledejte na

http://link.springer.de

http://www.springerlink.com/content/wuqn66p92rgvgm5k/?p=d8c123e005ec4758a17675fd8451a73f&pi=0