Нахождение всех локальных максимумов функции - PullRequest
Новая
       47

Нахождение всех локальных максимумов функции

1 голос
/ 24 марта 2020

Я написал код для поиска глобального минимума функции, используя алгоритм имитации отжига - ниже - но как использовать тот же алгоритм , чтобы найти все локальные максимумы функции ?

Мой код для нахождения локального минимума функции, обратите внимание, что я ничего не знаю о функции. Я спрашиваю интерактор для f(x) при x, т.е. стоимости функции в конкретном точка. 

#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;

}

моя попытка найти локальные максимумы 

#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;

}

1 Ответ

1 голос
/ 25 марта 2020

  1. Поместите алгоритм в функцию: 

    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;
}

    Таким образом, вы можете просто получить несколько локальных минимумов: 

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

    Как поясняется в комментариях, имитация отжига - это оптимизация heuristi c. Это не полный поиск , и он не находит все минимумы .

    В любом случае, вызывая minimum несколько раз, вы можете получить разные результаты, так как это стохастики c. Ожидается, что при достаточно большом количестве перезапусков любой локальный метод поиска когда-нибудь даст вам действительный глобальный минимум.

  2. Не переписывайте алгоритм для максимизации Задача: вы можете ввести ошибки, а тестирование сложнее.

    Просто возьмите противоположность своей функции: 

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

  return -fx;
}

Также учтите:

...