سأضيف القليل من تجربتي :)

طريقة الهبوط الإحداثي

فكرة هذه الطريقة هي أن البحث يحدث في اتجاه الهبوط الإحداثي أثناء التكرار الجديد. يتم الهبوط تدريجيًا على طول كل إحداثي. يعتمد عدد الإحداثيات بشكل مباشر على عدد المتغيرات.
لتوضيح مدى تقدم هذه الطريقة، عليك أولاً أن تأخذ الدالة z = f(x1, x2,…, xn) وتحدد أي نقطة M0(x10, x20,…, xn0) في مساحة n، والتي تعتمد على الرقم من خصائص الوظيفة. الخطوة التالية هي تثبيت جميع نقاط الدالة على ثابت، باستثناء النقطة الأولى. يتم ذلك من أجل تقليص البحث عن التحسين متعدد الأبعاد إلى حل البحث على جزء معين من مشكلة التحسين أحادي البعد، أي البحث عن الوسيطة x1.
للعثور على قيمة هذا المتغير، من الضروري النزول على طول هذا الإحداثي إلى نقطة جديدة M1(x11، x21،…، xn1). بعد ذلك، يتم اشتقاق الدالة ومن ثم يمكننا إيجاد قيمة النقطة التالية الجديدة باستخدام هذا التعبير:

بعد العثور على قيمة المتغير، تحتاج إلى تكرار التكرار، وإصلاح جميع الوسائط باستثناء x2 والبدء في التنازلي إحداثيات جديدةإلى النقطة الجديدة التالية M2(x11,x21,x30...,xn0). الآن ستعتمد قيمة النقطة الجديدة على التعبير:

مرة أخرى، سيتم تكرار تكرار الالتزام حتى تنفد جميع الوسيطات من xi إلى xn. في التكرار الأخير، سنمر بالتسلسل عبر جميع الإحداثيات الممكنة، حيث سنجد بالفعل الحد الأدنى المحلي، وبالتالي فإن الدالة الهدف في الإحداثي الأخير ستصل إلى الحد الأدنى العالمي. ومن مزايا هذه الطريقة أنه من الممكن مقاطعة الهبوط في أي وقت وستكون النقطة الأخيرة التي تم العثور عليها هي النقطة الدنيا. يكون هذا مفيدًا عندما تنتقل الطريقة إلى حلقة لا نهائية ويمكن اعتبار آخر إحداثي تم العثور عليه نتيجة هذا البحث. إلا أن هدف إيجاد الحد الأدنى العالمي في المنطقة قد لا يتحقق أبداً لأننا أجهضنا البحث عن الحد الأدنى (انظر الشكل 1).

الشكل 1 - إلغاء النسب الإحداثي

وأظهرت دراسة هذه الطريقة أن كل نقطة محسوبة تم العثور عليها في الفضاء هي نقطة دنيا عالمية وظيفة معينة، والدالة z = f(x1, x2,…, xn) محدبة وقابلة للتفاضل.
من هذا يمكننا أن نستنتج أن الدالة z = f(x1, x2,…, xn) محدبة وقابلة للتفاضل في الفضاء، وكل نقطة نهاية تم العثور عليها في التسلسل M0(x10, x20,…, xn0) ستكون قيمة دنيا عالمية نقطة (انظر الشكل 2) لهذه الوظيفة باستخدام طريقة النسب الإحداثي.

الشكل 2 - النقاط الدنيا المحلية على محور الإحداثيات

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

يتبع تقدم طريقة النسب الإحداثي الخوارزمية الموضحة في الرسم التخطيطي (انظر الشكل 3). تكرارات هذه الطريقة:
في البداية، من الضروري إدخال العديد من المعلمات: دقة Epsilon، والتي يجب أن تكون إيجابية تمامًا، ونقطة البداية x1 التي سنبدأ منها تنفيذ الخوارزمية الخاصة بنا وتعيين Lambda j؛
الخطوة التالية هي أخذ نقطة البداية الأولى x1، وبعدها يتم حل المعادلة المعتادة أحادية البعد بمتغير واحد وستكون صيغة إيجاد الحد الأدنى حيث k = 1، j=1:

