🥇SciPy, अनुकूलन | प्रोहोस्टर

SciPy (उच्चारण साई पाई) Numpy पाइथन विस्तारमा आधारित एक गणितीय अनुप्रयोग प्याकेज हो। SciPy को साथ, तपाइँको अन्तरक्रियात्मक पाइथन सत्र MATLAB, IDL, Octave, R-Lab, र SciLab जस्तै समान पूर्ण डाटा विज्ञान र जटिल प्रणाली प्रोटोटाइप वातावरण बन्छ। आज म scipy.optimize प्याकेजमा केही प्रख्यात अप्टिमाइजेसन एल्गोरिदमहरू कसरी प्रयोग गर्ने भन्ने बारेमा छोटकरीमा कुरा गर्न चाहन्छु। प्रकार्यहरू प्रयोग गर्न थप विस्तृत र अप-टु-डेट मद्दत सधैं मद्दत() आदेश वा Shift+Tab प्रयोग गरेर प्राप्त गर्न सकिन्छ।

परिचय

आफूलाई र पाठकहरूलाई प्राथमिक स्रोतहरू खोज्न र पढ्नबाट बचाउनको लागि, विधिहरूको विवरणहरूको लिङ्कहरू मुख्य रूपमा विकिपिडियामा हुनेछन्। एक नियमको रूपमा, यो जानकारी सामान्य सर्तहरूमा विधिहरू र तिनीहरूको आवेदनका लागि सर्तहरू बुझ्न पर्याप्त छ। गणितीय विधिहरूको सार बुझ्नको लागि, थप आधिकारिक प्रकाशनहरूको लिङ्कहरू पछ्याउनुहोस्, जुन प्रत्येक लेखको अन्त्यमा वा तपाईंको मनपर्ने खोज इन्जिनमा फेला पार्न सकिन्छ।

त्यसैले, scipy.optimize मोड्युलले निम्न प्रक्रियाहरूको कार्यान्वयन समावेश गर्दछ:

विभिन्न एल्गोरिदमहरू (नेल्डर-मीड सिम्प्लेक्स, BFGS, न्यूटन कन्जुगेट ग्रेडियन्टहरू) प्रयोग गरेर धेरै चरहरू (न्यूनतम) को स्केलर प्रकार्यहरूको सशर्त र बिना शर्त न्यूनीकरण, कोबिला и SLSQP)
ग्लोबल अप्टिमाइजेसन (उदाहरणका लागि: बेसिनहपिङ, diff_evolution)
अवशिष्टहरू न्यूनीकरण गर्दै MNC (least_squares) र वक्र फिटिंग एल्गोरिदमहरू nonlinear न्यूनतम वर्गहरू प्रयोग गरेर (curve_fit)
एउटा चर (minim_scalar) को स्केलर प्रकार्यहरू न्यूनतम गर्दै र जराहरू खोज्दै (root_scalar)
विभिन्न एल्गोरिदमहरू (हाइब्रिड पावेल, Levenberg-Marquardt वा ठूला स्तरका विधिहरू जस्तै न्यूटन-क्रिलोभ).

यस लेखमा हामी यो सम्पूर्ण सूचीबाट पहिलो वस्तुलाई मात्र विचार गर्नेछौं।

धेरै चरहरूको स्केलर प्रकार्यको बिना शर्त न्यूनीकरण

scipy.optimize प्याकेजबाट न्यूनतम प्रकार्यले धेरै चरहरूको स्केलर प्रकार्यहरूको सशर्त र बिना शर्त न्यूनीकरण समस्याहरू समाधान गर्नको लागि सामान्य इन्टरफेस प्रदान गर्दछ। यसले कसरी काम गर्छ भनेर देखाउनको लागि, हामीलाई धेरै चरहरूको उपयुक्त प्रकार्य चाहिन्छ, जसलाई हामीले विभिन्न तरिकामा न्यूनिकरण गर्नेछौं।

यी उद्देश्यका लागि, N चरहरूको रोजेनब्रोक प्रकार्य उत्तम छ, जसको फारम छ:

Rosenbrock प्रकार्य र यसको Jacobi र Hessian matrices (क्रमशः पहिलो र दोस्रो डेरिभेटिभहरू) पहिले नै scipy.optimize प्याकेजमा परिभाषित गरिएको छ भन्ने तथ्यको बावजुद, हामी यसलाई आफैं परिभाषित गर्नेछौं।

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)

स्पष्टताको लागि, दुई चरहरूको रोजेनब्रोक प्रकार्यको मानहरू 3D मा कोरौं।

