CODEWITHSUNDEEP
algorithm
Daniel S.
Daniel S.

Reputation: 6640

Exhaustive search for algorithms - existing works?

You might have to read this twice so that my idea becomes clear. Please be patient.
I'm looking for existing work for exhausive search for algorithms for given problems. Exhaustive search is also known as brute force search, or simply brute force.

Other exhaustive search algorithms search for a solution for a given problem. Usually, a solution for such a problem is some data which fulfills some requirements.

Exhaustive search example:
You want the solution for a KNAPSACK problem. That is the objects which can be packed into the bag so that there is no other combination of objects which fit into the bag and which would sum up to a bigger value than your result combination.
You can solve this by going over all possible combinations (exhaustive) and search for the one which fits into the bag and which is the most valuable one of those combinations.

What I'm looking for is just a special case of exhaustive search: Exhaustive search which searches for an algorithm as a solution. So in the end, I'm looking for an algorithm which searches for an algorithm which solves some given problem.

You might say: Go google it. Well, yes I've done that. The difficulty I'm facing here is that googling for "algorithm which searches for another algorithm" results in all the same as "another search algorithm". Obviously, this has too many unwanted results, so I'm stuck here.

How can I find existing work related to exhaustive search for algorithms?
More specifically: Has there any software been written for this? Can you point me to any links or algorithm names/better keywords in relation to this topic?

Update:
The purpose for which I'm looking for such an algorithm search is solving problems for which no good heuristics are known, e.g. prooving-algorithms or trying to finding other solution algorithms for problems which might or might not be NP-complete problems (thus proving that the problem is not NP-complete if a faster algorithm can be found; without any human interaction).

Upvotes: 2

Views: 1441

Answers (5)

Mihai Oltean
Mihai Oltean

Reputation: 201

I used Genetic Programming for evolving/generating heuristics for the Travelling Salesman Problem. The evolved heuristic is better than the Nearest Neighbor on the tested problems (random graphs and other graphs taken from TSPLIB). If you want the source code, you can download it from here: http://www.tcreate.org/evolve_heuristics.html

Upvotes: 1

NietzscheanAI
NietzscheanAI

Reputation: 966

This paper, entitled "Systematic search for lambda expressions" performs exhaustive enumeration in the space of small type-safe functional programs expressed in the lambda calculus.

Upvotes: 1

Yann TM
Yann TM

Reputation: 2075

You seem to be looking for "program synthesis", which can work in some limited instances, provided you can correctly and formally specify what your algorithm is supposed to do (without giving an implementation). Synthesis is an effective approach to build gate-level circuits, but applying synthesis to software is so far still more of a research avenue than practical.

Still, here are a couple of references on the subject,

(Some of the most advanced work in the area in my opinion, has a tool) program sketching by Armando Solar-Lezama

Check out Microsoft research page on the topic, they think it's hot topic: http://research.microsoft.com/en-us/um/people/sumitg/pubs/synthesis.html

Some other similar stuff I've seen : Model Checking-Based Genetic Programming with an Application to Mutual Exclusion. (Katz & Peled @ TACAS '08), they have a more recent version on ArXiv : http://arxiv.org/abs/1402.6785

Essentially the search space is explored (exhaustively) using a model-checker.

Upvotes: 2

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19837

Take a look at Neural Turing Machines by Alex Graves, Greg Wayne and Ivo Danihelka from Google DeepMind.

Abstract:

We extend the capabilities of neural networks by coupling them to external memory resources, which they can interact with by attentional processes. The combined system is analogous to a Turing Machine or Von Neumann architecture but is differentiable end-to-end, allowing it to be efficiently trained with gradient descent. Preliminary results demonstrate that Neural Turing Machines can infer simple algorithms such as copying, sorting, and associative recall from input and output examples.

Upvotes: 1

John Coleman
John Coleman

Reputation: 51998

I wouldn't think it would be possible (at least without some restriction on the class of algorithms) and, in any event, the search space would be so large that it would make ordinary brute-force tame by comparison. You could, for example, enumerate algorithms for a specific model of computation (e.g. Turing machines) but then the Halting problem rears its head -- how can you tell if it solves your problem? If you have a family of algorithms which depend on discrete parameters then you could of course brute force the choice of the parameters.

There is an extensive literature on Genetic Programming (see https://en.wikipedia.org/wiki/Genetic_programming ). That might give you something to go on. In particular -- the tree data structures that are often used in this context (essentially expression trees or more generally abstract syntax trees) could admit a brute force enumeration.

Upvotes: 1

Related Questions