الآن، بعد حساب النقطة القصوى، تحتاج إلى التحقق من عدد الوسائط في الدالة وإذا كانت j أقل من n، فأنت بحاجة إلى تكرار الخطوة السابقة وإعادة تعريف الوسيطة j = j + 1. وفي جميع الحالات الأخرى، انتقل إلى الخطوة التالية.
أنت الآن بحاجة إلى إعادة تعريف المتغير x باستخدام الصيغة x (k + 1) = y (n + 1) ومحاولة تقريب الدالة إلى الدقة المحددة وفقًا للتعبير:

الآن، يعتمد العثور على النقطة القصوى على هذا التعبير. إذا كان هذا التعبير صحيحًا، فسيتم تقليل حساب النقطة القصوى إلى x*= xk + 1. ولكن غالبًا ما يكون من الضروري إجراء تكرارات إضافية اعتمادًا على الدقة، لذلك سيتم إعادة تعريف قيم الوسائط y( 1) = x(k + 1)، وقيم المؤشرات j =1، k = k + 1.

الشكل 3 - رسم تخطيطي لطريقة النسب الإحداثية

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

طريقة نيلدر ميد

تجدر الإشارة إلى شعبية هذه الخوارزمية بين الباحثين في طرق التحسين متعددة الأبعاد. تعد طريقة Nelder-Mead إحدى الطرق القليلة التي تعتمد على مفهوم التحويل المتسلسل لشكل بسيط قابل للتشوه حول نقطة قصوى ولا تستخدم خوارزمية للتحرك نحو الحد الأدنى العالمي.
هذا البسيط منتظم ويتم تمثيله كمتعدد السطوح مع قمم متباعدة بشكل متساوٍ للبسيط في الفضاء ذي الأبعاد N. في مساحات مختلفة، يتم تعيين البسيط إلى مثلث متساوي الأضلاع R2، وفي R3 إلى رباعي منتظم.
كما ذكرنا أعلاه، فإن الخوارزمية عبارة عن تطوير لطريقة الإرسال البسيط الخاصة بـ Spendley وHext وHimsworth، ولكنها، على عكس الأخيرة، تسمح باستخدام صيغ بسيطة غير صحيحة. في أغلب الأحيان، يعني البسيط مجسمًا متعدد السطوح محدبًا بعدد القمم N+1، حيث N هو عدد معلمات النموذج في الفضاء ذي الأبعاد n.
من أجل البدء في استخدام هذه الطريقة، تحتاج إلى تحديد الرأس الأساسي لجميع مجموعات الإحداثيات المتاحة باستخدام التعبير:

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

حيث xc هو مركز الثقل (انظر الشكل 1).

الشكل 1 - الانعكاس من خلال مركز الجاذبية

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

تستخدم خوارزمية Nelder-Mead أيضًا هذه الوظائف البسيطة وفقًا للصيغ التالية:

يتم حساب دالة الانعكاس من خلال مركز ثقل الجسم البسيط باستخدام التعبير التالي:

يتم تنفيذ هذا الانعكاس بدقة نحو النقطة القصوى وفقط من خلال مركز الثقل (انظر الشكل 2).

الشكل 2 - يحدث انعكاس الجسم البسيط من خلال مركز الجاذبية

يتم حساب دالة الضغط الداخلي للبسيط باستخدام التعبير التالي:

من أجل إجراء الضغط، من الضروري تحديد النقطة ذات القيمة الأصغر (انظر الشكل 3).

الشكل 3 - يتم ضغط الإرسال البسيط إلى أصغر وسيطة.

يتم حساب دالة الانعكاس مع الضغط البسيط باستخدام التعبير التالي:

من أجل تنفيذ الانعكاس بالضغط (انظر الشكل 4)، من الضروري أن نتذكر تشغيل وظيفتين منفصلتين - الانعكاس من خلال مركز الثقل وضغط البسيط إلى أصغر قيمة.

الشكل 4 - الانعكاس مع الضغط

تحدث وظيفة الانعكاس مع تمديد البسيط (انظر الشكل 5) باستخدام وظيفتين - الانعكاس من خلال مركز الجاذبية والتمدد من خلال أكبر قيمة.

