Effective multi-search algorithms

Question

Reason for posting question: My programming experience is somewhere between amateur and moderate (but I'm pretty rusty at this point). I'll probably be working with C++, but I would be willing to switch to Python. I have some experience with basic sort/search algorithms like binary, M, A*, etc. I've heard that A* can be a pretty efficient search algorithm, but that when multiple search targets start being desired that there are some big losses on efficiency in A* compared to other algorithms. I'm looking into a multiple search/optimization problems with a multidimensional problem space, so efficiency is really going to start to matter.

Most multi-search algorithms I've seen are referred to as string searching algorithms. I wanted to inquire how well these algorithms work on other types of problems, or possibly be provided recommendations for other, more effective algorithms for the scenario I am providing. I do admit I need to do more research to understand the difference between optimization and multi-search algorithms, but the current ideas I have seem to work well with multi-search algorithms. I am looking into potential energy surfaces and finding rough approximations of local minima.

Imagine a something like a hilly surface. Now let's populate a 3D graph of the potential energies of an object at any x and y positions as a function of the two position coordinates. I am interested in finding all the local minima within a defined bound of this surface. I need algorithm(s) that allow for me to sample the surface at some resolution and then start searching the lowest points for local minima. In essence I was thinking of creating a low resolution mesh with some kind of constrained breadth-first search, then using another smart algorithm to increase the resolution of the mesh at the lower valued points. Ideally the algorithms would be used multi-threaded, but they need to be able to support an arbitrary dimensional PES. I have a black-box evaluation function that provides the potential energy. Here's a 2+1 dimensional illustration below.

Envision the redline was 1 of the dimensions of the initial sampling mesh, and it was actually crossing near the local minima. The algorithm then will start to increase mesh resolution around the valleys for a few steps prior to selecting the lowest value at that region. It will then move on to another low point.

Answer 1

You are trying to solve a Global Optimization problem.

http://en.wikipedia.org/wiki/Global_optimization is a good reference that has a number of links to methods used to solve this problem. I've used Simulated Annealing successfully before but the solution to fit your problem will really come down the the size and complexity of your problem space.