Font Size: a A A

Multi-objective Evolutionary Algorithm And Its Application In Optimization Problems

Posted on:2005-06-17Degree:MasterType:Thesis
Country:ChinaCandidate:F LiFull Text:PDF
GTID:2168360122490328Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
Many real-world problems involve two types of problem difficulty: i) multiple, conflicting objectives and ii) a highly complex search space. On the one hand, instead of a single optimal solution competing goals give rise to a set of compromise solutions, generally denoted as Pareto-optimal. In the absence of preference information, none of the corresponding trade-offs can be said to be better than the others. On the other hand, the search space can be too large and too complex to be solved by exact method. Thus, efficient optimization strategies are required that are able to deal with both difficulties.Evolutionary algorithms possess several characteristics that are desirable for this kind of problem and make them preferable to multi-objective optimization methods. In fact, various evolutionary approaches to multi-objective optimization have been proposed since 1985, capable of searching for multiple Pareto optimal solutions concurrently in a single simulation run. SPEA2 is one of the art of the date algorithms. The algorithm is a new multi-objective optimization evolutionary algorithm using elitism, in which fine-grained fitness assignment strategy, a density estimation technique, and an enhanced archive truncation method are used. The algorithm can converge to the Pareto optimal solutions rapidly and the non-dominated solutions gain better distribution and spread.Genetic algorithm is a class of effective algorithms based on natural selection and principle of genetics. Though GAs can find the compromise solutions in limited time, improving the speed of GA is an important issue when the problem is more complex and difficult. GA poses implicit parallelism and is suitable for implementation on large scale parallel computers. Dividing the whole population into sub-populations and coarse-grained island model of exchanging information among sub-populations are the most direct parallel method.A Parallel Strength Pareto Multi-objective Evolutionary Algorithm (PSPMEA) is proposed. PSPMEA is a parallel computing model designed for solving Pareto-based multi-objective optimization problems by using an evolutionary procedure. In this procedure, both global parallelization and island parallel evolutionary algorithm models are used. Each sub-population evolves separately with different crossover and mutation probability, but they exchange individuals in the elitist archive. In each sub-population, breeding and evaluation are implemented using multi-threaded mechanism. The benchmark problems numerical experiment results demonstrate that the proposed method can rapidly converge to the Pareto optimal front and spread widely along the front.Using the continuous test problems and the combinational test problems we compare the two algorithms: PSPMEA and SPEA2. Elitism, size of the population and exchanging among sub-populations are the key issues in PSPMEA. The results also show the PSPMEA is a promising parallel multi-objective evolutionary algorithm.
Keywords/Search Tags:genetic algorithm, multi-objective optimization, parallel genetic algorithm, elitism, multi-sub-population
PDF Full Text Request
Related items