Research On Shortest Path In Emergency System Using Parallel Genetic Algorithm

In recent years, emergencies frequently break up, we greatly pay attention to precaution of crisis management and accident, so we need construct the Emergency Decision System. The emergency system, using expert system and methodology base, research and locate knowledge, in order to assist decision. Knowledge accuracy and efficiency of decision system reaction are two chief points for weighing against the performance of Emergency Decision System. This paper is in the background of material schedule in Emergency Decision System, and makes a deep research of shortest path in emergency system using Parallel Genetic Algorithm.Firstly, this paper summarizes the developement and feature of emergency decision support system and parallel genetic algorithm. We introduce hardware system of parellel process and support software in the parallel environment. In the light of aid material schedule decision process in emergency system, making pretreatment for primitive road graph, the paper builds the adaptive net topology relationship. And we describe the shortest path problem in emergency decision support system with graphic theory term.Secondly, the point is this: we analyze the inherent potential parallel in Parallel Genetic Algorithm. In terms of master-slaveparallel programming design, we put forward a Parallel Genetic Algorithm of shortest path based on MPI in COW (cluster of workstation). We combine Annealing Algorithm with multi-group Parallel Genetic Algorithm and improve the Parallel Genetic Algorithm. So we make use of Boltzmann mechanism to accept the cross and variation individual and avoid the premature convergence problem existed in Parallel Genetic Algorithm, and enhance the global convergence. In the process of parallel algorithm design including partition, communication, combination and mapping, put forward the partition principle of genetic algorithm used to originate the groups.Finally in the experiment part we configure COW parallel environment and in the platform of Linux and MPI, we program the algorithm with C. The experiment results accord with the theory. This paper implements the parallel platform and Parallel Genetic Algorithm, and establishes the foundation for Emergency Decision System. By analyzing and comparing to experiment data, we compute the accelerated performance. Results show the algorithm has high fitness and optimized speed.But the size of this parallel algorithm is not enough .Genetic parameter is not allowed to modify, so is the content and time of message passing. What we can do is making it more perfect.