Parallel Problem Solving in Non-Equilibrium Environment Using Evolutionary Algorithms

(1)研究了动态环境下，在负载图上选择到达给定目的地的最短路径和准最短路径的问题。所提出的解决方案是使用遗传算法，采用病毒感染。该方法是使用病毒作为领域特定的知识。主干道的一部分被视为病毒。我们生成了一个病毒种群，以及一个路由种群。(2)为了评估动态路径选择方法，我们开发了一个交通流模拟器，使用细胞自动机在非平衡环境中，交通拥堵频繁发生。模拟器使用导航系统研究者协会的S标准地图，这是实际汽车导航设备中使用的地图，并产生发生自发交通拥堵的环境。(3)对驾驶员选择路线所需的信息进行分类。该方法的优点是驾驶员的情况由环境信息、目的地信息和车辆信息来表示。(4)在一个动态环境中的实验表明，该系统在真实的道路地图建立基于遗传算法的方法是上级的Dijkstra算法用于实际的汽车导航设备。DA唯一的上级是所需的时间。与此相反，GA在整个时间跨度的舒适性方面是上级的。GA的其他特定优势点包括响应于环境信息和目的地的变化的计算时间快约60倍，仅响应于环境信息的变化，GA快约100至300倍。

(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.