Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary algorithms too entail - performing search on a graph?
1
-
$\begingroup$ Graphs are just the representation of the probable solutions. In real life we have an initial state, we know the final state (at least a part of it) and some intermediate nodes that there can be. These nodes are either dependent on or have dependency on other nodes. Depending on the problem we might need to find intermediate/final node(s). Graphs/Trees provide us represent problem domain easily. This is the reason why we find ourselves dealing with them while working with searching algorithms. $\endgroup$– UgnesFeb 3, 2019 at 6:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms
These are examples of meta-heuristics. Genetic algorithms are a class of Evolutionary algorithms which itself is one of many meta-heuristics.
Both of these methods entail doing a search on a graph of candidate solutions.
Usually the "graph" is more conceptual than physical. Meaning that it's not actually represented by a graph data structure living in memory due to the huge search space. These techniques go (or not) from one solution (or a set of solutions) to its "neighbor" using heuristics. For example a solution that has a better fitness value.
Do all other evolutionary algorithms too entail - performing search on a graph?
Yes. Evolutionary algorithms are search based, meaning that we go from a set of solutions to another based on fitness functions. We also include a mutation step (and may include crossover).
This search happens on the "conceptual" graph of possible solutions.
It is worth to mention that this class is global search based in contrast with local search like the Simulated Annealing algorithm.
For more info check out this Wikipedia article on Meta-heuristics.
