c++mathematical-optimization heuristics simulated-annealing

Finding all local maxima of a function

I have written code to find the global minimum of a function using the simulated annealing algorithm — down below — but how to use the same algorithm to find all local maxima of a function?

My code for finding the local minimum of a function, note that i know nothing about the function I am asking the interactor for the f(x) at x i.e. the cost of the function in a particular point.

#include <bits/stdc++.h>

using namespace std;

double myRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}


int main()
{
    cout.flush();


    double x,fx,xMin;
    double fMin;

    cout << "? "<<fixed << setprecision(6) << -1<<endl;
    cin>>fMin;


    for(double T = 1000; T>1; T*=.995)
    {
        x=myRand(-100,100);
        cout << "? "<<fixed << setprecision(6) << x <<endl;
        cin>>fx;

        if (fx<fMin)
        {
            fMin=fx;
            xMin = x;
        }
        else
        {
            double P=exp((fMin-fx)/T);

            if (P>myRand(1,100))
            {
                fMin=fx;
                xMin=x;
            }
        }
    }

    cout << "! "<<fixed << setprecision(6)<<xMin<<endl;

    return 0;

}

my attempt to find the local maxima is

#include <bits/stdc++.h>

using namespace std;

double myRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}


int main()
{
    cout.flush();


    double x,fx,xMax;
    double fMax;
    int n;
    double a,b;
    cin>>n>>a>>b;

    double answer[n];




    for(int i=0; i<n; i++)
    {
        cout << "? "<<fixed << setprecision(6) << a+i/5 <<endl;
        cin>>fMax;

        for(double T = 1000; T>1; T*=.995)
        {
            x=myRand(a,b);


// i am avoiding to get the same local max twice
            while(i>0&&answer[i-1]==x)
                x=myRand(a,b);
            cout << "? "<<fixed << setprecision(6) << x <<endl;
            cin>>fx;
            if (fx>fMax)
            {
                fMax=fx;
                xMax = x;
            }
            else
            {
                double P=exp((fMax-fx)/T);

                if (P<myRand(0,1))
                {
                    fMax=fx;
                    xMax=x;
                }
            }
        }
        answer[i]=xMax;
    }
    cout << "!";
    for(int i=0; i<n; i++)
    {
        cout<<" "<<fixed << setprecision(6)<<answer[i];
    }

    return 0;

}

Solution

Place the algorithm inside a function:

double my_unknown_function(double x)
{
  cout << "? " << fixed << setprecision(6) << x << endl;
  cin >> fx;

  return fx;
}

using function = double(double);

double minimum(function func)
{
  double x, fx, xMin;

  /* ... */

  for(double T = 1000; T>1; T*=.995)
  {
    x = myRand(-100,100);
    fx = func(x);

    /* ... */
  }

  return xMin;
}

In this way you can simply get multiple local minima:

std::vector<double> lm;
for (int i(0); i < 100; ++i)
  lm.push_back(minimum(my_unknown_function));

As explained in the comments, simulated annealing is an optimization heuristic. It’s not an exhaustive search and it doesn’t find all minima.

Anyway calling minimum multiple times you can get different results, since it's stochastic. In expectation, with a large enough number of restarts, any local search method will someday give you the actual global minimum.

Do not rewrite the algorithm for the maximization task: you could introduce bugs and testing is harder.

Just take the opposite of your function:
```
double my_unknown_function(double x)
{
  cout << "? " << fixed << setprecision(6) << x << endl;
  cin >> fx;

  return -fx;
}
```

Also consider: