⛈️ 👩‍✈️ 👨‍👩‍👦 SciPy ، التحسين 🙇🏼 🛴 🤶🏼

SciPy (وضوح sai pie) عبارة عن حزمة تطبيق رياضية تستند إلى ملحق Numpy Python. باستخدام SciPy ، تتحول جلسة Python التفاعلية إلى نفس بيئة معالجة البيانات والنماذج الأولية الكاملة للأنظمة المعقدة مثل MATLAB و IDL و Octave و R-Lab و SciLab. أريد اليوم أن أتحدث باختصار عن كيفية استخدام بعض خوارزميات التحسين المعروفة في الحزمة. يمكن دائمًا الحصول على مساعدة أكثر تفصيلًا وحداثة حول استخدام الوظائف باستخدام الأمر help () أو باستخدام Shift + Tab.

مقدمة

من أجل إنقاذ نفسك والقراء من البحث وقراءة المصدر ، ستكون الروابط إلى أوصاف الطرق بشكل رئيسي على ويكيبيديا. كقاعدة عامة ، هذه المعلومات كافية لفهم الأساليب بشكل عام وشروط تطبيقها. لفهم جوهر الأساليب الرياضية ، نتبع الروابط الخاصة بالمنشورات الأكثر موثوقية ، والتي يمكن العثور عليها في نهاية كل مقالة أو في محرك البحث المفضل لديك.

لذلك ، تتضمن الوحدة النمطية scipy.optimize تنفيذ الإجراءات التالية:

التقليل الشرطي وغير المشروط للوظائف العددية للعديد من المتغيرات (minim) باستخدام خوارزميات مختلفة (Nelder-Mead simplex و BFGS وتدرجات نيوتن المتقاربة و COBYLA و SLSQP )
التحسين العالمي (على سبيل المثال: basinhopping ، diff_evolution )
التقليل من بقايا المربعات الصغرى (المربعة الصغرى ) وخوارزميات تركيب المنحنيات إلى المربعات الصغرى غير الخطية (curve_fit)
تقليل وظائف العددية لمتغير واحد (minim_scalar) وإيجاد الجذور (root_scalar)
المذيبات متعددة الأبعاد لنظام المعادلات (الجذر) باستخدام خوارزميات مختلفة (هجين باول ، ليفنبرغ ماركوارت أو أساليب واسعة النطاق ، مثل نيوتن-كريلوف ).

في هذه المقالة سننظر في العنصر الأول فقط من هذه القائمة بأكملها.

التقليل غير المشروط للوظيفة العددية للعديد من المتغيرات

توفر الدالة minim من الحزمة scipy.optimize واجهة مشتركة لحل مشاكل التقليل الشرطي وغير المشروط للوظائف العددية للعديد من المتغيرات. لإثبات عملها ، سنحتاج إلى وظيفة مناسبة للعديد من المتغيرات ، والتي سوف نقوم بتقليلها بطرق مختلفة.

لهذه الأغراض ، تكون دالة Rosenbrock للمتغيرات N مثالية ، والتي لها الشكل:

$f \ left (\ mathbf {x} \ right) = \ sum_ {i = 1} ^ {N-1} [100 \ left (x_ {i + 1} -x_ {i} ^ {2} \ right) ^ {2} + \ left (1-x_ {i} \ right) ^ {2}]$

على الرغم من حقيقة أن وظيفة Rosenbrock ومصفوفاتها Jacobi و Hessian (المشتقات الأولى والثانية ، على التوالي) محددة بالفعل في حزمة 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 قيم وظيفة Rosenbrock لمتغيرين.

رمز التقديم

 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 ل $x_i = 1 دولا$ ، خذ بعين الاعتبار أمثلة حول كيفية تحديد الحد الأدنى لقيمة الدالة Rosenbrock باستخدام مختلف الإجراءات scipy.optimize.

طريقة Nelder-Mead Simplex (Nelder-Mead)

فليكن هناك نقطة أولية x0 في الفضاء ذي الأبعاد الخمسة. ابحث عن النقطة الدنيا لوظيفة Rosenbrock الأقرب إليها باستخدام خوارزمية simplex Nelder-Mead (يتم تحديد الخوارزمية كقيمة لمعلمة الطريقة):

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

