2
$\begingroup$

I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?

Ever since I finished my implementation of a GA , since randomness is present in the mutation function,the initialization part (as well as the reinitialization part) and crossbreeding part as well... other than a encoder which tries to sense of the chromsomes (encoder tailored to make sense of the chromosome in context of the problem) and a fitness function , it feels like genetic algorithms are just random search functions in disguise .

So my question is : are GA implementations just plain old random searches with a shot of memory to make it look like there is some sort of meaningful feedback?

Improve this question
$\endgroup$
6
  • $\begingroup$ Is there anything in particular regarding genetic algorithms you are curious about, or randomness in algorithms in general? If the latter is the case, you should read up on Randomized algorithms. $\endgroup$
    – Pål GD
    Apr 2, 2013 at 16:23
  • 5
    $\begingroup$ Is this your question: Do genetic algorithms work provably better (i.e. smaller expected runtime) than random search? $\endgroup$
    – Raphael ♦
    Apr 2, 2013 at 19:38
  • $\begingroup$ think this is a reasonable question. it was the same one I had when introduced to GAs as an undergraduate, & also a general challenge to them when the field was new, & dont think the instructor answered it well. but have since come to this answer: briefly stated, a genetic algorithm exploits the gradient in the fitness function due to crossbreeding. if there is no gradient to exploit, it is indeed roughly the same as a random search over the search space. dont know of a ref that points this out. $\endgroup$
    – vzn
    Apr 2, 2013 at 20:40
  • $\begingroup$ When compared to other things that use some sort of feedback like stuff in control theory it makes sense, but when it comes to the crossbreeding part and specially when one knows that there is an end goal in sight and coupled with randomness , it feels(once again "feels") weird and not so convincing , and especially when you take the best ones in each generation and crossbreed them (with a chance of mutation) , its like throwing 10 dollar into a hurricane and hoping that a hundred bucks comes flying out . Would it be fair to say that the anwser would involve a heavy shot of probability theory? $\endgroup$
    – metric-space
    Apr 2, 2013 at 20:50
  • 2
    $\begingroup$ I wonder if the question Provable statements about genetic algorithms pretty much covers your question. $\endgroup$
    – Juho
    Apr 2, 2013 at 20:59

1 Answer 1

Reset to default
1
$\begingroup$

I guess the easiest way to reason it (this is after thinking about what user:vzn said

a genetic algorithm exploits the gradient in the fitness function due to crossbreeding. if there is no gradient to exploit, it is indeed roughly the same as a random search over the search space.

, um that the chromsomes which embedd some sort of a possible solution has a higher chance of being a solution than a randomly generated chromosome.On mutation and crossbreeding it up its chance of being closer to the answer.I do not know random variable theory or stochastic calculus(if it is ver used in such a thing) to prove it but it's feels pretty intuitive now.

ANd if you think carefully about what the fitness function does probabilistically, because it takes the best fits, the best fits have a higher chance of being crossbred and mutated into a better solution than an unfit solution.

As for a random search based searching , it really doesn't this narrowing down part to give an answer in most cases as compared to a GA.

Improve this answer
$\endgroup$

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