الشكل 5 - الانعكاس مع التمدد.

لتوضيح تشغيل طريقة Nelder-Mead، من الضروري الرجوع إلى الرسم التخطيطي للخوارزمية (انظر الشكل 6).
بادئ ذي بدء، كما في الأمثلة السابقة، تحتاج إلى تعيين معلمة التشويه ε، والتي يجب أن تكون أكبر من الصفر تمامًا، وكذلك تعيين المعلمات الضرورية لحساب α و β و a. سيكون هذا ضروريًا لحساب الدالة f(x0)، وكذلك لإنشاء البسيط نفسه.

الشكل 6 - الجزء الأول من طريقة نيلدر-ميد.

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

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

بمجرد أن يصبح هذا الشرط صحيحا، فإن النقطة x(0) من البسيط ستعتبر النقطة القصوى المطلوبة. وفي حالة أخرى، ننتقل إلى الخطوة التالية، حيث نحتاج إلى تحديد القيمة الجديدة لمركز الثقل باستخدام الصيغة:

إذا تم استيفاء هذا الشرط، فستكون النقطة x(0) هي الحد الأدنى للنقطة، وإلا فستحتاج إلى الانتقال إلى الخطوة التالية التي تحتاج فيها إلى البحث عن أصغر وسيطة للدالة:

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

الشكل 7 - الجزء الثاني من طريقة نيلدر-ميد.

يجب استبدال القيمة المحسوبة من الوظيفة السابقة في شرط fmin< f(xN). При истинном выполнении данного условия, точка x(N) будет являться минимальной из группы тех, которые хранятся в отсортированном списке и нужно вернуться к шагу, где мы рассчитывали центр тяжести, в противном случае, производим сжатие симплекса в 2 раза и возвращаемся к самому началу с новым набором точек.
تُظهر دراسات هذه الخوارزمية أن الأساليب ذات التبسيطات غير المنتظمة (انظر الشكل 8) لا تزال غير مدروسة بشكل جيد، لكن هذا لا يمنعها من التعامل بشكل جيد مع المهام المعينة.
تُظهر المزيد من الاختبارات المتعمقة أنه من الممكن بشكل تجريبي تحديد معلمات وظائف التمدد والضغط والانعكاس الأكثر ملاءمة للمهمة، ولكن يمكنك استخدام المعلمات المقبولة عمومًا لهذه الوظائف α = 1/2، β = 2، γ = 2 أو α = 1/4، β = 5/2، γ = 2. لذلك، قبل التخلص من هذه الطريقة لحل المشكلة، من الضروري أن نفهم أنه لكل بحث جديد عن الحد الأقصى غير المشروط، تحتاج لمراقبة سلوك البسيط عن كثب أثناء تشغيله وملاحظة الحلول غير القياسية للطريقة.

الشكل 8 - عملية إيجاد الحد الأدنى.

