🔢 mathematics

In ratio section method and algorithms for minimizing unimodal functions

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

المؤلفون الأصليون: Vladimir Kodnyanko

نُشر 2026-04-30

📖 4 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Vladimir Kodnyanko

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

تخيل أنك تحاول العثور على أدنى نقطة في وادٍ شاسع يغطيه الضباب. لا يمكنك رؤية التضاريس بأكملها دفعة واحدة؛ يمكنك فقط الوقوف في مكان ما، والنظر حولك، ثم اتخاذ خطوة. هدفك هو العثور على قاع الوادي (الحد الأدنى) باستخدام أقل عدد ممكن من الخطوات. هذا بالضبط ما يفعله علماء الرياضيات عندما يحاولون "تقليل" (minimize) دالة ما.

تقدم هذه الورقة طريقة جديدة أسرع لاتخاذ تلك الخطوات. إليك تفصيل لأفكار المؤلف باستخدام تشبيهات بسيطة:

المشكلة: الطرق القديمة للبحث

لفترة طويلة، استخدم علماء الرياضيات استراتيجيتين رئيسيتين للعثور على قاع ذلك الوادي:

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

الفكرة الجديدة: طريقة "قسمة النسبة" (Ratio Section)

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

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

تقدم الورقة نسختين من هذه الطريقة الجديدة:

1. الخوارزمية "الخاملة" (RatioP)

هذه هي النسخة الأساسية. إنها تشبه متنزهاً ذكياً لديه حجم خطوة مفضل.

كيف تعمل: تختار نقطة بناءً على نسبة محددة (وجد المؤلف أن قطع الحبل عند حوالي 20% من المسافة، بدلاً من 50% أو 61%، هو الأفضل لمعظم التلال).
القوة الخارقة: تمتلك ميزة "قوة الإبصار". إذا كان الوادي في الواقع عبارة عن هضبة مسطحة (قاع مسطح) أو إذا كانت الأرض تنحدر باستمرار للأعلى أو للأسفل (دالة رتيبة)، فإن هذه الطريقة تكتشف ذلك فوراً.
النتيجة: نظرًا لقدرتها على اكتشاف هذه الأشكال الخاصة بسرعة، فهي لا تضيع الوقت في اتخاذ خطوات غير ضرورية. في الاختبارات، كانت أسرع بـ 2.26 مرة من طريقة "القسمة إلى النصف" وأسرع بـ 1.72 مرة من طريقة "النسبة الذهبية".

2. الخوارزمية "النشطة" (RatioA)

هذا هو "المتنزه الخارق". هو لا يتبع نسبة فحسب؛ بل يتعلم أثناء حركته.

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

