SciPy, सर्तहरूको साथ अनुकूलन

SciPy (उच्चारण साई पाई) एक numpy-आधारित गणित प्याकेज हो जसमा C र Fortran पुस्तकालयहरू पनि समावेश छन्। SciPy ले तपाईको अन्तरक्रियात्मक पाइथन सत्रलाई MATLAB, IDL, Octave, R, वा SciLab जस्ता पूर्ण डेटा विज्ञान वातावरणमा परिणत गर्दछ।

यस लेखमा, हामी गणितीय प्रोग्रामिङको आधारभूत प्रविधिहरू हेर्नेछौं - scipy.optimize प्याकेज प्रयोग गरेर धेरै चरहरूको स्केलर प्रकार्यको लागि सशर्त अनुकूलन समस्याहरू समाधान गर्दै। अनियन्त्रित अप्टिमाइजेसन एल्गोरिदमहरू पहिले नै मा छलफल गरिएको छ अन्तिम लेख। स्किपी प्रकार्यहरूमा थप विस्तृत र अप-टु-डेट मद्दत सधैं मद्दत() आदेश, Shift+Tab वा भित्र प्रयोग गरेर प्राप्त गर्न सकिन्छ। आधिकारिक दस्तावेज.

परिचय

scipy.optimize प्याकेजमा सशर्त र अनियन्त्रित अप्टिमाइजेसन समस्याहरू समाधान गर्नको लागि एक साझा इन्टरफेस प्रकार्यद्वारा प्रदान गरिएको छ। minimize()। यद्यपि, यो ज्ञात छ कि सबै समस्याहरू समाधान गर्न कुनै विश्वव्यापी विधि छैन, त्यसैले पर्याप्त विधिको छनौट, सधैंको रूपमा, शोधकर्ताको काँधमा पर्छ।
उपयुक्त अप्टिमाइजेसन एल्गोरिथ्म प्रकार्य तर्क प्रयोग गरी निर्दिष्ट गरिएको छ minimize(..., method="").
धेरै चरहरूको प्रकार्यको सशर्त अनुकूलनको लागि, निम्न विधिहरूको कार्यान्वयनहरू उपलब्ध छन्:

• trust-constr - विश्वास क्षेत्रमा स्थानीय न्यूनतम खोज्नुहोस्। विकि लेख, Habré मा लेख;
• SLSQP - बाधाहरू सहितको क्रमिक चतुर्भुज प्रोग्रामिङ, Lagrange प्रणाली समाधान गर्न न्यूटोनियन विधि। विकि लेख.
• TNC - काटिएको न्यूटन सीमित, पुनरावृत्तिहरूको सीमित संख्या, स्वतन्त्र चरहरूको ठूलो संख्याको साथ ननलाइनर कार्यहरूको लागि राम्रो। विकि लेख.
• L-BFGS-B — Broyden–Fletcher–Goldfarb–Shanno टोलीबाट एउटा विधि, हेसियन म्याट्रिक्सबाट भेक्टरहरूको आंशिक लोडिङको कारणले मेमोरी खपत कम भएकोमा कार्यान्वयन गरियो। विकि लेख, Habré मा लेख.
• COBYLA — MARE Constrained Optimization by Linear approximation, constrained Optimization with linear approximation (gradient Calculation बिना)। विकि लेख.

छनौट गरिएको विधिको आधारमा, समस्या समाधान गर्नका लागि सर्तहरू र प्रतिबन्धहरू फरक रूपमा सेट गरिएका छन्:

• वर्ग वस्तु Bounds L-BFGS-B, TNC, SLSQP, ट्रस्ट-कन्स्ट्रर विधिहरूको लागि;
• सूची (min, max) समान विधिहरूका लागि L-BFGS-B, TNC, SLSQP, trust-constr;
• वस्तु वा वस्तुहरूको सूची LinearConstraint, NonlinearConstraint COBYLA, SLSQP, ट्रस्ट-कन्स्ट्र विधिहरूका लागि;
• शब्दकोश वा शब्दकोशहरूको सूची {'type':str, 'fun':callable, 'jac':callable,opt, 'args':sequence,opt} COBYLA, SLSQP विधिहरूको लागि।

लेख रूपरेखा:
1) विश्वास क्षेत्र (विधि="trust-constr") मा एक सशर्त अप्टिमाइजेसन एल्गोरिथ्म को प्रयोग विचार गर्नुहोस् वस्तुहरु को रूप मा निर्दिष्ट अवरोधहरु संग। Bounds, LinearConstraint, NonlinearConstraint ;
2) कम से कम वर्ग विधि (विधि = "SLSQP") प्रयोग गरी क्रमबद्ध प्रोग्रामिङलाई शब्दकोशको रूपमा निर्दिष्ट गरिएको प्रतिबन्धहरू विचार गर्नुहोस्। {'type', 'fun', 'jac', 'args'};
3) वेब स्टुडियोको उदाहरण प्रयोग गरेर निर्मित उत्पादनहरूको अनुकूलनको उदाहरणको विश्लेषण गर्नुहोस्।