रेखाचित्र कोड

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()

न्यूनतम ० मा छ भनेर अग्रिम थाहा छ , विभिन्न scipy.optimize प्रक्रियाहरू प्रयोग गरेर रोजेनब्रोक प्रकार्यको न्यूनतम मान कसरी निर्धारण गर्ने भन्ने उदाहरणहरू हेरौं।

नेल्डर-मीड सिम्प्लेक्स विधि

0-आयामिक स्पेसमा प्रारम्भिक बिन्दु x5 हुन दिनुहोस्। एल्गोरिथ्म प्रयोग गरेर यसको नजिकको रोजेनब्रोक प्रकार्यको न्यूनतम बिन्दु पत्ता लगाउनुहोस् नेल्डर-मीड सिम्प्लेक्स (एल्गोरिथ्म विधि प्यारामिटरको मानको रूपमा निर्दिष्ट गरिएको छ):

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.]

सिम्प्लेक्स विधि स्पष्ट रूपमा परिभाषित र पर्याप्त चिकनी प्रकार्यलाई कम गर्नको लागि सरल तरिका हो। यो एक प्रकार्य को डेरिभेटिभ गणना गर्न आवश्यक छैन; यो केवल यसको मान निर्दिष्ट गर्न पर्याप्त छ। Nelder-Mead विधि सरल न्यूनीकरण समस्याहरूको लागि राम्रो विकल्प हो। यद्यपि, यसले ढाँचा अनुमानहरू प्रयोग गर्दैन, यसले न्यूनतम फेला पार्न धेरै समय लिन सक्छ।

पावेल विधि

अर्को अप्टिमाइजेसन एल्गोरिथ्म जसमा केवल प्रकार्य मानहरू गणना गरिन्छ पावेलको विधि। यसलाई प्रयोग गर्न, तपाईंले विधि = 'पावेल' न्यूनतम प्रकार्यमा सेट गर्न आवश्यक छ।

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) एल्गोरिथ्म

समाधानको लागि छिटो अभिसरण प्राप्त गर्न, प्रक्रिया BFGS उद्देश्य प्रकार्यको ग्रेडियन्ट प्रयोग गर्दछ। ढाँचालाई प्रकार्यको रूपमा निर्दिष्ट गर्न सकिन्छ वा पहिलो अर्डर भिन्नताहरू प्रयोग गरेर गणना गर्न सकिन्छ। कुनै पनि अवस्थामा, BFGS विधिलाई सामान्यतया सिम्प्लेक्स विधि भन्दा कम प्रकार्य कलहरू चाहिन्छ।

हामी Rosenbrock प्रकार्य को व्युत्पन्न विश्लेषणात्मक रूप मा फेला पारौं:

यो अभिव्यक्ति पहिलो र अन्तिम बाहेक सबै चरहरूको डेरिभेटिभहरूको लागि मान्य छ, जसलाई निम्न रूपमा परिभाषित गरिएको छ:

यो ढाँचा गणना गर्ने पाइथन प्रकार्यलाई हेरौं:

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 der

ग्रेडियन्ट गणना प्रकार्यलाई न्यूनतम प्रकार्यको jac प्यारामिटरको मानको रूपमा निर्दिष्ट गरिएको छ, जस्तै तल देखाइएको छ।

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]

कन्जुगेट ग्रेडियन्ट एल्गोरिथ्म (न्यूटन)

एल्गोरिथ्म न्यूटनको कन्जुगेट ग्रेडियन्टहरू न्यूटनको परिमार्जित विधि हो।
न्यूटनको विधि दोस्रो डिग्रीको बहुपदद्वारा स्थानीय क्षेत्रमा कार्य अनुमानित गर्नमा आधारित छ:

जहाँ दोस्रो डेरिभेटिभको म्याट्रिक्स हो (हेसियन म्याट्रिक्स, हेसियन)।
यदि हेसियन सकारात्मक निश्चित छ भने, यस प्रकार्यको स्थानीय न्यूनतमलाई द्विघात फारमको शून्य ग्रेडियन्टलाई शून्यमा बराबर गरेर फेला पार्न सकिन्छ। परिणाम अभिव्यक्ति हुनेछ:

इन्वर्स हेसियन कन्जुगेट ग्रेडियन्ट विधि प्रयोग गरेर गणना गरिन्छ। Rosenbrock प्रकार्यलाई कम गर्न यो विधि प्रयोग गर्ने उदाहरण तल दिइएको छ। Newton-CG विधि प्रयोग गर्न, तपाईंले हेसियन गणना गर्ने प्रकार्य निर्दिष्ट गर्नुपर्छ।
विश्लेषणात्मक रूप मा रोजेनब्रोक प्रकार्य को हेसियन बराबर छ:

