SciPy, अनुकूलन

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

परिचय

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

तो, scipy.optimize मॉड्यूल में निम्नलिखित प्रक्रियाओं का कार्यान्वयन शामिल है:

1. विभिन्न एल्गोरिदम (नेल्डर-मीड सिम्प्लेक्स, बीएफजीएस, न्यूटन संयुग्म ग्रेडिएंट्स) का उपयोग करके कई चर (न्यूनतम) के स्केलर कार्यों का सशर्त और बिना शर्त न्यूनतमकरण, कोबाइला и एसएलएसक्यूपी)
2. वैश्विक अनुकूलन (उदाहरण के लिए: बेसिनहोपिंग, diff_evolution)
3. अवशेषों को न्यूनतम करना बहुराष्ट्रीय कंपनी (कम से कम वर्ग) और गैर-रेखीय न्यूनतम वर्ग (वक्र_फिट) का उपयोग करके वक्र फिटिंग एल्गोरिदम
4. एक चर (मिनिम_स्केलर) के अदिश कार्यों को न्यूनतम करना और जड़ों की खोज करना (रूट_स्केलर)
5. विभिन्न एल्गोरिदम (हाइब्रिड पॉवेल) का उपयोग करके समीकरणों की प्रणाली (रूट) के बहुआयामी सॉल्वर Levenberg-Marquardt या बड़े पैमाने पर तरीके जैसे न्यूटन-क्रायलोव).

इस लेख में हम इस पूरी सूची में से केवल पहले आइटम पर विचार करेंगे।

कई चरों के एक अदिश फलन का बिना शर्त न्यूनीकरण

Scipy.optimize पैकेज से न्यूनतम फ़ंक्शन कई चर के स्केलर कार्यों की सशर्त और बिना शर्त न्यूनतमकरण समस्याओं को हल करने के लिए एक सामान्य इंटरफ़ेस प्रदान करता है। यह प्रदर्शित करने के लिए कि यह कैसे काम करता है, हमें कई चरों के एक उपयुक्त फ़ंक्शन की आवश्यकता होगी, जिसे हम विभिन्न तरीकों से कम से कम करेंगे।

इन उद्देश्यों के लिए, एन वेरिएबल्स का रोसेनब्रॉक फ़ंक्शन एकदम सही है, जिसका रूप है:

इस तथ्य के बावजूद कि रोसेनब्रॉक फ़ंक्शन और इसके जैकोबी और हेसियन मैट्रिक्स (क्रमशः पहला और दूसरा डेरिवेटिव) पहले से ही 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)

स्पष्टता के लिए, आइए दो वेरिएबल्स के रोसेनब्रॉक फ़ंक्शन के मानों को 3डी में बनाएं।

ड्राइंग कोड

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

पहले से जानना कि न्यूनतम 0 है , आइए विभिन्न 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.]

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

पॉवेल विधि

एक अन्य अनुकूलन एल्गोरिदम जिसमें केवल फ़ंक्शन मानों की गणना की जाती है पॉवेल की विधि. इसका उपयोग करने के लिए, आपको न्यूनतम फ़ंक्शन में विधि = 'पॉवेल' सेट करना होगा।

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

ब्रोयडेन-फ्लेचर-गोल्डफार्ब-शन्नो (बीएफजीएस) एल्गोरिदम

किसी समाधान में तेजी से अभिसरण प्राप्त करने की प्रक्रिया बीएफजीएस उद्देश्य फ़ंक्शन के ग्रेडिएंट का उपयोग करता है। ग्रेडिएंट को एक फ़ंक्शन के रूप में निर्दिष्ट किया जा सकता है या पहले क्रम के अंतर का उपयोग करके गणना की जा सकती है। किसी भी स्थिति में, बीएफजीएस विधि को आमतौर पर सिंप्लेक्स विधि की तुलना में कम फ़ंक्शन कॉल की आवश्यकता होती है।

आइए हम विश्लेषणात्मक रूप में रोसेनब्रॉक फ़ंक्शन का व्युत्पन्न खोजें:

यह अभिव्यक्ति पहले और अंतिम को छोड़कर सभी चर के व्युत्पन्नों के लिए मान्य है, जिन्हें इस प्रकार परिभाषित किया गया है:

