Heuristic Algorithms For The Protein Structure Prediction Problem And The Rectangles Packing Problem

Solving NP-hard problems is always the bottleneck task in the field of computer science and technology. In recent years, investigations show that for NP-hard problems, there may not exist an algorithm that is both complete and rigorous and not too slow. So its solution methods are generally heuristic. The protein structure prediction problem and the rectangles packing problem are NP-hard problems. Solving them has profound theoretical significance and universal practical value. Inspired by the wisdom of nature and human being, we proposed some effective heuristic algorithms to solve these two NP-hard problems. The main works are as follows:A three-dimensional off-lattice protein AB model was studied, where two species of amino acids, hydrophobic and hydrophilic, were considered. Enlightened by the law of forces among things in the physical world, a corresponding quasi-physical algorithm was put forward for the protein structure prediction problem. By observing and learning from problem structure, high efficient heuristic strategies were presented, including producing the initial configurations and jumping out of traps. These approaches could effectively avoid falling into local minima, and even if the search fell into local minima, the calculation could get out of them and reached better prospects positions. The heuristic quasi-physical algorithm was proposed by integrating the heuristic strategies into the quasi-physical algorithm. For all instances in literature, the proposed algorithms found the configurations with lower energy than those obtained by PERM+, which integrated the off-lattice PERM (Pruned-Enriched Rosenbluth method) and conjugate gradient minimization.A heuristic conjugate gradient (HCG) algorithm was presented for the protein structure prediction problem of the AB model. The algorithm firstly produced initial configurations in three-dimensional Euclidian space by the heuristic method, and the conjugate gradient minimization was then used to optimize low-energy configurations. Once the computation fell into the local minima, the heuristic off-trap strategy was used to get out of the predicament. The HCG algorithm was applied to the AB protein model to predict protein structure. The computing results showed that for sequence with length n=55, the HCG algorithm found the configurations with lower energy than those nowadays given in literature.Inspired by the PERM+ algorithm, a so-called PERM++ algorithm based on face-centered-cubic (FCC) lattice was put forward to solve the protein structure prediction problem of the AB model. In PERM++, the initial configurations were produced by applying the PERM to the FCC lattice, and conjugate gradient minimization was then used to reach the minimum energy states. The numerical results showed that the performance of the PERM++ algorithm outperformed that of the PERM+.A technical shortcoming in ELP was revealed. In order to overcome it, a local search method based on the quasi-physical strategy was presented. An improved ELP algorithm (ELP+) was proposed as the integration of the local search method and the ELP method. The calculating results showed that for several of amino acids chains studied, the ELP+ algorithm found the configurations with lower energy than those by PERM+, by multicanonical (MUCA) Monte Carlo method, by energy landscape paving (ELP) method, and by conformational space annealing (CSA) algorithm, respectively.Based on the quasi-human strategy, we proposed the so-called corner-occupying and the largest hole degree first placement policy based on Euclidian distance. An effective heuristic algorithm was presented, and this algorithm could obtain the solution to the rectangles packing problem quickly. Experimental results on MCNC and GSRC benchmark circuits showed promising performance. As compared with other public algorithms, the proposed algorithms could get better results.Finally, based on the quasi-human strategy, the hole degree algorithm and the improved hole degree algorithm were proposed to solve the modules placement problem with pre-placed modules. Experimental results on MCNC benchmark circuits demonstrated that the proposed heuristic deterministic algorithm was quite effective in solving the problem and outperformed the stochastic optimization placement algorithms based on corner block list (CBL) and B*-tree type representations, respectively.In a word, two NP-hard problems, the protein structure prediction problem and the rectangles packing problem were studied in this dissertation. Inspired by nature, human being and problem structure, we put forward some effective algorithms to solve them. Experimental results showed that simulating the moves of things in nature and the actions of human being was an effective way of designing high-performance algorithms. These approaches have universal practical value for studying and solving other NP-hard problems. Since the protein structure prediction problem and the rectangles packing problem are open problems, there are still some other questions need to study.