3

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.

enter image description here

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.

1
  • I suggest using the term "multidimensional search". If the surface is convex then there will be a single global optimum and you can use a simple hill-climbing approach to find it, but it looks like that's not the case. If it's smooth then Newton's method will find an optimum quickly; you could try multiple restarts to increase the chances of finding the overall minimum. You can always try a general search method like Nelder-Mead, though again it doesn't guarantee optimality. Sep 5, 2014 at 17:31

1 Answer 1

3

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.