Searching with iterated maps PNAS

Searching With Iterated Maps Pnas-Free PDF

  • Date:18 Nov 2020
  • Views:1
  • Downloads:0
  • Pages:6
  • Size:901.92 KB

Share Pdf : Searching With Iterated Maps Pnas

Download and Preview : Searching With Iterated Maps Pnas


Report CopyRight/DMCA Form For : Searching With Iterated Maps Pnas


Transcription:

The fixed point sets of D are not useful for solving the set Adapting the difference map algorithm to the problem of linear. intersection problem unless they are attracting This is where the diophantine equations is very straightforward The n dimensional. distance minimizing property of the projections as well as the space of solution vectors x defines the Euclidean space where the. detailed forms of the maps fA and fB are critical It easily can be projections are performed One of the constraint sets A is the. checked that locally when the sets A and B are linear and affine space Cx b obtained by relaxing the binary constraint on. orthogonal the form above reduces to a projection onto the linear x The projection to this constraint is given by the matrix formula. space of fixed points convergence in one iteration 12 14 This Paff x 1 C 1C x C 1b where C 1 is the pseudoinverse. local model also illustrates how the algorithm avoids getting stuck matrix of C The second constraint set B is the hypercube of binary. at a near solution Consider a modification of the earlier example vectors and the corresponding projection Pbin simply rounds each. where X is shifted along the Z axis by an amount c the line defined component of x to 0 or 1. by y 0 z c thereby eliminating the solution The sequence of Once the algorithmic details of the projections have been worked. difference map iterates is now x y z 3 0 0 z c 3 0 0 z out the protocol for finding solutions is the same for any application. 2 c continuing at a uniform rate away from the near solution of the difference map First a value of is selected With no prior. What previously was the manifold of fixed points Z has become experience the values 1 are preferred because this uses only. for c 0 the attractor on which the search is carried out Taking half as many projection evaluations per iteration Second an initial. this local model one step further we arrive at a global picture of the element x0 is chosen usually with a random number generator. space that is searched by the algorithm Roughly it corresponds to Although this is the only explicit use of randomness round off. the cobbled together local attractors of numerous near solutions It errors in the finite precision arithmetic may lead to unpredictable. is this more limited search space of candidates that are all nearly machine specific outcomes This point reflects the strongly chaotic. elements of A B that the difference map is able to access nature of the underlying dynamical system The arrival at a fixed. Quantitative support of this interpretation is given below point is signaled by a small value of the displacement D x. Convergence to a fixed point set has been proven only when A x When this value falls below a chosen threshold the validity of the. and B are convex 11 a characterization that excludes most solution is checked and if successful the algorithm is terminated. difficult problems Our reporting of the algorithm therefore is based In the diophantine equations problem for example the binary. MATHEMATICS, almost entirely on a large body of empirical evidence This evidence vector xsol PB fA x would be confirmed as a solution of Cx b. supports the central hypothesis that the space being searched is a To demonstrate the solution of diophantine equations we gen. strange attractor when there is no solution A B A and that erated random solvable instances with n 80 and various values of. the presence of solutions only modifies this picture by introducing m All instances attempted were solved with the difference map. isolated traps fixed point sets that reduce the strange attractor to parameter 0 6 an empirically determined optimum Fig 1a. a simple attractor In the strongly mixing regime the dynamics on shows the evolution of for overconstrained m 36 and. a strange attractor quickly becomes uncorrelated in time Because underconstrained m 13 instances The mean fluctuating value. this behavior usually applies the sampling of the attractor and in of has the expected variation with m because this diagnostic. particular the discovery of solutions can be modeled as a Poisson measures directly the currently achieved distance between projec. process The number of iterations to reach a solution sampled over tions on the two constraint sets Phase retrieval normally is carried. random initial conditions therefore should have a decaying expo out in the overconstrained regime because image molecule recon. nential distribution 15 The mean of this distribution is a useful structions are uninteresting unless there is some guarantee of. measure of complexity for hard problems because the computation uniqueness We see from Fig 1a that in this case especially the. of each iterate should require only easy computations projections arrival at the fixed point is an unambiguous event The distribution. Finally our experience with the algorithm suggests that typically of run times iterations plotted in Fig 1b for a particular instance. there is only one strange attractor the benefit being that the has the exponential form expected of a Poisson process One of the. outcome of the search is independent of initial conditions We more interesting outcomes of this study is that the variation in the. attribute the absence of multiple attractors including short cycles mean iteration count with the parameter m shown in Fig 1c has. to the strong mixing generated by the sharp decisions made when the same behavior reported for other hard problems 16 a clear. projecting to highly nonconvex sets nearest integer etc maximum at the over under constrained boundary m m0. One of the simplest applications of the algorithm is finding Table 1 compares difference map performance with a linear. solutions to linear systems of diophantine equations As an example programming based solver CPLEX ILOG Inc Mountain View. consider the three equations in four unknowns x1 x2 1 x1 CA the leading methodology for this kind of problem. x3 1 and x2 x4 2 The solution is unique if we restrict the The most direct way of assessing the size of the space being. values of the variables to be 0 or 1 binary Given positive integers searched by the difference map is to enumerate the places visited. m and n an interesting ensemble of random instances is defined by by the algorithm in the course of trying to solve an insoluble. the matrix equation Cx b where C is an m n matrix with 0 1 instance In this scenario the iterates x ceaselessly sample a strange. entries uniformly sampled and b is a vector of m integers A attractor while generating a stream of candidate solutions binary. soluble instance is generated by first selecting C and a random strings of length n given by xbin Pbin faff x A probability. binary solution vector x and then evaluating the corresponding b distribution p xbin on the binary strings is defined by the frequency. Given C and b how hard is it to recover x with the guarantee that that the dynamical system visits xbin The corresponding entropy S. it exists Clearly there are two limits where this task is easy When xbinp xbin log2 p xbin measures the effective size of the search. m is small a greedy approach succeeds because few variables space Finding the solution of a soluble instance with similar. appear in more than one equation At the other extreme m n parameters n and m should require 2S iterations We confirmed. the matrix C is square and the solution is obtained by inverting C this estimate with experiments on instances of size n 32 By. When m and n are large a sharp transition occurs for the random choosing m 15 m0 and a particular random C the uncontrived. ensemble in the expected number of solutions from exponentially choice b n 4 n 4 almost always gives an insoluble instance. large m m0 to exponentially small m m0 In the latter case Separate runs of the algorithm up to 105 iterations gave practically. there is a probabilistic guarantee of solution uniqueness in instances indistinguishable probability distributions on the set of 2 000. known by construction to be soluble For fixed n we expect the binary strings that were visited the entropy was just below S 9. complexity of finding a solution to be a maximum when m is near. Downloaded by guest on November 17 2020, m0 The transition point m0 2n log2 n 4 is obtained by evalu. ating the density of points Cx fixed C random x with the central Tests. on the hardest instances showed that performance mean iteration count is de. limit theorem graded at most by a factor of 5 when 1. Elser et al PNAS January 9 2007 vol 104 no 2 419, Table 1 The difference map compared with the CPLEX solver. on hard instances of the diophantine equations problem. Difference map CPLEX,n m Iterations sec sec,0 2 20 10 26 0 00 0 00. 40 16 300 0 01 0 01,0 1 60 22 10 000 1 00 0 14,80 27 2 500 000 450 00 56 00.
100 32 48 000 000 12 000 00 4 800 00, 200 400 600 800 Timing at 1 GHz and iteration counts for the difference map are averaged. iteration number over 10 runs, map performance mean iterations timing is averaged over at least. 0 8 10 runs, 0 6 Graph Coloring This application is interesting because it shows the. difference map is chaotic even in a highly symmetric setting The. 0 4 task is to color the edges of a complete graph with three colors while. avoiding monochromatic triangles The minimum number of ver. 0 2 tices n for which this is impossible defines the Ramsey number. R3 3 Analysis has shown that R3 3 17 and that for n 16 there. are just two nonisomorphic colorings 17 In Fig 2 we show the. scaled iteration number, time evolution of one difference map solution for this most difficult. case n 16 Time iteration number increases vertically and. c 25 color assignments to the 120 edge variables are plotted horizontally. We see that although the color updates in each iteration are global. in nature there is persistence in a large fraction of the assignments. over many iterations This problem has many symmetry equivalent. log2 iterations, solutions the particular one found by the algorithm is set by initial.
conditions, 15 Our embedding in Euclidean space respects all of the symmetries. in the problem Associated with each of the ne graph edges is a. primary variable ei a 3 vector that symmetrically encodes a coloring. 10 when restricted to the set E 2 1 1 1 2 1 1 1,20 25 30 35. 2 Secondary variables tj are associated with each of the nt. m triangles in the graph The two sets of variables are related by linear. compatibility equations ei ej ek s tl 0 one for each triangle. Fig 1 The difference map applied to linear diophantine equations a Time and containing by symmetry a single free scale parameter s. series of the difference map displacements for overconstrained blue and. Combining edge and triangle variables into a single vector z these. underconstrained red instances A solution was found for both instances in. 1 000 iterations b Exponential distribution of iteration counts for 2 000 equations when written Cz 0 comprise the first constraint A. difference map solutions of a diophantine equation instance with n 80 and in the difference map construction When coloring a general graph. m 27 The horizontal axis is scaled to the mean iteration count 1 3 106 all of the graph specific information is contained in the nt ne. and the curve is the exponential distribution with unit mean c Complexity nt sparse matrix C and its dense pseudoinverse C 1 The projection. peak in the mean iteration counts for difference map solutions of diophantine to the compatibility constraint Pcom z 1 C 1C z through its. equations with n 80 variables The maximum occurs near the solvability. threshold of random instances m m0 27 Vertical bars correspond to. standard deviations in experiments with five instances. We then generated soluble instances for the same matrix C these. were solved typically in a few hundred iterations as expected. Example Applications, There is a large class of problems that are formulated in terms of. independently constrained primary variables that are linearly. related to a set of secondary variables whose values are inde. pendently constrained as well In the difference map scheme one. of the constraints A is the linear relationship between the two sets. of variables the other constraint B restricts the allowed values for. the combined set Below we summarize our experiences using the. difference map on a number of much studied problems that fit this. Downloaded by guest on November 17 2020, description In addition we also discuss three problems not in this Fig 2 Deterministic time evolution vertically of edge colorings in the. class where the difference map can take advantage of special kinds difference map solution of a graph coloring problem The solution top was. of projections In comparisons with other solvers the difference found after 2 148 iterations. 420 www pnas org cgi doi 10 1073 pnas 0606359104 Elser et al. Table 2 The difference map compared with the CPLEX solver Table 3 Difference map performance compared with Walksat. on finding three colorings of the edges of complete graphs 18 on the same set of random 3 SAT instances. that avoid monochromatic triangles Difference map Walksat. Difference map CPLEX,n m Iterations sec Flips per n sec.
n Iterations sec sec,50 210 120 0 01 4 0 00,12 700 3 00 0 14 100 420 700 0 09 15 0 00. 13 1 100 7 00 0 70 200 840 14 000 3 50 150 0 03,14 4 000 50 00 10 00 500 2 100 3 300 2 10 30 0 02. 15 60 000 1 000 00 34 000 00 1 000 4 200 11 000 16 00 120 0 14. 16 26 000 700 00 105 2 000 8 400 580 000 2 600 00 4 200 12 00. Searching with iterated maps Sudoku combinatorial search global optimization phase retrieval in geometric language 11 12 Fienup s iterated map has the form protein folding xdynamical systems P hase retrieval algorithms provide an indispensable service to structural biology by deriving from x ray diffraction data the shapes of proteins viruses etc The task of these algorithms is

Related Books