Я играю с правилом 110 клеточных автоматов Wolfram. Учитывая строку нулей и единиц, вы можете вычислить следующую строку по этим правилам:
Начиная с 00000000....1 в конце вы получите такую последовательность:
Просто из любопытства я решил аппроксимировать эти правила полиномом, чтобы ячейки могли быть не только 0 и 1, но и серым цветом между ними:
def triangle(x,y,z,v0):
v=(y + y * y + y * y * y - 3. * (1. + x) * y * z + z * (1. + z + z * z)) / 3.
return (v-v0)*(v-v0)
поэтому, если x, y, z и v0 соответствуют любому из этих правил из таблицы, он вернет 0 и положительное ненулевое значение в противном случае.
Затем я добавил все возможные группы из 4 соседей в единую сумму, которая будет равна нулю для целочисленных решений:
def eval():
s = 0.
for i in range(W - 1):
for j in range(1, W + 1):
xx = x[i, (j - 1) % W]
yy = x[i, j % W]
zz = x[i, (j + 1) % W]
r = x[i + 1, j % W]
s += triangle(xx, yy, zz, r)
for j in range(W - 1): s += x[0, j] * x[0, j]
s += (1 - x[0, W - 1]) * (1 - x[0, W - 1])
return torch.sqrt(s)
Также внизу этой функции я добавляю обычные условия для первой строки, чтобы все элементы были равны 0, кроме последнего, который равен 1. Наконец, я решил минимизировать эту сумму квадратов на матрице W * W с помощью pytorch:
x = Variable(torch.DoubleTensor(W,W).zero_(), requires_grad=True)
opt = torch.optim.LBFGS([x],lr=.1)
for i in range(15500):
def closure():
opt.zero_grad()
s=eval()
s.backward()
return s
opt.step(closure)
Вот полный код, можете попробовать сами. Проблема в том, что для 10*10 он сходится к правильному решению примерно за 20 шагов:
Но если я возьму доску 15*15, она никогда не закончит схождение:
График справа показывает, как сумма квадратов меняется с каждой следующей итерацией, и вы можете видеть, что она никогда не достигает нуля. Мой вопрос в том, почему это происходит и как я могу это исправить. Пробовал разные оптимизаторы pytorch, но все они работают хуже, чем LBFGS. Пробовал разные скорости обучения. Любые идеи, почему это происходит и как я могу достичь конечной точки во время оптимизации?
UPD: улучшен график сходимости, лог SOS:
UPD2: я также пытался сделать то же самое на C++ с dlib, и у меня нет проблем с конвергенцией, все идет намного глубже за гораздо меньшее время:
Я использую этот код для оптимизации на С++:
find_min_using_approximate_derivatives(bfgs_search_strategy(),
objective_delta_stop_strategy(1e-87),
s, x, -1)
