A Global Optimization Algorithm Based On Breeding Idea: Principle, Performance And Applications

As a quantitative analysis method, the aim of optimization technique is to search for the optimal values of the variables based on the specific index of the objective system. But it is difficult for the present algorithms to answer satisfactorily that whether there are better solutions than those in hand. A few of optimization algorithms included genetic algorithm (GA), can converge to the global optimum with probability 1 when undergoing infinite iterative calculations which can not be easily achieved in practical operations. Hence, the research work on developing more effective algorithms and strategies to enhance the effectiveness of optimization computation, and on the evaluating the optimal results to supply more reliable information for decision, attracts more and more attentions in this field. This paper starts the study on the above problems based on genetic algorithms. The main work and contributions are as follows.1. Based on the theoretical and experimental research, the problems in the globability and accuracy of optimization existing in GA is analyzed. It is revealed that the pitfalls and dilemma existing in the genetic algorithm in which the operations of exploration and exploitation are executed simultaneously and hence, a reasonable direction for the choice and improvement of the strategies of global optimization is designated.2. A new kind of evolutionary computation, identified as breeding algorithm (BA) is presented by borrowing the idea of modern breeding. BA separates the global optimization process into two independent operations named as seed selection by random sampling to achieve exploration and breeding by gene replacement to perform local search. The principle and model of BA to achieve the global optimization are constructed. The testing results show that BA can achieve more accurate search in the same probability of global optimization and with less than 1/2 of computation cost of GA.3. According to the process of seed selection by random sampling, the concept of sensitivity of exploration is proposed. A method of evaluation on the globablity of the solution is designed based on the number of sampling and best sample.4. The local search mechanism of gene replacement is analyzed and described. According to the characteristics of the codes after gene replacement, the technique to cope with the Hamming cliff phenomenon often emerging in binary encoded GA is proposed, and this guarantees that BA can achieve the upmost accuracy of computation under binary encoding. At the same time, the computation cost for the operation of gene replacement to perform local search is analyzed and estimated and the upper limit of iteration number is given.5. The implementation and variety of the algorithm are studied in the paper. In correspondence with the properties and constitution of the complex optimization problems, the relevant strategies are suggested. For the constraint optimization problems, the method to decide the penalty coefficient is presented. The results by testing over 40 classical problems with variables of 1 to 50 show that BA is advantageous over the conventional GAs both in global and local search. Further more, BA successfully renews the records of optimal solutions of some complex problems,6. This paper studied effectiveness of parallel BA when being applied to solve multi-objective optimization problems. The testing results show that the parallel BA is very effective in the solution of Pareto set. Further more, as a try to dispose the sensitivity of optimization often occurring in the multimodal processing systems, a new concept of average-effectiveness optimal solution (AEOS) is proposed. AEOS is based on the evaluation to the average effectiveness of the system controlled by some uncertain or fluctuating parameters. The concrete method of access to AEOS combined with parallel BA is demonstrated by means of optimization to a practical process system.7. Finally, the basic implementation flowchart of BA in solution of engineering optimization problems is given, and the relevant operational strategies are described in the paper.In conclusion, as compared with conventional genetic algorithms, BA is more specific in principle, simpler in structure, more accurate and effective in computation. It is suggested to be as a candidate of engineering optimization methods.