Maze Navigation via Genetic Optimization

作     者：David J. Webb Wissam M. Alobaidi Eric Sandgren 

作者机构：Axalta Coating Systems Front Royal Virginia USA Systems Engineering Department Donaghey College of Engineering & Information Technology University of Arkansas at Little Rock Little Rock Arkansas USA 

出 版 物：《Intelligent Information Management》 (智能信息管理（英文）)

年 卷 期：2018年第10卷第1期

页      面：1-15页

学科分类：1002[医学-临床医学] 100214[医学-肿瘤学] 10[医学] 

主　　题：Maze Navigation Genetic Optimization 

摘      要：One of the most interesting applications of genetic algorithms falls into the area of decision support. Decision support problems involve a series of decisions, each of which is influenced by all decisions made prior to that point. This class of problems occurs often in enterprise management, particularly in the area of scheduling or resource allocation. In order to demonstrate the formulation of this class of problems, a series of maze problems will be presented. The complexity of the mazes is intensified as each new maze is introduced. Two solving scenarios are introduced and comparison results are provided. The first scenario incorporated the traditional genetic algorithm procedure for the intended purpose of acquiring a solution based upon a purely evolutionary approach. The second scenario utilized the genetic algorithm in conjunction with embedded domain specific knowledge in the form of decision rules. The implementation of domain specific knowledge is intended to enhance solution convergence time and improve the overall quality of offspring produced which significantly increases the probability of acquiring a more accurate and consistent solution. Results are provided below for all mazes considered. These results include the traditional genetic algorithm final result and the genetic algorithm optimization approach with embedded rules result. Both results were incorporated for comparison purposes. Overall, the incorporation of domain specific knowledge outperformed the traditional genetic algorithm in both performance and computation time. Specifically, the traditional genetic algorithm failed to adequately find an acceptable solution for each example presented and prematurely converged on average within 54% of their specified generations. Additionally, the most complex maze generated an optimal path directional sequence (i.e. N, S, E, W) via a traditional genetic algorithm which possessed only 50% of the required allowable path sequences for maze completion.