Ceci est une suite du précédent (j'ai essayé de résoudre optuna).
La dernière fois, j'ai essayé de trouver la bonne réponse en optimisant avec optuna sans même connaître les règles de plusieurs Allemands. Cette fois, j'ai essayé de l'optimiser pour optuna après avoir connu la règle selon laquelle il n'y a pas de duplication des nombres dans les blocs verticaux, horizontaux et 3x3.
J'avais l'intention de le publier plus tôt, mais l'aventure Ringfit que j'ai commencée après le dernier message était trop difficile et j'ai perdu à la fois de l'énergie et de la force physique, il était donc tard.
Cette fois, nous allons le résoudre par la méthode émoussée.
La méthode émoussée modifie la valeur actuelle un peu au hasard pour créer la valeur suivante. (Comme il n'y a pas de valeur d'origine à la première fois, faites-la de manière complètement aléatoire.) Si le coût calculé à partir de la nouvelle valeur que vous avez créée diminue, passez à la nouvelle valeur. Même s'il ne diminue pas, il peut ou non se déplacer avec une probabilité. En réduisant progressivement la probabilité, il converge vers la solution locale.
La méthode d'émoussement avec optuna peut être trouvée dans les Documents officiels. Je viens de changer la partie qui échantillonne la nouvelle valeur, et le reste est conforme à la documentation officielle. Le code précédent demeure, sauf que l'échantillonneur a été modifié.
Seule la partie qui échantillonne la nouvelle valeur est affichée ici. Le code entier est affiché à la fin.
params = {}
#Ordre d'échantillonnage aléatoire
name_list = shuffle(list(search_space))
for param_name in name_list:
#Coordonnées bidimensionnelles(i, j)
i, j = int(param_name[1]), int(param_name[2])
#En avance(i, j)J'ai fait un masque pour retirer les éléments des blocs vertical, horizontal et 3x3.
#cependant,(i, j)Les éléments ne sont pas sortis avec un masque
mask = self._mask_array[i, j]
tmp = self._state * mask
# 1~Comptez combien de chacun des 9 éléments sont
cost = np.asarray([np.count_nonzero(tmp == v) for v in range(1, 10)])
probability = softmax(-cost * 5)
#Exemple de nouvelle valeur
new_value = np.random.choice(9, p=probability) + 1
#Enregistrer une nouvelle valeur
params[param_name] = new_value
self._state[i, j] = new_value
return params
Les nouvelles valeurs sont plus susceptibles d'être échantillonnées sur la base de la règle selon laquelle il n'y a pas de nombres en double dans les blocs verticaux, horizontaux et 3x3.
Nous utilisons ici notre connaissance des règles.
Les nombres avec * sur la gauche sont à l'origine donnés à titre indicatif.
*5*3 2 4*7 6 9 1 8
*6 7 4*1*9*5 3 5 2
1*9*8 2 3 8 4*6 7
*8 1 9 5*6 4 7 2*3
*4 2 6*8 7*3 5 9*1
*7 5 3 9*2 1 8 4*6
9*6 1 3 5 7*2*8 4
2 8 7*4*1*9 6 3*5
3 4 5 6*8 2 1*7*9
loss: 4.0
Je suis désolé.
Le nombre d'essais a atteint cette réponse pour la 115e fois. Après cela, je l'ai fait jusqu'à 200 fois, mais cela n'a pas fonctionné.
Vous ne pouvez pas dire en un coup d'œil ce qui ne va pas, mais il y a un chevauchement vertical 7 au centre. Le 7 au centre est faux dans le sens vertical, mais il remplit les conditions dans le sens horizontal. Par conséquent, la réponse correcte ne peut être atteinte que si plusieurs éléments changent en même temps, ce qui est une solution locale assez profonde. (Vous ne pouvez pas atteindre la bonne réponse sans passer par un état où le coût est assez élevé)
C'est devenu une solution locale. Cela semble difficile avec la méthode actuelle car plusieurs facteurs doivent changer en même temps pour parvenir à la bonne réponse. Si vous modifiez la valeur initiale et réessayez plusieurs fois, vous devriez pouvoir obtenir la bonne réponse.
Cette fois, il y avait un chevauchement vertical de 7 au centre, mais les 7 ne devraient pas être échantillonnés comme ils ont été initialement donnés. (Il est lié à la condition d'utilisation des connaissances sur les règles) Dans certains cas, la valeur est déterminée à partir des nombres initialement donnés, tels que la troisième colonne à partir de la droite et la troisième ligne à partir du haut.
Celles-ci n'ont pas du tout été prises en compte dans cette méthode, je voudrais donc résoudre ce problème la prochaine fois. (Je ne pense plus qu'oputuna soit pertinent)
from itertools import product
import numpy as np
import optuna
import click
from scipy.special import softmax
from sklearn.utils import shuffle
# https://optuna.readthedocs.io/en/stable/tutorial/sampler.html
class SimulatedAnnealingSampler(optuna.samplers.BaseSampler):
def __init__(self, temperature=100):
self._rng = np.random.RandomState()
self._temperature = temperature
self._current_trial = None
self._state = None
self._mask_array = make_mask_array()
def sample_relative(self, study, trial, search_space):
if search_space == {}:
return {}
#L'essai actuel est une étude.trials[-1]
previous_trial = study.trials[-2]
if self._current_trial is None or previous_trial.value <= self._current_trial.value:
probability = 1.0
else:
probability = np.exp((self._current_trial.value - previous_trial.value) / self._temperature)
self._temperature *= 0.99
if self._rng.uniform(0, 1) < probability:
self._current_trial = previous_trial
if self._state is None:
self._state = np.empty([9, 9], dtype=np.int32)
for i, j in product(range(9), repeat=2):
name = 'p{}{}'.format(i, j)
if name in preset:
self._state[i, j] = preset[name]
for i, j in product(range(9), repeat=2):
name = 'p{}{}'.format(i, j)
if name in self._current_trial.params:
self._state[i, j] = self._current_trial.params[name]
params = {}
name_list = shuffle(list(search_space))
for param_name in name_list:
i, j = int(param_name[1]), int(param_name[2])
mask = self._mask_array[i, j]
tmp = self._state * mask
cost = np.asarray([np.count_nonzero(tmp == v) for v in range(1, 10)])
probability = softmax(-cost * 5)
new_value = np.random.choice(9, p=probability) + 1
params[param_name] = new_value
self._state[i, j] = new_value
return params
def infer_relative_search_space(self, study, trial):
return optuna.samplers.intersection_search_space(study)
def sample_independent(self, study, trial, param_name, param_distribution):
independent_sampler = optuna.samplers.RandomSampler()
return independent_sampler.sample_independent(study, trial, param_name, param_distribution)
def make_mask_array():
mask_array = np.zeros([9, 9, 9, 9])
for i, j in product(range(9), repeat=2):
mask = mask_array[i, j]
mask[i] = 1
mask[:, j] = 1
s, t = i // 3 * 3, j // 3 * 3
mask[s:s + 3, t:t + 3] = 1
#Débarrassez-vous de vous
mask[i, j] = 0
return mask_array
"""
-----------------
|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|
-----------------
"""
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):
tmp = np.reshape(answer, [3, 3, 3, 3])
loss = np.sum((
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=0))) for i in range(1, 10)]),
np.sum([np.count_nonzero(np.logical_not(np.any(answer == i, axis=1))) for i in range(1, 10)]),
np.sum([np.count_nonzero(np.logical_not(np.any(tmp == i, axis=(1, 3)))) for i in range(1, 10)]),
))
return loss
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'
sampler = SimulatedAnnealingSampler()
study = optuna.create_study(study_name=study_name, storage='sqlite:///sudoku.db', load_if_exists=True,
sampler=sampler)
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()
Recommended Posts