जहाँ и , म्याट्रिक्स परिभाषित गर्नुहोस् .

म्याट्रिक्सका बाँकी गैर-शून्य तत्वहरू बराबर छन्:

उदाहरणका लागि, पाँच-आयामी स्पेस N = 5 मा, रोजेनब्रोक प्रकार्यको लागि हेसियन म्याट्रिक्समा ब्यान्डको रूप हुन्छ:

कोड जसले कन्जुगेट ग्रेडियन्ट (न्यूटन) विधि प्रयोग गरेर रोजेनब्रोक प्रकार्यलाई कम गर्नको लागि कोड सहित यो हेसियन गणना गर्दछ:

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]

हेसियन र एक स्वेच्छाचारी भेक्टर को उत्पादन प्रकार्य को परिभाषा संग एक उदाहरण

वास्तविक-विश्व समस्याहरूमा, सम्पूर्ण हेसियन म्याट्रिक्स कम्प्युटिङ र भण्डारण गर्न महत्त्वपूर्ण समय र मेमोरी स्रोतहरू आवश्यक पर्दछ। यस अवस्थामा, त्यहाँ वास्तवमा हेसियन म्याट्रिक्स आफै निर्दिष्ट गर्न आवश्यक छैन, किनभने मिनिमाइजेशन प्रक्रियाले अर्को स्वेच्छाचारी भेक्टरसँग हेसियनको गुणन बराबर भेक्टर मात्र चाहिन्छ। तसर्थ, कम्प्युटेसनल दृष्टिकोणबाट, यो तुरुन्तै एक प्रकार्य परिभाषित गर्न धेरै राम्रो हुन्छ जसले हेसियनको उत्पादनको नतिजा स्वेच्छाचारी भेक्टरसँग फर्काउँछ।

हेस प्रकार्यलाई विचार गर्नुहोस्, जसले मिनिमाइजेसन भेक्टरलाई पहिलो आर्गुमेन्टको रूपमा लिन्छ, र दोस्रो आर्गुमेन्टको रूपमा एक आर्बिट्रेरी भेक्टर (न्यूनतम गर्नका लागि प्रकार्यका अन्य तर्कहरूसँगै)। हाम्रो मामला मा, एक स्वैच्छिक भेक्टर संग Rosenbrock प्रकार्य को Hessian को गुणन गणना धेरै गाह्रो छैन। यदि p एक स्वेच्छाचारी भेक्टर हो, त्यसपछि उत्पादन फारम छ:

हेसियन र एक स्वेच्छाचारी भेक्टरको गुणन गणना गर्ने प्रकार्यलाई मिनिमाइज प्रकार्यमा हेस्प आर्गुमेन्टको मानको रूपमा पास गरिन्छ:

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: 66

कन्जुगेट ग्रेडियन्ट ट्रस्ट क्षेत्र एल्गोरिथ्म (न्यूटन)

हेसियन म्याट्रिक्सको खराब कन्डिसनिङ र गलत खोज निर्देशनहरूले न्यूटनको कन्जुगेट ग्रेडियन्ट एल्गोरिथ्म प्रभावहीन हुन सक्छ। यस्तो अवस्थामा, प्राथमिकता दिइन्छ विश्वास क्षेत्र विधि (ट्रस्ट-क्षेत्र) कन्जुगेट न्यूटन ग्रेडियन्ट।

हेसियन म्याट्रिक्स को परिभाषा संग उदाहरण:

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.]

हेसियन र एक स्वैच्छिक भेक्टरको उत्पादन प्रकार्यको साथ उदाहरण:

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.]

Krylov प्रकार विधिहरू

ट्रस्ट-एनसीजी विधि जस्तै, क्राइलोभ-प्रकारका विधिहरू ठूला-ठूला समस्याहरू समाधान गर्नका लागि उपयुक्त छन् किनभने तिनीहरूले म्याट्रिक्स-भेक्टर उत्पादनहरू मात्र प्रयोग गर्छन्। तिनीहरूको सार एक ट्रंकेटेड Krylov सबस्पेस द्वारा सीमित आत्मविश्वास क्षेत्र मा समस्या समाधान गर्न छ। अनिश्चित समस्याहरूका लागि, यो विधि प्रयोग गर्नु राम्रो हुन्छ, किनकि यसले ट्रस्ट-एनसीजी विधिको तुलनामा, प्रति सबसमस्या म्याट्रिक्स-भेक्टर उत्पादनहरूको सानो संख्याको कारणले गर्दा यो ननलाइनर पुनरावृत्तिहरूको सानो संख्या प्रयोग गर्दछ। थप रूपमा, ट्रस्ट-एनसीजी विधि प्रयोग गर्नु भन्दा चतुर्भुज उपसमस्याको समाधान अधिक सटीक रूपमा पाइन्छ।
हेसियन म्याट्रिक्स को परिभाषा संग उदाहरण:

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.]

