Ing. Lucie Vaníčková
Katedra inženýrské informatiky
Fsv ČVUT Praha
Technická 2
Praha 6
E - mail: lucie.vanickova @fsv.cvut.cz
Digital terrain model (DTM) is important for the civil engineering, for viewing buildings influence on their environment. Therefore it is need for effective model terrain output.
The raster model is the easiest type of DTM. A terrain relief is described by array of vertical coordinates of points. The points are located in a regular raster.
The polyhedry model is the next type of DTM. For polyhedry model a landscape is parceled in smaller plane areas. Usually triangles, quadrangles so as to adjoin to a terrain relief to the nines. The terrain relief is replaced by regular polyhedron with triangle or quadrangle faces.
The plate model has the most effective output . A terrain is parceled smaller areas. No only plane ones. They can be anyway curved.
One of the problems to make the plate model is curvature of the terrain plates so as to continue one another fluently.
Coons area is the most used method of the terrain plates curvatures. It is a quadratic area, which can be written by equation:
R1: z = ax2 + by2 + cxy + dx + ey + g
The area is running for all three points of the triangular plate. First derivation of the terrain is continuous at a border of two plates. These two rulles give 6 equations. By that of we can get 6 Coons area parameters (a,b,c,d,e,g).
There are used triangular plates even quadrangular plates. Fluent curvature of these plates problem is insoluble. We get more then 6 rulles, but the quadratic area have only 6 parametrts, which influence its continuance.
It rise the teoretical problem to continue these plates at least to the best fluently. That means difference right and left derivation of altitude along the arbitrary trajectory at the border of the plate comes to be the nearest to 0.
One of the optimization way to the best fluently continue plates is to use evolution computing methods.
It is possible to use GA (Genetic Algorithms) for finding the best curvature of quadrangular areas.
After substitution four given border points of the plate to the equation R1 we will get 4 equations with 6 parameters.
We will express the parameters a,b,c,d from these equations. By substitution these results to differents right and left derivations at all four sides of the plate we will get 4 equations f1-f4 with two parameters e and g.
We want to find such parameters e and g, for which all four function are the nearest to 0.
We can use GA for finding the optimal parameters g and e.
We will generate a lot of terrain models by this way. We will choose one model from their along some criteria.
It is several problems of to make GA:
To find applicable parameters representation,
invent applicable crossing operator and mutation operator.
We need to find system of make first solving generation, system of selection and current generation projection to next generations. We need to find stop rule for this GA.
Than we are finding expectations of crosssing and mutation by experiments, so that next generation will be improving.
We will choose the best of generated individuals set models from their along some criteria.
We will choose the most fluently model: such plates witch f1-f4 values are the nearest to 0.
The plates of the choosen model must hold:
R will be determined by experiments.
The alghoritm for model finding must be effective, to run generating DTM for resonable time. It will be necessary to provide a lot of experiments for various types of terrain areas and to set GA and its parameters.
Digitální modelování terénu (DMT) je důležité zejména ve stavebnictví. Jinak lze těžko posuzovat vliv budoucí stavby jako prostorového objektu na okolí.
K tomu je potřeba efektivních výstupů modelu terénu.
Takové výstupy nám poskytuje model plátový, který se skládá z elementárních n-úhelníkových plošek (většinou 3 a 4 úhelníkových), které na sebe hladce navazují (pokud tomu není v terénu jinak). Naproti tomu rastrový model terénu se skládá z plošek vytvořených nad pravidelnou půdorysnou obdélníkovou sítí. Tento model nemá dostatečnou vypovídací schopnost tam ,kde se terén místy prudce mění. Trojúhelníkový model terénu aproximuje terén rovinnými trojúhelníkovými ploškami. Tyto plošky na sebe navazují ostře, model tedy není zaoblený na rozdíl od skutečného terénu.
Jedním z mnoha problémů vytváření plátového modelu terénu je zaoblování na sebe navazujících elementárních plátů aproximujících terénní plochu
Nejčastěji používanou metodou pro zaoblování je tzv. Coonsova plocha. Coonsova plocha je plocha kvadratická, lze ji vyjádřit implicitní rovnicí:
R1: z = ax2 + by2 + cxy + dx + ey + g
a která splňuje následující dvě podmínky:
- Plocha prochází všemi třemi krajními body trojúhelníkového plátu.
- Na rozhraní dvou plátů je spojitá alespoň první derivace terénu.
Uvedené dvě podmínky dávají 6 rovnic. Pomocí nich lze vypočítat 6 parametrů Coonsovy plochy (a,b,c,d,e,g).
Praxe však ukazuje, že často je vhodné použít kromě plátů trojúhelníkových i pláty s větším počtem vrcholů, nejčastěji čtyřúhelníkové. Problém
hladkého navazování jiných než trojúhelníkových plátů je v oboru kvadratických ploch neřešitelný. Je zde totiž více než 6 podmínek, které musí daná kvadratická plocha splňovat ale jen 6 koeficientů, které tvar plochy ovlivňují.
Vzniká tedy teoretický problém, jak pláty větší než trojúhelníkové na sebe navázat, když už ne zcela hladce, tak "co nejblíže" hladkosti. To znamená tak, aby rozdíl pravé a levé derivace nadmořské výšky podle libovolné trajektorie v krajních bodech plátu byl co nejbližší 0.
Jedním z možných způsobů optimalizace co nejvíce hladkého napojení plátů je použití evolučních výpočetních technik (EVT). Lze použít genetické algoritmy (GA) pro nalezení co nejlepšího zaoblení čtyřúhelníkových ploch.
Po dosazení čtyř zadaných krajních bodů plátu (jejich souřadnic x, y, z) do rovnice R1, dostaneme čtyři rovnice o šesti proměnných.
Z těchto rovnic vyjádříme proměnné a,b,c,d a dosadíme do čtyř rozdílů pravé a levé derivace na všech čtyřech stranách plátu. Dostaneme čtyři rovnice f1-f4 o dvou proměnných e a g.
My potřebujeme nalézt takové hodnoty e a g, pro které budou mít všechny čtyři rovnice hodnoty blížící se co nejvíce k nule.
Na nalezení optimálních hodnot g a e použijeme genetický algoritmus.
Takhle vygenerujeme velké množství modelů terénu a z nich pak budeme vybírat na základě nějakých kritérií jeden model.
Při tvorbě GA pro vygenerování plátů se budeme potýkat s následujícími problémy:
Najít vhodnou reprezentaci proměnných e,g.
Použít vhodný a výkonný operátor křížení a mutace.
Použít efektivní způsob výběru jedinců z populace.
Nastavit pravděpodobnost křížení a mutace jedinců.
Určit zastavovací pravidlo nebo počet průchodů GA.
Určit systém sestavování nové generace.
Vygenerování startovací populace.
Při výběru nejvhodnějšího jedince z množiny vygenerovaných modelů budeme postupovat na základě určených kritérií. Kritéria určíme tak, abychom vybrali "nejhladší" model. Vybereme pláty takové, aby jejich f1, f2, f3 i f4 byly co nejbližší nule.
Pláty vybraného modelu musí splňovat:
R určíme na základě experimentů.
Algoritmy pro hledání modelu musí být efektivní, aby celé vygenerování DMT proběhlo v rozumném čase. Optimální GA s optimálními nastaveními bude nalezen pomocí experimentů.
Modelování se ve stavebnictví hojně využívá. Stavební objekty jsou unikátní, velkých rozměrů a nákladné. Proto bývají před svojí realizací modelovány. Většinou na počítači. Podobně bývá modelováno například okolí budoucího stavebního objektu. Při modelování je usilováno o docílení co nejlepších vlastností budoucího objektu ( tzn. budoucího stavu objektu), často však nelze dosáhnout optima pomocí klasických (výpočetních) prostředků.
V případě, že stavový prostor možných stavů objektu je příliš velký na to, aby byl prohledán celý, snažíme se optimu alespoň přiblížit. Ne vždy pro to existují efektivní nástroje mezi klasickými výpočetními metodami. Proto bych ráda našla efektivní nástroje pro tuto problematiku mezi evolučními výpočetními metodami.
Oblast modelování, na kterou se zaměřím, je digitální modelování terénu (DMT). Digitální modelování terénu je důležité pro stavebnictví. Bez něj lze těžko posuzovat vliv budoucí stavby jako prostorového objektu na okolí. Proto je potřeba efektivních výstupů modelu terénu.
Obr č.1 Digitální model terénu
Takové výstupy nám poskytuje model plátový, který se skládá z elementárních n-úhelníkových plošek (většinou 3 a 4 úhelníkových), které na sebe hladce navazují (pokud tomu není ve skutečném terénu jinak). Dalšími typy digitálního modelu terénu jsou model rastrový a model polyedrický. Rastrový model terénu se skládá z plošek vytvořených nad pravidelnou půdorysnou obdélníkovou sítí. Tento model nemá dostatečnou vypovídací schopnost tam, kde se terén místy prudce mění. Polyedrický model terénu aproximuje terén rovinnými trojúhelníkovými ploškami. Tyto plošky na sebe navazují ostře, model tedy není zaoblený na rozdíl od skutečného terénu.
Jedním z mnoha problémů vytváření plátového modelu terénu je zaoblování na sebe navazujících elementárních plátů aproximujících terénní plochu. V praxi je často vhodné použít kromě plátů trojúhelníkových i pláty s větším počtem vrcholů, nejčastěji čtyřúhelníkové.
Nejčastěji používanou metodou pro zaoblování plátového modelu jsou kvadratické plochy (např. Coonsova plocha). Kvadratickou plochu lze vyjádřit implicitní rovnicí:
R1: z = ax2 + by2 + cxy + dx + ey + g
a měla by splňovat následující dvě podmínky:
- plocha prochází všemi krajními body plátu.
- na rozhraní dvou plátů je spojitá alespoň první derivace terénu.
Vzniká tady teoretický problém, jak pláty na sebe navázat, když už ne zcela hladce, tak co nejblíže hladkosti. To znamená tak, aby rozdíl pravé a levé derivace nadmořské výšky podle libovolné trajektorie v krajních bodech plátu byl co nejbližší 0.
Většinou nelze vyřešit hladké navázání plátů takového DMT klasickými metodami. Řešení ani nemusí existovat. V každém případě se vyplatí hledat pouze přibližné řešení zaoblení nějakou iterační nebo heuristickou metodou.
Jedním z možných způsobů optimalizace co nejvíce hladkého napojení plátů je použití evolučních výpočetních technik. Lze použít genetické algoritmy pro nalezení co nejlepšího zaoblení celé plochy modelovaného DMT.
Při tvorbě GA pro vygenerování plátů se budeme potýkat s následujícími problémy:
Algoritmy pro hledání plátů modelu musí být efektivní, aby celé vygenerování DMT proběhlo v rozumném čase. Optimální GA s optimálními nastaveními bude nalezen pomocí experimentů.
Digitální model terénu (DMT) je programový prostředek sloužící k vytvoření a popisu třírozměrného modelu terénního reliéfu a k provádění jistých operací s tímto modelem. Základní činnosti, které DMT obvykle umožňují vykonávat, lze rozdělit do několika oblastí:
1. Získávání údajů o terénním reliéfu.
2. Vlastní tvorba terénního modelu.
3. Prohlížení terénního modelu.
4. Výpočty prováděné na DMT.
5. Úpravy terénu a modelování.
Abychom mohli modelovat terénní reliéf ve vší obecnosti, je potřeba využívat i další prostředky pro počítačové modelování a hlavně mít možnost spojovat výsledky získané různými metodami.
Nejjednodušším typem DMT je model rastrový. Terénní reliéf je popsán maticí výškových souřadnic bodů rozmístěných v pravidelném rastru. Data pro rastrový model nejsou obvykle získávána přímo měřením v terénu, ale interpolací bodů naměřených v rastru nepravidelném.
Dalším typem terénního modelu je model polyedrický. Při jeho použití je terén rozdělen na menší rovinné plošky, obvykle na trojúhelníky či čtyřúhelníky tak, aby se tyto plošky co nejlépe přimykaly k reliéfu terénu. Terénní reliéf je pak vlastně nahrazen pravidelným mnohostěnem s trojúhelníkovými či čtyřúhelníkovými stěnami.
Plátový model má mnoho rysů společných s modelem polyedrickým. Terén je opět rozdělen na menší plošky, které však nemusí být pouze rovinné, mohou být i jistým způsobem zakřivené. Nejčastěji se používají plochy popsatelné polynomickými funkcemi, které na sebe při hraničních liniích navazují natolik hladce, aby byla zaručena spojitost derivací do jistého předem daného řádu.
Tvorba plátového modelu ze vstupních dat postupuje v několika krocích. Prvním krokem je triangulace, tedy pospojování vstupního seznamu bodů do trojúhelníkové sítě. Takovou trojúhelníkovou síť lze vytvořit mnoha různými způsoby, z nichž některé jsou pro další práci vhodné více a jiné méně. Výsledkem triangulace je terénní model popsaný vhodnou datovou strukturou. Součástí tvorby modelu může být i optimalizace jednotlivých plátů. Při ní jsou některé zbytečné hrany trojúhelníkové sítě vypuštěny a model je pak tvořen i čtyřúhelníky, či ještě složitějšími mnohoúhelníky.
Poslední fází tvorby modelu je ošetření singularit. Singularitou rozumíme místo, kde se terén chová jiným způsobem, než by se dalo usoudit z jeho chování v okolí singularity. Typicky se může jednat například o ostrý horský hřeben, nebo pobřežní linii jezera.
Obr č.2 Plátový digitální model terénu
Během tvorby plátového modelu terénu vzniká celá řada teoretických problémů [2,4]. Prvním z nich je samotná triangulace. Efektivitu celého programového balíku pro digitální modelování terénu a krajiny totiž významně ovlivňuje právě efektivita triangulačního algoritmu. Tento algoritmus musí být dostatečně rychlý a přitom musí poskytovat triangulaci dobré kvality.
Dalším problémem je zaoblování terénních plátů tak, aby na sebe hladce navazovaly. Tento problém je v mnoha komerčních programech pominut, neboť pro praktickou práci je nejdůležitější vizuální dojem, a pro něj leckdy stačí pouze přibližně hladké navázání polyedrických plátů. Jinak je ovšem hladké navázání plátů zvláště v případě polyedrů s různým počtem vrcholů velkým teoretickým problémem.
Poslední sadou problémů je ošetření singularit. Singularity mohou být opět různých typů. Na některých hranách například můžeme požadovat spojitost vlastního terénu, ale nikoliv již hladké napojení plátů (spojitost derivací). Příkladem může být horský hřeben. Někdy ani samotný terén chápaný jako funkce dvou proměnných (k polohopisným souřadnicím x a y je přiřazena výška z) nemusí být spojitý. Terén může obsahovat zlom (tedy kolmý sráz, na kterém na sebe dva pláty nenavazují spojitě), nebo dokonce převis (místo, kde se dva pláty částečně překrývají a terén tedy netvoří funkci). Jelikož singularity těchto druhů (zlom, převis) se vyskytují poměrně zřídka a jejich programové ošetření je dosti náročné, řada programů pro DMT řešení takových singularit obchází. Často je například zlom realizován prudce klesajícím plátem, který je však stále ještě grafem funkce dvou proměnných. Místo kolmého srázu se tedy ve výsledném modelu objeví velmi prudce klesající svah.
Vzhledem k výše uvedenému, není možné dokonalé zaoblení plátového modelu terénu aproximovaného kvadratickými pláty. V praxi se používají různé heuristické metody pro přibližné zaoblení takových modelů. Např. je model ve skutečnosti tvořen trojúhelníkovými pláty, ale při zobrazování modelu jsou hrany rozdělující čtyřúhelníkové pláty na trojúhelníkové vypuštěny.
Hodně záleží na možnostech zobrazování konkrétního systému pro DMT. Pokud není možné zobrazení libovolných řezů, nebo alespoň řezů kolmých k osám x, y a z, je zbytečné se snažit terén dokonale zaoblit. Zvláště zobrazení povrchu terénu pomocí rastrových textur skryje mnoho nepřesností.
Obr č.3 Plátový DMT zobrazený pomocí řezů rovinami kolmými k ose X a rovinami kolmými k ose Y
Genetické algoritmy patří do množiny evolučních algoritmů. Jsou vyhledávací a optimalizační metodou založenou na principech evoluce v přírodě. Pomocí GA bylo vyřešeno mnoho problémů, u kterých ostatní metody selhaly. Na druhou stranu, GA jsou velmi závislé na svém provedení a nastavení pro dané dílčí problémy.
Hlavní síla GA spočívá v tom, že prohledávají několik bodů v prostoru možných řešení najednou, a tím jsou více odolné proti uvíznutí v nějakém lokálním extrému. Mnoha praktickými experimenty s mnoha různými konfiguracemi GA byly zjištěny vlastnosti genetických algoritmů. Ty jsou velmi složité, v každém případě je potřeba pro daný problém provést mnoho pokusů pro nastavení GA.
Pomocí GA hledáme (skoro) optimálního jedince (řešení problému). GA generují populace jedinců (potencionální řešení daného problému) a ty postupně vylepšují. Potenciální řešení jsou zakódována zpravidla do řetězců tvořených symboly z jisté abecedy.
Každý jedinec je v GA je reprezentován tzv. chromozómem (binárním řetězcem).
Chromozómy jsou tvořeny z genů, binární abecedou V={0,1}. K označení chromozómů budeme používat písmena velké abecedy. To znamená, že v čase t (generaci t) bude populace G(t) obsahovat chromozómy Gj, j=1,2,3,...,n, kde n vyjadřuje velikost této populace. Pro správné pochopení dějů probíhajících v rámci GA je potřeba zavést pojem podobnostního schématu. Tato schémata popisují podmnožiny si podobných řetězců (chromozómů) s některými pevně stanovenými pozicemi (geny). Tato schémata jsou definována nad původní abecedou chromozómů rozšířenou o symbol *, reprezentující tzv. volný parametr unifikovaný s libovolnou hodnotou genu. Výsledná abeceda schémat V+ je tedy tvořena tímto sjednocením V({*}.
Reálná čísla lze v GA reprezentovat např. pomocí plovoucí desetinné čárky, nebo je lze některým z mnoha možných způsobů převést na binární řetězce.
Fitness funkce je ohodnocení daného jedince tak, že čím vyšší, tím více se řešení blíží k optimu. Pro různé problémy je nutné ji stanovovat různými způsoby.
Selekce je výběr jedinců pro promítnutí do další generace. Jedinci s vyšší hodnotou fitness by měly být vybíráni do nové populace s větší pravděpodobností než jedinci s nižší hodnotou fitness. Používané způsoby selekce: ruletové kolo (výběr z populace pomocí fitness funkce a náhodně vygenerované hodnoty), turnajová selekce (výběr z n-tice jedinců podle fitness funkce), pořadová statistika (výběr z populace pomocí absolutního pořadí a náhodné hodnoty), elistický model (několik nejlepších jedinců se přímo okopíruje do další populace) a další [5,6,7].
Pomocí genetických operátorů (křížení a mutace) jsou vytvářeni jedinci do další populace. Křížení je rekombinace několika (zpravidla dvou) chromozómů vytvářející nové jedince (zpravidla dva). Mutace slouží k zanesení určité divergence do populace. Snižuje se tím možnost uvíznutí v některém z lokálních extrémů.
Obr č.4 Schéma výpočtu GA
program SGA;
*Náhodně vygeneruj populaci G(t) o rozsahu PopSize s prvky x[i], z nichž každý je reprezentován L-bitovým řetězcem
repeat
* Vyhodnoť členy populace G(t), urči jejich hodnoty fitness funkce f(x[i]), průměrnou hodnotu fitness funkce v populaci favg a nejlepší hodnotu fitness funkce v populaci BSF
* Urči pravděpodobnost přežití každého jedince p[i]
* Vypočti kumulativní pravděpodobnosti q[i]:=sum(k=1..i,p[k])
* Proveď selekci
* Proveď křížení
* Promítni výsledky křížení do populace
* Proveď mutaci
* Sadu jedinců x*[i] považuj za G(t)
until Zastavovací_pravidlo;
end.
V případě, že prostor přípustných řešení není souvislým intervalem, nastává problém, jak se vypořádat s jedinci, kteří jsou GA generováni, a přitom představují nepřípustná řešení.
Problémy s omezeními lze řešit několika způsoby. Např. pomocí pokutových funkcí, nebo pomocí speciálních procedur pro překódování řetězcové reprezentace jedinců tak, aby se stali reprezentanty legálních potencionálních řešení.
Prvním způsobem jsou nepřípustní kandidáti eliminováni pro další běh GA. Tato metoda je použitelná pouze pro případy, kdy není poměr počtu prvků prostoru nepřípustných řešení a poměr počtu prvků prostoru všech řešení příliš velký.
Další možností je přizpůsobit reprezentaci i rekombinační operátory konkrétnímu typu úlohy tak, aby se minimalizovala šance tvorby nelegálních jedinců.
V důsledku příliš rychlého eliminování horších individuí se může stát populace velmi homogenní, takže rekombinační operátory nejsou schopny zachovat diverzitu zkoumání prohledávacího prostoru. Důsledkem bývá uváznutí v lokálním optimu. Proto je potřeba věnovat pozornost prevenci předčasné konvergence (uváznutí v lokálním optimu): vhodnému způsobu selekce, křížení atd.
Výsledky výzkumu použití GA pro řešení Úlohy obchodního cestujícího (TSP) [5,7] budou přínosné i pro řešení problému zaoblení DMT. Jedná se o podobný typ úlohy z hlediska omezení prostoru přípustných řešení (velký poměr počtu nepřípustných řešení a možných řešení) i z hlediska potřeby zachovávání nadějných posloupností (cest) v reprezentačních řetězcích. Ovšem problém zaoblování DMT je komplikovanější z hlediska reprezentace jedinců. Je potřeba hledat posloupnosti vektorů reálných čísel, na rozdíl od hledání posloupností přirozených čísel v TSP.
Existuje několik způsobů reprezentace jedinců v TSP. Ordinální reprezentace umožňující klasické jednobodové křížení se ukázala jako neadekvátní pro tento typ úloh. Přirozená reprezentace cesty je asi nejjednodušší a nejúspěšnější reprezentace pro TSP. Cestu tvoří seznam měst, kudy daná cesta vede, v odpovídajícím pořadí.
Nejznámější operátory křížení navržené pro tuto reprezentaci jsou:
Nejúspěšnějším pro TSP se jeví operátor ERX.
Možnosti mutace pro TSP jsou následující: zamíchání, vložení, inverze, přesun úseku [5,7].
Mým cílem je vyřešit problém zaoblování plátového digitálního modelu terénu. Řešit ho budu použitím genetických algoritmů. Konkrétně: sestavím genetický algoritmus, který bude hledat optimální napojení plátů modelu terénního reliéfu. Pomocí experimentů tento algoritmus nastavím tak, aby pracoval efektivně a byl přínosem při řešení problému zaoblování plátového digitálního modelu terénu.
Plátový, rastrový a trojúhelníkový model terénního reliéfu jsou tři základní typy digitálních modelů terénu. Jak vyplývá z výše uvedeného, nejlepší vypovídací schopnost má plátový model. Jedním z mnoha problému vytváření plátového modelu terénu je zaoblování na sebe navazujících elementárních plátů aproximujících terénní plochu [1,2,3,4,8]. Nejčastěji jsou elementární plošky realizovány jako kvadratické beziérovy pláty - tzv. Coonsovy plochy.
Coonsova plocha je plocha kvadratická, tedy plocha, kterou lze vyjádřit implicitní rovnicí:
R1: z = ax2 + by2 + cxy + dx + ey + g
Měla by splňovat následující dvě podmínky:
- plocha prochází všemi krajními body plátu.
- na rozhraní dvou plátů je spojitá alespoň první derivace terénu. Přesněji řečeno, funkce jedné proměnné ?(t), která vznikne jako funkce nadmořská výška podél libovolné spojité trajektorie přecházející z jednoho plátu na druhý, má spojitou první derivaci.
Každý plát prochází danými krajními body. Pro každý plát hledáme šest koeficientů jeho implicitní rovnice tak, aby procházel danými body a aby hladce navazoval na okolní pláty.
Po dosazení krajních bodů plátu do rovnice R1 popsaném v první kapitole, dostaneme soustavu (tří, čtyř) rovnic o šesti proměnných. Z těchto rovnic vyjádříme některé parametry.
Nevyjádřené parametry budeme generovat tak, abychom po dopočítání zbylých (vyjádřených) parametrů dospěli k minimům funkce h(). Takhle vygenerujeme velké množství plátových modelů a z nich pak budeme vybírat na základě nějakých kritérií jeden model.
GA, které chci použít pro hledání vhodného zaoblení modelu terénu, generují množiny možných řešení problému (generace) tak, že další generace řešení vylepšují. K tomu požívají tzv. křížení vybraných prvků předchozí generace. Řešení je nutné prezentovat pomocí tzv. řetězců, které lze křížit, příp. mutovat. Generování množin řešení je nutné zastavit ve vhodném okamžiku, když už nedochází k podstatným zlepšením. Na zastavení GA se používá nějaké zastavovací pravidlo.
Sestavení vhodného GA znamená:
Dále budeme pomocí experimentů hledat takové pravděpodobnosti křížení a mutace, aby docházelo k efektivnímu zlepšování v dalších generacích. Potom bude nutné provést velké množství experimentů pro různé typy terénních reliéfů. Podle nich bude přestavován a dolaďován celý GA včetně výše zmíněných parametrů. Vše by mělo vést k nalezení univerzálního GA pro dostatečně efektivní zaoblování digitálního modelu terénu. Tzn. dostatečně rychlé vytvoření dostatečně zaobleného modelu terénu.
1. vygeneruj první generaci - tzn. prakticky všechny rovnice všech plátů modelu daného terénu, a to PopSize krát.
2. urči fitness aktuální populace (generace) - tzn. určit fitnessy pro všechny jedince
3. vyber nadějné jedince
4. křiž vybrané jedince
5. výsledek promítni do další populace - tzn. určit kolik procent jedinců v populaci bude vybraných, kolik vykřížených atd.
6. vyber jedince pro mutaci
7. zmutuj vybrané jedince
8. vyhodnoť zastavovací pravidlo
9. pokud neplatí podmínka pro zastavení, jdi na 2.