Pecyn cymhwysiad mathemategol yw SciPy (yngenir sai pie) sy'n seiliedig ar yr estyniad Numpy Python. Gyda SciPy, mae eich sesiwn Python rhyngweithiol yn dod yr un amgylchedd gwyddor data cyflawn ac amgylchedd prototeipio system gymhleth Γ’ MATLAB, IDL, Octave, R-Lab, a SciLab. Heddiw, rwyf am siarad yn fyr am sut i ddefnyddio rhai algorithmau optimization adnabyddus yn y pecyn scipy.optimize. Gellir cael cymorth manylach a mwy diweddar ar ddefnyddio swyddogaethau bob amser gan ddefnyddio'r gorchymyn help() neu ddefnyddio Shift+Tab.
Cyflwyniad
Er mwyn arbed eich hun a darllenwyr rhag chwilio a darllen ffynonellau cynradd, bydd dolenni i ddisgrifiadau o ddulliau yn bennaf ar Wicipedia. Fel rheol, mae'r wybodaeth hon yn ddigonol i ddeall y dulliau yn gyffredinol a'r amodau ar gyfer eu cymhwyso. I ddeall hanfod dulliau mathemategol, dilynwch y dolenni i gyhoeddiadau mwy awdurdodol, sydd iβw cael ar ddiwedd pob erthygl neu yn eich hoff beiriant chwilio.
Felly, mae'r modiwl scipy.optimize yn cynnwys gweithredu'r gweithdrefnau canlynol:
- Lleihad amodol a diamod o swyddogaethau sgalar nifer o newidynnau (lleiaf) gan ddefnyddio algorithmau amrywiol (Nelder-Mead simplex, BFGS, graddiannau cyfun Newton, ΠΈ )
- Optimeiddio byd-eang (er enghraifft: , )
- Lleihau gweddillion (lleiaf_squares) ac algorithmau gosod cromlin gan ddefnyddio sgwariau lleiaf aflinol (curve_fit)
- Lleihau swyddogaethau sgalar un newidyn (minim_scalar) a chwilio am wreiddiau (root_scalar)
- Datryswyr aml-ddimensiwn system o hafaliadau (gwraidd) gan ddefnyddio algorithmau amrywiol (hybrid Powell, neu ddulliau ar raddfa fawr fel ).
Yn yr erthygl hon byddwn yn ystyried yr eitem gyntaf yn unig o'r rhestr gyfan hon.
Lleihau swyddogaeth sgalar sawl newidyn yn ddiamod
Mae'r swyddogaeth minim o'r pecyn scipy.optimize yn darparu rhyngwyneb cyffredinol ar gyfer datrys problemau lleihau amodol a diamod o swyddogaethau sgalar o sawl newidyn. I ddangos sut mae'n gweithio, bydd angen i ni gael swyddogaeth addas o sawl newidyn, y byddwn yn ei leihau mewn gwahanol ffyrdd.
At y dibenion hyn, mae swyddogaeth Rosenbrock o newidynnau N yn berffaith, sydd Γ’'r ffurf:
Er gwaethaf y ffaith bod swyddogaeth Rosenbrock a'i matricsau Jacobi a Hessian (y deilliadau cyntaf a'r ail, yn y drefn honno) eisoes wedi'u diffinio yn y pecyn scipy.optimize, byddwn yn ei ddiffinio ein hunain.
import numpy as np
def rosen(x):
"""The Rosenbrock function"""
return np.sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0, axis=0)Er eglurder, gadewch i ni dynnu mewn 3D werthoedd swyddogaeth Rosenbrock o ddau newidyn.
Cod lluniadu
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from matplotlib import cm
from matplotlib.ticker import LinearLocator, FormatStrFormatter
# ΠΠ°ΡΡΡΠ°ΠΈΠ²Π°Π΅ΠΌ 3D Π³ΡΠ°ΡΠΈΠΊ
fig = plt.figure(figsize=[15, 10])
ax = fig.gca(projection='3d')
# ΠΠ°Π΄Π°Π΅ΠΌ ΡΠ³ΠΎΠ» ΠΎΠ±Π·ΠΎΡΠ°
ax.view_init(45, 30)
# Π‘ΠΎΠ·Π΄Π°Π΅ΠΌ Π΄Π°Π½Π½ΡΠ΅ Π΄Π»Ρ Π³ΡΠ°ΡΠΈΠΊΠ°
X = np.arange(-2, 2, 0.1)
Y = np.arange(-1, 3, 0.1)
X, Y = np.meshgrid(X, Y)
Z = rosen(np.array([X,Y]))
# Π ΠΈΡΡΠ΅ΠΌ ΠΏΠΎΠ²Π΅ΡΡ
Π½ΠΎΡΡΡ
surf = ax.plot_surface(X, Y, Z, cmap=cm.coolwarm)
plt.show()
Gwybod ymlaen llaw mai'r lleiafswm yw 0 yn , gadewch i ni edrych ar enghreifftiau o sut i bennu gwerth lleiaf y swyddogaeth Rosenbrock gan ddefnyddio gweithdrefnau scipy.optimize amrywiol.
Nelder-Mead dull simplex
Gadewch fod pwynt cychwynnol x0 mewn gofod 5-dimensiwn. Gadewch i ni ddod o hyd i bwynt lleiaf swyddogaeth Rosenbrock sydd agosaf ato gan ddefnyddio'r algorithm (mae'r algorithm wedi'i nodi fel gwerth y paramedr dull):
from scipy.optimize import minimize
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='nelder-mead',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 339
Function evaluations: 571
[1. 1. 1. 1. 1.]Y dull simplex yw'r ffordd symlaf o leihau swyddogaeth eithaf llyfn a diffiniedig yn benodol. Nid oes angen cyfrifo deilliadau swyddogaeth; mae'n ddigon i nodi ei werthoedd yn unig. Mae'r dull Nelder-Mead yn ddewis da ar gyfer problemau lleihau syml. Fodd bynnag, gan nad yw'n defnyddio amcangyfrifon graddiant, gall gymryd mwy o amser i ddod o hyd i'r isafswm.
dull Powell
Algorithm optimeiddio arall lle mai dim ond y gwerthoedd swyddogaeth sy'n cael eu cyfrifo yw . Er mwyn ei ddefnyddio, mae angen i chi osod method = 'powell' yn y ffwythiant minim.
x0 = np.array([1.3, 0.7, 0.8, 1.9, 1.2])
res = minimize(rosen, x0, method='powell',
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 1622
[1. 1. 1. 1. 1.]Algorithm Broyden-Fletcher-Goldfarb-Shanno (BFGS).
Er mwyn cael cydgyfeiriant cyflymach i ateb, y weithdrefn yn defnyddio graddiant y ffwythiant gwrthrychol. Gellir pennu'r graddiant fel ffwythiant neu ei gyfrifo gan ddefnyddio gwahaniaethau trefn gyntaf. Beth bynnag, mae dull BFGS fel arfer yn gofyn am lai o alwadau swyddogaeth na'r dull simplex.
Gadewch inni ddod o hyd i ddeilliad swyddogaeth Rosenbrock ar ffurf ddadansoddol:
Mae'r ymadrodd hwn yn ddilys ar gyfer deilliadau pob newidyn ac eithrio'r cyntaf a'r olaf, a ddiffinnir fel:
Edrychwn ar y swyddogaeth Python sy'n cyfrifo'r graddiant hwn:
def rosen_der (x):
xm = x [1: -1]
xm_m1 = x [: - 2]
xm_p1 = x [2:]
der = np.zeros_like (x)
der [1: -1] = 200 * (xm-xm_m1 ** 2) - 400 * (xm_p1 - xm ** 2) * xm - 2 * (1-xm)
der [0] = -400 * x [0] * (x [1] -x [0] ** 2) - 2 * (1-x [0])
der [-1] = 200 * (x [-1] -x [-2] ** 2)
return derPennir y ffwythiant cyfrifo graddiant fel gwerth paramedr jac y ffwythiant minim, fel y dangosir isod.
res = minimize(rosen, x0, method='BFGS', jac=rosen_der, options={'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 25
Function evaluations: 30
Gradient evaluations: 30
[1.00000004 1.0000001 1.00000021 1.00000044 1.00000092]Algorithm graddiant cyfun (Newton)
Algorithm yn ddull Newton wedi'i addasu.
Mae dull Newton yn seiliedig ar frasamcanu ffwythiant mewn ardal leol yn Γ΄l polynomial o'r ail radd:
lle yw matrics ail ddeilliadau (matrics Hessian, Hessian).
Os yw'r Hesian yn bositif yn bendant, yna gellir canfod lleiafswm lleol y ffwythiant hwn trwy hafalu graddiant sero y ffurf cwadratig i sero. Y canlyniad fydd y mynegiant:
Cyfrifir yr Hessian gwrthdro gan ddefnyddio'r dull graddiant cyfun. Rhoddir enghraifft isod o ddefnyddio'r dull hwn i leihau swyddogaeth Rosenbrock. I ddefnyddio'r dull Newton-CG, rhaid i chi nodi ffwythiant sy'n cyfrifo'r Hesian.
Mae swyddogaeth Hesian y Rosenbrock ar ffurf ddadansoddol yn hafal i:
lle ΠΈ , diffinio'r matrics .
Mae gweddill yr elfennau di-sero o'r matrics yn hafal i:
Er enghraifft, mewn gofod pum dimensiwn N = 5, mae gan y matrics Hessian ar gyfer swyddogaeth Rosenbrock ar ffurf band:
Cod sy'n cyfrifo'r Hesian hwn ynghyd Γ’ chod ar gyfer lleihau swyddogaeth Rosenbrock gan ddefnyddio'r dull graddiant cyfun (Newton):
def rosen_hess(x):
x = np.asarray(x)
H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1)
diagonal = np.zeros_like(x)
diagonal[0] = 1200*x[0]**2-400*x[1]+2
diagonal[-1] = 200
diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:]
H = H + np.diag(diagonal)
return H
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hess=rosen_hess,
options={'xtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 24
[1. 1. 1. 0.99999999 0.99999999]Enghraifft gyda diffiniad o swyddogaeth cynnyrch yr Hessian a fector mympwyol
Mewn problemau yn y byd go iawn, gall cyfrifiadura a storio'r matrics Hessian cyfan ofyn am adnoddau amser a chof sylweddol. Yn yr achos hwn, nid oes angen nodi'r matrics Hessian ei hun mewn gwirionedd, oherwydd dim ond fector sy'n hafal i gynnyrch yr Hessian Γ’ fector mympwyol arall sydd ei angen ar y weithdrefn leihau. Felly, o safbwynt cyfrifiannol, mae'n llawer gwell diffinio swyddogaeth ar unwaith sy'n dychwelyd canlyniad cynnyrch yr Hessian gyda fector mympwyol.
Ystyriwch ffwythiant hess, sy'n cymryd y fector lleihau fel y ddadl gyntaf, a fector mympwyol fel yr ail ddadl (ynghyd Γ’ dadleuon eraill y ffwythiant i'w lleihau). Yn ein hachos ni, nid yw'n anodd iawn cyfrifo cynnyrch swyddogaeth Hessian y Rosenbrock gyda fector mympwyol. Os p yn fector mympwyol, yna'r cynnyrch edrych fel:
Mae'r ffwythiant sy'n cyfrifo cynnyrch yr Hessian a fector mympwyol yn cael ei basio fel gwerth yr arg hessp i'r ffwythiant minimol:
def rosen_hess_p(x, p):
x = np.asarray(x)
Hp = np.zeros_like(x)
Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1]
Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1]
-400*x[1:-1]*p[2:]
Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1]
return Hp
res = minimize(rosen, x0, method='Newton-CG',
jac=rosen_der, hessp=rosen_hess_p,
options={'xtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 24
Function evaluations: 33
Gradient evaluations: 56
Hessian evaluations: 66Algorithm rhanbarth ymddiriedaeth graddiant cyfun (Newton)
Gall cyflyru gwael y matrics Hessian a chyfarwyddiadau chwilio anghywir achosi i algorithm graddiant cyfun Newton fod yn aneffeithiol. Mewn achosion o'r fath, rhoddir blaenoriaeth i (rhanbarth ymddiriedolaeth) sy'n cyfuno graddiannau Newton.
Enghraifft gyda diffiniad y matrics Hessian:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 19
[1. 1. 1. 1. 1.]Enghraifft gyda swyddogaeth cynnyrch yr Hessian a fector mympwyol:
res = minimize(rosen, x0, method='trust-ncg',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
print(res.x)Optimization terminated successfully.
Current function value: 0.000000
Iterations: 20
Function evaluations: 21
Gradient evaluations: 20
Hessian evaluations: 0
[1. 1. 1. 1. 1.]Dulliau math Krylov
Fel y dull trust-ncg, mae dulliau math Krylov yn addas iawn ar gyfer datrys problemau ar raddfa fawr oherwydd eu bod yn defnyddio cynhyrchion matrics-fector yn unig. Eu hanfod yw datrys problem mewn rhanbarth hyder sydd wedi'i gyfyngu gan is-ofod Krylov cwtogedig. Ar gyfer problemau ansicr, mae'n well defnyddio'r dull hwn, gan ei fod yn defnyddio nifer llai o iteriadau aflinol oherwydd y nifer llai o gynhyrchion matrics-fector fesul subproblem, o'i gymharu Γ’'r dull trust-ncg. Yn ogystal, canfyddir yr ateb i'r is-broblem cwadratig yn fwy cywir na defnyddio'r dull trust-ncg.
Enghraifft gyda diffiniad y matrics Hessian:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 18
print(res.x)
[1. 1. 1. 1. 1.]
Enghraifft gyda swyddogaeth cynnyrch yr Hessian a fector mympwyol:
res = minimize(rosen, x0, method='trust-krylov',
jac=rosen_der, hessp=rosen_hess_p,
options={'gtol': 1e-8, 'disp': True})
Optimization terminated successfully.
Current function value: 0.000000
Iterations: 19
Function evaluations: 20
Gradient evaluations: 20
Hessian evaluations: 0
print(res.x)
[1. 1. 1. 1. 1.]
Algorithm ar gyfer datrysiad bras yn y rhanbarth hyder
Mae'r holl ddulliau (Newton-CG, trust-ncg ac trust-krylov) yn addas iawn ar gyfer datrys problemau ar raddfa fawr (gyda miloedd o newidynnau). Mae hyn oherwydd y ffaith bod yr algorithm graddiant cyfun gwaelodol yn awgrymu penderfyniad bras o'r matrics Hessian gwrthdro. Mae'r ateb i'w gael yn ailadroddol, heb ehangu'r Hessian yn benodol. Gan mai dim ond ar gyfer cynnyrch Hessian a fector mympwyol y mae angen i chi ddiffinio swyddogaeth, mae'r algorithm hwn yn arbennig o dda ar gyfer gweithio gyda matricsau gwasgaredig (band croeslin). Mae hyn yn darparu costau cof isel ac arbedion amser sylweddol.
Ar gyfer problemau canolig eu maint, nid yw cost storio a ffactorio'r Hesian yn hollbwysig. Mae hyn yn golygu ei bod hi'n bosibl cael datrysiad mewn llai o iteriadau, gan ddatrys is-broblemau rhanbarth yr ymddiriedolaeth bron yn union. I wneud hyn, mae rhai hafaliadau aflinol yn cael eu datrys yn ailadroddol ar gyfer pob is-broblem cwadratig. Mae datrysiad o'r fath fel arfer yn gofyn am 3 neu 4 o ddadelfennu Cholesky o'r matrics Hessian. O ganlyniad, mae'r dull yn cydgyfeirio mewn llai o iteriadau ac mae angen llai o gyfrifiadau swyddogaeth gwrthrychol na dulliau rhanbarth hyder eraill a weithredir. Mae'r algorithm hwn ond yn awgrymu penderfyniad y matrics Hessian cyflawn ac nid yw'n cefnogi'r gallu i ddefnyddio swyddogaeth cynnyrch yr Hessian a fector mympwyol.
Enghraifft gyda lleihau swyddogaeth Rosenbrock:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization terminated successfully.
Current function value: 0.000000
Iterations: 13
Function evaluations: 14
Gradient evaluations: 13
Hessian evaluations: 14
array([1., 1., 1., 1., 1.])Mae'n debyg y byddwn yn stopio yno. Yn yr erthygl nesaf byddaf yn ceisio dweud y pethau mwyaf diddorol am leihau amodol, cymhwyso minimeiddio wrth ddatrys problemau brasamcanu, lleihau swyddogaeth un newidyn, lleihauyddion mympwyol, a dod o hyd i wreiddiau system o hafaliadau gan ddefnyddio'r scipy.optimize pecyn.
Ffynhonnell:
Ffynhonnell: hab.com