SciPy (تُنطق saipie) عبارة عن حزمة رياضيات قائمة على numpy تتضمن أيضًا مكتبات C وFortran. يقوم SciPy بتحويل جلسة Python التفاعلية إلى بيئة علوم بيانات كاملة مثل MATLAB أو IDL أو Octave أو R أو SciLab.
في هذه المقالة، سنلقي نظرة على التقنيات الأساسية للبرمجة الرياضية - حل مشكلات التحسين الشرطي لدالة عددية لعدة متغيرات باستخدام حزمة scipy.optimize. لقد تمت بالفعل مناقشة خوارزميات التحسين غير المقيدة في . يمكن دائمًا الحصول على تعليمات أكثر تفصيلاً وحديثة حول وظائف scipy باستخدام الأمر help() أو Shift+Tab أو في .
مقدمة
يتم توفير واجهة مشتركة لحل مشكلات التحسين المشروطة وغير المقيدة في حزمة scipy.optimize بواسطة الوظيفة minimize(). ومع ذلك، فمن المعروف أنه لا توجد طريقة عالمية لحل جميع المشاكل، وبالتالي فإن اختيار الطريقة المناسبة، كما هو الحال دائما، يقع على عاتق الباحث.
يتم تحديد خوارزمية التحسين المناسبة باستخدام وسيطة الوظيفة minimize(..., method="").
من أجل التحسين المشروط لدالة ذات عدة متغيرات، تتوفر تطبيقات الطرق التالية:
trust-constr- ابحث عن الحد الأدنى المحلي في منطقة الثقة. , ;SLSQP— البرمجة التربيعية المتتابعة ذات القيود، الطريقة النيوتونية لحل نظام لاغرانج. .TNC- نيوتن مبتور مقيد، عدد محدود من التكرارات، جيد للوظائف غير الخطية مع عدد كبير من المتغيرات المستقلة. .L-BFGS-B- طريقة من فريق Broyden–Fletcher–Goldfarb–Shanno، تم تنفيذها مع انخفاض استهلاك الذاكرة بسبب التحميل الجزئي للمتجهات من مصفوفة هسه. , .COBYLA— MARE التحسين المقيد بالتقريب الخطي، التحسين المقيد بالتقريب الخطي (بدون حساب التدرج). .
اعتمادًا على الطريقة المختارة، يتم تحديد الشروط والقيود الخاصة بحل المشكلة بشكل مختلف:
- كائن فئة
Boundsبالنسبة للطرق L-BFGS-B، TNC، SLSQP، Trust-constr؛ - القائمة
(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 مرتكز على لمشاكل مع قيود شكل المساواة وعلى لمشاكل مع القيود في شكل عدم المساواة. يتم تنفيذ كلتا الطريقتين بواسطة خوارزميات لإيجاد الحد الأدنى المحلي في منطقة الثقة وهي مناسبة تمامًا للمشكلات واسعة النطاق.
الصياغة الرياضية لمشكلة إيجاد القيمة الصغرى بشكل عام:
بالنسبة لقيود المساواة الصارمة، يتم تعيين الحد الأدنى مساويًا للحد الأعلى .
بالنسبة للقيد أحادي الاتجاه، يتم تعيين الحد الأعلى أو الأدنى np.inf مع الإشارة المقابلة.
يجب أن يكون من الضروري إيجاد الحد الأدنى لدالة Rosenbrock المعروفة لمتغيرين:
وفي هذه الحالة، يتم وضع القيود التالية على مجال تعريفها:
في حالتنا، هناك حل فريد في هذه النقطة ، والتي لا يصلح لها سوى التقييد الأول والرابع.
دعونا نستعرض القيود من الأسفل إلى الأعلى وننظر إلى كيفية كتابتها في scipy.
القيود и دعونا نحدده باستخدام كائن 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])وأخيرًا القيد غير الخطي في شكل مصفوفة:
نحدد مصفوفة جاكوبي لهذا القيد ومزيج خطي من مصفوفة هسه مع ناقل تعسفي :
الآن يمكننا تعريف القيد غير الخطي ككائن 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)إذا كان الحجم كبيرًا، فيمكن أيضًا تحديد المصفوفات في شكل متفرق:
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)عند حساب مصفوفة هسه يتطلب الكثير من الجهد، يمكنك استخدام فئة . الاستراتيجيات التالية متاحة: 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]إذا لزم الأمر، يمكن تعريف وظيفة حساب Hessian باستخدام فئة 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 تريليون.
- x1 - مواقع الشركات، ابتداءً من 20 طنًا.
- X2 - متاجر على الإنترنت، من 30 طنًا.
يضم فريق العمل الودود لدينا أربعة صغار واثنان من الوسط وواحد كبير. صندوق وقت العمل الشهري الخاص بهم:
- يونيو:
4 * 150 = 600 чел * час, - الوسط:
2 * 150 = 300 чел * час, - سينور:
150 чел * час.
دع أول مبتدئ متاح يقضي (0، 1، 2) ساعة في تطوير ونشر موقع واحد من النوع (x10، x20، x30)، المتوسط - (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 لبناء هيكل ثلاثي الأبعاد من مجموعة من الصور () يمكن مشاهدتها في .
المصدر الرئيسي للمعلومات هو للراغبين في المساهمة في ترجمة هذا القسم وغيره scipy مرحبا بك في .
شكرا للمشاركة في إعداد المنشور.
المصدر: www.habr.com