J'ai essayé de laisser optuna résoudre le nombre

introduction

Motivation

D'une manière ou d'une autre, je l'ai trouvé.

Si vous voulez résoudre des mathématiques sans puissance humaine, il est bien connu que vous pouvez le résoudre en utilisant la programmation linéaire ou le réseau de Hopfield. Cependant, je pensais qu'il serait possible de le résoudre en poussant le nombre d'essais sans connaître les règles de Sugoku, alors j'ai en fait essayé.

Qu'est-ce que le Sudoku

C'est une sorte de jeu de puzzle. Voir wikipedia pour plus de détails. Allemagne

Qu'est-ce que l'oputuna

optuna Une bibliothèque python pour l'optimisation des hyperparamètres développée par Preferred Networks. L'algorithme de recherche par hyperparamètres utilise TPE, qui est identique à HyperOpt.

En un mot, en omettant des explications détaillées, même si la cible d'optimisation est une boîte noire, cela optimisera la fonction objectif de manière agréable.

Méthode

Comme mentionné ci-dessus, nous utiliserons optuna. Par conséquent, la fonction objectif est définie de manière à ce que la valeur diminue à mesure que la réponse s'approche de la bonne réponse.

Fonction objective

La fonction objectif décide de compter le nombre de violations de règle. Ici, moins de violations sont synonymes de se rapprocher de la bonne réponse. Je ne connais pas explicitement la bonne réponse, mais comme je minimise la valeur de la fonction objectif, j'atteins finalement 0 violation et la bonne réponse.

def evaluate(answer):
    #Il viole la boucle de l'allemand et renvoie le nombre. Si la réponse est correcte, l'évaluation sera 0
    #La réponse est un tableau bidimensionnel 9x9 avec des nombres de 1 à 9 dans chaque élément
    tmp = np.reshape(answer, [3, 3, 3, 3])
    loss = np.sum((
        #Nombre de violations dans chaque colonne
        np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=0))) for i in range(9)]),
        #Nombre de violations dans chaque ligne
        np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=1))) for i in range(9)]),
        #Nombre de violations par zone 3x3
        np.sum([np.count_nonzero(np.logical_not(np.any(tmp == i, axis=(1, 3)))) for i in range(9)]),
    ))
    return loss

Le nombre de violations ne compte pas le nombre de numéros en double, mais le nombre de numéros qui n'apparaissent pas.

Si les règles sont respectées, 1-9 apparaîtra une fois pour chaque condition. S'il y a des doublons en raison d'une violation de règle, le nombre d'apparitions de l'un des autres numéros a diminué à 0, alors comptez-le.

Dans le cas de la duplication, il existe différents schémas de 2 à 9 fois, mais si le nombre d'apparitions diminue, il n'y en a que 0, donc je pense qu'il sera plus simple de compter cela.

Appeler optuna, etc. (code entier)

Le problème que je voulais résoudre était codé en dur dans le code source. C'est fondamentalement le même que le code de la documentation optuna.

from itertools import product

import numpy as np
import optuna
import click


"""
Le problème est https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%À partir de l'image d'exemple AC
 -----------------        
|5|3| | |7| | | | |
|-+-+-+-+-+-+-+-+-|
|6| | |1|9|5| | | |
|-+-+-+-+-+-+-+-+-|
| |9|8| | | | |6| |
|-+-+-+-+-+-+-+-+-|
|8| | | |6| | | |3|
|-+-+-+-+-+-+-+-+-|
|4| | |8| |3| | |1|
|-+-+-+-+-+-+-+-+-|
|7| | | |2| | | |6|
|-+-+-+-+-+-+-+-+-|
| |6| | | | |2|8| |
|-+-+-+-+-+-+-+-+-|
| | | |4|1|9| | |5|
|-+-+-+-+-+-+-+-+-|
| | | | |8| | |7|9|
 -----------------        
"""
#La partie avec la valeur à l'avance
preset = {'p00': 5, 'p01': 3, 'p04': 7,
          'p10': 6, 'p13': 1, 'p14': 9, 'p15': 5,
          'p21': 9, 'p22': 8, 'p27': 6,
          'p30': 8, 'p34': 6, 'p38': 3,
          'p40': 4, 'p43': 8, 'p45': 3, 'p48': 1,
          'p50': 7, 'p54': 2, 'p58': 6,
          'p61': 6, 'p66': 2, 'p67': 8,
          'p73': 4, 'p74': 1, 'p75': 9, 'p78': 5,
          'p84': 8, 'p87': 7, 'p88': 9}


def evaluate(answer):
    #Comme ci-dessus
    
    
def objective(trial):
    candidate = (1, 2, 3, 4, 5, 6, 7, 8, 9)
    
    answer = np.empty([9, 9], dtype=np.uint8)
    for i, j in product(range(9), repeat=2):
        key = 'p{}{}'.format(i, j)
        if key in preset:
            answer[i, j] = preset[key]
        else:
            answer[i, j] = trial.suggest_categorical(key, candidate)
            
    return evaluate(answer)
    
    
def run(n_trials):
    study_name = 'sudoku'
    study = optuna.create_study(study_name=study_name, storage='sqlite:///sudoku.db', load_if_exists=True)
    study.optimize(objective, n_trials=n_trials)
    
    show_result(study.best_params, study.best_value)
    
    df = study.trials_dataframe()
    df.to_csv('tpe_result.csv')


def show_result(best_params, best_value):
    for i in range(9):
        for j in range(9):
            key = 'p{}{}'.format(i, j)
            if key in preset:
                print('*{:1d}'.format(preset[key]), end='')
            else:
                print('{:2d}'.format(best_params[key]), end='')
        print('')
    print('loss: {}'.format(best_value))
        