हेसियन र एक स्वैच्छिक भेक्टरको उत्पादन प्रकार्यको साथ उदाहरण:

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.]

विश्वास क्षेत्र मा अनुमानित समाधान को लागी एल्गोरिथ्म

सबै विधिहरू (न्यूटन-सीजी, ट्रस्ट-एनसीजी र ट्रस्ट-क्रिलोभ) ठूला-ठूला समस्याहरू समाधान गर्नका लागि उपयुक्त छन् (हजारौं चरहरूसँग)। यो तथ्यको कारण हो कि अन्तर्निहित कन्जुगेट ग्रेडियन्ट एल्गोरिथ्मले व्युत्क्रम हेसियन म्याट्रिक्सको अनुमानित निर्धारणलाई संकेत गर्दछ। समाधान हेसियनको स्पष्ट विस्तार बिना पुनरावृत्ति फेला पर्यो। तपाईंले हेसियन र एक स्वेच्छाचारी भेक्टरको उत्पादनका लागि मात्र प्रकार्य परिभाषित गर्न आवश्यक भएकोले, यो एल्गोरिथ्म स्प्यार्स (ब्यान्ड विकर्ण) म्याट्रिकहरूसँग काम गर्नको लागि विशेष गरी राम्रो छ। यसले कम मेमोरी लागत र महत्त्वपूर्ण समय बचत प्रदान गर्दछ।

मध्यम आकारको समस्याहरूको लागि, हेसियन भण्डारण र फ्याक्टरिङको लागत महत्त्वपूर्ण छैन। यसको मतलब यो हो कि यो कम पुनरावृत्ति मा एक समाधान प्राप्त गर्न सम्भव छ, लगभग ठ्याक्कै विश्वास क्षेत्र को उपसमस्याहरु को समाधान। यो गर्नका लागि, प्रत्येक द्विघाती उपसमस्याका लागि केही ननलाइनर समीकरणहरू पुनरावृत्ति रूपमा समाधान गरिन्छ। यस्तो समाधानलाई सामान्यतया हेसियन म्याट्रिक्सको 3 वा 4 Cholesky विघटन चाहिन्छ। नतिजाको रूपमा, विधिले कम पुनरावृत्तिहरूमा रूपान्तरण गर्दछ र अन्य कार्यान्वयन गरिएका विश्वास क्षेत्र विधिहरू भन्दा कम वस्तुगत प्रकार्य गणनाहरू आवश्यक पर्दछ। यो एल्गोरिदमले पूर्ण हेसियन म्याट्रिक्स निर्धारण मात्र समावेश गर्दछ र हेसियनको उत्पादन प्रकार्य र एक स्वेच्छाचारी भेक्टर प्रयोग गर्ने क्षमतालाई समर्थन गर्दैन।

Rosenbrock प्रकार्य को न्यूनतम संग उदाहरण:

res = minimize(rosen, x0, method='trust-exact',
               jac=rosen_der, hess=rosen_hess,
               options={'gtol': 1e-8, 'disp': True})
res.x

Optimization terminated successfully.
         Current function value: 0.000000
         Iterations: 13
         Function evaluations: 14
         Gradient evaluations: 13
         Hessian evaluations: 14

array([1., 1., 1., 1., 1.])

हामी सायद त्यहाँ रोकिनेछौं। अर्को लेखमा म सशर्त न्यूनीकरणको बारेमा सबैभन्दा रोचक कुराहरू बताउन प्रयास गर्नेछु, अनुमानित समस्याहरू समाधान गर्न मिनिमाइजेसनको प्रयोग, एउटा चरको प्रकार्यलाई न्यूनीकरण गर्ने, स्वेच्छाचारी मिनिमाइजरहरू, र scipy.optimize प्रयोग गरेर समीकरणहरूको प्रणालीको जरा पत्ता लगाउने। प्याकेज।

स्रोत: https://docs.scipy.org/doc/scipy/reference/

स्रोत: www.habr.com

SciPy, अनुकूलन