I have read some papers and books about evolutionary algorithms (EAs), pros and cons, and still, I don't understand why they are stochastic and what is the principal justification. What is the main difference between EAs and a simple hill-climber algorithm?
A simple hill-climber will explore one (local) optimum. What would you prefer -- one choice or many (but random) choices? No matter how bad there other options are, what would you lose to consider them? Thus, even random choices are better than no choices. In addition to having more choices, evolution is tied to "survival of the fittest" -- all evolutionary algorithms have a bias to the best of the available (random) choices. Thus, despite having randomness/stochasticness, these biases invariably lead evolutionary algorithms to be better than random.
If you have perfect knowledge, use it. If not, do some exploration to expand your knowledge. If this exploration has to be random, so be it.
A review on evolutionary algorithms
http://www.math.ntua.gr/~fouskakis/Publications/4.pdf
The best answer to that is GA mimics the evolutionary process of reproduction. Normally, in nature the selection of couples to mate occurs by random and not by rule "chromosomes to mate" the siblings characteristics occurs in a random way and not by rule of course nowadays in nature there is researches to control the characteristics of the reproduced siblings "chromosomes" by controlling the genes. This is what make GA an interesting research topic because it applies the concept of the survival of the fittest as it is explained before by some colleagues.
all this occurs randomly an sometime with little guidance, but at the end it is a needed stochastic process to find a global optimal solution for problems where the solution is not deterministic and cannot be solved by a deterministic algorithm.
I think the stochastic characteristic enable EAs to explore the solutions space of optimization problem. Without the randomness, EAs usually will converge to a local optimum very quickly. The randomness is a way to realize the diversification and exploration.
It is believed that the balance of exploration and exploitation, or the intensification and diversification is very important to design efficient EA variants.
To understand why EA are stochastic, you have to look at the problem you have to solve. The problems (goal functions) are high dimensional and the only way to obtain information about the problem itself, is by sampling the goal function at different points or in different directions (the dimension is greater than 10, for smaller dimension the simplex-downhill algorithm is really good). With a simple goal (linear) function you can see, that for high dimensions random sampling generates faster progress in comparison to a systematic search of every possible of directions. Thus the stochastic nature of EAs is only a method to search efficient in a high dimensional space. If it is possible to come up with another efficient method, than it possible to drop the random sampling.
This is also the difference to a simple hill-climber: You are climbing the hill in very thick fog. Thus it is not easy to find a direction to go.
- Badges
- Science topic
- Similar topics
- Computer Science
- Research Topics