Založ si blog

Sudoku a genetické algoritmy

Čo je sudoku, takmer všetci vedia, väčšina nevie, čo je genetický algoritmus alebo genetické programovanie.

Genetický algoritmus je nedeterministická metóda riešenia problému, vychádzajúca z princípov Darwinovej evolučnej teórie. 

Každé riešenie úlohy (aj „zlé“) sa nazýva chromozóm, je tvorené binárnym reťazcom danej dĺžky, ktorá je rovnaká pre všetky chromozómy populácie. Populácia je konečná množina chomozómov. Základná populácia resp. nultá generácia populácie je začiatočný stav riešenia. Vývoj k optimálnemu riešeniu prebieha prirodzeným vývojom populácií. Nultá generácia je vygenerovaná náhodne, vygenerované chromozómy, musia byť riešením problému.

Proces reprodukcie:

  • Výber chromozómov na kríženie či mutáciu (pseudonáhodný výber podľa pravdepodobnosti úmernej jeho fitness)
  • Kríženie chromozómov (výmena podreťazcov, kde môže prebiehať kríženie jednobodovo, či viacbodovo)
  • Mutácia, náhodne zmutujú niektoré gény, mutuje sa s malou pravdepodobnosťou, aby zostala zachovaná genetická informácia

Náhodnosť sa zaisťuje pomocou generovania pseudonáhodných čísel.

Prečo som sa rozhodol pre genetický algoritmus?

Naprogramovať riešenie sudoku klasickým programovaním je „triviálna záležitosť“ a pre mňa ako programátora nie je žiadnou výzvou (?). Sudoku predstavuje NP-úplný problém a doteraz sa nepodarilo vyčísliť, koľko existuje riešení pre sudoku 16×16 , o vyšších dimenziách nehovoriac. Pre klasické sudoku 9×9 existuje  6 670 903 752 021 072 936 960 riešení, po odrátaní symetrických pozícií je ich „iba“ 5 472 730 538. Napriek tomu, že riešení je takéto ohromné množstvo, pravdepodobnosť toho, že náhodne rozhodíme 81 číslic od 1 do 9, pričom každá číslica sa vyskytne presne 9 krát a rozloženie číslic bude zodpovedať pravidlám sudoku je mizivá, keďže možných rozmiestnení číslic je odhadom 3.10 × 1037.

Genetický pohľad na mriežku sudoku

Hoci je mriežka dvojrozmerná, môžeme na ňu pozerať tak, že je to 81 lineárne usporiadaných buniek od 1 do 81, pričom bunky v prvom riadku sú 1 až 9, v druhom 10..18, až v poslednom 73..81.

Vytvorme triviálneho prarodiča v tvare 123456789 123456789 … 123456789, tohto prarodiča náhodne spermutujme a vytvorme nultú populáciu pozostávajúcu napríklad zo 100 exemplárov (v definitívnom programe si používateľ bude môcť zvoliť veľkosť populácie. Hoci „sedliacky“ rozum navráva, že čím je populácia väčšia, tým skôr bude spieť k optimálnemu riešeniu, po mojich prvotných experimentoch sa zdá, že to tak nie je, 100 členná populácia dosahovala oveľa lepšiu hodnotiacu funkciu než 200 členná, keď som veľkosť populácie zmenšil na 50, tak zase na tom bola 100 členná populácia oveľa lepšie).

Ako budeme exempláre navzájom krížiť?

