Křížení

Křížení je reprodukční operátor, který vlastně simuluje náhodnou výměnu informací obsažených v rodičích při vytváření nového potomka. Jeho působením by se měly vyvíjet lepší chromozomy (jedinci složení z lepších stavebních bloků).

Křížení může být jednobodové, dvoubodové nebo vícebodové. Body, ve kterých dochází ke křížení, se volí náhodně. Volbou n bodů křížení se oba rodiče rozdělí na n+1 částí. Vlastní křížení probíhá tak, že do prvního potomka se zkopírují např. liché části z prvního rodiče a sudé z druhého. U druhého potomka je tomu opačně. Četnost křížení se volí nastavením pravděpodobnosti křížení, což je jeden ze základních parametrů GA (typicky se volí přibližně 0.75). Zvětšením pravděpodobnosti křížení se ale zvětší nejen rekombinace stavebních bloků, ale také pravděpodobnost, že budou zničeni i dobří jedinci. Optimální hodnota závisí na konkrétním řešeném problému a stanovuje se empiricky.

Mezi další varianty křížení patří rovnoměrné a informované křížení. Rovnoměrné křížení je vlastně n-bodové křížení, u něhož se nevolí n bodů, ale u každého bitu se náhodně rozhoduje s pravděpodobností 0.5, do kterého z potomků bude patřit. Bylo pozorováno, že pomocí křížení se dosahuje rychlejšího prohledávání než pomocí mutace (viz.dále) při použití ztrátových funkcí, které berou v úvahu nelineární vztahy mezi jednotlivými bity řetězců. Pokud je pravděpodobnost, že ke křížení dojde za určitým bitem, závislá na pozici v řetězci, říkáme, že operátor křížení má polohové zaměření. Pokud rozdělení počtu bitů prohozených operátorem křížení není rovnoměrné, říkáme, že křížení má distribuční zaměření. Jednobodové křížení má maximální polohové a minimální distribuční zaměření, zatímco u rovnoměrného křížení je to naopak. Jedno a dvoubodové křížení zachovávají velké množství stavebních bloků, ale v homogenní populaci generují málo odlišné jednotlivce. Rovnoměrné křížení naproti tomu prohazuje bity nezávisle na jejich pozici a zachovává tak pouze menší množství stavebních bloků. Proto se doporučuje používat u menších populací, kde zaručuje prohledání větší oblasti stavového prostoru. Ve velkých populacích, kde se rozmanitost chromozomů (jejich umístění ve stavovém prostoru) zajišťuje spíše jejich počtem, je vhodnější dvoubodové křížení.