Extending Graph Based Evolutionary Algorithms with Novel Graphs

Graph Based Evolutionary Algorithms (GBEAs) are a novel modification to the local mating rules of an evolutionary algorithm that allow for the control of diversity loss by restricting mating choices. Graph structures are used to impose an artificial geography on the solution set to mimic geographical boundaries and other mating retrictions found in nature. Previous work has shown that by using graphs of a lower degree, diversity in the population dereases at a slower rate, allowing for the formation of more diverse set of good building blocks. This research also indicated that graph degree is not the only factor affecting diversity preservation; different graphs with the same degree hinted at other factors that could influence information flow. In this paper, we investigate the effect of broadening the number of candidate graphs by introducing two new sets of graphs, one constructed from regular sub-graphs and one set constructed using geographic data from six locations in the United States. It was found that the use of sub-graphs connected to a central hub can promote the development of necesary building blocks and increasing performance for certain problems. In addition, it was shown that graphs with moderate to high level of diversity preservation are analogous to some geographic features in nature, providing a method to validate graphs used in epidemiological studies