V aktuálnej populácii majme 100 (poprípade n) potencionálnych rodičov. Pseudonáhodne 1000 krát (10 x n) vylosujme „otca“ a „matku“ (pričom otec nemôže byť zároveň matkou) a losujme, ktorú časť genetickej informácie získa potomok od otca a ktorú od matky (pre jednoduchosť, nech sú exempláre bezpohlavné, potom môžeme hovoriť o Rodičovi1 a Rodičovi2. Týchto 1000 potomkov ohodnoťme funkciou životaschopnosti a pre splodenie ďalšej generácie zachovajme 100 najživotaschopnejších – vždy len 100 potomkov dosiahne pohlavnú zrelosť a reprodukčnú schopnosť. Aby sa zachovala kvalitná genetická informácia, do ďalšieho kola reprodukcie zachovajme 20 exemplárov s doteraz najlepšou životaschopnosťou. Potom  ďalšiu generáciu bude plodiť 20 exemplárov z predchádzajúcej populácie a 80 z aktuálnej (v konečnom programe si používateľ bude môcť zvoliť percento zachovania rodičov).

Aká časť genetickej informácie sa bude dediť?

Môžeme dediť jednotlivé bunky, pre každú bunku budeme losovať, či sa zdedí informácia od otca alebo matky, alebo sa budú dediť celé jednotlivé riadky, stĺpce či štvorce. Pri dedení jednotlivých buniek sa genetická informácia zachováva, ale spätne po niekoľkých generáciách nikto nezistí od ktorého predka informácia pochádza. Druhou možnosťou je, že budeme dediť 9 členné úseky. Prvotne ťažko odhadnúť, ktorý spôsob dedenia bude efektívnejší. Preto otestujeme jednobodové i 9 bodové dedenie. Intuícia mi nahovára, že elementárnou jednotkou dedičnej infromácie by v sudoku 9×9 mala byť trojica buniek, v sudoku 16×16 štvorica, atď. Otestujeme preto i takýto prístup. Nultá populácia bude spoločná pre všetky tri metódy dedenia a otestujeme, ktorá metóda vedie po m generáciách k lepšej hodnotiacej funkcii.

Hodnotiaca funkcia

Hodnotiaca funkcia by mala merať o koľko sa potomok líši od optimálneho riešenia. Optimálne riešenie je dané pravidlami sudoku – v každom riadku, stĺpci a štvorci je práve jedna číslica daného druhu. V klasickom sudoku 9×9 sú to číslice 1 až 9. V sudoku 16×16 navyše pribúdajú číslice 0, A, B, C, D, E, F. Ak riadok, stĺpec alebo štvorec spĺňa pravidlá sudoku, tak ho hodnotiaca fukcia ohodnotí nulou. Ak je nejaká číslica v riadku, stĺpci alebo štvorci 2x či viackrát, každý výskyt číslice navyše prispieva hodnotou jedna. Nevýskyt číslice hodnotiť nebudeme, keďže číslica navyše spôsobuje nevýskyt inej číslice. Hodnotiaca funkcia pozostáva z troch hodnotení:

  • horizontálne – hodnotenie po riadkoch
  • vertikálne – hodnotenie po stĺpcoch
  • štvorcové – hodnotenie po štvorcoch

Pokiaľ umožníme voľné dedenie, malo by pribudnúť globálne hodnotenie z hľadiska odchýlky celkového počtu jednotlivých číslic od ideálu. V sudoku 9×9 by sa každá číslica mala vyskytnúť práve 9 krát. Keďže odchýlka od tohto ideálu spôsobuje nemožnosť nájdenia optimálneho riešenia, prohibujme ju vyššou váhou napríklad váhou 3. Druhá možnosť je obmedziť jeden stupeň voľnosti napríklad tak, že riadky musia vždy spĺňať podmienku jedinečnosti výskytu každej cifry. Dosiahneme to úpravou generovania nultej populácie a dedením celých riadkov, stĺpcov alebo štvorcov od jednotlivých rodičov.

Musí popri dedení a krížení nastúpiť mutácia?

V prvotnej populácii by musela nastať veľmi nepravdepodobná zhoda okolností, aby už prvotná genetická informácia potencionálne obsahovala optimálne riešenie problému. Ak budeme dediť celé riadky a populácia bude mať veľkosť 100, tak 100 prarodičov bude obsahovať 900 riadkov. Všetkých možných riadkov však je 9! (9 faktoriál čo predstavuje 362880 možných riadkov).  Že sa medzi týmito prvotne vygenerovanými riadkami bude vyskytovať konkrétny riadok na konkrétnom mieste, ktorý je riešením problému má pravdepodobnosť 900/9! a že tam bude všetkých 9 má pravdepodobnosť (900/9!)9. Ak hľadáme ľubovoľné riešenie, tak je pravdepodobnosť omnoho vyššia, napriek tomu je však stále veľmi malá.

Pôvodná podoba článku bola uverejnená na stránke Košického bridžového klubu v roku 2013.

Touto témou sa už predo mnou zaoberali aj iní. Tento článok vznikol nezávisle od prác, ktoré možno vyhľadať na internete, napr.:

 

Literatúra:

Každému udeľujem právo voľne použiť informácie z tohoto článku, s podmienkou uvedenia zdrojov.

 

Diplomovka

15.11.2020

Obhájil som diplomovku, ani neviem ako. Sám som si ju nenapísal, predsa nie som pako. Študentky a študentíci, načo študujete, v parlamente vedomosti nepotrebujete. Predseda nám vždy ukáže, jak hlasovať treba, sám volič si za to môže, že nemá na chleba. My musíme nosiť rúška, Igor však nemusí, že sme preňho iba svoloč, zverejní statusy, o ponožkách, o [...]

Prechádzka od 1: 00 do 5: 00

14.11.2020

Poďme sa priatelia prechádzať od jednej do piatej poďme to spolu spočítať tej vláde prekliatej. Boli sme sa spolu testovať, postáli si v rade, boli sa spolu nakaziť, nech covid je všade. Poďme si spoločne vypočuť tlačovku Matelka, keď je tam tento nedouk, vypína sa telka. Spoločne sme si to skazili, pravdu má premiér, veď sme ho na jar zvolili, takže je všetko fér.

Plošné testovanie a žonglovanie s číslami (2)

10.11.2020

V predchádzajúcom článku som z matematického pohľadu analyzoval prvé kolo plošného testovania. Po druhom kole k tomu v podstate nemožno nič nové zmysluplného dodať, iba možno konštatovať Pat a Mat (Naď a Matovič) naďalej žonglujú s číslami, ako sa im zachce. Bez ohľadu, aké percento pozitívnych by v druhom kole vyšlo, bol by to dôkaz toho, že plošné testovanie Ag [...]

žena, rúško, ochrana

Otvárajú sa ďalšie obchody, rúška už nemusia byť všade

19.04.2021 06:00, aktualizované: 07:25

Slovensko zmierňuje reštriktívne opatrenia proti šíreniu koronavírusu. Otvárajú sa ďalšie obchody, za istých podmienok možno ísť von bez rúška.

Johnson & Johnson

ONLINE: V USA zaočkovali už polovicu dospelých

19.04.2021 06:00, aktualizované: 07:47

V USA na 100 obyvateľov použili 61,6 dávky vakcíny, na Slovensku 23,57, v EÚ 24,9, v Maďarsku 48,02.

ČR Rusko ambasáda zamestnanci vyhostenie

Ľudia, čo útočili v Česku, sú hrdlorezi, tvrdí expert na tajné služby

19.04.2021 06:00

Jednotka ruskej vojenskej rozviedky GRU, ktorá sa v roku 2014 mala podieľať na sabotáži v muničnom sklade v českých Vrběticiach, stále existuje a funguje dobre.

navaľnyj

EÚ vyzvala na okamžité prepustenie Navaľného. USA hrozia následkami, ak zomrie

18.04.2021 22:00

Zdravotný stav Alexeja Navaľného sa rýchlo zhoršuje. Vo väzení v ruskej kolónii už viac ako dva týždne drží protestnú hladovku.

Tibor Menyhért

Tak dlho sa hádali na maličkostiach, až z toho bola veličkosť

Štatistiky blogu

Počet článkov: 160
Celková čítanosť: 364868x
Priemerná čítanosť článkov: 2280x

Autor blogu

Kategórie