طريقة simplex هي أسهل طريقة لتقليل وظيفة محددة بوضوح وسلسة إلى حد ما. لا يتطلب حساب مشتقات دالة ؛ يكفي لتحديد قيمها فقط. طريقة Nelder-Mead هي اختيار جيد لمشاكل التقليل البسيطة. ومع ذلك ، نظرًا لأنه لا يستخدم تقديرات التدرج ، فقد يستغرق الأمر وقتًا طويلاً للعثور على الحد الأدنى.

طريقة باول

خوارزمية التحسين الأخرى التي يتم فيها احتساب قيم الوظيفة فقط هي طريقة Powell . لاستخدامها ، تحتاج إلى ضبط method = 'powell' في الدالة 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-Channo (BFGS)

للحصول على تقارب أسرع مع الحل ، يستخدم الإجراء BFGS تدرج الدالة الهدف. يمكن تحديد التدرج كدالة أو حساب باستخدام اختلافات من الدرجة الأولى. في أي حال ، عادةً ما يتطلب أسلوب BFGS استدعاءات دالة أقل من أسلوب simplex.

نجد مشتق وظيفة Rosenbrock في الشكل التحليلي:

ج ز ئ ي ة ج ز ئ ي ة ، ، ،

$\ frac {\ جزئية f} {\ جزئية x_j} = \ sum \ limit_ {i = 1} ^ N 200 (x_i - x_ {i-1} ^ 2) (\ delta_ {i، j} - 2x_ {i -1 ، j}) - 2 (1 - x_ {i-1}) \ delta_ {i-1، j} =$

$= 200 (x_j - x_ {j-1} ^ 2) - 400x_j (x_ {j + 1} - x_j ^ 2) - 2 (1-x_j)$

هذا التعبير صالح للمشتقات من جميع المتغيرات باستثناء الأولى والأخيرة ، والتي يتم تعريفها على النحو التالي:

ج ز ئ ي ة ج ز ئ ي ة ،

$\ frac {\ جزئية f} {\ جزئية x_0} = -400 x_0 (x_1 - x_0 ^ 2) - 2 (1 - x_0) ،$

ج ز ئ ي ة ج ز ئ ي ة

$\ frac {\ جزئية f} {\ جزئية x_ {N-1}} = 200 (x_ {N-1} - x_ {N-2} ^ 2).$

دعونا نلقي نظرة على وظيفة بيثون التي تحسب هذا التدرج:

 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 لوظيفة minim ، كما هو موضح أدناه.

 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]

خوارزمية التدرج المترافق (نيوتن)

تعد خوارزمية التدرج المتزامن لـ Newton طريقة نيوتن معدلة.
تعتمد طريقة نيوتن على تقريب وظيفة في منطقة محلية من خلال كثير الحدود من الدرجة الثانية:

$f \ left (\ mathbf {x} \ right) \ approx f \ left (\ mathbf {x} _ {0} \ right) + \ nabla f \ left (\ mathbf {x} _ {0} \ right) \ cdot \ left (\ mathbf {x} - \ mathbf {x} _ {0} \ right) + \ frac {1} {2} \ left (\ mathbf {x} - \ mathbf {x} _ {0} \ right) ^ {T} \ mathbf {H} \ left (\ mathbf {x} _ {0} \ right) \ left (\ mathbf {x} - \ mathbf {x} _ {0} \ right)$

اين $\ mathbf {H} \ left (\ mathbf {x} _ {0} \ right)$ هي مصفوفة من المشتقات الثانية (مصفوفة هسي ، هسيان).
إذا كان Hessian محددًا بشكل إيجابي ، يمكن العثور على الحد الأدنى المحلي لهذه الوظيفة عن طريق مساواة التدرج الصفري للشكل التربيعي على الصفر. والنتيجة هي تعبير:

$\ mathbf {x} _ {\ textrm {opt}} = \ mathbf {x} _ {0} - \ mathbf {H} ^ {- 1} \ nabla f$

