Parallel Problem Solving in Non-Equilibrium Environment Using Evolutionary Algorithms

点击翻译按钮获取中文摘要

(1) This paper addresses the problem of selecting the easiest-to-drive and quasi-shortest route to a given destination on a load map under a dynamic environment. The proposed solution is using a genetic algorithm adopting viral infection. The method is to use viruses as domain specific knowledge. A part of an arterial road is regarded as a virus. We generate a population of viruses in addition to a population of routes.(2) To evaluate dynamic route selection methods, we developed a traffic flow simulator that uses cellula automata in a non-equilibrium environment where traffic congestion occurs frequently. The simulator uses the S standard map of the Navigation System Researchers' Association, which is the map used in actual car navigation devices, and produces environments where spontaneous traffic congestion occurs.(3) A classification is established for the information required by drivers in selecting routes. The advantage of the method is that the driver's situation is expressed by environment information, destination information and vehicle information.(4) Experiments with the system in a dynamic environment built from a real road map show that the GA-based method is superior to the Dijkstra algorithm for use in practical car navigation devices. The only point on which the DA is superior is the time required. In contrast to this, the GA is superior in terms of amenity over the entire time-span. Other particular points of superiority for the GA include a computational time in response to changes in the environmental information and destination which is about 60 times faster, in response to changes in the environmental information alone, the GA is about 100 to 300 times faster.