Global optimization

الموسوعة الحرة

Global optimization is a branch of operations research, applied mathematics, and numerical analysis that attempts to find the global minimum or maximum of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function g(x){\displaystyle g(x)} is equivalent to the minimization of the function f(x):=(−1)⋅g(x){\displaystyle f(x):=(-1)\cdot g(x)}.

Given a possibly nonlinear and non-convex continuous function f:Ω⊂Rn→R{\displaystyle f:\Omega \subset \mathbb {R} ^{n}\to \mathbb {R} } with the global minimum f∗{\displaystyle f^{*}} and the set of all global minimizers X∗{\displaystyle X^{*}} in Ωأوميغا, the standard minimization problem can be given as

minx∈Ωf(x),{\displaystyle \min _{x\in \Omega }f(x),}

that is, finding f∗{\displaystyle f^{*}} and a global minimizer in X∗{\displaystyle X^{*}}; where Ωأوميغا is a (not necessarily convex) compact set defined by inequalities gi(x)⩾0,i=1,…,r{\displaystyle g_{i}(x)\geqslant 0,i=1,\ldots ,r}.

Global optimization is distinguished from local optimization by its focus on finding the minimum or maximum over the given set, as opposed to finding local minima or maxima. Finding an arbitrary local minimum is relatively straightforward by using classical local optimization methods. Finding the global minimum of a function is far more difficult: analytical methods are frequently not applicable, and the use of numerical solution strategies often leads to very hard challenges.

Applications

Typical examples of global optimization applications include:

Deterministic methods

The most successful general exact strategies are:

Inner and outer approximation

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

أساليب القطع بالمسحاة

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

أساليب التفرع والتقييد

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

طرق الفترات

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

طرق تعتمد على الهندسة الجبرية الحقيقية

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

الأساليب العشوائية

توجد العديد من الخوارزميات الدقيقة أو غير الدقيقة القائمة على طريقة مونت كارلو:

أخذ العينات المباشر باستخدام طريقة مونت كارلو

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

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

النفق العشوائي

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

التصليد المتوازي

التبريد المتوازي ، المعروف أيضًا باسم أخذ عينات مونت كارلو ماركوف المتسلسلة (MCMC) باستخدام تبادل النسخ ، هو أسلوب محاكاة يهدف إلى تحسين الخصائص الديناميكية لمحاكاة مونت كارلو للأنظمة الفيزيائية، وطرق أخذ عينات مونت كارلو ماركوف المتسلسلة (MCMC) بشكل عام. ابتكر سويندسن طريقة تبادل النسخ في الأصل، [ 1 ] ثم وسّعها غيير [ 2 ] وطوّرها لاحقًا، من بين آخرين، جورجيو باريسي [ 3 ] [ 4 ] . صاغ سوجيتا وأوكاموتو نسخة ديناميكية جزيئية من التبريد المتوازي: [ 5 ] وتُعرف عادةً باسم ديناميكيات الجزيئات بتبادل النسخ أو REMD.

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

الأساليب الاستدلالية والأساليب الاستدلالية المتقدمة

وتشمل الأساليب الأخرى استراتيجيات استدلالية للبحث في مساحة البحث بطريقة ذكية إلى حد ما، بما في ذلك:

الأساليب القائمة على منهجية سطح الاستجابة

انظر أيضاً

الحواشي

  1. ↑ Swendsen RH and Wang JS (1986) Replica Monte Carlo simulation of spin glass Physical Review Letters 57 : 2607–2609
  2. ↑ CJ Geyer, (1991) في علوم الحاسوب والإحصاء ، وقائع الندوة الثالثة والعشرين حول الواجهة، الجمعية الإحصائية الأمريكية، نيويورك، ص 156.
  3. ↑ ماركو فالسيوني ومايكل دبليو ديم (1999). "مخطط مونت كارلو متحيز لحل بنية الزيوليت". مجلة الفيزياء الكيميائية 110 (3): 1754-1766 . arXiv : cond-mat/9809085 . Bibcode : 1999JChPh.110.1754F . doi : 10.1063/1.477812 . S2CID 13963102 . 
  4. ↑ ديفيد ج. إيرل ومايكل و. ديم (2005) "التسخين المتوازي: النظرية والتطبيقات والآفاق الجديدة" ، مجلة الفيزياء الكيميائية ، 7، 3910
  5. ↑ واي. سوجيتا وواي. أوكاموتو (1999). "طريقة ديناميكيات الجزيئات لتبادل النسخ لطي البروتين". رسائل الفيزياء الكيميائية . 314 ( 1-2 ): 141-151 . Bibcode : 1999CPL...314..141S . doi : 10.1016/S0009-2614(99)01123-9 .
  6. ↑ ثاكر، نيل؛ كوتس، تيم (1996). "طرق التحسين المتدرجة غير المحدبة ومتعددة الدقة" . الرؤية من خلال التحسين .
  7. ↑ بليك، أندرو؛ زيسرمان، أندرو (1987). إعادة البناء البصري . مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-02271-0.
  8. ↑ حسين موباهي، جون دبليو فيشر الثالث. حول العلاقة بين استمرار التماثل الغاوسي والأغلفة المحدبة ، في سلسلة محاضرات في علوم الحاسوب (EMMCVPR 2015)، سبرينغر، 2015.
  9. ↑ جوناس موكوس (2013). النهج البايزي للتحسين العالمي: النظرية والتطبيقات . كلوير أكاديميك.

مراجع

التحسين العالمي الحتمي:

للمحاكاة الحرارية:

لتحسين البحث التفاعلي:

  • روبرتو باتيتي ، إم. بروناتو، وإف. ماسكيا، البحث التفاعلي والتحسين الذكي، سلسلة واجهات بحوث العمليات/علوم الحاسوب، المجلد 45، سبرينغر، نوفمبر 2008. ISBN 978-0-387-09623-0

بالنسبة للطرق العشوائية:

للتطبيع المتوازي:

لطرق المتابعة:

للاطلاع على الاعتبارات العامة المتعلقة بأبعاد مجال تعريف دالة الهدف:

للاستراتيجيات التي تسمح بمقارنة أساليب التحسين العالمي الحتمية والعشوائية