Как эффективно найти все локальные минимумы функции - PullRequest
Новая
       10

Как эффективно найти все локальные минимумы функции

0 голосов
/ 02 ноября 2018

Этот вопрос относится к глобальной оптимизации, и он проще. Задача - найти все локальные минимумы функции. Иногда это полезно, например, в физике мы можем захотеть найти метастабильные состояния помимо истинного основного состояния в фазовом пространстве. У меня есть наивная реализация, которая была протестирована на скалярной функции x sin (x) + x cos (2 * x) путем случайного поиска точек в интервале. Но очевидно, что это не эффективно. Код и выходные данные прилагаются, если вы заинтересованы. 

#!/usr/bin/env python

from scipy import *
from numpy import *
from pylab import *
from numpy import random
"""
search all of the local minimums using random search  when the functional form of the target function is known.
"""
def function(x):
    return x*sin(x)+x*cos(2*x)
#   return x**4-3*x**3+2

def derivative(x):
    return sin(x)+x*cos(x)+cos(2*x)-2*x*sin(2*x)
#   return 4.*x**3-9.*x**2

def ploting(xr,yr,mls):
    plot(xr,yr)
    grid()
    for xm in mls:
        axvline(x=xm,c='r')
    savefig("plotf.png")
    show()

def findlocmin(x,Nit,step_def=0.1,err=0.0001,gamma=0.01):
    """
    we use gradient decent method to find local minumum using x as the starting point 
    """
    for i in range(Nit):
        slope=derivative(x)
        step=min(step_def,abs(slope)*gamma)
        x=x-step*slope/abs(slope)
#       print step,x
        if(abs(slope)<err):
           print "Found local minimum using "+str(i)+' iterations'
           break
        if i==Nit-1:
            raise Exception("local min is not found using Nit=",str(Nit),'iterations')
    return x

if __name__=="__main__":
    xleft=-9;xright=9
    xs=linspace(xleft,xright,100)
    ys=array([function(x) for x in xs ])
    minls=[]
    Nrand=100;it=0
    Nit=10000
    while it<Nrand:
          xint=random.uniform(xleft,xright)
          xlocm=findlocmin(xint,Nit)
          print xlocm
          minls.append(xlocm)
          it+=1
#   print minls 
    ploting(xs,ys,minls)`]

all local minimums of the tested function

Я хотел бы знать, существует ли лучшее решение для этого?

...