7

If crossover is excluded from genetic algorithms, they become something between the gradient descent and the simulated annealing. The main effect of crossover consists in the exchange of parts of different solutions. If an optimization task can be loosely decomposed into somewhat independent subtasks, and this decomposition is reflected in genes, then ...


5

As others have said, there is less than you would expect. A couple of tangentially related papers: "Multiplicative Weights in Coordination Games and the Theory of Evolution" by Chastain, Livnat, Papadimitriou, and Vazirani. This paper argues that evolutionary dynamics (in a simple model) is equivalent to a coordination game between genes being played with ...


3

I am not sure that there is one Theorem to point to. Anyhow, you will probably be interested in the following reference, which summarizes many more recent results than those you mention in the question, e.g., for the (1+1)-EA with linear functions, quadratic functions, and monotone polynomials as objective functions (I know these are probably much simpler ...


1

Without paying much attention to your code, your crossover rate is maybe a touch low, your mutation rate is orders of magnitude too low, your population is tiny, and you're only running 20 generations. You're just not doing enough search for anything to work. If your initial population had a 6 or 7, you find it. Otherwise, you get a handful of crossovers to ...


1

One nice thing about QAP is that local search methods can take advantage of incremental evaluation of modified solutions, and GAs typically can't. So a pure GA needs O(n^2) time for every fitness evaluation, but a local search can do many fitness calculations in O(1) time, and the rest in O(n). What I've often done for QAP is to employ something like a tabu ...


1

You may have a look at the article "The Analysis of Evolutionary Algorithms — A Proof That Crossover Really Can Help" published in 2002 by Jansen and Wegener in the journal Algorithmica. This might not really answer your two questions, but at least it shows that your statement ("It seems to me that one can obtain similar results with algorithms that do not ...


1

Two different questions. How to map your decoded values onto a non-power of two range is really just basic arithmetic. Suppose your target range is the half-open interval [10, 20). (That is, 10.0 <= x < 20.0). Suppose further you have an 8-bit encoding. Let's take the string 01001011. In standard binary, this decodes to the integer 128+8+2+1=139. The ...


Only top voted, non community-wiki answers of a minimum length are eligible