A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents

In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of "hard" exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.