From: Thorsten Winterer <thorsten_winterer_at_web.de>

Date: Fri, 05 Jul 2013 11:36:29 +0200

Date: Fri, 05 Jul 2013 11:36:29 +0200

Am 03.07.2013 08:55, schrieb Sergii Dymchenko: > Also I've implemented simulated annealing using 'tentative' and > 'tentative_constraints' libraries pointed to by Joachim (I didn't > really look at 'repair' library because 'tentative' "is intended as a > successor for library(repair)."). After some tweaking N = 4000 took > 1m15s on my laptop, and N = 33000 took about 2.5 hours (which is > acceptable) with very little memory consumption. > > I reimplemented the same simulated annealing algorithm in C++ from > scratch and got about 8 seconds for N = 4000 and about 12 minutes for > N = 33000. It often helps a lot if you can initialize the variables in a way that gives your local search algorithm a head start. (though sometimes you may find yourself in a local optimum straight away) I tweaked Joachim's code a bit, changing the initialization such that the first queen is on position 1, the second on 3 etc. This gives an almost valid placement: % initialize N2 is integer(round(N/2)), ( foreacharg(X, Board), count(I, 1, _), param(N2) do ( I =< N2 -> V is (I*2 - 1) ; V is (I - N2)*2 ), X tent_set V ), I also changed the code so that the neighbourhood size increases when no improving move was found in the last iteration. If the neighbourhood becomes too large, a random move is made. ( fromto(V0,V1,V2,0), fromto(-1,LD,D,_), fromto(SampleSize,LS,S,_), param(Vars,N,N0,SampleSize,Violations) do vs_random_worst(Vars, X), % get a most violated variable ( ( LD < 0, % if last move was improvement S = SampleSize ; S0 is LS*10, % or larger neighbourhood S0 =< N0, % is not too large S = S0 ) -> % then find a best neighbour tent_minimize_random( ( random_sample(1..N,S,I), X tent_set I ), Violations, I ) ; % else make some random move random(R), I is (R mod N) + 1, S = SampleSize ), X tent_set I, Violations tent_get V2, D is V2-V1 ). Here are the times for a couple of runs on my laptop: ?- queens(30000, B). B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ... Yes (0.49s cpu) ?- queens(30000, B). B = [](15306, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ... Yes (4.31s cpu) ?- queens(30000, B). B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 15351, 21, 23, ... Yes (3.29s cpu) ?- queens(30000, B). B = [](1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ... Yes (6.64s cpu) With a random initialization, the runtime was about 1.5 hours. Cheers, ThorstenReceived on Fri Jul 05 2013 - 09:36:38 CEST

*
This archive was generated by hypermail 2.2.0
: Sat Jul 06 2013 - 06:16:25 CEST
*