आइए पायथन फ़ंक्शन को देखें जो इस ग्रेडिएंट की गणना करता है:

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

ग्रेडिएंट गणना फ़ंक्शन को न्यूनतम फ़ंक्शन के जेएसी पैरामीटर के मान के रूप में निर्दिष्ट किया गया है, जैसा कि नीचे दिखाया गया है।

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]

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

कलन विधि न्यूटन की संयुग्मी प्रवणताएँ न्यूटन की एक संशोधित विधि है।
न्यूटन की विधि किसी स्थानीय क्षेत्र में किसी फ़ंक्शन को दूसरी डिग्री के बहुपद द्वारा अनुमानित करने पर आधारित है:

जहां दूसरे डेरिवेटिव (हेस्सियन मैट्रिक्स, हेस्सियन) का मैट्रिक्स है।
यदि हेसियन सकारात्मक निश्चित है, तो इस फ़ंक्शन का स्थानीय न्यूनतम द्विघात रूप के शून्य ग्रेडिएंट को शून्य के बराबर करके पाया जा सकता है। परिणाम अभिव्यक्ति होगी:

व्युत्क्रम हेसियन की गणना संयुग्म ढाल विधि का उपयोग करके की जाती है। रोसेनब्रॉक फ़ंक्शन को न्यूनतम करने के लिए इस विधि का उपयोग करने का एक उदाहरण नीचे दिया गया है। न्यूटन-सीजी पद्धति का उपयोग करने के लिए, आपको एक फ़ंक्शन निर्दिष्ट करना होगा जो हेसियन की गणना करता है।
विश्लेषणात्मक रूप में रोसेनब्रॉक फ़ंक्शन का हेसियन इसके बराबर है:

जहां и , मैट्रिक्स को परिभाषित करें .

मैट्रिक्स के शेष गैर-शून्य तत्व इसके बराबर हैं:

उदाहरण के लिए, पांच-आयामी स्थान 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]

हेसियन और एक मनमाना वेक्टर के उत्पाद फ़ंक्शन की परिभाषा के साथ एक उदाहरण

वास्तविक दुनिया की समस्याओं में, संपूर्ण हेसियन मैट्रिक्स की गणना और भंडारण के लिए महत्वपूर्ण समय और स्मृति संसाधनों की आवश्यकता हो सकती है। इस मामले में, वास्तव में हेसियन मैट्रिक्स को निर्दिष्ट करने की कोई आवश्यकता नहीं है, क्योंकि न्यूनीकरण प्रक्रिया के लिए केवल एक अन्य मनमाने वेक्टर के साथ हेसियन के उत्पाद के बराबर एक वेक्टर की आवश्यकता होती है। इस प्रकार, कम्प्यूटेशनल दृष्टिकोण से, एक फ़ंक्शन को तुरंत परिभाषित करना बहुत बेहतर है जो एक मनमाना वेक्टर के साथ हेसियन के उत्पाद का परिणाम लौटाता है।

हेस फ़ंक्शन पर विचार करें, जो न्यूनतमकरण वेक्टर को पहले तर्क के रूप में लेता है, और एक मनमाना वेक्टर को दूसरे तर्क के रूप में लेता है (न्यूनतम किए जाने वाले फ़ंक्शन के अन्य तर्कों के साथ)। हमारे मामले में, एक मनमाना वेक्टर के साथ रोसेनब्रॉक फ़ंक्शन के हेसियन के उत्पाद की गणना करना बहुत मुश्किल नहीं है। अगर 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.]

क्रायलोव प्रकार की विधियाँ

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

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 चोल्स्की अपघटनों की आवश्यकता होती है। परिणामस्वरूप, विधि कम पुनरावृत्तियों में परिवर्तित होती है और अन्य कार्यान्वित आत्मविश्वास क्षेत्र विधियों की तुलना में कम उद्देश्य फ़ंक्शन गणना की आवश्यकता होती है। इस एल्गोरिदम में केवल संपूर्ण हेसियन मैट्रिक्स का निर्धारण शामिल है और यह हेसियन के उत्पाद फ़ंक्शन और एक मनमाना वेक्टर का उपयोग करने की क्षमता का समर्थन नहीं करता है।

रोसेनब्रॉक फ़ंक्शन को न्यूनतम करने का उदाहरण:

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