SciPy (inayotamkwa sai pie) ni kifurushi cha matumizi ya hisabati kulingana na kiendelezi cha Numpy Python. Ukiwa na SciPy, kipindi chako shirikishi cha Python kinakuwa sayansi kamili ya data na mazingira changamano ya uchapaji wa mfumo kama MATLAB, IDL, Octave, R-Lab, na SciLab. Leo nataka kuzungumza kwa ufupi juu ya jinsi ya kutumia algorithms fulani inayojulikana ya uboreshaji kwenye kifurushi cha scipy.optimize. Usaidizi wa kina na wa kisasa zaidi wa kutumia vipengele unaweza kupatikana kila wakati kwa kutumia help() amri au kwa kutumia Shift+Tab.
Utangulizi
Ili kujiokoa wewe na wasomaji kutokana na kutafuta na kusoma vyanzo vya msingi, viungo vya maelezo ya mbinu vitakuwa hasa kwenye Wikipedia. Kama sheria, habari hii inatosha kuelewa njia kwa maneno ya jumla na masharti ya matumizi yao. Ili kuelewa kiini cha mbinu za hisabati, fuata viungo vya machapisho yenye mamlaka zaidi, ambayo yanaweza kupatikana mwishoni mwa kila makala au katika injini yako ya utafutaji ya favorite.
Kwa hivyo, moduli ya scipy.optimize inajumuisha utekelezaji wa taratibu zifuatazo:
- Upunguzaji wa masharti na usio na masharti wa kazi za scalar za vigezo kadhaa (minim) kwa kutumia algoriti mbalimbali (Nelder-Mead simplex, BFGS, Newton conjugate gradients, ΠΈ )
- Uboreshaji wa ulimwengu (kwa mfano: , )
- Kupunguza mabaki (least_squares) na algoriti zinazolingana na curve kwa kutumia miraba isiyo ya mstari (curve_fit)
- Kupunguza utendakazi wa scalar wa kigezo kimoja (minim_scalar) na kutafuta mizizi (root_scalar)
- Vitatuzi vya multidimensional vya mfumo wa hesabu (mizizi) kwa kutumia algorithms anuwai (mseto wa Powell, au njia za kiwango kikubwa kama vile ).
Katika makala hii tutazingatia tu bidhaa ya kwanza kutoka kwenye orodha hii yote.
Kupunguza bila masharti ya kazi ya scalar ya vigezo kadhaa
Utendakazi mdogo kutoka kwa kifurushi cha scipy.optimize hutoa kiolesura cha jumla kwa ajili ya kutatua matatizo ya upunguzaji wa masharti na bila masharti ya kazi za scalar za vigezo kadhaa. Ili kuonyesha jinsi inavyofanya kazi, tutahitaji kazi inayofaa ya vigezo kadhaa, ambayo tutapunguza kwa njia tofauti.
Kwa madhumuni haya, kazi ya Rosenbrock ya anuwai ya N ni kamili, ambayo ina fomu:
Licha ya ukweli kwamba kazi ya Rosenbrock na matrices yake ya Jacobi na Hessian (derivatives ya kwanza na ya pili, kwa mtiririko huo) tayari imefafanuliwa katika mfuko wa scipy.optimize, tutafafanua wenyewe.
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)Kwa uwazi, hebu tuchore katika 3D maadili ya kazi ya Rosenbrock ya vigezo viwili.
Msimbo wa kuchora
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()
Kujua mapema kwamba kiwango cha chini ni 0 saa , hebu tuangalie mifano ya jinsi ya kuamua thamani ya chini ya kazi ya Rosenbrock kwa kutumia taratibu mbalimbali za scipy.optimize.
Mbinu ya Nelder-Mead simplex
Acha kuwe na sehemu ya mwanzo x0 katika nafasi ya 5-dimensional. Wacha tupate kiwango cha chini cha kazi ya Rosenbrock karibu nayo kwa kutumia algorithm (algorithm imeainishwa kama thamani ya paramu ya njia):
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.]Njia rahisi ni njia rahisi zaidi ya kupunguza utendaji uliofafanuliwa wazi na laini. Haihitaji kuhesabu derivatives ya chaguo za kukokotoa; inatosha kutaja tu maadili yake. Njia ya Nelder-Mead ni chaguo nzuri kwa shida rahisi za kupunguza. Hata hivyo, kwa kuwa haitumii makadirio ya upinde rangi, inaweza kuchukua muda mrefu kupata kiwango cha chini zaidi.
Njia ya Powell
Algorithm nyingine ya uboreshaji ambayo tu maadili ya kazi huhesabiwa . Ili kuitumia, unahitaji kuweka method = 'powell' katika kitendakazi cha 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.]Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm
Ili kupata muunganisho wa haraka kwa suluhisho, utaratibu hutumia gradient ya kitendakazi cha lengo. Upinde rangi unaweza kubainishwa kama chaguo za kukokotoa au kukokotwa kwa kutumia tofauti za mpangilio wa kwanza. Kwa hali yoyote, mbinu ya BFGS kawaida inahitaji simu chache za utendaji kuliko mbinu rahisi.
Wacha tupate derivative ya kazi ya Rosenbrock katika fomu ya uchambuzi:
Usemi huu ni halali kwa derivatives ya anuwai zote isipokuwa ya kwanza na ya mwisho, ambayo hufafanuliwa kama:
Wacha tuangalie kazi ya Python inayohesabu gradient hii:
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 derKitendakazi cha kukokotoa upinde rangi kimebainishwa kama thamani ya kigezo cha jac cha chaguo za kukokotoa za minim, kama inavyoonyeshwa hapa chini.
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 ya upinde rangi ya kuunganisha (Newton)
Algorithm ni njia iliyorekebishwa ya Newton.
Njia ya Newton inategemea kukadiria utendaji katika eneo la karibu na polynomial ya shahada ya pili:
ambapo ni matrix ya derivatives ya pili (Matrix ya Hessian, Hessian).
Ikiwa Hessian ni chanya dhahiri, basi kima cha chini cha ndani cha chaguo hili la kukokotoa kinaweza kupatikana kwa kusawazisha upinde rangi ya sifuri ya umbo la robo na sifuri. Matokeo yake yatakuwa usemi:
Hessian kinyume inakokotolewa kwa kutumia mbinu ya upinde rangi ya mnyambuliko. Mfano wa kutumia njia hii ili kupunguza kazi ya Rosenbrock imetolewa hapa chini. Ili kutumia njia ya Newton-CG, lazima ubainishe chaguo za kukokotoa zinazokokotoa Hessian.
Hessian ya kazi ya Rosenbrock katika fomu ya uchanganuzi ni sawa na:
ambapo ΠΈ , fafanua matrix .
Vipengele vilivyobaki visivyo vya sifuri vya matrix ni sawa na:
Kwa mfano, katika nafasi ya tano-dimensional N = 5, tumbo la Hessian kwa kazi ya Rosenbrock ina umbo la bendi:
Msimbo unaokokotoa Hessian hii pamoja na msimbo wa kupunguza kitendakazi cha Rosenbrock kwa kutumia njia ya upinde rangi ya kuunganisha (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]Mfano na ufafanuzi wa kazi ya bidhaa ya Hessian na vector ya kiholela
Katika matatizo ya ulimwengu halisi, kompyuta na kuhifadhi matrix yote ya Hessian inaweza kuhitaji rasilimali za muda na kumbukumbu. Katika kesi hii, kwa kweli hakuna haja ya kutaja tumbo la Hessian yenyewe, kwa sababu utaratibu wa kupunguza unahitaji tu vekta sawa na bidhaa ya Hessian na vekta nyingine ya kiholela. Kwa hivyo, kutoka kwa mtazamo wa hesabu, ni vyema zaidi kufafanua mara moja kazi ambayo inarudi matokeo ya bidhaa ya Hessian na vector ya kiholela.
Fikiria kazi ya hess, ambayo inachukua vekta ya kupunguza kama hoja ya kwanza, na vekta ya kiholela kama hoja ya pili (pamoja na hoja zingine za chaguo la kukokotoa kupunguzwa). Kwa upande wetu, kuhesabu bidhaa ya Hessian ya kazi ya Rosenbrock na vector ya kiholela si vigumu sana. Kama p ni vector kiholela, basi bidhaa inaonekana kama:
Chaguo za kukokotoa zinazokokotoa bidhaa ya Hessian na vekta ya kiholela hupitishwa kama thamani ya hoja ya hessp kwenye kitendakazi cha kupunguza:
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 ya eneo la imani ya gradient (Newton)
Uwekaji hali mbaya wa tumbo la Hessian na maelekezo yasiyo sahihi ya utafutaji yanaweza kusababisha algoriti ya uunganisho ya gradient ya Newton kutofanya kazi. Katika hali kama hizo, upendeleo hupewa (eneo la imani) unganisha gradients za Newton.
Mfano na ufafanuzi wa matrix ya 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.]Mfano na kazi ya bidhaa ya Hessian na vekta ya kiholela:
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.]Njia za aina ya Krylov
Kama njia ya uaminifu-ncg, njia za aina ya Krylov zinafaa kwa kutatua shida kubwa kwa sababu hutumia bidhaa za vekta ya matrix pekee. Kiini chao ni kutatua tatizo katika eneo la kujiamini lililopunguzwa na nafasi ndogo ya Krylov iliyopunguzwa. Kwa matatizo yasiyo ya uhakika, ni bora kutumia njia hii, kwa kuwa hutumia idadi ndogo ya marudio yasiyo ya mstari kutokana na idadi ndogo ya bidhaa za matrix-vector kwa kila tatizo, ikilinganishwa na njia ya uaminifu-ncg. Kwa kuongeza, suluhisho la tatizo la quadratic linapatikana kwa usahihi zaidi kuliko kutumia njia ya uaminifu-ncg.
Mfano na ufafanuzi wa matrix ya 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.]
Mfano na kazi ya bidhaa ya Hessian na vekta ya kiholela:
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 ya suluhisho la takriban katika eneo la kujiamini
Njia zote (Newton-CG, trust-ncg na trust-krylov) zinafaa kwa ajili ya kutatua matatizo makubwa (pamoja na maelfu ya vigezo). Hii ni kutokana na ukweli kwamba kanuni ya msingi ya upinde rangi ya unganisha inaashiria uamuzi wa kukadiria wa matriki ya Hessian kinyume. Suluhisho linapatikana mara kwa mara, bila upanuzi wa wazi wa Hessian. Kwa kuwa unahitaji tu kufafanua kazi ya bidhaa ya Hessian na vekta ya kiholela, algorithm hii ni nzuri sana kwa kufanya kazi na matrices ya sparse (bendi ya diagonal). Hii hutoa gharama ya chini ya kumbukumbu na kuokoa muda muhimu.
Kwa shida za ukubwa wa kati, gharama ya kuhifadhi na kutengeneza Hessian sio muhimu. Hii ina maana kwamba inawezekana kupata suluhisho kwa marudio machache, kutatua matatizo madogo ya eneo la uaminifu karibu kabisa. Ili kufanya hivyo, baadhi ya milinganyo isiyo ya mstari hutatuliwa mara kwa mara kwa kila tatizo ndogo la quadratic. Suluhisho kama hilo kawaida linahitaji mtengano 3 au 4 wa Cholesky wa tumbo la Hessian. Kwa hivyo, mbinu huchanganyika katika marudio machache na inahitaji mahesabu machache ya utendakazi wa lengo kuliko mbinu zingine zinazotekelezwa za eneo la imani. Kanuni hii inahusisha tu kubainisha matrix kamili ya Hessian na haiauni uwezo wa kutumia utendaji wa bidhaa wa Hessian na vekta ya kiholela.
Mfano na kupunguzwa kwa kazi ya 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.])Pengine tutaishia hapo. Katika makala inayofuata nitajaribu kueleza mambo ya kuvutia zaidi kuhusu upunguzaji wa masharti, utumiaji wa kupunguza katika kutatua matatizo ya ukadiriaji, kupunguza utendakazi wa kipunguza kimoja, kipunguza kiholela, na kutafuta mizizi ya mfumo wa milinganyo kwa kutumia scipy.optimize. kifurushi.
Chanzo:
Chanzo: mapenzi.com