Memory-efficient Genetic Algorithm for Path Optimization in Embedded Systems

• Item type: Trans(1)
• 公開日: 2013-03-12
• タイトル: Memory-efficient Genetic Algorithm for Path Optimization in Embedded Systems
• タイトル / 言語: en
• タイトル: Memory-efficient Genetic Algorithm for Path Optimization in Embedded Systems
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [オリジナル論文] multi-objective shortest path problem (MOSP), Genetic Algorithm (GA), embedded systems
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Department of Production Science & Technology, Gunma University
• 著者所属: Department of Production Science & Technology, Gunma University
• 著者所属: Center for Communications and Information Technology Research, Research Institute, King Fahd University of Petroleum & Minerals
• 著者所属(英): en
• 著者所属(英): Department of Production Science & Technology, Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Production Science & Technology, Gunma University
• 著者所属(英): en
• 著者所属(英): Center for Communications and Information Technology Research, Research Institute, King Fahd University of Petroleum & Minerals
• 著者名: UmairF.Siddiqi; Yoichi, Shiraishi; SadiqM.Sait
• 著者名(英): Umair, F.Siddiqi; Yoichi, Shiraishi; Sadiq, M.Sait
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Multi-objective path optimization is a critical operation in a large number of applications. Many applications execute on embedded systems, which use less powerful processors and limited amount of memory in order to reduce system costs and power consumption. Therefore, fast and memory-efficient algorithms are needed to solve the multi-objective path optimization problem. This paper proposes a fast and memory-efficient algorithm based on a Genetic Algorithm (GA) that can be used to solve the multi-objective path optimization problem. The proposed algorithm needs memory space approximately equal to its population size and consists of two GA operations (crossover and mutation). During each iteration, any one of the GA operations is applied to chromosomes, which can be either dominated or non-dominated. Dominated chromosomes prefer the crossover operation with a non-dominated chromosome in order to produce an offspring that has genes from both parents (dominated and non-dominated chromosomes). The mutation operation is preferred by non-dominated chromosomes. The offspring replaces its parent chromosome. The proposed algorithm is implemented using C++ and executed on an ARM-based embedded system as well as on an Intel-Celeron-M-based PC. In terms of the quality of its Pareto-optimal solutions, the algorithm is compared with Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Simulated Annealing (SA). The performance of the proposed algorithm is better than that of SA. Moreover, comparison with NSGA-II shows that at approximately equal amounts of execution time and memory usage, the performance of the proposed algorithm is 5% better than that of NSGA-II. Based on the experimental results, the proposed algorithm is suitable for implementation on embedded systems.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Multi-objective path optimization is a critical operation in a large number of applications. Many applications execute on embedded systems, which use less powerful processors and limited amount of memory in order to reduce system costs and power consumption. Therefore, fast and memory-efficient algorithms are needed to solve the multi-objective path optimization problem. This paper proposes a fast and memory-efficient algorithm based on a Genetic Algorithm (GA) that can be used to solve the multi-objective path optimization problem. The proposed algorithm needs memory space approximately equal to its population size and consists of two GA operations (crossover and mutation). During each iteration, any one of the GA operations is applied to chromosomes, which can be either dominated or non-dominated. Dominated chromosomes prefer the crossover operation with a non-dominated chromosome in order to produce an offspring that has genes from both parents (dominated and non-dominated chromosomes). The mutation operation is preferred by non-dominated chromosomes. The offspring replaces its parent chromosome. The proposed algorithm is implemented using C++ and executed on an ARM-based embedded system as well as on an Intel-Celeron-M-based PC. In terms of the quality of its Pareto-optimal solutions, the algorithm is compared with Non-dominated Sorting Genetic Algorithm-II (NSGA-II) and Simulated Annealing (SA). The performance of the proposed algorithm is better than that of SA. Moreover, comparison with NSGA-II shows that at approximately equal amounts of execution time and memory usage, the performance of the proposed algorithm is 5% better than that of NSGA-II. Based on the experimental results, the proposed algorithm is suitable for implementation on embedded systems.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 6, 号 1, p. 1-9, 発行日 2013-03-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会