Exelixis: A parallel generic Genetic Algorithm

by Dimitrios Tsapakidis
supervised by Dr Yike Guo and Prof John Darlington

Exelixis [ekseleeksees, Greek for Evolution] is the result of my final year project for my BSc in Mathematics and Computer Science. A project report is available. Exelixis is a parallel, generic, portable and expandable Genetic Algorithm:

• parallel, currently following the panmictic model and fully utilising the AP1000's broadcast network.
• generic, by being problem and representation independent. Its design allows for not-yet-implemented GA models.
• portable, being implemented in C and MPI.
• expandable, allowing easy addition of operators, representations and models.

• Representations: binary, order-based.
• Initialiasation methods: random for binary, random for order, user defined.
• Termination methods: iterations, reaching a fitness function, user defined.
• Selection operators: roulette wheel, uniform, user defined, hybrid, 2-member tournament.
• Reproduction operators: one-point crossover for binary, two-point crossover for binary, uniform crossover for binary, user defined crossover, flipping mutation for binary, setting mutation for binary, uniform crossover for order, scramble sublist mutation for order, user defined mutation.
• Elitism (which can be updated at run time).
• Classic reproduction model (ie crossover first, mutation second).
• Printed after each iteration: generation best chromosome, its fitness, fitness sum and average of the whole generation and iteration time.
• Testbed functions: f1, f2, f3, f4, f5 and f6, zeroes, simple and TSP.