algorithms, artificial intelligence, evolution

Is P ~= NP?

At least sometimes it is. For example, when we succeed in constructing an  evolutionary algorithm which approximately solves a particular NP hard problem and stumbles upon an optimal solution, we have built a royal shortcut between those two worlds. The NP and the P. However fragile and sporadic the bridge was, it lasted long enough for us to get the solution we wanted, even if the solution wasn’t perfect. We were after an approximation and we found a better one, than we could have hoped for using the brute force approach.

Imagine, that we are able to tackle every NP problem with this strategy! By translating it first to some evolutionary process yielding ever better results and then wait until an acceptably good solution occurs “naturally” in this process.

The packing problems are famous and most probably NP. We have managed to install some of them inside an emulation of evolution and got a lot of results. Some are world records, some have been surpassed by others since, many have just been fine-tuned by humans, many are waiting to be published. Unfortunately, we are so CPU hungry, that this low priority process is all but dead at the moment. Fortunately we use all the computing we get, for other more practical evolutions. Like scheduling — another NP problem that we routinely leave to evolution.

The greatest achievement of this stupid evolutionary algorithm is that it turns out to be very innovative. Thus, not stupid at all, but  actually very intelligent by any sensible definition! The biggest irony here is that some humans grab the original, unexpected, evolved idea and then fine tune it, when it should be the other way around! The innovative brilliant human should invent a new solution, the computer should just polish it.

The traditional roles have changed here.

Here is an original computer creation. Almost all circles are violet, which means that they don’t even touch each other. What utter sloppiness!  Still it’s the best known  (July 17. 2013) packing of 249 circles inside a square.

Sooner or later a human will fine tune and publish it under his/her name. It’s okay, the Internet will preserve the whole history.

Advertisements
Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s