A Study On The Theory And Applications Of Meta-Heuristic Optimization Algorithms

Computer science and technology has penetrated all walks of life and changed human societies from industry to daily life. However the current computer, especially the personal computer, is not powerful enough. It requires the computing task to be well-defined, fairly predictable, and computable in reasonable time. It generates unsatisfied performance on uncertain, dynamic, nonlinear, or multi-modal problems. So the human beings never cease to explore alternative computing techniques with high performance.Meta-heuristic optimization algorithms are one of the alternatives which have caught comprehensive attentions in these years. Meta-heuristic optimization algorithm refers to a general-purpose heuristic algorithm that can be used on different types of problems, including genetic algorithm, simulated annealing and some others. They are also called nature-inspired algorithms and have provided novel approaches for attacking complicated problems as mentioned above. In this dissertation two kinds of meta-heuristic optimization algorithms have been discussed. One is swarm intelligence technique including ant colony optimization (ACO) and particle swarm optimization (PSO). These two are both bio-inspired population-based algorithms. The other is microcanonical annealing (MA) algorithm which comes from physics. In the dissertation, several improved strategies about these algorithms are introduced by means of simulations. The whole paper consists of nine chapters listed as follows:Chapter 1 introduces the background of this work and presents brief reviews on swarm intelligence and microcanonical annealing. The main research contents and corresponding contributions are summarized in the end of this chapter.Chapter 2 provides relevant concepts of meta-heuristic optimization algorithm and divides it into two categories, the first searches the target space by a single solution, the second seeks optimal solution in a population-based way. The latter is also divided into two styles, one utilizes interaction among the population and the other works on interaction between individual and environment. Chapter 3 presents reviews on ant colony optimization. The main contents are made up of the algorithm background, basic paradigms and notable improvements, attempts of tackling continuous function, convergence researches and its applications.Chapter 4 gives surveys on particle swarm optimization. This section consists of biology background, canonical algorithms, well-known improvements and attempts of attacking discrete problem. Industry applications of particle swarm optimization are also listed in a short summary.Chapter 5 explains the theory background of microcanonical annealing and its implementation process on optimization. The simulations on benchmark show that this new annealing approach is faster than simulated annealing with comparative success rate. Microcanonical annealing requires fewer evaluations in success trials, so it will be a competitive algorithm in the circumstances attaching much importance to computing efficiency. The simulations also reveal that there is an optimal range for the initial upper bound (Emax) of demon's energy(E_D) and too large value will decrease the possibility of finding optimal solution. This observation is not consistent with Creutz who just claimed that the start value of Emax be considerably larger than the largest energy gap normally encountered. The decreasing coefficient should be a large value in order to provide high success rate, further more the simulations show that even if the coefficient is set to 1 the algorithm can also provide good performance as long as Emax be specified to an appropriate start value. Three improvements are proposed in this chapter, the first one called a history state conserving mechanism is designed to save a number of good states. Once the current state cannot be improved for certain iterations, the algorithm will sample a random state in the conserved queues and transfer to it. Simulations indicate this mechanism can accelerate the convergence process of microcanonical annealing if relevant parameters be set a proper value. The second one named energy enhancement strategy is to increase E_D to some extent when the optimization stagnates. Two kinds of energy enhancements are investigated including enhancement with upper bound and without upper bound. An approach to decrease the evaluation times under the improvement is also proposed. The last one is called energy shrinking which is combinded with a decreasing operation on E_D when E_D exceeds the threshold. At the end of this chapter, an application on frequency assignment problem by means of microcanonical annealing has demonstrated its promising future in network optimization. Chapter 6 discusses an extended particle swarm optimization which combines Gbest and Lbest to consider both global best particle and local best neighbor in the updating formula of velocity. Two kinds of weight assignment rules in the formula are proposed, the first one fixes the weight for each part but the performance is not outstanding, the second* one specifies a random weight for one of the parts. The simulations show that if the weight for global best part is a random value, the new algorithm outperforms Lbest in both success rate and evaluation times and is not sensitive to the other two weights on the benchmark.Chapter 7 applies a niche technique called sharing fitness to particle swarm optimization. Niche technique comes from bionomics and prevents similar individuals from gathering around a single individual. Two versions of this algorithm are proposed, one fixes the neighborhood structure (F-ShPSO) and the other constructs the neighborhood dynamically (D-ShPSO). The simulations on benchmark show that F-ShPSO provides a comparative success rate than Lbest with a lower fluctuating on the evaluation times. Furthermore it is not much sensitive to neighborhood size. D-ShPSO exhibits bad performance in the comparison and this result indicates the dynamic strategy in this context is not feasible.Chapter 8 introduces a two-stage implementation strategy for particle swarm optimization. The essence of this method is to divide the whole population into several subpopulations and an updating process is performed on the temporary colony composed of global best individual in each subpopulations. The updating formula of individual is not specified in the current approach. Simulations on multi-modal function reveal that it can enhance the success rate and decrease the sensitivity of weights in the traditional updating formula. The experiments demonstrate that the amount of subpopulations should be in an appropriate range to balance success rate and computation cost.Chapter 9 gives a summary of the whole dissertation and points out the limitations and potential directions in future research.