2
$\begingroup$

What is a genetic algorithm, and what are its practical advantages over other algorithms? Is it similar to any commonly used machine learning algorithm like linear/logistic regression, neural networks, or tree-based methods like gradient boosting and random forests? I've heard it's based on "mutated" combinations of other models. Does this make it more like an ensemble?

$\endgroup$
4
$\begingroup$

A genetic algorithm is an algorithm based on biological evolution, on how nature evolved. It does exactly that, evolve the algorithm so that "it" finds the best solution to the problem at hand. You can use a genetic algorithm to find a solution to a problem which you don't know the answer, you know the answer but want to know a different one, or you are just lazy. The common steps for a genetic algorithm are:

  1. Generate a random population of elements
  2. Evaluate fitness of each element (how good are they against the solution)
  3. Take the best elements for the next generation
  4. Generate child elements using the above elements
  5. Mutate (randomly) each child. This can also be done before step 4 with parents.
  6. Repeat from step 2 for n number of generations until the solution is found, the maximum number of generations have been reached or the fitness is not changing anymore (local minima).

Two basic problems with GAs:

  • To get trapped in a local minima (or local maximum depending on the point of view). This means that you might find a good answer (or not even a good one) but it will never reach the best answer because fitness values are not changing or not getting better. This is fought using Mutation in step 5 to keep diversity in the population so it doesn't get stuck.
  • They are generally slower than other approaches.

If you can, take a look at this book. It is not free, but worth a look. Alternatively, take a look at this online book for free, it is a great source and he has his own youtube channel. It's more basic than the other book I recommend, but will help you get started with GAs.

To answer the other part of your question, the GA should be used to find a model, but will not act as a model. For example, if you have a neural network you can train it using the backpropagation method, but you could also train it using a GA. The GA will not use anything of the backpropagation mathematics, it could be used to generate weights in its neurons, and evaluate the answer (last layer). Weights will evolve to get closer to the solution. In this scenario, the model will still be the NN, but you used a different algorithm to find the best NN.

Hope this helps.

$\endgroup$
2
$\begingroup$

For the machine learning algorithm you mentioned, regression and neural networks are formulated in optimization framework, and tree-based method is based on information gain.

Genetic algorithm (GA) is a local search method. Given a value in the solution space, it will mutate to create several candidates. A criteria will be used to evaluate each candidates and only the few best ones will be kept for further mutation. It could usually be proven that GA could converge to the best solution if there is enough iteration. However, it is unfeasible practically. More discussion could be found here

As for ensemble learning, it refers to (weighted) voting of multiple models. There are two normal ways, bagging or boosting.

$\endgroup$
  • $\begingroup$ Adding a bit about the different between GA and ensemble method. GA is used to find a model. Ensemble methods are used (some time to construct) and combine models. $\endgroup$ – DaL Jun 30 '16 at 6:01
  • $\begingroup$ So for example, would you say that gradient descent is to a linear model as genetic algorithm is to ... { some other type of model }? In other words it would be inaccurate to say that you have a "trained genetic algorithm" (as a model artifact/output as a result of training) in the same way that you might say you have a trained a linear model? $\endgroup$ – Ryan Zotti Jun 30 '16 at 14:39
  • 1
    $\begingroup$ Genetic algorithm is different from gradient descent in the sense that the mutation in genetic algorithm is random, and the update of target in gradient descent is based on math properties. $\endgroup$ – William Jun 30 '16 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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