Založ si blog

Sudoku a genetické algoritmy (2)

V prvej časti som načrtol ideu, ako by sa dalo naprogramovať riešenie sudoku pomocou genetického algoritmu. Medzičasom som to  naprogramoval. Kto má záujem, môžem mu poslať zdrojový kód.

Program je naprogramovaný ako PHP skript, preto beží pomerne pomaly, pokiaľ by ho niekto vedel transformovať do skompilovaného tvaru, budem veľmi rád. Našiel som na internete niekoľko kompilátorov PHP skriptov, ale žiaden sa mi nepodarilo na mojom notebooku rozchodiť.

Po spustení skriptu sa zobrazí formulár, v ktorom zadáte, aká veľká má byť populácia a koľko generácii má skript generovať. Pokiaľ nájde optimálne riešenie, skript sa ukončí a vypíše riešenie.

Algoritmus

1. Inicializuje sa sudoku Adam v tvare:

123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789

Takéto „riešenie“ má životaschopnosť (fitnes 126), optimálne riešenie má fitness rovné nule.
2. Tento Adam sa pomocou generátora náhodných čísel spermutuje a vytvorí sa n potomkov nultej generácie.

3. Náhodne sa n-20 krát vylosujú otec a matka, ktorí spolu splodia 6 potomkov krížením, pričom sa traja potomkovia vytvoria krížením 1.druhu: prvá časť od 1 po m od otca a druhá časť od m+1 po 81 od mamy a traja potomkovia kížením 2. druhu: náhodným výberom jednotlivých riadkov od otca alebo mamy.

4. Z týchto šiestich potomkov sa vyberie najživotaschopnejší, ostatní súrodenci neprežijú. Ak je životaschopnejší než každé z doteraz vygenerovaných riešení, stane sa riešením jedna a doterajšie riešenia od 1 po 19 sa posunú o jednu pozíciu nahor.

5. Z 30% pravdepodobnosťou dôjde k mutácii preživšieho potomka. Ak je doteraz najlepším riešením, stane sa riešením číslo 1.

6. Vypíšu sa tri najlepšie riešenia aktuálnej generácie. Zelene sú označené políčka, ktoré sú v konflikte s pravidlami riešenia sudoku.

7. Ak nebolo nájdené optimálne riešenie a nedosiahol sa maximálny počet generácií opakuje sa bod 3.

8. Vypíšu sa všetky riešenia poslednej generácie.

 

Táto verzia programu hľadá ľubovoľné riešenie sudoku, čiže akoby bola mriežka sudoku na začiatku úplne prázdna. V ďalšej verzii bude môcť používateľ zadať prvotné pevné polia, tieto budú u všetkých riešení nultej generácie rovnaké a nebudú môcť mutovať. Odhadujem, že úspešnosť riešení sa výrazne zvýši.

Aká je úspešnosť riešení?

Dal som vygenerovať po 5-krát riešenia pre n=50; 100; 200; 400; 800; 1600 a 3000 pre 200 generácií. S rastúcou veľkosťou lineárne rastie doba generovania jednotlivých generácií.

Výsledky sú nasledovné:

Veľkosť populácie Priemerné minimum Minimum Vyriešené V generácii
 50  20,2  16  Nie
 100  6,2  4  Nie
 200  2,8  0  1x  74
 400  1,8  0  1x  59
 800  1,2  0  2x  41; 167
 1600  0,4  0  4x  45; 46; 53; 63
 3000 0 0 5x 50; 51; 52; 53; 54

 

Ako vidno, s rastúcou veľkosťou populácie sa zlepšuje priemerné minimálne fitnes. S počtom generácií sa fitnes síce tiež zlepšuje, spočiatku sa zlepšuje takmer po každej generácii, po dosiahnutí fitnes okolo 5 sa pravdepodobnosť nájdenia lepšieho riešenia prudko znižuje.

Na hostingu, kam som skript umiestnil je maximálny čas vykonávania skriptu 30 sekúnd, pre veľké populácie a veľa generácii sa skript po 30 sekundách automaticky ukončí, preto by to chcelo ho skompilovať alebo to urobiť to interaktívne, po každej generácii používateľ spustí generovanie ďalšej generácie, čím by sa obmedzenie na čas obišlo, prípadne by do interaktívneho módu skript prechádzal tesne pred uplynutím časového limitu.

Aké parametre by mohli pribudnúť?

  • Voľba spôsobu kríženia.
  • Pravdepodobnosť mutácie
  • Počet uchovávaných najlepších riešení
  • druh sudoku 3×3, 4×4, 5×5, …

Pokiaľ máte záujem o zaslanie skriptu, napíšte mi na adresu: otm@bridgekosice.sk

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 [...]

Fabrika Kia - Teplička nad Váhom

Vláda chce zaplátať migrantmi zo Strednej Ázie dieru na trhu práce. Ako útok v Moskve zmení tento zámer?

29.03.2024 08:00

Po tom, čo skupina teroristov pôvodom z Tadžikistanu zabila v Moskve 139 ľudí, sa slovenské zložky rozhodli posilniť bezpečnostné opatrenia

Rusko, Ukrajina

ONLINE: Masívny útok opäť cielil na ukrajinskú energetiku. Poliaci poslali do vzduchu lietadlá

29.03.2024 07:45, aktualizované: 08:14

Rusko masívne útočí na ukrajinskú energetiku, ktorá je v zložitej situácii. Keď Rusi spúšťajú útoky, Poliaci posielajú do vzduchu lietadlá.

Joe Biden, Barack Obama

Štyria prezidenti v New Yorku. Biden s Obamom a Clintonom zozbierali 25 miliónov USD, Trump bol na pohrebe policajta

29.03.2024 07:11

Americká prezidentská kampaň vo štvrtok večer dostala do New Yorku štyroch amerických prezidentov.

Nehoda, ilustračná, sklo

Autobus s desiatkami cestujúcich sa prevrátil na nemeckej diaľnici

29.03.2024 06:38

Autobus s približne 60 cestujúcimi havaroval vo štvrtok večer na diaľnici v západnom Nemecku, zranenia utrpelo vyše 20 ľudí, informovala DPA.

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ť: 473878x
Priemerná čítanosť článkov: 2962x

Autor blogu

Kategórie