يتم حساب معكوس هسه باستخدام طريقة التدرج المتقارن. فيما يلي مثال لاستخدام هذه الطريقة لتقليل وظيفة Rosenbrock. لاستخدام طريقة Newton-CG ، يجب عليك تحديد دالة تقوم بتقييم Hessian.
تساوي وظيفة Hessian of the Rosenbrock في الشكل التحليلي:

$H_ {i، j} = \ frac {\ جزئية ^ 2 f} {\ جزئية x_i x_j} = 200 (\ delta_ {i، j} - 2x_ {i-1} \ delta {i-1، j} - 400x_i (\ delta_ {i + 1، j} - 2x_i \ delta {i، j}) - 400 \ delta_ {i، j} (x_ {i + 1} - x_i ^ 2) + 2 \ delta_ {i، j } =$

$= (202 + 1200x_i ^ 2 - 400x_ {i + 1}) \ delta_ {i، j} - 400x_i \ delta_ {i + 1، j} - 400x_ {i-1} \ delta_ {i-1، j}$

اين $i ، j \ in \ left [1 ، N-2 \ right]$ و $i ، j \ in \ left [0 ، N-1 \ right]$ تحديد المصفوفة $N \ مرة N$ .

العناصر غير الصفرية المتبقية في المصفوفة تساوي:

$\ frac {\ جزئية ^ 2 f} {\ جزئية x_0 ^ 2} = 1200x_0 ^ 2 - 400x_1 +2$

$\ frac {\ جزئية ^ 2 f} {\ جزئية x_0 x_1} = \ frac {\ جزئية ^ 2 f} {\ جزئية x_1 x_0} = -400x_0$

$\ frac {\ جزئية ^ 2 f} {\ جزئية x_ {N-1} x_ {N-2}} = \ frac {\ جزئية ^ 2 f} {\ جزئية x_ {N-2} x_ {N-1 }} = -400x_ {N-2}$

$\ frac {\ جزئية ^ 2 f} {\ جزئية x_ {N-1} ^ 2} = 200x$

على سبيل المثال ، في الفضاء ثلاثي الأبعاد N = 5 ، تحتوي مصفوفة Hessian لوظيفة Rosenbrock على شكل شريط:

$\ tiny \ mathbf {H} = \ تبدأ {bmatrix} 1200 × _ {0} ^ {2} -400x_ {1} +2 & -400x_ {0} & 0 & 0 & 0 \\ -400x_ {0} & 202 + 1200x_ {1} ^ {2} -400x_ {2} & -400x_ {1} & 0 & 0 \\ 0 & -400x_ {1} & 202 + 1200x_ {2} ^ {2} -400x_ {3} & -400x_ {2} & 0 \\ 0 & & -400x_ {2} & 202 + 1200x_ {3} ^ {2} -400x_ {4} & -400x_ {3} \\ 0 & 0 & 0 & -400x_ { 3} & 200 \ end {bmatrix}$

الكود الذي يحسب هذا Hessian مع الكود لتقليل وظيفة Rosenbrock باستخدام طريقة التدرج المترافق (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]

مثال مع تعريف وظيفة منتج Hessian وناقلات تعسفية

في مشاكل العالم الحقيقي ، قد يتطلب حساب وتخزين مصفوفة Hessian بأكملها موارد كبيرة من الوقت والذاكرة. علاوة على ذلك ، في الواقع ، ليست هناك حاجة لتحديد مصفوفة هسي نفسها ، منذ ذلك الحين لا يتطلب إجراء التقليل إلى الحد الأدنى سوى متجه يساوي منتج Hessian مع متجه تعسفي آخر. وبالتالي ، من وجهة نظر حسابية ، من الأفضل بكثير تحديد الوظيفة التي تُرجع نتيجة منتج Hessian باستخدام متجه تعسفي على الفور.

النظر في وظيفة hess ، والتي تأخذ ناقلات التقليل إلى الحد الأدنى كوسيطة الأولى ، وناقلات تعسفية كالوسيطة الثانية (جنبًا إلى جنب مع وسائط أخرى من الدالة المصغرة). في حالتنا ، ليس من الصعب جدًا حساب ناتج دالة Hessian of the Rosenbrock باستخدام ناقل تعسفي. إذا كان p هو ناقل تعسفي ، ثم المنتج $H (x) \ cdot p$ لديه النموذج:

$\ mathbf {H} \ left (\ mathbf {x} \ right) \ mathbf {p} = \ تبدأ {bmatrix} \ left (1200x_ {0} ^ {2} -400x_ {1} +2 \ right) p_ {0} -400x_ {0} p_ {1} \\ \ vdots \\ -400x_ {i-1} p_ {i-1} + \ left (202 + 1200x_ {i} ^ {2} -400x_ {i + 1} \ right) p_ {i} -400x_ {i} p_ {i + 1} \\ \ vdots \\ -400x_ {N-2} p_ {N-2} + 200p_ {N-1} \ end {bmatrix }.$

يتم تمرير الدالة التي تحسب منتج Hessian والناقل التعسفي كقيمة وسيطة hessp لتقليل الدالة:

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

طرق نوع كريلوفسكي

مثل طريقة الثقة في ncg ، تعتبر طرق Krylovsky من النوع المناسب تمامًا لحل المشكلات واسعة النطاق ، لأنها تستخدم فقط منتجات ناقلات المصفوفات. جوهرها هو في حل المشكلة في المجال السري المحدود بمساحة Krylov الفرعية المقطوعة. بالنسبة للمهام غير المؤكدة ، من الأفضل استخدام هذه الطريقة ، لأنها تستخدم عددًا أقل من التكرارات غير الخطية نظرًا لوجود عدد أقل من منتجات ناقلات المصفوفات في كل مهمة فرعية ، مقارنةً بأسلوب ثقة ncg. بالإضافة إلى ذلك ، فإن حل المهمة الفرعية التربيعية هو أكثر دقة من طريقة trust-ncg.
مثال تعريف مصفوفة هسه:

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

الخوارزمية التقريبية المستندة إلى الثقة

جميع الطرق (Newton-CG و trust-ncg و trust-krylov) مناسبة تمامًا لحل المهام واسعة النطاق (بآلاف المتغيرات). ويرجع ذلك إلى حقيقة أن الخوارزمية الكامنة وراء التدرجات المترافقة تتضمن تحديدًا تقريبيًا لمصفوفة Hessian العكسية. الحل تكراري ، دون تحلل صريح لهيسيان. نظرًا لأنه من الضروري تحديد وظيفة منتج Hessian والناقل التعسفي ، تعد هذه الخوارزمية مفيدة بشكل خاص للعمل مع مصفوفات متفرق (شريط قطري). هذا يوفر تكاليف ذاكرة منخفضة وتوفير كبير في الوقت.

في المشكلات متوسطة الحجم ، لا تعد تكاليف تخزين Hessian ومعالجتها مهمة. هذا يعني أنه يمكن الحصول على حل بتكرار أقل ، مما يؤدي إلى حل المهام الفرعية لمنطقة الثقة تمامًا تقريبًا. لهذا ، يتم حل بعض المعادلات غير الخطية بشكل متكرر لكل مهمة فرعية من الدرجة الثانية. مثل هذا الحل عادة ما يتطلب 3 أو 4 تحلل من مصفوفة هيتس هولتس. نتيجة لذلك ، تتقارب الطريقة في عدد أقل من التكرارات وتتطلب حسابًا أقل للدالة الموضوعية مقارنة بالطرق الأخرى المطبقة في مجال الثقة. هذه الخوارزمية تعني فقط تحديد مصفوفة هيسان الكاملة ولا تدعم القدرة على استخدام وظيفة منتج هسيا وناقلات تعسفية.

مثال لتقليل وظيفة 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.])

هذا ، ربما ، يسكن. في المقالة التالية سأحاول أن أقول الأكثر إثارة للاهتمام حول التقليل الشرطي ، وتطبيق التقليل إلى أدنى حد في حل مشاكل التقريب ، والتقليل إلى أدنى حد من وظيفة متغير واحد ، minimizers التعسفي ، وإيجاد جذور نظام المعادلات باستخدام حزمة scipy.optimize.

المصدر: https://docs.scipy.org/doc/scipy/reference/

SciPy ، التحسين