SciPy (تُنطق sai pai) هي حزمة تطبيقات رياضية تعتمد على امتداد Numpy Python. مع SciPy ، تصبح جلسة Python التفاعلية هي نفس بيئة المعالجة الكاملة للبيانات والنماذج الأولية المعقدة مثل MATLAB و IDL و Octave و R-Lab و SciLab. أود اليوم أن أتحدث بإيجاز عن كيفية تطبيق بعض خوارزميات التحسين المعروفة في حزمة scipy.optimize. يمكن دائمًا الحصول على تعليمات أكثر تفصيلاً وحداثة حول استخدام الوظائف باستخدام الأمر help () أو باستخدام Shift + Tab.
مقدمة
من أجل إنقاذ نفسي والقراء من البحث عن المصادر الأولية وقراءتها ، ستكون روابط أوصاف الأساليب بشكل أساسي على ويكيبيديا. كقاعدة عامة ، هذه المعلومات كافية لفهم الأساليب بشكل عام وشروط تطبيقها. لفهم جوهر الأساليب الرياضية ، نتبع الروابط المؤدية إلى المزيد من المنشورات الموثوقة التي يمكن العثور عليها في نهاية كل مقالة أو في محرك البحث المفضل لديك.
لذا ، فإن وحدة scipy.optimize تتضمن تنفيذ الإجراءات التالية:
- التصغير الشرطي وغير المشروط للوظائف العددية للعديد من المتغيرات (الحد الأدنى) باستخدام خوارزميات مختلفة (Nelder-Mead simplex ، BFGS ، تدرجات نيوتن المقترنة ، и )
- التحسين العام (على سبيل المثال: , )
- تقليل المخلفات (المربعات الصغرى) وخوارزميات ملائمة منحنى المربعات الصغرى غير الخطية (curve_fit)
- تصغير الدوال العددية لمتغير واحد (minim_scalar) وإيجاد الجذور (root_scalar)
- حلول نظام المعادلات متعددة المتغيرات (الجذر) باستخدام خوارزميات مختلفة (Hybrid Powell ، أو الأساليب واسعة النطاق مثل ).
في هذه المقالة ، سننظر فقط في العنصر الأول من هذه القائمة بأكملها.
تصغير غير مشروط لدالة عددية لعدة متغيرات
توفر وظيفة minim من حزمة scipy.optimize واجهة مشتركة للتصغير المشروط وغير المشروط للوظائف العددية للمتغيرات المتعددة. لإثبات عملها ، نحتاج إلى وظيفة مناسبة للعديد من المتغيرات ، والتي سنقوم بتقليلها بطرق مختلفة.
لهذه الأغراض ، تعتبر وظيفة Rosenbrock لمتغيرات N مثالية ، والتي تبدو كما يلي:
على الرغم من حقيقة أن دالة Rosenbrock ومصفوفتيها Jacobi و Hesse (من المشتقات الأولى والثانية ، على التوالي) محددة بالفعل في حزمة 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)من أجل الوضوح ، دعنا نرسم قيم دالة 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 في ، دعنا نلقي نظرة على أمثلة حول كيفية تحديد الحد الأدنى لقيمة وظيفة Rosenbrock باستخدام إجراءات scipy.optimize المختلفة.
طريقة Simplex لـ Nelder-Mead (Nelder-Mead)
يجب أن يكون هناك نقطة أولية x0 في مساحة خماسية الأبعاد. ابحث عن النقطة الدنيا لوظيفة Rosenbrock الأقرب إليها باستخدام الخوارزمية (يتم تحديد الخوارزمية كقيمة معلمة الطريقة):
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' في وظيفة الحد الأدنى.
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 عادةً استدعاءات وظيفية أقل من طريقة simplex.
لنجد مشتق دالة روزنبروك في شكل تحليلي:
هذا التعبير صالح لمشتقات جميع المتغيرات باستثناء الأول والأخير ، والتي يتم تعريفها على النحو التالي:
لنلقِ نظرة على دالة Python التي تحسب هذا التدرج:
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]خوارزمية التدرج المقترن (نيوتن)
خوارزمية هي طريقة نيوتن المعدلة.
تعتمد طريقة نيوتن على تقريب دالة في منطقة محلية بواسطة كثير الحدود من الدرجة الثانية:
حيث هي مصفوفة من المشتقات الثانية (Hessian matrix، Hessian).
إذا كان Hessian موجبًا محددًا ، فيمكن إيجاد الحد الأدنى المحلي لهذه الدالة عن طريق مساواة تدرج الصفر للصيغة التربيعية بالصفر. والنتيجة هي تعبير:
يتم حساب المعكوس Hessian باستخدام طريقة التدرج المترافق. فيما يلي مثال على استخدام هذه الطريقة لتقليل وظيفة Rosenbrock. لاستخدام طريقة Newton-CG ، يجب عليك تحديد دالة تحسب الدالة Hessian.
تساوي دالة Hessian of Rosenbrock في الشكل التحليلي:
حيث и ، حدد المصفوفة .
العناصر المتبقية غير الصفرية في المصفوفة متساوية:
على سبيل المثال ، في الفضاء خماسي الأبعاد N = 5 ، تحتوي مصفوفة Hessian لوظيفة Rosenbrock على شكل نطاق:
الكود الذي يحسب هذا Hessian ، جنبًا إلى جنب مع الكود لتقليل وظيفة Rosenbrock باستخدام طريقة التدرج المترافق (نيوتن):
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 لوظيفة Rosenbrock باستخدام ناقل تعسفي. لو p هو ناقل تعسفي ، ثم المنتج لديه النموذج:
يتم تمرير الدالة التي تحسب منتج 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.]مثال على وظيفة منتج Hessian والمتجه التعسفي:
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.]طرق نوع كريلوفسكي
مثل طريقة trust-ncg ، فإن طرق نوع Krylov مناسبة تمامًا لحل المشكلات واسعة النطاق لأنها تستخدم فقط منتجات مصفوفة متجهة. يكمن جوهرها في حل المشكلة في منطقة الثقة التي يحدها فضاء Krylov الجزئي المبتور. بالنسبة للمشكلات غير المؤكدة ، من الأفضل استخدام هذه الطريقة ، نظرًا لأنها تستخدم عددًا أقل من التكرارات غير الخطية نظرًا لوجود عدد أقل من منتجات المصفوفة المتجهية لكل مشكلة فرعية ، مقارنةً بطريقة Trust-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.]
مثال على وظيفة منتج Hessian والمتجه التعسفي:
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 توسعات لمصفوفة Cholesky Hessian. نتيجة لذلك ، تتقارب الطريقة في عدد أقل من التكرارات وتتطلب حساب دالة أقل موضوعية من طرق منطقة الثقة المطبقة الأخرى. تتضمن هذه الخوارزمية فقط تعريف مصفوفة Hessian الكاملة ولا تدعم القدرة على استخدام وظيفة منتج Hessian والمتجه التعسفي.
مثال مع تصغير وظيفة Rosenbrock:
res = minimize(rosen, x0, method='trust-exact',
jac=rosen_der, hess=rosen_hess,
options={'gtol': 1e-8, 'disp': True})
res.xOptimization 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. طَرد.
المصدر:
المصدر: www.habr.com