@click.command()
@click.option('--n-trials', type=int, default=1000)
def cmd(n_trials):
    run(n_trials)
    
    
def main():
    cmd()
    
    
if __name__ == '__main__':
    main()

Résultat expérimental

Je suis désolé pour ceux qui ont lu jusqu'ici en prévision.

Je n'ai pas pu le résoudre du tout.

Le temps requis pour chaque évaluation est beaucoup plus long que prévu et le nombre d'essais n'est pas suffisant. Le nombre d'essais est de 0 pendant environ 7 secondes et de 200 pendant environ 25 secondes.

Même si nous continuons ainsi, il faudra des centaines de milliers à des millions d’essais pour parvenir à la bonne réponse, je pense donc qu’il est impossible d’y parvenir en réalité.

Enfin, pour le moment, la sortie au bout de 200 fois est affichée.

*5*3 5 5*7 2 6 1 2
*6 7 8*1*9*5 7 3 5
 4*9*8 6 3 7 8*6 4
*8 1 4 7*6 9 7 6*3
*4 3 9*8 5*3 2 7*1
*7 8 9 3*2 1 5 4*6
 3*6 1 6 7 9*2*8 7
 5 7 3*4*1*9 8 1*5
 4 7 6 2*8 4 3*7*9
loss: 73.0

Les nombres avec * sur le côté gauche sont les nombres du début comme indices de réponse.

Résumé

Dougoku ne peut pas être résolu avec optuna (algorithme TPE). J'avais l'intention de pousser par le nombre d'essais, mais le temps de calcul était beaucoup plus long que prévu et je ne pouvais pas pousser.

optuna (algorithme TPE) prend plus de temps à échantillonner à mesure que le nombre d'essais augmente.

Plans futurs

La cause de cet échec était le long temps de calcul de l'algorithme TPE, donc je pense que ce problème peut être résolu en utilisant un autre algorithme. Puisque l'algorithme TPE ne considère pas la distribution conditionnelle en premier lieu, c'est un algorithme plutôt inadapté pour résoudre les mathématiques.

La prochaine fois, j'aimerais essayer un algorithme qui échantillonne à partir d'une distribution conditionnelle. Par conséquent, il est nécessaire de comprendre les règles de Sugoku avant de résoudre. Cela aurait été une tentative imprudente pour parvenir à la bonne réponse sans connaître les règles de l'Allemagne comme cette fois.

Le calendrier est complètement indécis. Je pense que l'algorithme sera un système de recuit simulé, mais l'heure d'affichage est indécise car je vais l'étudier à partir de maintenant.

Recommended Posts

J'ai essayé de laisser optuna résoudre le nombre
Je veux résoudre SUDOKU
J'ai essayé de résoudre TSP avec QAOA
J'ai un peu assoupli les conditions et laissé optuna résoudre le nombre
J'ai essayé de déboguer.
J'ai essayé de laisser VAE apprendre les animations
J'ai essayé d'apprendre PredNet
J'ai essayé d'organiser SVM.
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé d'implémenter PCANet
J'ai essayé de réintroduire Linux
J'ai essayé de présenter Pylint
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé de résumer SparseMatrix
jupyter je l'ai touché
J'ai essayé d'implémenter StarGAN (1)
J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python
J'ai essayé de résoudre le problème d'optimisation des combinaisons avec Qiskit
J'ai essayé d'implémenter Deep VQE
J'ai essayé de créer l'API Quip
J'ai essayé de toucher Python (installation)
J'ai essayé de mettre en place une validation contradictoire
J'ai essayé d'expliquer l'ensemble de données de Pytorch
J'ai touché l'API de Tesla
J'ai essayé de m'organiser à propos de MCMC.
J'ai essayé d'implémenter Realness GAN
J'ai essayé de déplacer le ballon
J'ai essayé d'estimer la section.
J'ai essayé de résoudre l'édition du débutant du livre des fourmis avec python
J'ai essayé de résoudre 100 traitements linguistiques Knock 2020 version [Chapitre 2: Commandes UNIX 10 à 14]
J'ai essayé de laisser Pepper parler des informations sur l'événement et des informations sur les membres
J'ai essayé de résoudre 100 traitements linguistiques Knock 2020 version [Chapitre 2: Commandes UNIX 15-19]
J'ai essayé de résoudre le problème de planification des équipes par diverses méthodes
J'ai essayé de créer un linebot (implémentation)
J'ai essayé de résumer la gestion des exceptions Python
J'ai essayé d'implémenter PLSA en Python
J'ai essayé d'utiliser Azure Speech to Text.
J'ai essayé d'implémenter Autoencoder avec TensorFlow
J'ai essayé de résumer la commande umask
J'ai essayé d'implémenter la permutation en Python
J'ai essayé de visualiser AutoEncoder avec TensorFlow
J'ai essayé de reconnaître le mot de réveil
Entrée standard Python3 que j'ai essayé de résumer
Je voulais résoudre ABC160 avec Python
J'ai essayé de classer le texte en utilisant TensorFlow
J'ai essayé de résumer la modélisation graphique.
J'ai essayé d'ajouter un post-incrément à l'implémentation CPython
J'ai essayé d'implémenter ADALINE en Python
J'ai essayé d'estimer le rapport de circonférence π de manière probabiliste
Je voulais résoudre ABC159 avec Python
J'ai essayé de toucher l'API COTOHA
J'ai essayé d'implémenter PPO en Python
J'ai essayé d'implémenter CVAE avec PyTorch
J'ai créé une API Web
[Python] J'ai essayé de calculer TF-IDF régulièrement
J'ai essayé de toucher Python (syntaxe de base)
Je voulais résoudre ABC172 avec Python
J'ai fait de mon mieux pour retourner au Lasso