Prírodou inšpirované algoritmy

Farbenie grafov

Podkapitoly:

Applet

Graf G = (V,H) nazveme k-zafarbiteľným, ak jeho vrcholy možno zafarbiť k farbami tak, aby žiadne dva susedné vrcholy neboli zafarbené rovnakou farbou. Zafarbenie, ktoré žiadnym dvom susedným vrcholom nepriraďuje tú istú farbu nazveme prípustným zafarbením. Chromatické číslo grafu je najmenšie prirodzené číslo k také, že graf G je k - zafarbiteľný.

Problém zafarbiť graf s minimálnym počtom farieb je NP-tažký. Vo väčšine úloh tohto typu je množina možných kombinácií veľmi veľká. V teórii výpočtov patria niektoré tieto problémy to triedy tzv. NP-úplných úloh.

Na riešenie je mozne použit dva postupy :

• Nepriamu reprezentáciu
• Priamu reprezentáciu

Nepriama reprezentácia

Problémom, ktorý treba riešiť, je najmä problém reprezentácie genotypu jedinca, t.j. reprezentácia postupnosti vrcholov v takom poradí, v akom sa majú vyfarbiť vrcholy grafu. Čiže poradie vyfarbovania vrcholov je uvedené v genotype jedinca. Vo fenotype jedinca je uschovaná informácia, aká farba pripadla konkrétnemu vrcholu a na poslednom mieste je uvedená vhodnosť, čo v našom prípade znamená počet nevyfarbených vrcholov grafu. Z uvedeného vyplýva, že cieľom je nájsť jedinca s vhodnosťou veľkosti 0, u ktorého teda v grafe nezostane nevyfarbený vrchol.

Po selekcii nastáva kríženie populácie. To je realizované krížením typu OX. Vygenerujú sa dva deliace body, prvá časť sa prenesie z prvého rodiča a z druhého rodiča sa vyškrtnú všetky použité miesta a doplní sa genetický materiál potomka v poradí v akom zostali nevyškrtnuté miesta v druhom rodičovi . Tu má užívateľ sám možnosť určiť pravdepodobnosť kríženia. Príklad daného kríženia môžete vidieť na nasledujcom obrázku

OX kríženie

Priama reprezentácia

Táto reprezentácia je odlišná od predchádzajúcej, ale veľká časť sa bude opakovať. Genotyp a fenotyp sa tu rovnajú a obsahujú záznamy o jednotlivých vrcholoch akou farbou sme ich na začiatku náhodne vyfarbili. Pri každom jedincovi sa prechádzajú všetky hrany grafu a zisťuje sa, či daná hrana nespája vrcholy s rovnakou farbou. Ak je tomu tak vhodnosť sa inkrementuje o jednotku. Čiže jedinec, ktorý našiel riešenie ma vhodnosť rovnú nule.

Štart Appletu