सशर्त अनुकूलन विधि="trust-constr"

विधिको कार्यान्वयन trust-constr मा आधारित EQSQP समानता र अन्य को रूप को बाधा संग समस्याहरु को लागी यात्रा असमानता को रूप मा अवरोध संग समस्याहरु को लागी। दुबै विधिहरू एल्गोरिदमहरूद्वारा विश्वास क्षेत्रमा स्थानीय न्यूनतम फेला पार्नका लागि लागू गरिन्छ र ठूला-ठूला समस्याहरूको लागि उपयुक्त छन्।

सामान्य रूपमा न्यूनतम पत्ता लगाउने समस्याको गणितीय सूत्रीकरण:

कडा समानता बाधाहरूको लागि, तल्लो सीमा माथिल्लो सीमा बराबर सेट गरिएको छ .
एकतर्फी अवरोधको लागि, माथिल्लो वा तल्लो सीमा सेट गरिएको छ np.inf सम्बन्धित चिन्ह संग।
दुई चरहरूको ज्ञात रोजेनब्रोक प्रकार्यको न्यूनतम फेला पार्न आवश्यक हुन दिनुहोस्:

यस अवस्थामा, निम्न प्रतिबन्धहरू यसको परिभाषाको डोमेनमा सेट गरिएका छन्:

हाम्रो मामला मा, बिन्दु मा एक अद्वितीय समाधान छ , जसको लागि केवल पहिलो र चौथो प्रतिबन्धहरू मान्य छन्।
तलदेखि माथिसम्म प्रतिबन्धहरू मार्फत जाऔं र हेरौं कि हामी तिनीहरूलाई कसरी स्काइपीमा लेख्न सक्छौं।
प्रतिबन्धहरू и Bounds वस्तु प्रयोग गरेर यसलाई परिभाषित गरौं।

from scipy.optimize import Bounds
bounds = Bounds ([0, -0.5], [1.0, 2.0])

प्रतिबन्धहरू и यसलाई रेखीय रूपमा लेखौं:

यी बाधाहरूलाई LinearConstraint वस्तुको रूपमा परिभाषित गरौं:

import numpy as np
from scipy.optimize import LinearConstraint
linear_constraint = LinearConstraint ([[1, 2], [2, 1]], [-np.inf, 1], [1, 1])

र अन्तमा म्याट्रिक्स फारममा ननलाइनर बाधा:

हामी यो बाधाको लागि जेकोबियन म्याट्रिक्स परिभाषित गर्छौं र हेसियन म्याट्रिक्सको एक स्वैच्छिक भेक्टरको साथ एक रेखीय संयोजन। :

अब हामी एक nonlinear अवरोध एक वस्तु को रूप मा परिभाषित गर्न सक्नुहुन्छ NonlinearConstraint:

from scipy.optimize import NonlinearConstraint

def cons_f(x):
     return [x[0]**2 + x[1], x[0]**2 - x[1]]

def cons_J(x):
     return [[2*x[0], 1], [2*x[0], -1]]

def cons_H(x, v):
     return v[0]*np.array([[2, 0], [0, 0]]) + v[1]*np.array([[2, 0], [0, 0]])

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=cons_H)

यदि साइज ठुलो छ भने, matrices लाई स्पेर्स फारममा पनि निर्दिष्ट गर्न सकिन्छ:

from scipy.sparse import csc_matrix

def cons_H_sparse(x, v):
     return v[0]*csc_matrix([[2, 0], [0, 0]]) + v[1]*csc_matrix([[2, 0], [0, 0]])

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
                                            jac=cons_J, hess=cons_H_sparse)

वा वस्तुको रूपमा LinearOperator:

from scipy.sparse.linalg import LinearOperator

def cons_H_linear_operator(x, v):
    def matvec(p):
        return np.array([p[0]*2*(v[0]+v[1]), 0])
    return LinearOperator((2, 2), matvec=matvec)

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1,
                                jac=cons_J, hess=cons_H_linear_operator)

हेसियन म्याट्रिक्स गणना गर्दा धेरै प्रयास आवश्यक छ, तपाईं एक कक्षा प्रयोग गर्न सक्नुहुन्छ HessianUpdateStrategy। निम्न रणनीतिहरू उपलब्ध छन्: BFGS и SR1.

from scipy.optimize import BFGS

nonlinear_constraint = NonlinearConstraint(cons_f, -np.inf, 1, jac=cons_J, hess=BFGS())

