Parallel Evolutionary Algorithm And Its Application On The Combinatorial Optimization Problem

Many combinatorial optimization problems are Nondeterministic Polynomial time complete (NP-complete). It is difficult to solve these combinatorial optimization problems by polynomial-time optimization algorithm, and the running time of an algorithm for these problems will be increased exponentially with growth of the problem size. Though it can not be sure that an evolutionary algorithm can find an optimal solution for an NP-complete problem within polynomial time, it has been demonstrated by a lot of application problems that it can find solutions good enough and can often find better solutions than traditional heuristic algorithm. The main work of this thesis is as follows:First,a novel evlutionary algorithm is proposed for multi-objective minimum spanning tree problem. The spanning tree is encoded directly by the set of its edges, and a novel algorithm for generating initial population of the spanning trees is presented. Moreover, a new crossover operator is designed. Second, a new evolutionary algorithm is proposed for the degree-constrained spanning tree problem. In the algorithm, the method for generating initial population and the crossover operator are carefully designed. The simulation results indicate these two proposed algorithms are effective. Third, an efficient enumeration algorithm is proposed for solving the constrained minimum spanning tree problem. At last, a new parallel evolutionary algorithm based on multithread is proposed for multi-objective minimum spanning tree problem. The numerical experiments on a computer with the Intel dual-core processor show that the average speedup ratio of the proposed parallel evolutionary algorithm is over 2, and the algorithm based on multithread can find better results than the algorithm based on single thread.