أظهرت الإحصائيات أن إحدى المشكلات الأكثر شيوعًا في تشغيل هذه الخوارزمية هي انحطاط الشكل البسيط القابل للتشوه. يحدث هذا في كل مرة تقع فيها عدة رؤوس بسيطة في مساحة واحدة، لا يفي أبعادها بالمهمة.
وبالتالي، فإن البعد أثناء التشغيل والبعد المعطى يلقيان عدة رؤوس من البسيط في خط مستقيم واحد، مما يطلق الطريقة في حلقة لا نهائية. الخوارزمية في هذا التعديل ليست مجهزة حتى الآن بطريقة للخروج من هذا الموقف وتحريك قمة واحدة إلى الجانب، لذلك يتعين علينا إنشاء مفرد جديد بمعلمات جديدة لمنع حدوث ذلك في المستقبل.
تحتوي هذه الطريقة على ميزة أخرى - فهي لا تعمل بشكل صحيح مع ستة رؤوس أو أكثر من الرؤوس البسيطة. ومع ذلك، من خلال تعديل هذه الطريقة، يمكنك التخلص من هذه المشكلة وعدم فقدان سرعة التنفيذ، ولكن قيمة الذاكرة المخصصة ستزداد بشكل ملحوظ. هذه الطريقةيمكن اعتبارها دورية، لأنها تعتمد بالكامل على الدورات، ولهذا السبب يتم ملاحظة التشغيل غير الصحيح عندما كميات كبيرةقمم
يمكن اعتبار خوارزمية Nelder-Mead واحدة من هذه الخوارزميات أفضل الطرقالعثور على النقطة القصوى باستخدام البسيط وهو ممتاز لاستخدامه في مختلف أنواع الهندسة و المهام الاقتصادية. حتى على الرغم من الدورية، فإنها تستخدم كمية صغيرة جدًا من الذاكرة، مقارنة بنفس طريقة الهبوط الإحداثي، وللعثور على الحد الأقصى نفسه، من الضروري حساب قيم مركز الثقل والوظيفة فقط. إن وجود عدد صغير ولكن كافٍ من المعلمات المعقدة يجعل هذه الطريقة مستخدمة على نطاق واسع في مشاكل الإنتاج الرياضية والفعلية المعقدة.
خوارزميات Simplex هي منطقة لن نفتح آفاقها قريبًا، ولكنها الآن تعمل بالفعل على تبسيط حياتنا بشكل كبير من خلال مكونها المرئي.

ملاحظة. النص هو لي تماما. أتمنى شخص ما هذه المعلومةسيكون مفيدا.

تعتمد الطريقة على التعديل التكراري التالي للصيغة

س ك +1 = س ك + أ ك ق(س ك)،

س ك+1 = س ك - أ ك Ñ و(س ك)، حيث

أ هو معامل إيجابي معين؛

Ñ ​​​​f(x k) هو التدرج للدالة الموضوعية من الدرجة الأولى.

عيوب:

الحاجة إلى اختيار القيمة المناسبة لـ ؛

تقارب بطيء إلى النقطة الدنيا بسبب صغر f(x k) بالقرب من هذه النقطة.

طريقة النزول الحاد

خالية من العيب الأول لأبسط طريقة للتدرج، لأن يتم حساب a k عن طريق حل مشكلة تقليل Ñ f(x k) على طول الاتجاه Ñ f(x k) باستخدام إحدى طرق التحسين أحادية البعد x k+1 = x k - a k Ñ f(x k).

تسمى هذه الطريقة أحيانًا بطريقة كوشي.

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

طريقة الاتجاهات المترافقة

تتلخص المشكلة العامة للبرمجة غير الخطية غير المقيدة في ما يلي: تقليل f(x), x E n حيث f(x) هي الوظيفة الموضوعية. عند حل هذه المشكلة، نستخدم طرق التصغير التي تؤدي إلى نقطة ثابتة f(x)، محددة بالمعادلة f(x *)=0. تشير طريقة الاتجاه المترافق إلى طرق التقليل غير المقيدة التي تستخدم المشتقات. المشكلة: تصغير f(x)، x E n، حيث f(x) هي الدالة الموضوعية للمتغيرات المستقلة n. ميزة مهمة هي التقارب السريع نظرًا لأنه عند اختيار الاتجاه يتم استخدام مصفوفة هسه التي تصف منطقة طوبولوجيا سطح الاستجابة. على وجه الخصوص، إذا كانت الدالة الهدف تربيعية، فيمكن الحصول على النقطة الدنيا في ما لا يزيد عن عدد من الخطوات المساوية لبعد المشكلة.

ولتطبيق الطريقة عمليا، يجب استكمالها بإجراءات التحقق من التقارب والاستقلال الخطي لنظام الاتجاه. طرق الأمر الثاني

طريقة نيوتن

يؤدي التطبيق المتسق لمخطط التقريب التربيعي إلى تطبيق طريقة نيوتن للتحسين حسب الصيغة

س ك +1 = س ك - Ñ 2 و(س ك -1) Ñ و(س ك).

عيب طريقة نيوتن هو عدم موثوقيتها عند تحسين الدوال الموضوعية غير التربيعية. ولذلك، غالبا ما يتم تعديله:

س ك +1 = س ك - أ ك Ñ 2 و(س ك -1) Ñ و(س ك)، حيث