ترقية "طريقة برنت" (Brent's Method)

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

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

الخلاصة

اختبرت الورقة هذه الطرق الجديدة مقابل 20 نوعاً مختلفاً من "التلال" الرياضية (بعضها ناعم، وبعضها مسطح، وبعضها متعرج).

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

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

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

1. بيان المشكلة

تتناول الورقة تحدي تقليل الدوال أحادية المنوال (Unimodal Functions) ذات المتغير الواحد. وبينما تُعد الأساليب الكلاسيكية مثل البحث بالتنصيف (Bisection Search)، وبحث القطع الذهبي (Golden Section Search - GSS)، وطريقة برينت (Brent's Method) أساليب راسخة، إلا أنها تعاني من بعض القيود:

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

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

2. المنهجية

يقترح المؤلف طريقة قسم النسبة (Ratio Section Method) جديدة ويطور ثلاث خوارزميات محددة بناءً عليها:

أ. تصنيف الدوال

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

الدوال الثابتة: النطاق بأكمله عبارة عن قاع مسطح.
الدوال الرتيبة (Monotone): متزايدة أو متناقصة بشكل صارم (مع إمكانية وجود قاع مسطح في أحد الجوانب).
الدوال أحادية المنوال الصارمة: تمتلك حداً أدنى واحداً، مع إمكانية وجود منطقة قاع مسطحة ( $\alpha < \beta$ ).

ب. الخوارزميات الجوهرية

خوارزمية RatioP (الخوارزمية السلبية):
- الآلية: تقسم مجال عدم اليقين $[a, b]$ بنسبة معينة $c$ . يتم وضع نقطة جديدة $p$ بالقرب من الحد الأدنى الحالي $m$ بناءً على النسبة $c$ .
- التحسين: على عكس التنصيف (حيث $c=0.5$ )، وُجد أن النسبة المثلى هي $c \approx 0.2$ . وهذا يضع نقطة التقييم الجديدة بالقرب من أفضل تقدير حالي، مما يؤدي إلى ضغط قطعة عدم اليقين بشكل أكثر قوة.
- التعامل الخاص: تتضمن كتلة منطقية للكشف المبكر عن الرتابة والقيعان المسطحة. إذا تم العثور على ثلاث نقاط ذات قيم متساوية، تتوقف الخوارزمية فوراً. وإذا تم اكتشاف الرتابة، يتم تحديد الحد الأدنى عند الطرف.
خوارزمية RatioA (الخوارزمية النشطة):
- الآلية: تبني على خوارزمية RatioP ولكنها تدمج خطوة الاستيفاء القطعي (Parabolic Interpolation) (وهي طريقة من الدرجة الثانية).
- المنطق: بمجرد إنشاء ثلاث نقاط تحقق شروطاً معينة (تشكل "إطاراً" حول الحد الأدنى)، تقوم الخوارزمية بحساب رأس القطع المكافئ الذي يمر عبر هذه النقاط للتنبؤ بالحد الأدنى.
- النهج الهجين: تستخدم RatioP لإيجاد الإطار الأولي ثم تنتقل إلى الخطوات القطعية لتحقيق تقارب أسرع، مع العودة إلى تقسيم النسبة في حال فشل القطع المكافئ.
طريقة برينت المحدثة (BrentM):
- التعديل: تجمع طريقة برينت الكلاسيكية بين الاستيفاء القطعي وبحث القطع الذهبي. يستبدل المؤلف مكون القطع الذهبي بإجراء RatioP.
- التعزيز: تدمج النسخة المحدثة أيضاً منطق اكتشاف الرتابة والقيعان المسطحة الموجود في خوارزمية RatioP، وهو ما تفتقر إليه طريقة برينت الأصلية.

3. المساهمات الرئيسية

استراتيجية قسم النسبة الجديدة: تقديم طريقة لتقسيم القطعة باستخدام نسبة $c$ (المحسنة عند 0.2) بدلاً من النسبة الثابتة 0.5 (التنصيف) أو النسبة الذهبية (~0.618).
منطق الإنهاء المبكر: تطوير كتلة خوارزمية محددة (Mnt) لتحديد الدوال الرتيبة ودوال القيعان المسطحة/الثابتة بسرعة، مما يسمح بإنهاء البحث في عدد قليل يتراوح بين 3 إلى 6 تقييمات لهذه الحالات المحددة.
تحسين النسبة $c$ : التحديد التجريبي بأن $c=0.2$ يحقق أفضل أداء لخوارزمية RatioP عبر مختلف أنواع الدوال.
تحديث طريقة برينت: دمج قسم النسبة واكتشاف الرتابة بنجاح في خوارزمية برينت القياسية، مما خلق نموذجاً هجيناً يتفوق على الطريقة الأصلية.

4. النتائج التجريبية

تم اختبار الخوارزميات على 20 دالة أحادية المنوال من أنواع متنوعة (سلسة، مسطحة، رتيبة، مجزأة) ومقارنتها بطرق التنصيف، والقطع الذهبي، وطريقة برينت القياسية.

مقاييس الأداء: تم قياسها بإجمالي عدد تقييمات الدالة ( $\Sigma k$ ).
RatioP مقابل الطرق الكلاسيكية (على الـ 20 دالة):
- خوارزمية RatioP ( $c=0.2$ ) أسرع بمقدار 2.26 مرة من البحث بالتنصيف.
- خوارزمية RatioP أسرع بمقدار 1.72 مرة من بحث القطع الذهبي.
- بالنسبة للدوال أحادية المنوال الصارمة (باستثناء الحالات الرتيبة/المسطحة)، لا تزال RatioP أسرع بمقدار 1.40 مرة من GSS.
RatioA مقابل RatioP:
- الخوارزمية النشطة (RatioA) أسرع بشكل ملحوظ، حيث قللت التقييمات بعامل إضافي مقارنة بـ RatioP السلبية.
برنت المحدث (BrentM) مقابل برنت الكلاسيكي:
- خوارزمية BrentM أسرع بمقدار 1.69 مرة من طريقة برينت الأصلية.
- خوارزمية BrentM أسرع بنحو 4 مرات من التنصيف وحوالي 3 مرات من GSS.
المتانة: تلغي طريقة برينت المحدثة الأخطاء التي تحدث في الخوارزمية الأصلية عند تقليل الدوال الرتيبة، مما يوفر نتائج دقيقة لهذه الفئة.

5. الأهمية والخاتمة

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

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

يخلص المؤلف إلى أن الطرق المقترحة، وخاصة RatioA النشطة وBrentM المحدثة، تمثل أسرع النهج المعروفة لتقليل الدوال أحادية المنوال، حيث تتفوق على المعايير الراسخة بهوامش كبيرة (تصل إلى 3-4 أضعاف في مقارنات محددة).