Evolving artificial neural networks for solving NP problems

Problem Detail: 

I've recently read a really interesting blog entry from Google Research Blog talking about neural network. Basically they use this neural networks for solving various problems like image recognition. They use genetic algorithms to "evolve" the weights of the axons.

So basically my idea is the following. If I was supposed to write a program that recognizes numbers I would not know how to start (I could have some vague idea but my point is: It is not trivial, nor easy.) but by using neural network I do not have to. By creating the right context in order for the neural network to evolve, my neural network will "find the correct algorithm". Down below I quoted a really interesting part of the article where they explain how each layer have different role in the process of image recognition.

One of the challenges of neural networks is understanding what exactly goes on at each layer. We know that after training, each layer progressively extracts higher and higher-level features of the image, until the final layer essentially makes a decision on what the image shows. For example, the first layer maybe looks for edges or corners. Intermediate layers interpret the basic features to look for overall shapes or components, like a door or a leaf. The final few layers assemble those into complete interpretations—these neurons activate in response to very complex things such as entire buildings or trees.

So basically my question is the following: Couldn't we use genetic algorithms + neural networks in order to solve every NP problem? We just create the right evolutionary context and leave "nature" find a solution.

Inceptionism: Going Deeper into Neural Networks

EDIT: I know we can use Brute-Force or find a not-efficient solution in many cases. That is why I try to highlight Evolving artificial neural networks. As I said in a comment: Given sufficient time and an appropriate mutation rate we could find the optimal solution (Or at least that is what I think).

Asked By : NMO

Answered By : D.W.

No. This direction is unlikely to be useful, for two reasons:

1. Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the neural network will itself be a polynomial-time algorithm. It follows that if P $\ne$ NP, neural networks cannot efficiently solve any NP-complete problem.

2. Neural networks aren't "magic". They are a way of trying to find patterns. For some problems where there are strong enough patterns to be found, and the patterns can be learned from a reasonable number of examples, they might be effective. But they're not magic fairy dust. Just because you can set up a neural network doesn't mean that backpropagation will necessarily find a good way to solve your problem. It might be that there are no patterns to be found, that the patterns can only be discovered with an unfeasible number of examples, or that patterns exist but the neural network training procedure isn't able to find them.

Neural networks are just another form of machine learning. We could make the same remarks about SVMs or random forests or linear regression any other form of machine learning. Neural networks aren't some kind of magical silver bullet that solve all machine learning problems. They're about as effective as other machine learning methods, or for some kinds of problems, maybe a little bit more effective, but they're not magic.

Sometimes I run across people who have heard only a little bit about neural networks, and they walk away thinking that neural networks are the answer to everything -- maybe because they heard that "your brain uses neural networks too", or they saw some very cool application (voice recognition or something). But don't be fooled. Don't believe the hype. Neural networks are a useful technique, but they're not going to enable computers to solve NP-complete problems, or to beat the Turing test, take away all our jobs and replace humans with computers. Not anytime soon, anyway. That's just science fiction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47474