Research On Parallel Evolutionary Algorithms For Solving Combination Optimization Problem

TSP (Traveling Salesman Problem) is a problem of combination optimization with simple definition but difficult to be solved, which attracts many researchers in various fields including mathematics, physics, biology and artificial intelligence (AI). It has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. But to all computers nowadays, it's hardly to obtain its best answer in such huge researching space by using common enumeration. Therefore, all kinds of algorithms to solve TSP came into being because of demand. Among of them, evolutionary algorithm (EA) is one of advanced technologies.EA itself has the intrinsic parallel mechanism, so it has the possibility of parallel compute on a large scale. Furthermore, EA always trends to converge early, while parallel EA may avoid it to some extent. So, it's necessary to study parallel EA. These two factors decide that parallel EA will become an important researching part of EA. Firstly, this paper practiced a distributed EA based on distributed environment, according to the existent framework, and tested its performance with experiment. After that, the author optimized it, and tested the performance of the optimized distributed EA: Firstly, made the migration individual vary with the parameters such as the scale of group, the migration intervals, instead of setting it 'one ' evermore; secondly, changed the synchronized communication into the semi-synchronized communication. The experiment showed that the optimized algorithm had a better performance of convergence.Then, a multi-thread EA algorithm was mentioned. In fact, multi-thread EA was one of parallel EAs. But the research on it just began without available theory or framework to use. The computational power of a multi-thread EA can't be mentioned with other EAs because it runs on single-handed PC. However, it has the superiority of convenient communication because the threads in this algorithm have public memory space. So this multi-thread EA algorithm put emphasis on designingreasonable communication steps. There were complex communications between the threads. The experiment showed that this multi-thread EA could get better answers than the distributed EA could.Finally, the paper explained its idea to design a distributed evolutionary algorithm about two-level-communication based on the distributed system. The realization of this blueprint will be the next focal point.