Parallel Problem Solving in Non-Equilibrium Environment Using Evolutionary Algorithms

使用进化算法解决非平衡环境中的并行问题

• 批准号: 13680430
• 负责人: KANOH Hitoshi
• 金额: $ 0.9万
• 依托单位: UNIVERSITY OF TSUKUBA
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13680430/
• 关键词: Genetic Algorithm; Cellular Automata; Non-equilibrium; Path Planning; Digital Road Map; Car Navigation; 地図

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

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

项目成果

狩野均: "知識の集団を用いたGAによる不特定な立ち寄り地を含む経路探索"人工知能学会 論文誌. Vol.17,No.2. 145-152 (2002)

Hitoshi Kano：“通过 GA 使用知识组进行路线搜索”，《日本人工智能学会汇刊》第 17 卷，第 145-152 期（2002 年）。

狩野均: "Evaluation of GA-Based Dynamic Route Guidance for Car Navigation Using Cellular Automata"IEEE Proc.of Intelligent Vehicle Symposium. (印刷中). (2003)

Hitoshi Kano：“使用元胞自动机评估基于 GA 的汽车导航动态路线指导”IEEE Proc.of 智能车辆研讨会（2003 年出版）。

小塚英城, 狩野均: "Traffic Flow Simulation using Cell Automata under Non-equilibrium Environment"IEEE Proc.of International Conference on Systems, Man, and Cybernetics. 1341-1345 (2001)

Hideki Kozuka、Hitoshi Kano：“非平衡环境下使用元胞自动机进行交通流模拟”IEEE Proc. of International Conference on Systems, Man, and Cyber​​netics 1341-1345 (2001)

Hideki Kozuka and Hitoshi Kanoh: "Traffic Flow Simulation using Cell Automata under Non-equilibrium Environment"IEEE Proc. of International Conference on Systems, Man, and Cybernetics. 1341-1345 (2001)

Hideki Kozuka 和 Hitoshi Kanoh：“非平衡环境下使用元胞自动机的交通流模拟”IEEE Proc。