Article Preview
Top1. Introduction
Many real-world problems contain multiple conflicting objectives and multi-objective optimization (MO) is gaining increasing attention from both practitioners and researchers. Aggregated objective function was often used to convert the multi-objective problems to single objective problems which can be solved by standard algorithms. However, the aggregated objective function required a set of weights based on the prior preference of the decision makers, which can only be applied subjectively because the decision makers have only little or no knowledge about the range of each objective functions. Besides, the fact that only single solution is found provides the decision makers with very little information about potential trade-offs. In order to solve this problem, the algorithm needs to be run several times with different set of weights and the cost of this approach is the high computational time. As a result, weight-free methods such as multi-objective Evolutionary Algorithm (EA) are preferred by researchers in this field because of their ability to find various non-dominated solutions on the Pareto front.
Srinivas and Deb (1994) introduced the Non-dominated Sorting Genetic Algorithm (NSGA), which can be considered as one of the first EA methods to deal with multi-objective optimization problems. The basic idea was to measure the fitness of each solution based on their dominance (with respect to all objective functions) in the population rather than a single objective value in traditional EA methods. The drawbacks of this method are the high computational complexity and the use of the pre-determined sharing parameter. Deb et al. (2002) introduced NSGA-II which could eliminate the problems with the old version by adopting an elitism structure and a measurement of the crowdedness. This algorithm had outperformed other MOEAs such as Pareto-archived evolutionary strategy (PAES) and strength- Pareto EA (SPEA) on many test problems.
Similar to the GA research community, the group of researchers interested in PSO have also developed new algorithms for multi-objective optimization. The most popular technique is to use an external archive to store the non-dominated solutions via the search of the swarm and to perform a selection procedure to choose the candidates to guide the search of each particle. Coello el al. (2002) proposed the idea to store flying experience in an external archive which is then updated by using geographically-based system. In their algorithm, the search area in the objective-space is divided into hypercubes. Each hypercube is assigned a fitness based on the number of particles it covers. Roulette-wheel selection is applied to choose the hypercube and a random particle from that hypercube is selected as the leader or global guidance for a particle in the swarm in each iteration. The disadvantage of this algorithm is that its complexity increases with the number of objective functions to be minimized. Fieldsend el al. (2002) improved this work by using a tree data structure to maintain unconstrained archive. More recently, Raquel et al. (2005) adopted the idea of crowding distance (CD) proposed in NSGA-II in their PSO algorithm as a criterion for selection of leader from the particles. In this method, when preparing to move, a particle will select its global leader from the top particles in the external archive which are sorted in decreasing order of CD. The same mechanism was also adopted by Li (2003) where two parameter-free niching techniques (niche count and crowding distance) are used to promote solution diversity. Other algorithms which were not based on non-dominance concept have been also proposed. Parsopoulos and Vrahatis (2002) introduced three types of aggregate functions which included a conventional linear aggregate function; a dynamic aggregate function and the bang-bang weighted aggregation approach aiming at generate concave portions of the Pareto front. Hu and Eberhart (2002) proposed a PSO algorithm for multi-objective problem in which only one objective is optimized at a time using a scheme similar to lexicographic ordering. The drawback of this algorithm is that it depends on the number of objective functions to be optimized.