R, 39 788 537 400 052
Here is my attempt to do a genetic algorithm but only with asexual reproduction. I hope I understood the challenge correctly. Edit: sped it up a bit, tried a different random seed, and restricted to 100 generations.
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
}
Output:
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
I'm surprised that this problem is not already solved. Is the answer known for circulant matrices? – xnor – 2015-07-15T20:19:56.243
@xnor http://oeis.org/A086432 exists and maybe others for circulant matrices as does http://oeis.org/A215724 .
– None – 2015-07-15T20:21:38.773The Mathematica code though for A086432 and related sequences just seems to be trying every legal matrix. I take it then no efficient algorithm is known? – xnor – 2015-07-15T20:23:47.150
@xnor Not that I know of. See http://codegolf.stackexchange.com/questions/52851/find-the-maximum-determinant-for-each-size-toeplitz-matrix for example :)
– None – 2015-07-15T20:24:34.177Couldn't people just use the same solutions from your last Toeplitz determinant challenge and let them run to n=30? – Alex A. – 2015-07-15T20:38:02.243
@AlexA. Well, possibly. However, based on my numbers, to get to n=21, we may experience heat death before a maximum is found out. Currently, all of those programs are brute-force. We don't have a good formula for this (yet). – Kade – 2015-07-15T20:53:18.640
Is there a time limit or computational power limit? (i.e., is it time for me to get into CUDA programming =P) – 2012rcampion – 2015-07-16T04:15:23.087
Is it allowed to call (high powered) optimization libraries? There are very advanced methods that could probably solve this problem completely (eg., branch and cut with a trust region interior point method for the subproblem relaxations). – Nick Alger – 2015-07-16T05:15:21.110
1@NickAlger If the library is publicly available for everyone, you can use it. – orlp – 2015-07-16T06:01:04.763
@2012rcampion No limits. Please feel free to CUDA away :) – None – 2015-07-16T07:10:19.060
I let my code run longer and it seems to have achieved the maximum value listed in OEIS A086432 – Nick Alger – 2015-07-16T09:02:22.050
@NickAlger That's great! But note that this is not necessarily the max for Toeplitz matrices. In fact I am 100% sure it is isn't as you can compare the max for smaller n where we can compute it exhaustively. – None – 2015-07-16T09:07:32.780
@Lembik Oh you're right, good call. Well I'm done for now anyways. – Nick Alger – 2015-07-16T09:08:39.597
There are only 2^30 such matrices (roughly one billion), right? Sounds like it should be doable by brute force in under a day... – user253751 – 2015-07-16T12:01:22.277
2@immibis Sadly there are 2^59 of them. – None – 2015-07-16T12:02:14.250
@Lembik I missed that the diagonals don't wrap around. – user253751 – 2015-07-16T12:03:16.667
1It's interesting that two independent methods have achieved a Toeplitz matrix with exactly the maximum circulant matrix determinant. I don't have any mathematical intuition as to why—is that determinant just common for binary Toeplitz matrices? – lirtosiast – 2015-07-17T04:16:46.243
@ThomasKwa Yes. It would be interesting to test smaller cases where we know the max to see what is going on. – None – 2015-07-17T08:27:59.600
I'm interested in the maximum (maximal ?) determinants for other than n=30. Do the two top solutions still output same values for n >= 31 ? – Min_25 – 2015-07-20T13:25:53.437
@Min_25 n=8 is interesting in relation to the determinant max problem.. for circulant matrices 275 is optimal, for toeplitz matrices 315 is optimal and for general 0,1 matrices 320 is optimal. It seems that the optimal values do however coincide sometimes for other values of n. – None – 2015-07-20T16:56:38.987
1@Min_25 I should have the maximum up to 19 by tomorrow. Will get the code/values to you in the related question, Lembik. With heuristic algorithms, I have maxed out at exactly the same values for n=30 as the other two posters so far. Multiple times, with randomization involved. Also with circulant matrices as the result every time I reach that maximum, even though my search is not restricted to circulant matrices. BTW, another baffling (to me) fact: The maximum for n=15 is exactly 2^17. – Reto Koradi – 2015-07-21T06:07:56.763