Solving Maximum Number of Run Using Genetic Algorithm

Abstract

<p> This thesis defends the use of genetic algorithms (GA) to solve the maximum number of repetitions in a binary string. Repetitions in strings have significant uses in many different fields, whether it is data-mining, pattern-matching, data compression or computational biology 14]. Main extended the definition of repetition, he realized that in some cases output could be reduced because of overlapping repetitions, that are simply rotations of one another [10]. As a result, he designed the notion of a run to capture the maximal leftmost repetition that is extended to the right as much as possible. Franek and Smyth independently computed the same number of maximum repetition for strings of length five to 35 using an exhaustive search method. Values greater than 35 were not computed because of the exponential increase in time required. Using GAs we are able to generate string with very large, if not the maximum, number of runs for any string length. The ability to generate strings with large runs is an advantage for learning more about the characteristics of these strings. </p>