Reasearching On High Performance Algorithms For Packing Unequal Spheres And Disks

NP-hard problem is widely encountered in real world. Efficiently Solving them is very critical for economy, research and military applications. Since whether NP is equal to P is still unsettled in theory, finding the gobal optimum of these problems become unreachable with the scale of the problem growing large. Even for a simple problem with very small scale N, i.e, equal circle packing problem with N=20, the exact global optimum of it is still not found (or certificated). So the designing of high performance heuristic algorithm to obtain a local optimum as close as possible to the globle one with available resources and within acceptable duration becomes the only reasonable method.This thesis concentrates on the research of high performance solving methods of two simple cases of NP-hard problems, which have very important real world applications: unequal spheres packing problem and unequal circles packing problem. We integrated several techniques such as Tabu Search, Iterated Local Search, Quasi-Newton method, Combined Neighborhoods search to solve these two problems. At the same time, in the purturbation phase of Iterated Local Search, we use CEGP (Critical Element Guided Perturbation) strategy, and deem the disks or spheres with larger radii as critical elements.The innovation of this thesis can be described as follows:1Using Iterated Tabu Search to solve the unequal disks or spheres packing problems for the first time.2Using Quasi-Newton method instead of traditional Quasi-Physical method in the continuous optimization phase, which is more fast.3During the procedure of Tabu Search, this thesis presents a new type of neighborhood for this problem, which is formed by inserting a relative small disk into a relative large vacncy.4We combine this new kind of neighborhood mentioned above and the traditional neighborhood formed by exchanging positions of two similliar disks, and use them alternately.5We use the "Making Lattice" method to determine vacancy of a configuration.6In the purturbation phase of Iterated Local Search, we use CEGP (Critical Element Guided Perturbation) strategy, and deem the disks or spheres with larger radii as critical elements.7In Quasi-Newton method, this thesis use a greedy strategy called Greedy-Redo to make the time complexity of most iterations of Quasi-Newton method decreased from O(n2) to O(n);8During the process of the Quasi-Newton Merhod, we set some "checkpoint". At the checkpoint, we compare the current potential to the corresponding checkpoint potential of the other neighborhood’s, and make immediate greedy cutoff decisions to spare time.9We devised an adaptive method for unequal sphere packing which makes the whole algorithm does not need an initial input container radius.By comparing the experiments outcomes with world records, one can observe that our algorithm gains an advamtage over most present algorithms. For a classical serial of benchmark instances ri=1/i-1/2, we beaten thirteen world records of it, ie:i=17-19and i=21-30; And for another classical serial of benchmark instances ri=i,we can match all the world records of N<=30.This thesis also analyzed the characteristics of the best configurations of seravel instances, including the relationship between container radius and number of small disks, the relationship between packing density and the number of small disks. The characteristics of small disks arrangement are also analyzed. The conclusion we drawn from the analysis will provide basis for further algorithm design.At the same time, the pros and cons of the heaustic function of potential are analyzed, we pointed out that the configuration with smaller potential not always corresponds a better configuration, but the errors are occasional and deviations are acceptable, and we also come out with some resorts to mitigate the disadvantage caused by it.