Translated Abstract
Ant colony optimization (ACO) algorithm is a typical swarm intelligence optimization algorithm inspired by the foraging behavior of real ants. ACO algorithm uses pheromone as a medium to share the information among ants. Positive feedback mechanism generated by pheromone updating makes more and more ants concentrate to the region of optimal solution. Finally ACO algorithm will achieve the optimal solution. Now, it has been widely applied to the fields of combinatorial optimization, functional optimization, machine learning, and image processing, etc., and good effects of application are gained. It has become an effective tool for hard optimization problem due to its adaptability, robustness, and distributed computing. This dissertation systematically investigates improvements of ACO algorithm model, applications of ACO algorithm, and the evaluation of ACO algorithm solution performance on the basis of analyzing and studying ACO algorithm basic principles. The main achievements of this dissertation include the following aspects:(1) A simple ant colony optimization (SACO) is proposed based on Max-Min ant system (MMAS). In SACO, the upper and lower bound of pheromone trail are set to be constant, and the updated quantity of pheromone trail is determined by the upper bound and evaporation coefficient. Its main characteristics are that the pheromone model is simplified and pheromone trail is independent of the objective function values. Simplified strategies are used to eliminate the drawbacks of MMAS. The parameters setting and convergence of SACO are analyzed theoretically. Numerical experiments are carried out on the traveling salesman problem (TSP). Compared with MMAS, computational results show that the SACO is effective and robust.(2) A two-stage updating pheromone for invariant ant colony optimization (TSIACO) is proposed. A number of suboptimal solutions are produced during the iterative process of ACO. In order to reasonably use them and keep the balance between exploration and exploitation, the updating process of pheromone is divided into two stages. The first stage is ordinal update stage. All ants are sorted by fitness, and then the top rank of ant gets a certain updated quantity according to their order. The second stage is one solution update. Only optimal ant can obtain updated quantity. Moreover, with the purpose of possessing invariance for TSIACO, the upper and lower bound of pheromone trail are set to be constant, and the independent variable of quality function is solution order. It is proved that not only the TSIACO is an invariant algorithm but also its performance is not affected by the limits of pheromone under certain condition. Experimental results show the feasibility and effectiveness of presented algorithm.(3) In order to further investigate the performance of TSIACO, it is applied to solve multi-satellite TT&C resource scheduling problem (MuSTSP). MuSTSP is a kind of large combinatorial optimization problem belonging to the aerospace field, which has the characteristics such as various types of elements, complicated constraints and many objectives to be optimized at the same time. Aiming to minimize the working burden as optimization objective, the optimization model of MuSTSP, called complex independent set model, is developed based on visible arcs and working periods. It is suitable for solving by ACO. The effect of parameters on the algorithm’s performance is studied by experimental method. The experiment results demonstrate that the global exploration ability and solution quality of the TSIACO is superior to existed algorithms such as genetic algorithm, iterative repair algorithm and MMAS.(4) Due to the theoretical issue of evaluating the quality of the ACO solutions in a finite time, the further research is carried out. After analyzing existing work, the research objective is transferred to the ordinal performance of solution rather than value performance. With the inspiration of ordinal optimization, an evaluation method of ordinal performance is proposed for solution produced by ACO. The method is based on studying characteristics of problems which are suitable to be solved by ACO and the feasible solution produced by ACO. Firstly, with the help of clustering method, a number of uniformly-distributed subclass is obtained from solution samples produced by ACO. Then, the “good enough” subset is decomposed according to the ordered performance curve of problem and characteristic of ACO. Finally, the alignment probability is calculated. Taking TSP as an example, detailed procedure of the evaluation method is given, and experiments are given to validate the method.
Corresponding authors email