हेसियनलाई सीमित भिन्नताहरू प्रयोग गरेर पनि गणना गर्न सकिन्छ:

nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = cons_J, hess = '2-point')

सीमित भिन्नताहरू प्रयोग गरेर अवरोधहरूको लागि जेकोबियन म्याट्रिक्स पनि गणना गर्न सकिन्छ। यद्यपि, यस अवस्थामा हेसियन म्याट्रिक्सलाई सीमित भिन्नताहरू प्रयोग गरेर गणना गर्न सकिँदैन। Hessian लाई प्रकार्यको रूपमा वा HessianUpdateStrategy वर्ग प्रयोग गरी परिभाषित गरिनुपर्छ।

nonlinear_constraint = NonlinearConstraint (cons_f, -np.inf, 1, jac = '2-point', hess = BFGS ())

अनुकूलन समस्याको समाधान यस्तो देखिन्छ:

from scipy.optimize import minimize
from scipy.optimize import rosen, rosen_der, rosen_hess, rosen_hess_prod

x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess,
                constraints=[linear_constraint, nonlinear_constraint],
                options={'verbose': 1}, bounds=bounds)
print(res.x)

`gtol` termination condition is satisfied.
Number of iterations: 12, function evaluations: 8, CG iterations: 7, optimality: 2.99e-09, constraint violation: 1.11e-16, execution time: 0.033 s.
[0.41494531 0.17010937]

यदि आवश्यक भएमा, हेसियन गणना गर्ने प्रकार्यलाई LinearOperator वर्ग प्रयोग गरेर परिभाषित गर्न सकिन्छ

def rosen_hess_linop(x):
    def matvec(p):
        return rosen_hess_prod(x, p)
    return LinearOperator((2, 2), matvec=matvec)

res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hess=rosen_hess_linop,
                 constraints=[linear_constraint, nonlinear_constraint],
                 options={'verbose': 1}, bounds=bounds)

print(res.x)

वा प्यारामिटर मार्फत हेसियन र एक स्वेच्छाचारी भेक्टरको गुणन hessp:

res = minimize(rosen, x0, method='trust-constr', jac=rosen_der, hessp=rosen_hess_prod,
                constraints=[linear_constraint, nonlinear_constraint],
                options={'verbose': 1}, bounds=bounds)
print(res.x)

वैकल्पिक रूपमा, अप्टिमाइज गरिएको प्रकार्यको पहिलो र दोस्रो डेरिभेटिभहरू अनुमानित गर्न सकिन्छ। उदाहरणका लागि, हेसियन प्रकार्य प्रयोग गरेर अनुमानित गर्न सकिन्छ SR1 (अर्ध-न्यूटोनियन अनुमान)। ढाँचालाई सीमित भिन्नताहरूद्वारा अनुमानित गर्न सकिन्छ।

from scipy.optimize import SR1
res = minimize(rosen, x0, method='trust-constr',  jac="2-point", hess=SR1(),
               constraints=[linear_constraint, nonlinear_constraint],
               options={'verbose': 1}, bounds=bounds)
print(res.x)

सशर्त अनुकूलन विधि="SLSQP"

SLSQP विधि फारममा कार्यलाई न्यूनीकरण गर्ने समस्याहरू समाधान गर्न डिजाइन गरिएको हो:

कहाँ и - समानता वा असमानताहरूको रूपमा प्रतिबन्धहरू वर्णन गर्ने अभिव्यक्तिहरूको सूचकांकहरूको सेट। - प्रकार्यको परिभाषाको डोमेनको लागि तल्लो र माथिल्लो सीमाहरूको सेटहरू।

रैखिक र गैररेखीय अवरोधहरू कुञ्जीहरूसँग शब्दकोशको रूपमा वर्णन गरिएको छ type, fun и jac.

ineq_cons = {'type': 'ineq',
             'fun': lambda x: np.array ([1 - x [0] - 2 * x [1],
                                          1 - x [0] ** 2 - x [1],
                                          1 - x [0] ** 2 + x [1]]),
             'jac': lambda x: np.array ([[- 1.0, -2.0],
                                          [-2 * x [0], -1.0],
                                          [-2 * x [0], 1.0]])
            }

eq_cons = {'type': 'eq',
           'fun': lambda x: np.array ([2 * x [0] + x [1] - 1]),
           'jac': lambda x: np.array ([2.0, 1.0])
          }

न्यूनतम खोज निम्नानुसार गरिन्छ:

x0 = np.array([0.5, 0])
res = minimize(rosen, x0, method='SLSQP', jac=rosen_der,
               constraints=[eq_cons, ineq_cons], options={'ftol': 1e-9, 'disp': True},
               bounds=bounds)

print(res.x)