a k هي معلمة تم اختيارها بحيث تكون f(x k+1) min.

2. إيجاد الحد الأقصى للدالة دون حصر

بالنظر إلى دالة معينة f(x) على فترة مفتوحة (a, b) من التغييرات في الوسيطة x. نحن نفترض أن ext موجود خلال هذه الفترة (يجب القول أنه في الحالة العامة لا يمكن ذكر ذلك رياضيًا مسبقًا؛ ومع ذلك، في التطبيقات التقنية، غالبًا ما يكون وجود ext خلال فترة زمنية معينة من التغيير في فترة تغيير يمكن التنبؤ بالحجة من الاعتبارات المادية).

تعريف تحويلة. الدالة f(x) المعطاة على الفاصل الزمني (a, b) تكون عند النقطة x * max(min)، إذا كان من الممكن أن تكون هذه النقطة محاطة بمثل هذا الفاصل الزمني (x * -ε, x * +ε) الموجود في الفاصل الزمني (a, b) ، والذي بالنسبة لجميع نقاطه x التي تنتمي إلى الفاصل الزمني (x * -ε, x * +ε) ، فإن عدم المساواة التالية:

f(x) ≥ f(x *) → للحد الأقصى

f(x) ≥ f(x *) → للدقيقة

لا يفرض هذا التعريف أي قيود على فئة الوظائف f(x)، والتي تعد بالطبع ذات قيمة كبيرة.

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

نظرية فيرما. دع الدالة f (x) يتم تعريفها في فترة زمنية معينة (a، b) وعند النقطة "c" من هذه الفترة تأخذ القيمة الأكبر (الأصغر). إذا كان هناك مشتق محدود ذو وجهين عند هذه النقطة، فإن وجود exst ضروري.

ملحوظة. تتميز المشتقة ذات الوجهين بخاصية بمعنى آخر، نحن نتحدث عن حقيقة أنه عند النقطة "ج" يكون المشتق في النهاية هو نفسه عند الاقتراب من النقطة "ج" من اليسار واليمين، أي f(x) ) – وظيفة سلسة.

* في حالة الحد الأدنى، وفي → الحد الأقصى. أخيرًا، إذا كانت x=x 0، فإن استخدام المشتق الثاني لا يساعد وتحتاج إلى استخدام، على سبيل المثال، تعريف exst.

عند حل المشكلة الأولى، يتم استخدام الشروط الضرورية exst (أي نظرية فيرما) في كثير من الأحيان.

إذا كانت المعادلة لها جذور حقيقية، فإن النقاط المقابلة لهذه الجذور تكون مشبوهة في exst (ولكن ليس بالضرورة الأطراف المتطرفة نفسها، لأننا نتعامل مع الشروط الضرورية، وليس مع الشروط الضرورية والكافية). لذلك، على سبيل المثال، عند نقطة انعطاف X n يحدث، ولكن، كما هو معروف، هذا ليس أقصى.

ولنلاحظ أيضاً أن:

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

ومن الشروط الضرورية يستحيل تحديد ما إذا كان هذا الحد الأقصى عالميًا أم محليًا.

لذلك، عند العثور على نقاط مشبوهة بالنسبة لـ exst، يتم فحصها بشكل أكبر، على سبيل المثال، بناءً على تعريف exst أو المشتق الثاني.

تعتمد طرق التدرج للبحث عن الوظيفة الهدف الأمثل على استخدام خاصيتين رئيسيتين لتدرج الوظيفة.

1. تدرج الدالة هو متجه عند كل نقطة من مجال تعريف الدالة
يتم توجيهها بشكل طبيعي إلى المستوى السطحي المرسوم من خلال هذه النقطة.

توقعات التدرج
على محور الإحداثيات تساوي المشتقات الجزئية للدالة
وفقا للمتغيرات المقابلة، أي.

. (2.4)

تشمل طرق التدرج: طريقة الاسترخاء، وطريقة التدرج، وطريقة الهبوط الأكثر انحدارًا، وعدد من الطرق الأخرى.

دعونا نلقي نظرة على بعض أساليب التدرج.

طريقة التدرج

