Eine entscheidende Herausforderung für die Optimierung

13

Betrachten Sie 30 mal 30 Toeplitz- Matrizen, von denen alle Einträge 0 oder 1 sind. Diese Abfrage ist eine einfache Optimierungsabfrage, um die Matrix mit der größtmöglichen Determinante zu finden.

Eingabe Keine

Ausgabe A 30 mal 30 Toeplitz-Matrix, deren Einträge zusammen mit ihrer Determinante 0 oder 1 sind.

Ergebnis Die Determinante der von Ihnen ausgegebenen Matrix. Erhalten zwei Personen die gleiche Punktzahl, gewinnt die erste Antwort.

Bisher führende Einträge

  • 65,455,857,159,975 in Matlab von Nick Alger (ungefähr (10 ^ 13.8)
  • 65.455.857.159.975 in Python von Isaacg (ungefähr 10 ^ 13.8)
  • 39,994,961,721,988 in Mathematica bis 2012rcampion (ungefähr 10 ^ 13,6)
  • 39,788,537,400,052 in R von Flounderer (ungefähr 10 ^ 13.6)
  • 8.363.855.075.832 in Python von Vioz- (ungefähr 10 ^ 12.9)
  • 6,984,314,690,903 in Julia von Alex A. (ungefähr 10 ^ 12,8)

Ärgerliche zusätzliche Einschränkungen 16. Juli 2015

Wenn es überhaupt möglich ist, verwenden Sie bitte eine willkürliche oder hochgenaue Arithmetik, um die endgültige Ausgabedeterminante zu berechnen, damit wir sicher sein können, was es wirklich ist (es sollte immer eine ganze Zahl sein). In Python dies sollte hilfreich sein.

code-challenge math optimization Gemeinschaft
quelle
Ich bin überrascht, dass dieses Problem noch nicht gelöst ist. Ist die Antwort für zirkulierende Matrizen bekannt?
15.
1
@NickAlger Wenn die Bibliothek öffentlich zugänglich ist, können Sie sie verwenden.
Orlp
2
@immibis Leider gibt es 2 ^ 59 von ihnen.
1
Es ist interessant, dass zwei unabhängige Methoden eine Toeplitz-Matrix mit genau der maximalen zirkulanten Matrixdeterminante erhalten haben. Ich habe keine mathematische Ahnung, warum - ist diese Determinante nur für binäre Toeplitz-Matrizen üblich?
Lirtosiast
1
@ Min_25 Ich sollte morgen das Maximum von bis zu 19 haben. Erhalten Sie den Code / die Werte in der verwandten Frage, Lembik. Mit heuristischen Algorithmen habe ich für n = 30 genau dieselben Werte erreicht wie für die beiden anderen Poster. Mehrfach mit Randomisierung. Auch mit zirkulierenden Matrizen als Ergebnis jedes Mal, wenn ich dieses Maximum erreiche, obwohl meine Suche nicht auf zirkulierende Matrizen beschränkt ist. Übrigens, eine andere (für mich) verwirrende Tatsache: Das Maximum für n = 15 ist genau 2 ^ 17.
Reto Koradi

Antworten:

11

Matlab, 65.455.857.159.975 (10 ^ 13.8159)

Die Methode ist Steigungsanstieg im Inneren des Würfels [0,1] ^ 59 mit vielen zufälligen Anfangsschätzungen und Abrunden am Ende, um alles zu Nullen und Einsen zu machen.

Matrix:

0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0
0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1
1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1
1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1
1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0
0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1
1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1
1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1
1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0
0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1
1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0
0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0
0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0
0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1
1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0
0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0
0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1
1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0
0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1
1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1
1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0
0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1
1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0
0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0
0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0
0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0
0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1
1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1
1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1
1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0

Code:

% Toeplitz 0-1 determinant optimization

n = 30;
m = n + n-1;

toeplitz_map = @(w) toeplitz(w(n:-1:1), w(n:end));

objective = @(w) det(toeplitz_map(w));

detgrad = @(A) det(A)*inv(A)';

toeplitz_map_matrix = zeros(n^2,m);
for k=1:m
    ek = zeros(m,1);
    ek(k) = 1;
    M = toeplitz_map(ek);
    toeplitz_map_matrix(:,k) = M(:);
end

gradient = @(w) (reshape(detgrad(toeplitz_map(w)),1,n^2)*...
                 toeplitz_map_matrix)';

%check gradient with finite differences
w = randn(m,1);
dw = randn(m,1);
s = 1e-6;
g_diff = (objective(w+s*dw) - objective(w))/s;
g = gradient(w)'*dw;
grad_err = (g - g_diff)/g_diff

warning('off')
disp('multiple gradient ascent:')
w_best = zeros(m,1);
f_best = 0;
for trial=1:100000
    w0 = rand(m,1);
    w = w0;
    alpha0 = 1e-5; %step size
    for k=1:20
        f = objective(w);
        g = gradient(w);
        alpha = alpha0;
        for hh=1:100
            w2 = w + alpha*g;
            f2 = objective(w2);
            if f2 > f
                w = w2;
                break;
            else
                alpha = alpha/2;
            end
        end

        buffer = 1e-4;
        for jj=1:m
            if (w(jj) > 1)
                w(jj) = 1 - buffer;
            elseif (w(jj) < 0)
                w(jj) = 0 + buffer;
            end
        end
    end

    w = round(w);
    f = objective(w);
    if f > f_best
        w_best = w;
        f_best = f;
    end
    disp(trial)
    disp(f_best)
    disp(f)
end

M = toeplitz_map(w_best);

Die Mathematik hinter der Berechnung des Gradienten:

Im elementweisen Innenprodukt (Hilbert-Schmidt-Innenprodukt) ist der Gradient der Determinante den Riesz-Repräsentanten G gegeben durch

G = det (A) A ^ (- *).

Die Karte J von den Optimierungsvariablen (Diagonalwerten) bis zu den Toeplitz-Matrizen ist linear, daher ist der Gesamtgradient g die Zusammensetzung dieser beiden linearen Karten.

g = (vec (G) * J) ',

Dabei ist vec () der Vektorisierungsoperator , der eine Matrix aufnimmt und in einen Vektor .

Innensteigung:

Danach müssen Sie nur noch einen Anfangsvektor mit diagonalen Werten w_0 auswählen und für einige kleine Schrittgrößen Alpha iterieren:

  1. w_proposed = w_k + alpha * g_k

  2. Um w_ (k + 1) zu erhalten, nehmen Sie w_proposed und kürzen Sie Werte außerhalb von [0,1] auf 0 oder 1

  3. Wiederholen, bis Sie zufrieden sind. Runden Sie dann alles auf 0 oder 1.

Mein Ergebnis erreichte diese Determinante nach ungefähr 80.000 Versuchen mit einheitlichen zufälligen Anfangsschätzungen.

Nick Alger
quelle
Der von Ihnen angegebene OEIS-Link betraf zirkulierende Matrizen, bei denen es sich um einen Sonderfall von Topelitz-Matrizen handelt. Also noch besser geht es nicht.
isaacg
@isaacg Und auch sehr wahrscheinlich!
Ja natürlich, ich habe mich geirrt. Ich habe meinen Beitrag bearbeitet, um ihn zu korrigieren.
Nick Alger
1
Ja, es hat diesen Wert bei Iteration 250 erreicht und ist dort für 100000 Iterationen geblieben. Der Vektor, der die 18x18-Toeplitz-Matrix mit der Determinante 2994003 definiert, war [0,0,0,1,0,1,1,1,1,1,0,0,1,0,1,0, 0,0,1,0,1,1,1,1,0,1,1,0,0,0,1,0], wobei die Reihenfolge von links unten nach rechts oben verläuft.
Nick Alger
2
Ich habe Ihnen den Gewinn zuerkannt, als Sie eine neue Idee hatten und die höchste Nummer als erstes IIRC hatten. Oh und das zeigt, warum Ihre Antwort funktioniert math.stackexchange.com/questions/1364471/… .
11

Python 2 mit Numpy, 65, 455, 857, 159, 975 ~ = 10 ^ 13,8

Dies ist Bergsteigen, so einfach wie möglich. Die endgültige Determinantenberechnung wurde mit SymPy durchgeführt, um ein genaues Ergebnis zu erhalten. Alle mit dieser Determinante gefundenen Matrizen sind zirkulierend.

Mit dieser Determinante gefundene Matrizen, angegeben als Wert der Diagonale von links unten nach rechts oben:

01000100101101000011100111011101000100101101000011100111011
01011101110011100001011010010001011101110011100001011010010
01100001000111011101001110100101100001000111011101001110100
01110100111010010110000100011101110100111010010110000100011
01011101110001000011010010111001011101110001000011010010111
01000101100010110100111101110001000101100010110100111101110
01000100101101000011100111011101000100101101000011100111011

Der erste als Matrix:

[[1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1]
 [1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1]
 [1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0]
 [0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
 [1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1]
 [1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1]
 [1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0]
 [0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1]
 [1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1]
 [1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0]
 [0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0]
 [0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0]
 [0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 0]
 [0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1]
 [1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0]
 [0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1]
 [1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0 1]
 [1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1 0]
 [0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0 1]
 [1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 0]
 [0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0]
 [0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0 1]
 [1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0 0]
 [0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 0]
 [0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0]
 [0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1]
 [1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0]
 [0 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1]]

Code:

import numpy as np
import sympy as sp
import random
import time
SIZE = 30

random.seed(0)

def gen_diag():
    return [random.randint(0, 1) for i in range(SIZE*2 - 1)]

def diag_to_mat(diag):
    return [diag[a:a+SIZE] for a in range(SIZE-1, -1, -1)]

def diag_to_det(diag):
    matrix = diag_to_mat(diag)
    return np.linalg.det(matrix)

def improve(diag):
    old_diag = diag
    really_old_diag = []
    while really_old_diag != old_diag:
        really_old_diag = old_diag
        for flip_at in range(SIZE * 2 - 1):
            new_diag = old_diag[:]
            new_diag[flip_at] ^= 1
            old_diag = max(old_diag, new_diag, key=diag_to_det)
    return old_diag

overall_best_score = 0
time.clock()
while time.clock() < 500:
    best = improve(gen_diag())
    best_score = diag_to_det(best)
    if best_score > overall_best_score:
        overall_best_score = best_score
        overall_best = best
        print(time.clock(), sp.Matrix(diag_to_mat(overall_best)).det(), ''.join(map(str,overall_best)))


mat = diag_to_mat(overall_best)

sym_mat = sp.Matrix(mat)

print(overall_best)
print(sym_mat.det())
isaacg
quelle
1
Das ist verrückt. Gute Arbeit.
Alex A.
Die .227 ist ein wenig besorgniserregend. Glauben Sie, dass es einen Weg gibt, zuversichtlich zu sein, was die Determinante wirklich ist?
Es scheint, dass stackoverflow.com/questions/6876377/… dazu beitragen könnte, die endgültige Determinante zu bewerten.
@Lembik Danke - SymPy hat den Trick gemacht.
isaacg
Das ist wirklich toll!
10

R 39 788 537 400 052

Hier ist mein Versuch, einen genetischen Algorithmus zu erstellen, aber nur mit ungeschlechtlicher Fortpflanzung. Ich hoffe, ich habe die Herausforderung richtig verstanden. Bearbeiten: Beschleunigen Sie es ein wenig, probieren Sie einen anderen Zufallsstartwert aus und beschränken Sie sich auf 100 Generationen.

    options(scipen=999)

toeplitz <- function(x){
# make toeplitz matrix with first row
# x[1:a] and first col x[(a+1):n]
# where n is the length of x and a= n/2
# Requires x to have even length
#
# [1,1] entry is x[a+1]

N <- length(x)/2
out <- matrix(0, N, N)
out[1,] <- x[1:N]
out[,1] <- x[(N+1):length(x)]
for (i in 2:N){
  for (j in 2:N){
    out[i,j] <- out[i-1, j-1]
  }
} 

out
}

set.seed(1002)

generations <- 100
popsize <- 25
cols <- 60
population <- matrix(sample(0:1, cols*popsize, replace=T), nc=cols)
numfresh <- 5 # number of totally random choices added to population

for (i in 1:generations){

fitness <- apply(population, 1, function(x) det(toeplitz(x)) )
mother <- which(fitness==max(fitness))[1]

population <- matrix(rep(population[mother,], popsize), nc=cols, byrow=T)
for (i in 2:(popsize-numfresh)){
  x <- sample(cols, 1)
  population[i,x] <- 1-population[i,x]
}
for (i in (popsize-numfresh +1):popsize){
  population[i,] <- sample(0:1, cols, replace=T)
}


print(population[1,])
print(fitness[mother])
print(det(toeplitz(population[1,]))) # to check correct

}

Ausgabe:

print(population[1, 1:(cols/2)]) # first row
print(population[1, (cols/2+1):(cols)]) # first column (overwrites 1st row)

to <- toeplitz(population[1,])

for (i in 1:(cols/2)) cat(to[i,], "\n")

1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 
0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 
1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 
0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 
0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 
0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 
1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 
1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 
1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 
1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 
0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 
1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 
1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 
0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 
0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 
0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 
0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 
1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 
0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 
0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 
1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 
0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 
0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 
0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 
0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 
1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 
0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 
1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 
1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1
Flunder
quelle
Das ist sehr nett. Sie gewinnen derzeit bei weitem.
Nicht mehr :)
3

Julia, 6,984,314,690,902,998

Dabei werden nur 1.000.000 zufällige Toeplitz-Matrizen konstruiert und ihre Determinanten überprüft, wobei das maximal angetroffene Maximum aufgezeichnet wird. Hoffentlich hat jemand eine elegante analytische Lösung, aber in der Zwischenzeit ...

function toeplitz(a, b)
    n = length(a)
    T = Array(Int, n, n)
    T[1,:] = b
    T[:,1] = a
    for i = 2:n
        T[i,2:n] = T[i-1,1:n-1]
    end
    T
end

d = 0
A = Any[]

for i = 1:1000000
    # Construct two random 0,1 arrays
    r1 = rand(0:1, 30)
    r2 = rand(0:1, 30)

    # Compute the determinant of a toeplitz matrix constructed
    # from the two random arrays
    D = det(toeplitz(r1, r2))

    # If the computed determinant is larger than anything we've
    # encountered so far, add it to A so we can access it later
    D > d && begin
        push!(A, (D, r1, r2))
        d = D
    end
end

M,N = findmax([i[1] for i in A])

println("Maximum determinant: ", M, "\n")
println(toeplitz(A[N][2], A[N][3]))

Sie können die Ausgabe hier anzeigen .

Alex A.
quelle
Ich frage mich, wie genau die Determinantenberechnung ist. Ich denke, dass die zugrunde liegende Berechnung in doppelter Genauigkeit erfolgt? Da die Nachkommastellen 0,998 sind, besteht wahrscheinlich eine gute Chance, dass die nächste Ganzzahl immer noch die richtige Determinante ist. Im Allgemeinen treten Gleitkommapräzisionsprobleme auf, wenn Sie eine universelle Determinantenberechnung, z. B. basierend auf einer Standard-LR-Zerlegung, auf diese Matrizen anwenden, sobald diese relativ groß sind.
Reto Koradi
@RetoKoradi Sieht so aus, als würde eine LU-Zerlegung verwendet, um die Determinante abzurufen.
Alex A.
3

Mathematica, 39.994.961.721.988 (10 ^ 13.60)

Eine einfache simulierte Glühoptimierungsmethode; noch keine optimierung oder einstellung.

n = 30;
current = -\[Infinity];
best = -\[Infinity];
saved = ConstantArray[0, {2 n - 1}];
m := Array[a[[n + #1 - #2]] &, {n, n}];
improved = True;
iters = 1000;
pmax = 0.1;
AbsoluteTiming[
 While[improved || RandomReal[] < pmax,
   improved = False;
   a = saved;
   Do[
    Do[
      a[[i]] = 1 - a[[i]];
      With[{d = Det[m]},
       If[d > best,
          best = d;
          current = d;
          saved = a;
          improved = True;
          Break[];,
          If[d > current || RandomReal[] < pmax (1 - p/iters),
           current = d;
           Break[];,
           a[[i]] = 1 - a[[i]];
           ]
          ];
        ;
       ],
      {i, 2 n - 1}];,
    {p, iters}];
   ];
 ]
best
Log10[best // N]
a = saved;
m // MatrixForm

Beispielausgabe:

{20.714876,Null}
39994961721988
13.602
(1  1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0
0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0
0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0
0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0
0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1
1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0
0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0
0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0
0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0
0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1
1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1
1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0
0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1
1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1
1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0
0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1
1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1
1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1
1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0
0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1
1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1
1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0
0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0
0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0
0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0
0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1
1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0
0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1
1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1
1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1

)
2012rcampion
quelle
1

Python 2, 8 363 855 075 832

Dies hat eine sehr grundlegende, fast nicht existierende Strategie zur Folge.

from scipy import linalg

start = 2**28
mdet  = 0
mmat  = []
count = 0
powr  = 1
while 1:
 count += 1
 v = map(int,bin(start)[2:].zfill(59))
 m = [v[29:]]
 for i in xrange(1,30):
     m += [v[29-i:59-i]]
 d = 0
 try: d = linalg.det(m, check_finite=False)
 except: print start
 if d > mdet:
     print d
     print m
     mdet = d
     mmat = m
     start += 1
     powr = 1
 else:
     start += 2**powr
     powr += 1
     if start>(2**59-1):
         start-=2**59-1
         powr = 1
 if count%10000==0: print 'Tried',count

Hier ist die beste Matrix, die nach ~ 5.580.000 Versuchen gefunden wurde:

1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0
1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0
0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1
1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1
0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0
0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1
1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0
0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0
0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0
1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1
0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1
1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1
1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0
1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1
1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1
1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1
0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0
1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1

Funktioniert immer noch...

Kade
quelle