^{1}

^{2}

^{*}

^{2}

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. The incorporation of embedded rules enabled the genetic algorithm to locate the optimum path for all examples considered within 5% of the traditional genetic algorithm computation time.

Decision support has developed into a broad spectrum of applications encompassing optimization through a variety of methods including genetic algorithms [

The aim of this research is to illustrate the use of domain specific knowledge to enhance the genetic algorithm search through the minimization of computation time for solution convergence. Domain specific knowledge has been introduced into the genetic algorithm in the form of a two-phase rule approach to enhance both topological and structural optimization problems as demonstrated by Webb, et al. [

This study determines the appropriate path sequence to effectively negotiate a series of mazes within this prescribed research. Similarly to this optimization initiative, the use of domain specific knowledge was demonstrated by Alobaidi, et al. [

Traditional genetic optimization or scenario one began with a series of encoded strings which represents the framework of a maze under investigation. These encoded strings allow the genetic algorithm to determine whenever a move is selected (i.e. N, E, S, W) that the move is a legitimate move within the maze. A maze essentially is a predefined amount of space where a grid or lattice is formed which represents a series of rows and columns of square blocks. Each block formed within the lattice represents a “cell”. The surrounding walls of user specified cells are removed and the formation of a maze becomes apparent. The strings within this input file are four characters long which represent the directions of north, east, south and west respectively. Each character within the string can either represent the values of “0” or “1” to appropriately define each cell. A value of “0” for the first character within the first row indicates that there is a north wall within the first cell of the grid. Conversely, a value of “1” for the first character within the first row indicates an absence of a north wall within the first cell of the lattice. Each cell is labeled throughout the maze where the first block or entrance of the maze is designated by (1, 1), meaning row one, column one, and is located at the lower left corner as illustrated by the example in

Character Value | Representation |
---|---|

1 | North |

2 | East |

3 | South |

4 | West |

GENETIC INPUT PARAMETERS |
---|

Population Size = Maze Grid Size * 10 |

Probability of Mutation = 0.02 |

Number of Generations = (5 * Maze Grid Size) + Number of Best Generation Members to Pass to the Next Generation |

Penalty Factor = 10 |

Multiplier of Penalty Factor = 2 |

Number of Best Generation Members to Pass to the Next Generation = 2 |

Number of Generations Between Penalty Factor Updates = 10 |

utilized in the problem formulation for all mazes considered.

A random population of travel sequences is generated and evaluated by the objective function as illustrated in Equation (1). If deemed a legitimate move within the maze, the objective function calculates the total distance of each travel sequence, however the final result is path and distance weighted as illustrated in Equation (2), for the directional moves within the travel sequence are theoretically legitimate, but actual distances may not be calculated in the event N-S or E-W moves are introduced into the travel sequence. Once evaluated by the objective function, the best travel sequences are selected and placed within a mating pool, where travel sequences are randomly paired and genetic chromosome cross over commences. Chromosome cross over is the process of mating two parent travel sequence strings by the random selection of a numbered character shared by both strings. Once a shared character between both strings is selected, each chromosome string exchanges characteristics the right of the selected gene until the end of both chromosome strings has been reached. Subsequent to genetic cross over, each offspring produced is evaluated by the objective function, where directional moves within the new travel sequence are only implemented if legitimate within the maze. Illegitimate moves within travel sequences are simply ignored by the objective function and the travel sequence string is reduced in total length. This process continues until a predetermined number of generations of offspring have been produced. Mutation, or the random alteration of genes of a parent travel sequence string within the mating pool occurs, however the probability is minimal. Mutation introduces randomness, which provides the design or decision chromosomes with characteristics normally unattainable subsequent to a number of generated offspring. Upon the completion of a user specified number of generations, the genetic algorithm has potentially created a travel sequence string which encompasses the total or partial path which unites both start and end cells.

Objective Function:

f ( x ) = ( ( x actual − x final ) 2 + ( y actual − y final ) 2 ) (1)

Weighted objective function f ( x ) Weighted

f ( x ) Weighted = W 1 − W 2 ∗ ( ( ( x actual − x final ) + ( y actual − y final ) 2 ) − W 3 ∗ ( n p a t h − C ) ) (2)

where, n p a t h = total number of paths each cell move possesses that culminates the defined path.

x a c t u a l , y a c t u a l , x final , & y final are parameters which represent the start and end point locations of travel sequences for each maze considered which determine overall travel distance

W1, W2, & W3 are relevant weighting factors to balance out the outcome of the objective function with the number of moves required utilizing constant factor C. The use of a weighted objective function accounts for directional moves within the travel sequence; however actual distance values may not be calculated in the event N-S or E-W moves are introduced into the travel sequence

Domain specific knowledge in the form of rules were embedded within scenario one. These rules are governed by each travel sequence and the travel sequence is controlled by the genetic algorithm.

The cells which compose of the maze are initially predefined by how many exits each cell possesses and if the cell possesses only one exit, information is provided to which direction the available exit is located (i.e. N, E, S or W). When a cell is located within the travel sequence and only one exit is available, the genetic code is provided with what direction out the cell possesses. With this information, a wall is created to block off the cell, creating a block, so that no future travel sequences may enter. All cells are updated with the creation of this new wall and the process continues whenever a travel sequence encounters a one exit cell. This prescribed embedded rule is attributed by prior knowledge acquired from Williams [

The implementation of rules within the objective function subroutine which eliminate redundant moves before being drawn is controlled by the genetic code, since the travel sequence is governed by the genetic algorithm and rules are applied as travel sequences are introduced to the embedded rules. This also holds true for walls created when travel sequences encounter a cell with only one exit. The rule for the implementation of a wall is only executed if the genetic code generates a travel sequence which leads to a cell with only one exit. Computation time for solving all mazes considered was minimal with the inclusion of embedded rules.

Three mazes were investigated and solved by the use of both a traditional genetic algorithm and a genetic algorithm with embedded rules. Each maze scenario presented was programmed in Visual Basic [

Function evaluations considered are derived via Equation (3) below

FunctionEvaluations = Population Size ∗ Generation Size (3)

Below illustrated in

The traditional genetic algorithm result is shown below in

Maze Grid Size | Population Size | Generation Size | Function Evaluations |
---|---|---|---|

10 × 10 | 100 | 52 | 5200 |

20 × 20 | 200 | 102 | 20,400 |

50 × 50 | 500 | 252 | 126,000 |

completion of fifty two generations and an initial population size of one hundred, the genetic algorithm was unable to locate an acceptable solution. Population and generation sizes must be largely increased to potentially locate the maze solution. The objective function versus generation graph provided in

Below illustrated in

knowledge. Genetic input parameters were identical to the traditional genetic optimization result illustrated in

the traditional genetic algorithm technique, for the genetic algorithm is a global search method based upon an evolutionary approach.

Illustrated within

An examination of

The illustration within

genetic algorithm with an embedded rules approach applied to the 20 × 20 cell maze. Notice that all routes were not blocked, for the genetic algorithm found the optimal path without traveling to every available location, which further reinforced that the rules embedded are executed based upon travel sequences controlled by the genetic algorithm.

The final maze investigated consisted of a 50 × 50 cell maze [

The traditional genetic algorithm approach was unable to locate an acceptable solution shown in

genetic algorithm result; the genetic algorithm was able to locate a portion of the optimal path. Genetic input parameters consisted of a population size of five hundred and a generation size of two hundred fifty-two. Since an acceptable portion of the path was located, an increase in genetic input parameters would potentially improve the probability of locating a more acceptable solution in comparison to the previous 20 × 20 and 10 × 10 maze results. Surprisingly, the conventional genetic algorithm procedure failed to locate the complete travel path for each maze considered.

An examination of

The genetic algorithm which incorporated embedded rules was utilized to solve the 50 × 50 cell maze. Genetic input parameters remained identical to its counterpart. This optimization approach effectively solved the maze illustrated in

The implementation of embedded rules within a genetic algorithm based upon domain specific knowledge significantly decreases computation time and enhances the quality of offspring produced during each generation. A complete and accurate solution was located for all mazes investigated which employed the use of domain specific knowledge within a conventional genetic algorithm. The traditional genetic algorithm approach failed to solve each maze provided, while subjected up to extensively larger generations than its counterpart approach. Lastly, the genetic algorithm with embedded rules required only 5% of the solution time for all mazes considered in comparison to the traditional genetic algorithm

to locate an acceptable solution which effectively solved each maze.

Webb, D.J., Alobaidi, W.M. and Sandgren, E. (2018) Maze Navigation via Genetic Optimization. Intelligent Information Management, 10, 1-15. https://doi.org/10.4236/iim.2018.101001