في هذه الطريقة، يتم إجراء الهبوط في اتجاه التغيير الأسرع في وظيفة الهدف، مما يؤدي بطبيعة الحال إلى تسريع عملية العثور على الأمثل.

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

عند تنفيذ خطوة ما، تتغير قيم جميع المتغيرات المستقلة في وقت واحد. يتلقى كل واحد منهم زيادة تتناسب مع المكون المقابل للتدرج على طول محور معين.

يمكن أن يبدو التدوين الصيغةي للخوارزمية كما يلي:

,
. (2.5)

في هذه الحالة، حجم الخطوة
في قيمة ثابتةتتغير المعلمة h تلقائيًا مع التغييرات في قيمة التدرج وتتناقص مع اقترابها من المستوى الأمثل.

صيغة أخرى للخوارزمية هي:

,
. (2.6)

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

في استراتيجية التغيير الخطوة
في هذه الحالة يتم استخدامه أن التدرجات
و
تختلف في الاتجاه. يتم تغيير خطوة البحث وفقًا للقاعدة:

(2.7)

أين
- زاوية دوران التدرج عند الخطوة k، التي يحددها التعبير

,

,
– الحدود المسموح بهازاوية الدوران المتدرجة.

طبيعة البحث عن الأمثل في طريقة التدرج موضحة في الشكل. 2.1.

يمكن العثور على لحظة نهاية البحث عن طريق التحقق من كل خطوة من خطوات العلاقة

,

أين - خطأ حسابي محدد.

أرز. 2.1. طبيعة الحركة نحو الأمثل بطريقة التدرج مع حجم خطوة كبير

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

عيب آخر لهذه الطريقة هو الكم الكبير من الحسابات، لأنه في كل خطوة يتم تحديد قيم جميع المشتقات الجزئية للدالة الأمثل فيما يتعلق بجميع المتغيرات المستقلة.

طريقة النزول الحاد

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

يمكن تحقيق تقليل مقدار الحساب باستخدام طريقة الهبوط الأكثر انحدارًا.

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

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

أرز. 2.2. - طبيعة الحركة نحو الأمثل في الأسلوب شديد الانحدار(-) وطريقة التدرج (∙∙∙∙)

بالمقارنة مع طريقة التدرج، تعتبر طريقة الهبوط الأكثر انحدارًا أكثر فائدة بسبب انخفاض كمية الحسابات.

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

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

بالإضافة إلى ذلك، يمكنك أيضًا أخذ شرط إنهاء البحث في شكل العلاقة

,

أين
و
– إحداثيات نقطة البداية والنهاية للجزء الأخير من الهبوط. ويمكن استخدام نفس المعيار مع مراقبة قيم الدالة الهدف عند النقاط
و

.

إن التطبيق المشترك لشروط إنهاء البحث له ما يبرره في الحالات التي يكون فيها للوظيفة التي يتم تحسينها حد أدنى محدد بوضوح.

أرز. 2.3. تحديد نهاية البحث بطريقة النزول الأكثر انحداراً

كإستراتيجية لتغيير خطوة النزول، يمكنك استخدام الطرق الموضحة أعلاه (2.7).

كما أشرنا سابقًا، فإن مشكلة التحسين هي مهمة العثور على قيم العوامل هذه X 1 = X 1* , X 2 = X 2* , …, Xك = Xك * ، والتي وظيفة الاستجابة ( في) يصل إلى قيمة متطرفة في= تحويلة (الأمثل).

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

دعونا نفكر في جوهر طريقة التدرج باستخدام مثال دالة الاستجابة ذات العاملين ص =F(س 1 ، اكس 2 ). في التين. ويبين الشكل 4.3 منحنيات القيم المتساوية لدالة الاستجابة (منحنيات المستوى) في فضاء العامل. نقطة مع الإحداثيات X 1 *, X 2 * يتوافق مع القيمة القصوى لوظيفة الاستجابة فيتحويلة.

إذا اخترنا أي نقطة في مساحة العامل لتكون النقطة الأولية ( X 1 0 , X 2 0)، ثم أقصر الطرقإلى الجزء العلوي من دالة الاستجابة من هذه النقطة يوجد مسار على طول المنحنى، حيث يتزامن المماس عند كل نقطة مع المنحنى الطبيعي إلى المستوى، أي. وهو المسار في اتجاه تدرج دالة الاستجابة.

