Research On Backtracking Search Algorithm With Its Engineering Applications

Optimization model is one of the basic tools to analyses and solve scientific and engineering problems. With the continuous development of science and technology, these problems are more and more complex, and often appears characteristics of larger scale, discrete, nonlinear, non-differentiable and non-convexity etc. Therefore, the study of methods to solve this kind of complex model has been the forefront in domestic and overseas research field. Due to the high efficiency characteristic when dealing with these complex models, intelligent optimization algorithms are paid more attention, and are becoming the research topics in the field of intelligent computing and engineering optimization. In this paper, a new born intelligent optimization algorithm called Backtracking Search Algorithm(BSA) is studied. Some research about this algorithm, such as detail descriptions and analyses about BSA, applying BSA to solve constrained problems and combination optimization problems after certain improvements, and two application cases, are also introduced.Firstly, the basic principle, flowchart and main operators of BSA are introduced. The advantages and disadvantages of BSA are analyzed, which lays the foundation of improvements.Secondly, after analyzing the difficulties when solving constrained problems and the disadvantages of current constraint handling mechanisms, the self-adaptive ?(SA?) constraint handling mechanism is proposed. 13 classical constrained optimization test functions are used to verify the efficiency of the proposed SA?, and demonstrate the advantages of SA?-based BSA(BSA-SA?) in terms of convergence speed and searching precision.Thirdly, after factorizing solution space, changing crossover and mutation operators, introducing simulated annealing mechanism and random inserting local search method, we propose a Hybrid Backtracking Search Algorithm(HBSA) to solve Permutation Flow-shop Scheduling Problems(PFSPs), which belong to combination optimization problems. 29 standard test functions are used to verify the validity of the random inserting local search method and the efficiency of HBSA in dealing with this kind of discrete problems.Then, the proposed BSA-SA? and HBSA in above two chapters are applied to the parameters optimization of structural design and scheduling optimization of connecting rod production workshop, respectively. These engineering cases illustrate the efficiency of BSA-SA? and HBSA, and reflect their broad application prospect in scientific research field and engineering practice.Lastly, the thesis is summarized, and the future research is prospected.