Heuristic Algorithms For The Circle Packing Problem And The Cluster Structure Optimization Problem

NP hard optimization problems arise in many scientific and engineering applications and play a key role in their respective area. However, previous study on computational com-plexity has shown that, for NP hard problems, it is very possible that there does not exist algorithms which are both complete and efficient. Up to now, all the complete algorithms proposed for the NP hard problems have exponential time complexity, they are only applica-ble to small-scale instances or instances with special property. To solve many complex and large-scale real-world problems practically, researchers turn their attention to incomplete heuristic algorithms. Meanwhile, research experiences in the last decades have shown that, good heuristic algorithms can solve many challenging problems efficiently and effective-ly because they can usually find high-quality solutions in a reasonable computation time. Heuristic optimization has become a hot topic in computer science, artificial intelligence and operations research.In this thesis, we first present a systematic review of the theoretical background, de-sign schema and evaluation criteria of the heuristic optimization algorithm. Then, we carry out research on two classic and very important problems:the circle packing problem and the cluster structure optimization problem. We propose efficient heuristic algorithms for these problems and then evaluate and analyze the proposed algorithms via computational experiments. The main contributions of this thesis can be summarized as follows:(1) A quasi-physical global optimization algorithm is proposed for the problem of pack-ing equal circles in a circle. The algorithm includes three important procedures:a quasi-physical descent procedure, a quasi-physical basin hopping procedure and a container ad-justing procedure. The first two procedures respectively simulate two kinds of movements of n elastic disks:smooth movement driven by elastic pressures and violent movement driven by strong repulsive forces and attractive forces. The smooth movement makes the disks reach a locally optimal configuration, while the violent movement makes them jump out of the local optimum trap and reach a more promising place. The third procedure, the container adjusting procedure, adjusts the container to a proper size such that the contain-er is minimal and no overlap exists. The proposed algorithm is tested on the instances of n=1,2,…,200. Though many researchers have searched these instances using various methods, we can still find63new packings better than the best-known ones reported in the literature.(2) A greedy vacancy search algorithm is proposed for the problem of packing equal circles in a square. A physically inspired model is first proposed to formulate this problem. Then we proposed a greedy vacancy algorithm which iteratively improves a packing by moving a circle to the most vacant area in the container. The proposed algorithm is tested on the instances of n=1,2,…,200. Though many researchers have searched these instances using various methods, we can still find41new packings better than the best-known ones reported in the literature.(3) An effective and efficient heuristic algorithm is proposed for structure optimization of binary Lennard-Jones clusters. Global optimization of binary Lennard-Jones clusters is a challenging problem in computational chemistry. The difficulty lies in not only that there are enormous local minima on the potential energy surface, but also that we must determine both the coordinate position and the atom type for each atom and thus have to deal with both continuous and combinatorial optimization. This thesis presents a heuristic algorithm (denoted by3OP) which makes extensive use of three perturbation operators. With these operators, the proposed3OP algorithm can efficiently move from a poor local minimum to another better local minimum, and detect the global minimum through a sequence of local minima with decreasing energy. The proposed3OP algorithm has been evaluated on a set of96×6instances with up to100atoms. We have found most putative global minima listed in the Cambridge Cluster Database, as well as discovering12new global minima missed in previous research.