التدرج من وظيفة مستمرة ذات قيمة واحدة ص =F(س 1 ، اكس 2) هو متجه محدد في الاتجاه بواسطة التدرج مع الإحداثيات:

أين أنا،ي- متجهات الوحدة في اتجاه محاور الإحداثيات X 1 و X 2. المشتقات الجزئية تميز اتجاه المتجه.

لأننا لا نعرف نوع الاعتماد ص =F(س 1 ، اكس 2) لا يمكننا إيجاد مشتقات جزئية وتحديد الاتجاه الحقيقي للتدرج.

وفقا لطريقة التدرج، يتم تحديد نقطة أولية (المستويات الأولية) في جزء ما من مساحة العامل X 1 0 , X 20 . تم إنشاء تصميم تجريبي متماثل من مستويين فيما يتعلق بهذه المستويات الأولية. علاوة على ذلك، تم اختيار فترة الاختلاف صغيرة جدًا بحيث يكون النموذج الخطي مناسبًا. ومن المعروف أن أي منحنى في مساحة صغيرة بما فيه الكفاية يمكن تقريبه بواسطة نموذج خطي.

بعد بناء خطة متناظرة ذات مستويين، يتم حل مشكلة الاستيفاء، أي. تحت التشيد نموذج خطي:

ويتم التحقق من كفايتها.

إذا تبين أن النموذج الخطي مناسب لفترة التباين المحددة، فيمكن تحديد اتجاه التدرج:

وبالتالي، يتم تحديد اتجاه تدرج دالة الاستجابة من خلال قيم معاملات الانحدار. وهذا يعني أننا سوف نتحرك في اتجاه التدرج إذا كان من النقطة ذات الإحداثيات ( ) دعنا نذهب إلى النقطة بالإحداثيات:

أين م –رقم موجب يحدد حجم الخطوة في اتجاه التدرج.

بسبب ال X 1 0 = 0 و X 2 0 = 0 إذن .

من خلال تحديد اتجاه التدرج () واختيار حجم الخطوة م، نقوم بإجراء التجربة على المستوى الأولي X 1 0 , X 2 0 .

ثم نخطو خطوة في اتجاه التدرج أي: نجري التجربة عند نقطة ذات إحداثيات. إذا زادت قيمة دالة الاستجابة مقارنة بقيمتها عند المستوى الأولي، فإننا نخطو خطوة أخرى في اتجاه التدرج، أي. نجري التجربة عند نقطة ذات إحداثيات:

نواصل التحرك على طول التدرج حتى تبدأ وظيفة الاستجابة في الانخفاض. في التين. 4.3 الحركة على طول التدرج تتوافق مع خط مستقيم منبثق من النقطة ( X 1 0 , X 20). وهو ينحرف تدريجياً عن الاتجاه الحقيقي للتدرج، الموضح بالخط المتقطع، بسبب عدم خطية دالة الاستجابة.

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

من خلال بناء نموذج خطي جديد ، تنفيذ تحليل الانحدار. إذا، في نفس الوقت، والتحقق من أهمية العوامل يظهر أن معامل واحد على الأقل

العامل، مما يعني أن المنطقة القصوى لوظيفة الاستجابة (المنطقة المثلى) لم يتم الوصول إليها بعد. يتم تحديد اتجاه جديد للتدرج وتبدأ الحركة نحو المنطقة المثالية.

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

في منظر عاميمكن عرض تسلسل الإجراءات المطلوبة لحل مشكلة التحسين باستخدام طريقة التدرج في شكل مخطط تدفق (الشكل 4.4).

1) المستويات الأولية للعوامل ( Xي 0) ينبغي للمرء أن يختار أقرب ما يمكن إلى النقطة المثلى، إذا كانت هناك بعض المعلومات المسبقة عن موقعها؛

