Dies ist eine Fortsetzung der vorherigen (Ich habe versucht, Optuna zu lösen).
Beim letzten Mal habe ich versucht, die richtige Antwort zu finden, indem ich mit optuna optimiert habe, ohne die Regeln mehrerer Deutscher zu kennen. Dieses Mal habe ich versucht, es für optuna zu optimieren, nachdem ich die Regel kannte, dass es in vertikalen, horizontalen und 3x3-Blöcken keine doppelten Zahlen gibt.
Ich hatte vor, es früher zu veröffentlichen, aber das Ringfit-Abenteuer, das ich nach dem letzten Beitrag begonnen hatte, war zu schwer und ich verlor sowohl Energie als auch körperliche Kraft, so dass es spät war.
Dieses Mal werden wir es durch die stumpfe Methode lösen.
Die Abstumpfungsmethode ändert den aktuellen Wert ein wenig zufällig, um den nächsten Wert zu erstellen. (Da es beim ersten Mal keinen ursprünglichen Wert gibt, machen Sie ihn völlig zufällig.) Wenn die aus dem neu erstellten Wert berechneten Kosten sinken, wechseln Sie zum neuen Wert. Selbst wenn es nicht abnimmt, kann es sich mit einer Wahrscheinlichkeit bewegen oder nicht. Indem die Wahrscheinlichkeit schrittweise verringert wird, konvergiert sie zur lokalen Lösung.
Informationen zum Abstumpfen mit Optuna finden Sie in der offiziellen Dokumentation. Ich habe gerade den Teil geändert, der den neuen Wert abtastet, und der Rest entspricht der offiziellen Dokumentation. Der vorherige Code bleibt erhalten, außer dass der Sampler geändert wurde.
Hier wird nur der Teil angezeigt, der den neuen Wert abtastet. Der gesamte Code wird am Ende angezeigt.
params = {}
#Zufällige Stichprobenreihenfolge
name_list = shuffle(list(search_space))
for param_name in name_list:
#Zweidimensionale Koordinaten(i, j)
i, j = int(param_name[1]), int(param_name[2])
#Im Voraus(i, j)Ich habe eine Maske erstellt, um die Elemente der vertikalen, horizontalen und 3x3-Blöcke herauszunehmen.
#Jedoch,(i, j)Elemente werden nicht mit einer Maske herausgenommen
mask = self._mask_array[i, j]
tmp = self._state * mask
# 1~Zählen Sie, wie viele der 9 Elemente vorhanden sind
cost = np.asarray([np.count_nonzero(tmp == v) for v in range(1, 10)])
probability = softmax(-cost * 5)
#Probieren Sie einen neuen Wert aus
new_value = np.random.choice(9, p=probability) + 1
#Neuen Wert aufzeichnen
params[param_name] = new_value
self._state[i, j] = new_value
return params
Es ist wahrscheinlicher, dass die neuen Werte auf der Grundlage der Regel abgetastet werden, dass in vertikalen, horizontalen und 3x3-Blöcken keine doppelten Zahlen vorhanden sind.
Wir nutzen hier unser Wissen über Regeln.
Die Zahlen mit * links sind ursprünglich als Hinweise angegeben.
*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
Es tut mir Leid.
Die Anzahl der Versuche erreichte diese Antwort zum 115. Mal. Danach habe ich es bis zu 200 Mal gemacht, aber es hat nicht funktioniert.
Sie können nicht auf einen Blick erkennen, was falsch ist, aber es gibt eine vertikale 7-Überlappung in der Mitte. Die 7 in der Mitte ist in vertikaler Richtung falsch, erfüllt aber die Bedingungen in horizontaler Richtung. Daher kann die richtige Antwort nur erreicht werden, wenn sich mehrere Elemente gleichzeitig ändern. Dies ist eine ziemlich tiefe lokale Lösung. (Sie können nicht die richtige Antwort erreichen, ohne einen Zustand zu durchlaufen, in dem die Kosten ziemlich hoch sind.)
Es ist eine lokale Lösung geworden. Mit der aktuellen Methode scheint es schwierig zu sein, da sich mehrere Faktoren gleichzeitig ändern müssen, um die richtige Antwort zu erhalten. Wenn Sie den Anfangswert ändern und es mehrmals versuchen, sollten Sie in der Lage sein, die richtige Antwort zu erhalten.
Diesmal gab es eine vertikale Überlappung von 7s in der Mitte, aber 7s sollten nicht so abgetastet werden, wie sie ursprünglich angegeben wurden. (Es hängt mit der Bedingung zusammen, wie viel Wissen über Regeln verwendet wird.) In einigen Fällen wird der Wert aus den ursprünglich angegebenen Zahlen bestimmt, z. B. aus der dritten Spalte von rechts und der dritten Zeile von oben.
Diese wurden bei dieser Methode überhaupt nicht berücksichtigt, daher möchte ich dies beim nächsten Mal lösen. (Ich denke nicht, dass Oputuna mehr relevant ist)
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 {}
#Die aktuelle Studie ist Studie.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
#Werde dich los
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