طريقة أشد النسب(في الأدب الإنجليزي "طريقة المنحدر الحاد") هي طريقة عددية تكرارية (من الدرجة الأولى) لحل مشاكل التحسين، والتي تسمح لك بتحديد الحد الأقصى (الحد الأدنى أو الحد الأقصى) للدالة الهدف:
هي قيم وسيطة الوظيفة (المعلمات الخاضعة للتحكم) في المجال الحقيقي.
وفقًا للطريقة قيد النظر، يتم تحديد الحد الأقصى (الحد الأقصى أو الأدنى) للوظيفة الهدف في اتجاه أسرع زيادة (تناقص) للوظيفة، أي. في اتجاه التدرج (مضاد التدرج) للوظيفة. وظيفة التدرج عند نقطة ما هو متجه تكون إسقاطاته على محاور الإحداثيات هي المشتقات الجزئية للدالة بالنسبة إلى الإحداثيات:
حيث i، j،…، n هي متجهات وحدة موازية لمحاور الإحداثيات.
التدرج عند نقطة الأساس 
متعامد تمامًا مع السطح، ويوضح اتجاهه اتجاه أسرع زيادة في الوظيفة، والاتجاه المعاكس (مضاد التدرج)، على التوالي، يوضح اتجاه أسرع انخفاض في الوظيفة.
الطريقة الأكثر انحدارًا هي مزيد من التطويرطريقة النزول المتدرج. في حالة عامةعملية إيجاد الحد الأقصى للدالة هي إجراء تكراري، وهو مكتوب على النحو التالي:
حيث يتم استخدام علامة "+" للعثور على الحد الأقصى للدالة، ويتم استخدام علامة "-" للعثور على الحد الأدنى من الوظيفة؛
متجه اتجاه الوحدة، والذي يتم تحديده بواسطة الصيغة:
- وحدة التدرج تحدد معدل زيادة أو نقصان الدالة في اتجاه التدرج أو عكس التدرج:
ثابت يحدد حجم الخطوة وهو نفسه لجميع الاتجاهات i.
يتم تحديد حجم الخطوة من شرط الحد الأدنى للدالة الموضوعية f(x) في اتجاه الحركة، أي نتيجة لحل مشكلة التحسين أحادية البعد في اتجاه التدرج أو مضاد التدرج:
بمعنى آخر يتم تحديد حجم الخطوة من خلال حل هذه المعادلة:
وبالتالي يتم اختيار خطوة الحساب بحيث تتم الحركة حتى تتحسن الوظيفة، وبالتالي الوصول إلى الحد الأقصى في مرحلة ما. عند هذه النقطة، يتم تحديد اتجاه البحث مرة أخرى (باستخدام التدرج) ويتم البحث عن نقطة مثالية جديدة للدالة الهدف، وما إلى ذلك. وبالتالي، في هذه الطريقة، يتم البحث في خطوات أكبر، ويتم حساب تدرج الدالة بعدد أقل من النقاط.
في حالة وجود دالة بمتغيرين هذه الطريقةله التفسير الهندسي التالي: اتجاه الحركة من نقطة يمس خط المستوى عند النقطة . مسار الهبوط متعرج، مع روابط متعرجة مجاورة متعامدة مع بعضها البعض. تتم كتابة شرط تعامد متجهات اتجاهات النسب عند النقاط المجاورة بالتعبير التالي:
مسار الحركة إلى النقطة القصوى باستخدام طريقة الهبوط الأكثر انحدارًا، كما هو موضح في الرسم البياني لخط المستوى المتساوي للدالة f(x)
ينتهي البحث عن الحل الأمثل عند الوصول إلى خطوة الحساب التكرارية (عدة معايير):
يبقى مسار البحث في حي صغير من نقطة البحث الحالية:
لا تتغير زيادة الوظيفة الهدف:
يصبح تدرج الدالة الهدف عند النقطة الدنيا المحلية صفرًا:
تجدر الإشارة إلى أن طريقة النزول المتدرج تكون بطيئة جدًا عند التحرك على طول الوادي، ومع زيادة عدد المتغيرات في الوظيفة الموضوعية، يصبح سلوك الطريقة نموذجيًا. الوادي عبارة عن منخفض، تكون خطوط مستواه تقريبًا على شكل قطع ناقص مع أنصاف محاور تختلف عدة مرات. في حالة وجود وادٍ، يأخذ مسار الهبوط شكل خط متعرج بخطوة صغيرة، ونتيجة لذلك تتباطأ سرعة النزول الناتجة إلى الحد الأدنى بشكل كبير. ويفسر ذلك حقيقة أن اتجاه التدرج العكسي لهذه الوظائف ينحرف بشكل كبير عن الاتجاه إلى النقطة الدنيا، مما يؤدي إلى تأخير إضافي في الحساب. ونتيجة لذلك، تفقد الخوارزمية الكفاءة الحسابية.
وظيفة اخدود
إن طريقة التدرج، إلى جانب تعديلاتها العديدة، منتشرة على نطاق واسع طريقة فعالةالبحث عن الأمثل للأشياء قيد الدراسة. عيب البحث عن التدرج (بالإضافة إلى الطرق التي تمت مناقشتها أعلاه) هو أنه عند استخدامه، يمكن اكتشاف الحد الأقصى المحلي للوظيفة فقط. للعثور على الآخرين التطرف المحليفمن الضروري البحث من نقاط انطلاق أخرى. كما أن معدل تقارب طرق التدرج يعتمد أيضًا بشكل كبير على دقة حسابات التدرج. يمكن أن يؤدي فقدان الدقة، والذي يحدث عادةً بالقرب من النقاط الدنيا أو في حالة الأخدود، إلى تعطيل تقارب عملية نزول التدرج.
طريقة الحساب
الخطوة 1:تعريف التعبيرات التحليلية (في شكل رمزي) لحساب تدرج الوظيفة
الخطوة 2: اضبط التقريب الأولي
الخطوة 3:يتم تحديد الحاجة إلى إعادة تشغيل الإجراء الخوارزمي لإعادة تعيين اتجاه البحث الأخير. نتيجة لإعادة التشغيل، يتم إجراء البحث مرة أخرى في اتجاه النزول الأسرع.
يمكنك أيضًا البحث ليس عن أفضل نقطة في اتجاه التدرج، بل عن نقطة أفضل من النقطة الحالية.
الأسهل في تنفيذ جميع أساليب التحسين المحلية. لقد تماما ظروف ضعيفةالتقارب، ولكن معدل التقارب منخفض جدا (الخطي). خطوة طريقة التدرجغالبًا ما يتم استخدامه كجزء من طرق التحسين الأخرى، مثل طريقة فليتشر-ريفز.
وصف [ | ]
التحسينات[ | ]
تبين أن طريقة النزول المتدرج تكون بطيئة جدًا عند التحرك على طول الوادي، ومع زيادة عدد المتغيرات في الوظيفة الموضوعية، يصبح سلوك الطريقة نموذجيًا. لمكافحة هذه الظاهرة، يتم استخدامه، وجوهرها بسيط للغاية. بعد إجراء خطوتين من النزول المتدرج والحصول على ثلاث نقاط، ينبغي اتخاذ الخطوة الثالثة في اتجاه المتجه الذي يربط النقطتين الأولى والثالثة، على طول الجزء السفلي من الوادي.
بالنسبة للدوال القريبة من الدرجة التربيعية، تكون طريقة التدرج المترافق فعالة.
التطبيق في الشبكات العصبية الاصطناعية[ | ]
تُستخدم طريقة النسب المتدرج، مع بعض التعديلات، على نطاق واسع في تدريب الإدراك الحسي، وتُعرف في نظرية الشبكات العصبية الاصطناعية باسم طريقة الانتشار العكسي. عند تدريب شبكة عصبية من نوع الإدراك الحسي، من الضروري تغيير معاملات الترجيح للشبكة لتقليل متوسط الخطأعند مخرج الشبكة العصبية عندما يتم توفير سلسلة من بيانات إدخال التدريب إلى الإدخال. رسميًا، من أجل اتخاذ خطوة واحدة فقط باستخدام طريقة النزول المتدرج (إجراء تغيير واحد فقط في معلمات الشبكة)، من الضروري إرسال مجموعة بيانات التدريب بالكامل بشكل تسلسلي إلى مدخلات الشبكة، وحساب الخطأ لكل كائن من بيانات التدريب وحساب التصحيح اللازم لمعاملات الشبكة (ولكن لا تقم بهذا التصحيح)، وبعد تقديم جميع البيانات، احسب مقدار تصحيح كل معامل شبكة (مجموع التدرجات) وتصحيح المعاملات "خطوة واحدة" . من الواضح أنه مع وجود مجموعة كبيرة من بيانات التدريب، ستعمل الخوارزمية ببطء شديد، لذلك من الناحية العملية، غالبًا ما يتم تعديل معاملات الشبكة بعد كل عنصر تدريب، حيث يتم تقريب قيمة التدرج من خلال تدرج دالة التكلفة، ويتم حسابها على تدريب واحد فقط عنصر. هذه الطريقة تسمى نزول التدرج العشوائي أو نزول التدرج التشغيلي . النسب التدرج العشوائي هو شكل من أشكال التقريب العشوائي. توفر نظرية التقريبات العشوائية شروطًا لتقارب طريقة النسب التدرج العشوائي.
روابط [ | ]
- جي ماثيوز.وحدة لطريقة الهبوط الحاد أو التدرج. (الرابط غير متوفر)
الأدب [ | ]
- أكوليتش آي إل.البرمجة الرياضية في الأمثلة والمسائل. - م: الثانوية العامة 1986. - ص298-310.
- جيل إف، موراي دبليو، رايت إم.التحسين العملي = التحسين العملي. - م: مير، 1985.
- كورشونوف يو. كورشونوف يو.الأسس الرياضية لعلم التحكم الآلي. - م: الطاقة الذرية، 1972.
- ماكسيموف يو. فيليبوفسكايا إي.خوارزميات لحل مشاكل البرمجة غير الخطية. - م: ميفي، 1982.
- ماكسيموف يو.خوارزميات للبرمجة الخطية والمنفصلة. - م: ميفي، 1980.
- كورن جي، كورن تي.دليل الرياضيات للعلماء والمهندسين. - م: ناوكا، 1970. - ص 575-576.
- S. Yu. Gorodetsky، V. A. Grishagin.البرمجة غير الخطية والتحسين متعدد الأطراف. - نيجني نوفغورود: دار النشر بجامعة نيجني نوفغورود، 2007. - الصفحات من 357 إلى 363.
قواعد لإدخال وظيفة
في طريقة الهبوط الأكثر حدةيتم تحديد المتجه الذي يكون اتجاهه معاكسًا لاتجاه متجه التدرج للدالة ▽f(x) باعتباره اتجاه البحث. من التحليل الرياضيمن المعروف أن المتجه grad f(x)=▽f(x) يميز اتجاه أسرع زيادة في الوظيفة (انظر تدرج الوظيفة). لذلك، يتم استدعاء المتجه - grad f (X) = -▽f(X). مكافحة التدرجوهو اتجاه أسرع انخفاض له. علاقة التكرار التي يتم من خلالها تنفيذ طريقة الهبوط الأكثر انحدارًا لها الشكل X k +1 =X k - lect k ▽f(x k), k = 0,1,...,
حيث k >0 هو حجم الخطوة. اعتمادا على اختيار حجم الخطوة، يمكنك الحصول عليها خيارات مختلفةطريقة التدرج. إذا كان حجم الخطوة ثابتًا أثناء عملية التحسين، فإن الطريقة تسمى طريقة التدرج بخطوة منفصلة. يمكن تسريع عملية التحسين في التكرارات الأولى بشكل كبير إذا تم تحديد lect k من الشرط lect k =min f(X k + lectS k) .
لتحديد k، يتم استخدام أي طريقة تحسين أحادية البعد. في هذه الحالة، تسمى الطريقة طريقة الهبوط الأكثر انحدارًا. كقاعدة عامة، في الحالة العامة، لا تكفي خطوة واحدة لتحقيق الحد الأدنى من الوظيفة؛ يتم تكرار العملية حتى تؤدي الحسابات اللاحقة إلى تحسين النتيجة.
إذا كانت المساحة ممدودة للغاية في بعض المتغيرات، فسيتم تشكيل "الوادي". قد يتباطأ البحث ويتعرج عبر قاع "الوادي". في بعض الأحيان لا يمكن التوصل إلى حل خلال فترة زمنية مقبولة.
قد يكون عيب آخر لهذه الطريقة هو معيار التوقف ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
مثال. بدءًا من النقطة x k =(-2, 3)، حدد النقطة x k +1 باستخدام طريقة الهبوط الأكثر انحدارًا لتقليل الوظيفة.
كاتجاه البحث، حدد متجه التدرج عند النقطة الحالية 
دعونا نتحقق من معيار التوقف. لدينا 
لنحسب قيمة الدالة عند نقطة البداية f(X 1) = 35. لنفعل ذلك
خطوة على طول الاتجاه المضاد للتدرج
لنحسب قيمة الدالة عند نقطة جديدة
و(X 2) = 3(-2 + 19 1) 2 + (3-8 1) 2 - (-2 + 19 1)(3-8 1) - 4(-2 + 19 1)
دعونا نجد خطوة بحيث تصل الدالة الهدف إلى الحد الأدنى على طول هذا الاتجاه. من الشرط الضروري لوجود أقصى للدالة
و'(X 2) = 6(-2 + 19lect 1) 19 + 2(3-8lect 1)(-8) – (73 - 304 lect 1) – 4*19
أو f’(X 2) = 2598 1 – 425 = 0.
نحصل على الخطوة 1 = 0.164
إكمال هذه الخطوة سيؤدي إلى هذه النقطة 
حيث قيمة التدرج 
، قيمة الدالة f(X 2) = 0.23. لم يتم تحقيق الدقة، من النقطة التي نخطو فيها خطوة على طول اتجاه التدرج المضاد.
f(X 2) = 3(1.116 – 1.008lect 1) 2 + (1.688-2.26lect 1) 2 - (1.116 – 1.008lect 1)(1.688-2.26lect 1) - 4(1.116 – 1.008lect 1)
و'(X 2) = 11.76 – 6.12 1 = 0
نحصل على 1 = 0.52 
تعليق توضيحي: تغطي هذه المحاضرة على نطاق واسع طرق التحسين متعددة المعلمات مثل طريقة الهبوط الأكثر انحدارًا وطريقة دافيدون-فليتشر-باول. بالإضافة إلى ذلك، يتم إجراء تحليل مقارن للطرق المذكورة أعلاه من أجل تحديد الأكثر فعالية، وتحديد مزاياها وعيوبها؛ ويأخذ في الاعتبار أيضًا مشكلات التحسين متعددة الأبعاد، مثل طريقة الوادي وطريقة متعددة الأطراف.
1. طريقة النزول الحاد
جوهر هذه الطريقة هو استخدام ما سبق ذكره طريقة الهبوط المنسقيتم البحث من نقطة معينة في اتجاه موازي لأحد المحاور إلى أدنى نقطة في هذا الاتجاه. ثم يتم إجراء البحث في اتجاه موازي للمحور الآخر، وهكذا. الاتجاهات ثابتة بالطبع. يبدو من المعقول محاولة تعديل هذه الطريقة بحيث يتم في كل مرحلة البحث عن النقطة الدنيا على طول الاتجاه "الأفضل". ليس من الواضح أي اتجاه هو "الأفضل"، لكن من المعروف ذلك اتجاه التدرجهو اتجاه أسرع زيادة في الدالة. وبالتالي فإن الاتجاه المعاكس هو اتجاه أسرع تناقص للدالة. يمكن تبرير هذه الخاصية على النحو التالي.
لنفترض أننا ننتقل من النقطة x إلى النقطة التالية x + hd، حيث d هو اتجاه معين وh هي خطوة بطول معين. وبالتالي تتم الحركة من النقطة (x 1، x 2، ...، x n) إلى النقطة (x 1 + zx 1، x 2 + zx 2، ...، x n + zx n)، أين
يتم تحديد التغيير في قيم الوظائف من خلال العلاقات
| (1.3) |
حتى الدرجة الأولى zx i، مع حساب المشتقات الجزئية عند النقطة x. كيف يجب اختيار الاتجاهات d i التي تحقق المعادلة (1.2) للحصول على أكبر قيمة للتغير في الدالة df؟ هذا هو المكان الذي تنشأ فيه مشكلة التعظيم مع القيد. دعونا نطبق طريقة مضاعفات لاغرانج، والتي من خلالها نحدد الوظيفة
تصل القيمة df المُرضية للقيد (1.2) إلى الحد الأقصى عندما تكون الوظيفة
يصل إلى الحد الأقصى. مشتق منه
لذلك،
 |
(1.6) |
ثم di ~ df/dx i والاتجاه d موازي للاتجاه V/(x) عند النقطة x.
هكذا، أكبر زيادة محليةدالة لخطوة صغيرة معينة h تحدث عندما يكون d هو اتجاه Vf(x) أو g(x) . ولذلك فإن اتجاه الهبوط الأكثر انحدارًا هو الاتجاه
وبصورة أبسط يمكن كتابة المعادلة (1.3) كما يلي:
أين هي الزاوية بين المتجهين Vf(x) و dx. بالنسبة لقيمة معينة لـ dx، نقوم بتقليل df عن طريق اختيار أن اتجاه dx يتزامن مع اتجاه -Vf(x) .
تعليق. اتجاه التدرجعمودي على أي نقطة على خط المستوى الثابت، حيث أن الدالة ثابتة على طول هذا الخط. وبالتالي، إذا كانت (د 1، د 2، ...، د ن) هي خطوة صغيرة على طول خط المستوى، إذن
وبالتالي
 |
(1.8) |
