37
$\begingroup$

I've read a few papers discussing pros and cons of each method, some arguing that GA doesn't give any improvement in finding the optimal solution while others show that it is more effective. It seems GA is generally preferred in literature (although mostly people modify it in some way to achieve results they need), then why majority of software solutions seem to use backpropagation only?

Is there some general rule of thumb when to use one or another? Maybe it depends on type of NN or there exists some state of the art solution which generally outperforms others?

If possible I'm looking for general answers: i.e., "if the NN is huge, GA is better", or "GA is always better but has computational performance issues" etc...

Improve this question
$\endgroup$
1
  • $\begingroup$ Also note that in some cases you can't use backpropagation but can only use GA. For example when you can evaluate the success of the entire neural network but can't tell which value it should have outputed. Like in games, you can say if the agent won but can't say what values (moves) it needed to output at each turn, so you can only use GA and can't use backpropagation. $\endgroup$
    – Tomer Wolberg
    Sep 21, 2020 at 14:00

6 Answers 6

Reset to default
28
$\begingroup$

If you look carefully at the scientific literature you'll find contrasting results. Obviously, in some cases GA (and more in general, Evolutionary Algorithms) may help you to find an optimal NN design but normally they have so many drawbacks (algorithm parameters' tuning, computational complexity etc) and their use is not feasible for real-world applications. Of course you can find a set of problems where GA/EAs is always better than backpropagation. Given that finding an optimal NN design is a complex multimodal optimization problem GA/EAs may help (as metaheuristics) to improve the results obtained with "traditional" algorithms, e.g. using GA/EAs to find only the initial weights configuration or helping traditional algorithms to escape from local minima (if you are interested I wrote a paper about this topic).

I worked a lot on this field and I can tell you that there are many scientific works on GA/EAs applied to NNs because they are (or better, they used to be) an emerging research field.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This is something I also came up with recently - first find 'good' solution and then improve it further with GA. Not only applicable to NNs, but optimization in general... $\endgroup$
    – sashkello
    Apr 21, 2013 at 4:35
  • 1
    $\begingroup$ I'm confused why they are mutually exclusive. I thought GA is supposed to learn the structure; Backpropagation can only learn the weights $\endgroup$
    – pete
    Apr 27, 2015 at 19:22
8
$\begingroup$

One of the key problems with neural networks is over-fitting, which means that algorithms that try very hard to find a network that minimises some criterion based on a finite sample of data will end up with a network that works very well for that particular sample of data, but which will have poor generalisation. I am rather wary of using GAs to design neural networks for this reason, especially if they do architecture optimisation at the same time as optimising the weights. I have generally found that training networks (with regularisation) from a number (say 20) of random initial weight vectors and then forming an ensemble of all the resulting networks is generally as good an approach as any.

Essentially optimisation is the root of all evil in machine learning, the more of it you do, the more likely you are to end up over-fitting the data.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Dikran, though GA make natural selection but does not ignore the information as you mentioned, it only ensure if the selected solution solve its problem if not, it find out to know why and upgrade the agorithm which form the basis of it dynamism till the network converge at one or two best solution. hope you get that rignt? $\endgroup$
    – user55737
    Sep 13, 2014 at 17:53
  • $\begingroup$ converging to the best solution evaluated over a finite sample of data is exactly what causes over-fitting. To avoid overfitting you want to converge on a solution that is not the best (e.g. early stopping in training neural networks). GAs are no better than any other form of optimisation in fitting neural networks, you need to avoid over-optimising the training criterion. $\endgroup$
    – Dikran Marsupial
    Sep 15, 2014 at 7:59
5
$\begingroup$

Whenever you deal with huge amounts of data and you want to solve a supervised learning task with a feed-forward neural network, solutions based on backpropagation are much more feasible. The reason for this is, that for a complex neural network, the number of free parameters is very high. One industry project I am currently working on involves a feed-forward neural network with about 1000 inputs, two hidden layers @ 384 neurons each and 60 outputs. This leads to 1000*384 + 384*384 + 384*60 = 554496 weight parameters which are to be optimized. Using a GA approach here would be terribly slow.