Optimization terminated successfully.    (Exit mode 0)
            Current function value: 0.34271757499419825
            Iterations: 4
            Function evaluations: 5
            Gradient evaluations: 4
[0.41494475 0.1701105 ]

अनुकूलन उदाहरण

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

• x0 - ल्यान्डिङ पृष्ठहरू बेच्दै, 10 tr बाट।
• x1 - कर्पोरेट वेबसाइटहरू, 20 tr बाट।
• x2 - अनलाइन स्टोरहरू, 30 tr बाट।

हाम्रो मैत्री कार्य टोलीमा चार जुनियर, दुई मध्य र एक वरिष्ठ समावेश छन्। तिनीहरूको मासिक कार्य समय कोष:

• जुन: 4 * 150 = 600 чел * час,
• मध्य: 2 * 150 = 300 чел * час,
• वरिष्ठ: 150 чел * час.

पहिलो उपलब्ध जुनियरलाई एक प्रकारको साइट (x0, x1, x2), मध्य - (10, 20, 30), वरिष्ठ - (7, 15, 20) को विकास र तैनातीमा (5, 10, 15) घण्टा खर्च गर्न दिनुहोस्। ) तपाईंको जीवनको सबैभन्दा राम्रो समयको घण्टा।

कुनै पनि सामान्य निर्देशक जस्तै, हामी मासिक नाफा अधिकतम गर्न चाहन्छौं। सफलताको पहिलो पाइला भनेको उद्देश्य कार्य लेख्नु हो value प्रति महिना उत्पादित उत्पादनहरु को आय को रूप मा:

def value(x):
    return - 10*x[0] - 20*x[1] - 30*x[2]

यो त्रुटि होइन; अधिकतम खोज्दा, उद्देश्य प्रकार्य विपरित चिन्हको साथ न्यूनतम हुन्छ।

अर्को चरण भनेको हाम्रा कर्मचारीहरूलाई बढी काम गर्नबाट निषेध गर्नु र काम गर्ने घण्टामा प्रतिबन्धहरू लागू गर्नु हो:

के बराबर छ:

ineq_cons = {'type': 'ineq',
             'fun': lambda x: np.array ([600 - 10 * x [0] - 20 * x [1] - 30 * x[2],
                                         300 - 7  * x [0] - 15 * x [1] - 20 * x[2],
                                         150 - 5  * x [0] - 10 * x [1] - 15 * x[2]])
            }

एक औपचारिक प्रतिबन्ध भनेको उत्पादन उत्पादन मात्र सकारात्मक हुनुपर्छ:

bnds = Bounds ([0, 0, 0], [np.inf, np.inf, np.inf])

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

x0 = np.array([10, 10, 10])
res = minimize(value, x0, method='SLSQP', constraints=ineq_cons, bounds=bnds)
print(res.x)

[7.85714286 5.71428571 3.57142857]

पूर्ण संख्याहरूमा ढिलो राउन्ड गरौं र उत्पादनहरूको इष्टतम वितरणको साथ रोवरहरूको मासिक भार गणना गरौं। x = (8, 6, 3) :

• जुन: 8 * 10 + 6 * 20 + 3 * 30 = 290 чел * час;
• मध्य: 8 * 7 + 6 * 15 + 3 * 20 = 206 чел * час;
• वरिष्ठ: 8 * 5 + 6 * 10 + 3 * 15 = 145 чел * час.

निष्कर्ष: निर्देशकले आफ्नो राम्रो योग्य अधिकतम प्राप्त गर्नको लागि, यो 8 ल्यान्डिङ पृष्ठहरू, 6 मध्यम आकारको साइटहरू र 3 स्टोरहरू प्रति महिना सिर्जना गर्न इष्टतम छ। यस अवस्थामा, सिनियरले मेसिनबाट माथि नहेरी हलो जोत्नु पर्छ, बीचको भार लगभग 2/3 हुनेछ, जुनियरहरू आधा भन्दा कम हुनेछ।

निष्कर्षमा

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

धेरै सिद्धान्त र भर्चुअल उदाहरणहरू फेला पार्न सकिन्छ, उदाहरणका लागि, I.L. Akulich को पुस्तकमा "उदाहरण र समस्याहरूमा गणितीय प्रोग्रामिङ।" थप हार्डकोर आवेदन scipy.optimize छविहरूको सेटबाट 3D संरचना निर्माण गर्न (Habré मा लेख) मा हेर्न सकिन्छ स्किपी-कुकबुक.

जानकारीको मुख्य स्रोत हो docs.scipy.orgयो र अन्य खण्डहरूको अनुवादमा योगदान गर्न चाहनेहरू scipy स्वागत छ GitHub.

Спасибо मेफिस्टोफिस प्रकाशनको तयारीमा सहभागिताको लागि।

स्रोत: www.habr.com