<jupyter_start><jupyter_text>Jako poslední pokus vyřešit logickou hru Futoshiki jsem zkusil použít genetické algoritmy. Ty by měly umožňovat řešit optimalizační úlohy, takže třeba zaberou i v tomto případě.Pokud vás zajímá pouze výsledek mého snažení, tak musím dopředu avizovat, že jsem se k nějakým dobrým výsledkům nedopracoval. Jednotlivá řešení konvergovala, ale obtížně jsem se dostával k řešení, které by bylo úplně bez chyb.Pro vás ostatní, uvádím postup pro jedno zadání hry s velikostí 5x5.Nechtěl jsem psát vše úplně od počátku, proto jsem vyzkoušel použít existující knihovnu [PyGAD](https://pygad.readthedocs.io/en/latest/). A bylo to také ze studijních důvodů. Ono se vždy lépe zkouší nový software na nějakém reálném problému, než jen opakovat příklady z tutoriálu.  Zdroj testovacích datTestovací data mám již připravená ve třídě `SampleSource`, takže stačí je jen použít stejně jako v předchozím příspěvku.<jupyter_code>from Futoshiki_DataSource import SampleSource

samples = SampleSource()

sample_number = 5
print(*samples.data(sample_number), sep='\n')

SIZE = samples.size(sample_number)
grid = samples.grid(sample_number)
constraints = samples.constraints(sample_number)<jupyter_output>0>0 5 0 0

0 2 0 0 0
        ^
0 0 0 0 0

0 0 0 3 0

0 0 0 2<0<jupyter_text>Řešení s využitím PyGAD Reprezentace řešeníPrvní otázka je, jak budu reprezentovat jedno řešení (chromozom). Pro použití v PyGAD je nejvhodnější, pokud je řešení reprezentováno jako jednorozměrné pole celočíselných hodnot. To mně docela vyhovuje, takže budu jedno řešení reprezentovat jako spojení jednotlivých řádků řešení hry za sebou. Každé políčko (gen) může nabývat hodnot 1..N.<jupyter_code>import math
import random
import pygad
import numpy as np<jupyter_output><empty_output><jupyter_text>Výpočet kvality řešeníJedním z klíčových bodů GA je stanovení "kvality" jednoho řešení.V mém případě je lepší to řešení, které má méně konfliktů v požadovaných omezeních. Těmi omezeními se rozumí unikátnost v řádku a slouci, a také splnění explicitně požadovaných relací v zadání.Následující metoda `fitness` tedy počítá, kolik konfliktů má zadané řešení.* Nejdříve si převedu vektor zpět do matice (to aby se mně lépe pracovalo s řádky, sloupci a jednotlivými políčky).* Pro každý řádek zjistím rozdíl mezi velikosti řádku a velikostí množiny hodnot v řádku. Pokud mám v řádku opakovaně stejné číslo, pak je výsledek nenulový.* Stejně tak pro každý sloupec zjistím rozdíl velikosti sloupce a velikostí množiny hodnot ve sloupci.* Nakonec projdu všechna požadovaná omezení a ověřuji, jestli jsou platná. Pokud ne, opět přispívají do výsledné hodnoty kvality.* Výsledek je pak součet všech zjištěných konfliků, převedený do záporné hodnoty (to proto, aby mělo horší řešení menší hodnotu fitness).<jupyter_code>def fitness(solution, index):
    res = 0
    size = math.isqrt(len(solution))
    grid = np.reshape(solution, (size, size))
    res += sum((size - len(set(row)) for row in grid))
    res += sum((size - len(set(col)) for col in grid.T))
    for low, high in constraints:
        res += int(not (grid[low] < grid[high]))
    return - res<jupyter_output><empty_output><jupyter_text>Rozsahy hodnot pro jednotlivé genyDříve jsem v reprezentaci řešení napsal, že každý gen může nabývat hodnot z rozmezí 1..N. Ono to ale není tak úplně pravda.V případě, že mám v zadání specifikovánu hodnotu konkrétního políčka (genu), pak chci, aby gen nabýval pouze této hodnoty.Navíc mohu při posouzení povolených hodnot pro jednotlivé geny vzít v úvahu také explcitně stanovená omezení a omezení unikátnosti v řádku a sloupci.Například, pokud mám pro nějaké políčko stanovenu hodnotu v zadání, pak pro všechna ostatní políčka v řádku a sloupci platí, že tuto hodnotu obsahovat nesmí.Nebo pokud je explicitně stanovena relace mezi dvěma políčky, pak množina povolených hodnot pro větší políčko nesmí obsahovat minimum hodnot menšího políčka (pokud by taková hodnota byla povolena, pak by nebylo možné omezení splnit).A navíc, mezi relacemi je tranzitivní vztah, kdy změnou rozsahu hodnot pro jeden gen mohou být ovlivněny rozsahy hodnot jiných genů.Takhle tedy vypadá implementace metody `gene_spaces`, která mně počítá množiny povolených hodnot pro jednotlivé geny:<jupyter_code>def gene_spaces(grid, constraints):
    size = len(grid)
    spaces = [[{val} if val else set(range(1, size + 1)) for val in row] for row in grid]

    def flatten_size(item):
        return len(item) if isinstance(item, set) else sum((flatten_size(s) for s in item))

    curr_size = flatten_size(spaces)
    while True:
        # unique value constraint for rows and columns
        for x in range(size):
            for y in range(size):
                sp = spaces[x][y]
                if len(sp) == 1:
                    for i in range(size):
                        if i != x:
                            spaces[i][y] -= sp
                        if i != y:
                            spaces[x][i] -= sp

        # constraints defined by assignment
        for low, high in constraints:
            l0, l1, h0, h1 = *low, *high

            min_value = min(spaces[l0][l1])
            spaces[h0][h1] = {v for v in spaces[h0][h1] if v > min_value}

            max_value = max(spaces[h0][h1])
            spaces[l0][l1] = {v for v in spaces[l0][l1] if v < max_value}

        new_size = flatten_size(spaces)
        if new_size >= curr_size:
            break
        curr_size = new_size

    return spaces


def gene_space_prep(space):
    return [list(space[i][j]) for i in range(len(space)) for j in range(len(space))]
        
gene_spaces(grid, constraints)<jupyter_output><empty_output><jupyter_text>Postup je zhruba tento:* pro každý hledaný gen definuji množinu povolených hodnot v rozsahu 1..N, geny se zadanou hodnotou mají množinu jednoprvkovou.* dále opakuji cyklus, dokud se mně nějak mění množiny hodnot pro všechny geny* v každém cyklu pak:    * pokud je množina povolených hodnot políčka jednoprvková, odečtu tuto hodnotu od všech ostatních množin v řádku a ve sloupci    * procházím všechna omezení a z množiny povolených hodnot většího políčka odečtu minimum povolených hodnot políčka menšího    * obdobně tak z množiny povolených hodnot menšího políčka odečtu maximum políčka většíhoVýsledek si můžete ověřit výše.  Spuštění řešeníA teď již se můžu dostat k vlastnímu spuštění řešení.Nejdříve potřebuji instanci třídy `GA`, ve které stanovuji parametry chování algoritmu.V tomto konkrétním případě jsem nastavoval tyto parametry (možnosti nastavení algoritmu jsou daleko širší, pro zájemce odkazuji na [dokumentaci PyGAD](https://pygad.readthedocs.io/en/latest/README_pygad_ReadTheDocs.htmlpygad-ga-class)):`num_generations` - maximální počet generací`num_parents_mating` - celový počet řešení z jedné generace, které budou vybrány jako rodiče pro generaci následující`fitness_func` - funkce pro výpočet kvality jednoho řešení`sol_per_pop` - počet řešení v populaci`num_genes` - počet genů, které tvoří jedno řešení `gene_type` - typ hodnot, kterých nabývají geny`gene_space` - rozsahy povolených hodnot pro jednotlivé geny`parent_selection_type` - algoritmus výběru rodičů pro následující generaci`crossover_type` - způsob křížení rodičů a vytvoření jejich potomků`mutation_type` - metoda výběru genů pro mutaci`mutation_probability` - pravděpodobnost mutace jednoho genu`stop_criteria` - kritérium, při jehož splnění se algoritmus zastaví (najdu řešení s kvalitou rovnou 0)Dále již postačuje spustit řešení zavoláním metody `run`.<jupyter_code>random.seed(0)
np.random.seed(0)

ga = pygad.GA(num_generations=10000,
              num_parents_mating=16,
              fitness_func=fitness,
              sol_per_pop=20,
              num_genes=SIZE**2,
              gene_type=int,
              gene_space=gene_space_prep(gene_spaces(grid, constraints)),
              parent_selection_type='sss',
              crossover_type='single_point',
              mutation_type='random',
              mutation_probability=0.01,
              stop_criteria='reach_0',
              )
ga.run()

ga.plot_fitness()

result = np.where(ga.last_generation_fitness == 0)
if len(result[0]) > 0:
    s = samples.size(sample_number)
    print(f"SUCCESS: ({ga.generations_completed})\n{ga.population[result[0][0]].reshape((s, s))}")
else:
    print("BEST FITNESS:", ga.last_generation_fitness.max())<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06910520671988563, 'fraction_numerical': 0.00869772429405457, 'mean_word_length': 3.946375957572186, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 24, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '607300', 'license': 'Apache-2.0', 'n_tokens_mistral': 3392, 'n_tokens_neox': 3422, 'n_words': 944, 'path': 'Futoshiki-ga.ipynb', 'repo_name': 'jraska1/py-notebooks', 'size': '8393'}