Research On Method Of Combinatorial Optimization Based On State Transition

It is impossible to tackle all combinatorial optimization problems (COP) in deterministic polynomial time with accurate solution. People are exploring different searching strategy with high efficiency to tackle COP with large scale. But it is difficult to get the optimal solution of COP and its approximation is adopted widely in practice instead of the optimal solution. Current approximation methods avoid being trapped in local optimal with heuristic strategies and much useful information about the problem is unused. So these methods cannot avoid repeated searching. In this thesis a method of combinatorial optimization based on state transition (MCOBST) is proposed. It may reduce searching range and decrease repeated searching greatly and get the optimal solution or approximation with higher quality quickly. It is used to get the solution of combinatorial optimization problems here. The contributions are listed as follows.MCOBST is a hybrid method and comprises many methods. Problems are classified by different domain knowledge in order to get better solution with different approximation to each type of problem. The solution of COP is improved iteratively while the dimension is reduced by dimensional reduction on the basis of the bound, current optimal solution and other useful information. Exact solution is adopted to get the remaining of the original problem. The first method of dimensional reduction proposed in this thesis is dimensional reduction by comparison between the current optimal solution and bound of the problem. It is the basis of other dimensional reduction methods such as the dimensional reduction by comparison according to the relation among the elements, dimensional reduction based on the feature value, dimensional reduction by decomposition of the problem, dimensional reduction by reasoning and dimensional reduction based on evaluation function. The methods of improving approximation proposed here are combined with bound algorithm to simplify the original problem step by step. The exact solution proposed to the remaining of COP is a hybrid method combined with dynamic program, bound algorithm and heuristics.Research on examples is to get the general solution of them with MCOBST. Examples include three-machine permutation flow-shop problem (PFSP), 0/1 knapsack problem (KP01), traveling salesman problem (TSP) and weapon-target assignment problem (WTA) in tank war.A better lower bound algorithm to three-machine PFSP is proposed here. It may be used to choose the first job processed in approximation of three-machine PFSP. An evaluation function constructed here is used to select the next job of solution one by one. It is useful to get better solution by changing the first job processed or parameters in the evaluation function. Experiments show that the makespan is very close to the lower bound and the solution is almost the optimal. Compare to the current methods, the solution of three-machine PFSP with this method is better and less computation is needed. An approximation to PFSP with machines more than three is also proposed. A heuristic bi-directional breadth first (HBBFS) algorithm combined with lower bound algorithm and approximation is proposed to get the accurate solution of PFSP. Experiments show that only fewer searches are needed for the accurate solution when sum ofmachines in PFSP is few.Currently quick exact solution to 0/1 knapsack problem is valid only to those problems without relation between price and weight of instance or price is linear correlated to weight of instance. It is invalid to most problems when the price is nonlinear correlated to the weight of the instance in KP01. Upper bound algorithms, dimensional reductions and methods to improve approximation are proposed to simplify the knapsack problems in this case. Exact solution is adopted to tackle the remaining of the original knapsack problem in this case and get the accurate solution quickly.An approximation and a lower bound algorithm on the basis of the minimum 1-tree are proposed. Better structure of the minimum 1-tree f...