| Genetic Algorithm (GA) is a new subject. Its application began to flourish since the eighties of the 20's century. The Genetic Algorithm (GA) is a new parallel optimize algorithm, which can be used to solve many kinds of NP-hard problems.But standard Genetic Algorithm has some faults. In order to overcome these faults, we designed a new hybrid genetic algorithm--Simultaneous Evolution Genetic Algorithm (SEGA). This SEGA is different from traditional GA in evolution manner, and then we use Markov modeling to analysis our SEGA. It is a global search algorithm which combines the respective advantages of hybrid genetic algorithm and neighborhood search algorithm. It has a global searching capacity of genetic algorithm as well as effective local searching capacity. This algorithm resolves contradictions between two different kinds of algorithms. The experimental research shows SEGA has a good performance of global searching.With the development of the problems, the searching space becomes more and more complicated. The optimization time and the optimization quality of GA can't keep up with the actual demand. In order to solve the massive complicated optimization problems, the author analyzes the parallelization principle and the application environment of Parallel genetic algorithm, and presents a kind of Extended Network-based Distributed Genetic Algorithm (ENDGA) which combines the respective ideal of SEGA and parallel genetic algorithm. The key implementations of ENDGA are discussed; we use Markov modeling to analysis our ENDGA; the corresponding program flow is also given.In this paper, we presented a kind of PGA which is based on distributed computation of the network for solving identical parallel machine scheduling problem with constraint, and computational results show that ENDGA can not only save the optimization time evidently but also largely improve the optimization quality, which provides an effective solution to massive complicated optimization problems. |
PDF Full Text Request