2) فترات الاختلاف (Δ Xي) يجب اختياره بحيث يكون النموذج الخطي مناسبًا على الأرجح. الحدود أدناه Δ Xيفي هذه الحالة، هذا هو الحد الأدنى لقيمة الفاصل الزمني للتغيير الذي تظل فيه وظيفة الاستجابة مهمة؛

3) قيمة الخطوة ( ت) عند التحرك على طول التدرج، يتم اختياره بحيث لا يتجاوز أكبر المنتجات الفرق بين المستويات العليا والدنيا للعوامل في الشكل الطبيعي

.

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

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

بهذا المعدل،

تحتوي الفصول التالية على محاضرة واحدة أو أكثر. المواد المقدمة في الفصول أوسع إلى حد ما مما يتم تقديمه عادة في المحاضرات. تحتوي الملاحق على وصف للبرامج المستخدمة في هذه الدورة (

بما في ذلك مستويين - مستوى طلبات مكونات الكمبيوتر العصبي العالمي ومستوى اللغات لوصف المكونات الفردية للكمبيوتر العصبي.

المنهج

مهام المختبر

#AutBody_14DocRoot

#AutBody_15DocRoot

كتاب عصبي

#AutBody_16DocRoot

مشروع معيار الكمبيوتر العصبي

هذا الدليل إلكتروني ويتضمن البرامج اللازمة لأداء العمل المختبري.

كتاب:

الأقسام الموجودة في هذه الصفحة:

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

طريقة النزول الحاد

1. احسب_تقدير O2
2. O1=O2
3. احسب_التدرج
4. الخطوة الأمثل Null_pointer
5. احسب_تقدير O2
6. إذا كان O1-O2<Точность то переход к шагу 2

أرز. 5. طريقة النزول الحاد

الأكثر شهرة بين طرق التدرج هي طريقة النزول الأكثر انحدارًا. فكرة هذه الطريقة بسيطة: بما أن ناقل التدرج يشير إلى اتجاه أسرع زيادة في الدالة، فيجب البحث عن الحد الأدنى في الاتجاه المعاكس. يظهر تسلسل الإجراءات في الشكل. 5.

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

أرز. 6. مسارات النسب لتكوينات مختلفة للحي الأدنى وطرق التحسين المختلفة.

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

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

kParTan

1. إنشاء_ناقل B1
2. إنشاء_ناقل B2
3. الخطوة=1
4. احسب_تقدير O2
5. Save_vector B1
6. O1=O2
7. ن = 0
8. احسب_التدرج
9. خطوة_التحسين Null_pointer
10. ن=ن+1
11. إذا ن 12. Save_vector B2
13. ب2=ب2-ب1
14. ستيببارتان=1
15. تحسين الخطوة B2 StepParTan
16. احسب_تقدير O2
17. إذا كان O1-O2<Точность то переход к шагу 5

أرز. 7. طريقة kParTan

واحدة من أبسط الطرق لمكافحة الأخاديد هي طريقة kParTan. تتمثل فكرة الطريقة في تذكر نقطة البداية، ثم تنفيذ خطوات التحسين k باستخدام طريقة الهبوط الأكثر انحدارًا، ثم تنفيذ خطوة التحسين في الاتجاه من نقطة البداية إلى النقطة النهائية. ويرد وصف للطريقة في الشكل 7. ويبين الشكل 6ج خطوة تحسين واحدة باستخدام طريقة 2ParTan. يمكن أن نرى أنه بعد خطوة على طول الاتجاه من النقطة الأولى إلى النقطة الثالثة، أدى مسار النزول إلى الحد الأدنى. ولسوء الحظ، هذا ينطبق فقط على الحالة ثنائية الأبعاد. في الحالة متعددة الأبعاد، لا يؤدي اتجاه kParTan مباشرة إلى النقطة الدنيا، ولكن الهبوط في هذا الاتجاه، كقاعدة عامة، يؤدي إلى جوار الحد الأدنى لنصف قطر أصغر من خطوة أخرى من طريقة الهبوط الأكثر انحدارًا (انظر الشكل 6 ب). بالإضافة إلى ذلك، تجدر الإشارة إلى أن الخطوة الثالثة لم تتطلب حساب التدرج، مما يوفر الوقت أثناء التحسين العددي.