5
$\begingroup$

I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new concept. However I'm wondering which specific algorithms I should use for selection, crossover and mutation.

I understand that it often depends on what your data type is, for example individuals who's chromosome order is important should use crossover algorithms listed on this Wikipedia article (with maybe a few more to be added to that list), but how do I choose between them? What should I consider when I am selecting which algorithms to use for these three things?

Currently I have implemented Tournament selection, partially matched crossover and index shuffling for mutation and this gives me the exact output I want, but how do I know these are the best choice for my problem.

(P.S. This is purposefully as abstract as possible, I'm not looking for an answer to my specific problem but more how anybody can go about choosing which algorithms are best for their particular situation.)

$\endgroup$
1
  • 1
    $\begingroup$ there are many strategies and it depends on the data structure. ie this may not be specific enough to answer. sometimes using different ones only improves the (speed of) convergence somewhat but not necessarily the final solution. it sounds like you are already familiar or more with the basic theory. you can look for operations from other problems similar to yours studied in the literature. $\endgroup$
    – vzn
    Jan 14, 2015 at 16:41

2 Answers 2

2
$\begingroup$

SELECTION. Different types of selections will have different advantages and disadvantages. You will mostly find the right one through trial and error.

CROSSOVER. The optimal crossover technique is usually problem-specific. A general rule is to avoid using a single point crossover, as suggested by this paper.

MUTATION. Some mutation guidelines are provided in this paper.

$\endgroup$
2
$\begingroup$

(TL;DR - see table at the end)

After several days of reading academic papers, I have came to one simple conclusions: everything is problem specific.

My advice to anybody reading this for the answer is test, test and test. Not just different methods of selection, crossover and mutation; but also different combinations.

I have been using the DEAP python library to implement my GA, so I have been restricted to the methods they have already implemented in their source code (I plan to spend a fair amount of time contributing to that library to increase the options they have once I have finished my current project, it really is great) but it made writing the GA much faster and swapping out different selection, crossover and mutation functions much much easier. On those grounds I would recommend using something like this if possible to figure out what methods are best for your problem.

I ran all possible combinations of viable methods (some methods as I said in the question are specific to chromosomes where the order is important) and recorded time taken and final solution fitness (this the score my objective function gives the final solution the GA outputs); and from this I chose which was my best combination.

However, nobody wants a "go figure it out for yourself" answer, so I have provided a table that show how long (in relative time) different crossover algorithms took to "solve" (by this I mean give an answer to) a 20-city Hamilton path problem.

A table of time complexities for several CX algorithms Poon, P. W., & Carter, J. N. (1995). Genetic algorithm crossover operators for ordering applications. Computers & Operations Research, 22(1), 135-147.

I also encourage you to read that paper, it helped me a lot regarding crossover choice, but bare in mind that methods will vary from problem to problem. It unfortunately is a trial and error thing as there is no "choose X, Y and Z methods" solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.