Several NP-complete Problem Solving Algorithm Research
|Keywords||Circle permutation Model Hybrid genetic algorithm Branch and bound algorithm Region deletion strategy|
This paper studies solving two NP-complete problems (circle permutationproblem and a kind of nonlinear sum of ratios problem).Firstly, for the general circle permutation problem, we give themathematical model of the problem, and further get the condition that themathematical model of the general circle permutation problem can bedegenerated to the model of the special circle permutation problem solved bythe existing literatures. Furthermore, an optimal solution of the model of thethe special circle permutation problem is given, and the results show that thecircle permutation problem with condition is not necessarily NP-completeproblem.Secondly, based on an optimal solution of the special circle permutationproblem, we put forward a heuristic algorithm for solving the general circlepermutation problem. For the circle permutation problem group by300-3000rounds whose radius are any one in [1,3000], take1000experiments, and theexperimental results show that the average approximation ratio of thealgorithm is not more than1.048. These show that the heuristic algorithm forsolving the general circle permutation problem is feasible.Thirdly, in order to improve the accuracy, the genetic algorithm isintroduced. Based on the heuristic algorithm, we design a hybrid geneticalgorithm for solving the general circle permutation problem. Furthermore, wetake a lot of contrast experiments on the performance of the the heuristicalgorithm, genetic algorithm and the hybrid genetic algorithm for solving thecircle permutation problem. The experimental results show that the threealgorithms have a good average approximation performance ratio, and theaverage approximation performance ratio of the hybrid genetic algorithm isthe best. In addition, the hybrid genetic algorithm has the ability for solvinglarge scale problems. Finally, we study a class of nonlinear sum of ratios problems widely used inthe economic, traffic and other fields. We first transform the problem to theequivalent problem. Then, by using the inequality scaling method on theequivalence problem, we obtain the linear programming relaxation model ofthe equivalent problem. Based on the above relaxation model, we put forwarda branch and bound algorithm for solving the equivalent problem. Furthermore,based on the above relaxation model, we put forward region deletion strategy,and prove the convergence of the algorithm. Finally, we make some numericalexperiments. These numerical examples show that the algorithm is feasible.