The Application Research Of Virus Evolutionary Genetic Algorithm On Job-Shop Scheduling

Genetic Algorithm is a kind of random search algorithm that simulates biology evolutionary course. It is of self-control, self-adapative, self-study and population evolutionary ability for large-scale complex optimization problem. It shows the solution of the problem as the course of survival of the fittest of "chromosome " and through evolution of population, including copy, crossover and mutate, eventually converge to the fittest individual so as to get the optimum or satisfactory solution of the problem. With the development of computer technology, people pay more and more attention on GA, and it has been applied successfully in the fields such as machine learning, pattern recognition, nerve network, optimization control and combination optimization.Production scheduling problems nearly exits everywhere in the real environment, especially in the field of industrial project. A lot of real world scheduling problems are very complex essentially, so it is hard to solve with traditional optimization methods. Therefore, scheduling problems become a pet subject in the field of Genetic Algorithm. Because this problem show all features of constrained combination optimization problems, and become testing case of new algorithm.This paper put forward an improved Virus Evolutionary Genetic Algorithm mainly for Job Shop Scheduling Problem.First, the improved algorithm improves the generation of virus individual, in which, some virus individual is generated from some excellent host individuals and raises the fitness and infection ability of virus population. In the same time, the theory of steady-state reproduction is introduced into the improved algorithm and has avoided the lost of the problem optimum effectivelly. Second, the improved algorithm combines priority rule-based heuristic method and Virus Evolutionary Genetic Algorithm. So that on the one hand it improves the performance of initial host population through the heuristic algorithm, and on the other hand let it coordinate the virus infection, so as to strengthen local search ability, quicken evolutionary speed and convergence speed of Genetic Algorithm.Finally, the improved algorithm is tested using examples in the standard test set and the results show that the performance of the algorithm is obviously improved. The improved algorithm is also applied to resolve the actural JSP and the result is feasible and effective.