Improve this answer
$\endgroup$
3
  • $\begingroup$ My understanding is that GA is designed to tackle problems which are harder to solve with standard approaches. Shouldn't it perform better exactly in a situation you described? $\endgroup$
    – sashkello
    Apr 13, 2013 at 1:50
  • 2
    $\begingroup$ I thought GA is supposed to be used to figure out what structure it is e.g. how many hidden layers and how they are connected. Backpropagation can only figure out the weights $\endgroup$
    – pete
    Apr 27, 2015 at 19:23
  • $\begingroup$ @pete, using GA to figure out what the structure is means you have to test many different models. When you crate a new model you initialize weights to random and start from zero again. So, evolving structure is even slower. If your GA is going to evolve 10 different network structures per minute, it means 600 different networks per hour and 14,400 per day. How on Earth are you going to train all these netwroks? Even petaflop supercomputer won't be enough $\endgroup$
    – Nulik
    Mar 15, 2020 at 11:45
3
$\begingroup$

Second answer is wrong. Overfitting isn't caused by optimization. Overfitting happens when your model is over-complicated and can fit all the datapoints without learning the actual rule that created them (i.e. just memorizing them, in the extreme case.) There are many ways to prevent overfitting such as choosing simpler models, dropout, dropconnect, weight decay, and just using more data. The goal should be to optimize your network and make it as accurate as possible, taking those constraints into account.

To answer the question, backprop is supposedly much faster than stochastic optimization (genetic algorithms and the like.) My guess is this is because it takes advantage of what the actual output was supposed to be, adjusts the weights in the right direction based on that, where stochastic optimization tries completely random changes and ignores that information.

However by exploring a larger area, GAs will probably do better in the long run by avoiding local optimas, it will just take longer to train.

I am curious how much slower GAs are than backprop, and if anyone knows of hybrid algorithms (scatter search seems like it would be ideal for this.)

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Disagree with your first paragraph. Overfitting is prevented mainly via regularization approaches in the training problem. If you start doing meta-optimization --- that is solving lots of training problems (for example tuning kernel parameters, network architectures, ...) -- taking care of overfitting becomes much more difficult and is certainly not implicitly guaranteed anymore. $\endgroup$
    – Marc Claesen
    Sep 14, 2014 at 7:51
  • $\begingroup$ If overfitting were not caused by optimisation, early stopping wouldn't be an effective remedy for overfitting. $\endgroup$
    – Dikran Marsupial
    Jan 10, 2019 at 16:49
1
$\begingroup$

imho the difference between GA and backpropagation is that GA is based on random numbers and that backpropagation is based on a static algorithm such as stochastic gradient descent. GA being based on random numbers and add to that mutation means that it would likely avoid being caught in a local minima. But then GA being based on random numbers means that it is fairly likely for 2 different times you run the learning on the same network, it may reach a different conclusion i.e. a different set of weights

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just commenting, we also use random init. for the weights in back-prop. If we use the same seed while initializing, it will lead to the same solution, but if you don't, probably it won't. So, back-prop, too, depends on a random input. When you fix the seed, you'll also have the same result in genetic algorithm since it'll use the same seq. of numbers again. $\endgroup$
    – gunes
    Dec 24, 2018 at 12:12
0
$\begingroup$

To answer your question, I have tried to write selective algo to train mnist without tensorflow or pytorch. Only using numpy. It works but terribly slow. So tried utilizing gpu using cupy. I optimized my code. I wrote a custom kernel to cupy etc etc ...

So I have invented binary minist :P . Very small dataset only with ones and zeros. And tried GA algorithm with this. It worked

The solution I have reached is backpropagation math and code applicaiton is far easier to understand and track to see what is going on. Selective algorithms are easier to coder harder to track (what is going on how it evolves)

Main part of code:

enter image description here

My results: enter image description here

Improve this answer
$\endgroup$

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.