البحث عن الأنماط (التحسين)

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

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

تاريخ

صاغ هوك وجيفز مصطلح "البحث عن الأنماط". [ 1 ] يُنسب شكلٌ مبكرٌ وبسيطٌ منه إلى فيرمي وميتروبوليس عندما كانا يعملان في مختبر لوس ألاموس الوطني . وقد وصفه ديفيدون، [ 2 ] على النحو التالي:

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

التقارب

التقارب هو أسلوب بحث عن الأنماط اقترحه يو، الذي أثبت تقاربه باستخدام نظرية القواعد الموجبة. [ 3 ] لاحقًا، استخدم توركزون ولاغارياس وزملاؤهما [ 4 ] [ 5 ] تقنيات القواعد الموجبة لإثبات تقارب أسلوب بحث آخر عن الأنماط على فئات محددة من الدوال. خارج هذه الفئات، يُعد البحث عن الأنماط أسلوبًا استدلاليًا يُمكنه توفير حلول تقريبية مفيدة لبعض المسائل، ولكنه قد يفشل في مسائل أخرى. خارج هذه الفئات، لا يُعد البحث عن الأنماط أسلوبًا تكراريًا يتقارب إلى حل؛ بل إن أساليب البحث عن الأنماط قد تتقارب إلى نقاط غير ثابتة في بعض المسائل البسيطة نسبيًا. [ 6 ] [ 7 ]

انظر أيضاً

  • يشبه البحث باستخدام النسبة الذهبية من الناحية المفاهيمية البحث باستخدام النسبة الذهبية في تضييق نطاق البحث، ولكن فقط بالنسبة لمساحات البحث أحادية البعد.
  • طريقة نيلدر-ميد المعروفة أيضًا باسم طريقة سيمبلكس تشبه من الناحية المفاهيمية طريقة PS في تضييق نطاق البحث لمساحات البحث متعددة الأبعاد، ولكنها تفعل ذلك عن طريق الحفاظ على n  +  1 نقطة لمساحات البحث ذات الأبعاد n ، في حين أن طرق PS تحسب 2 n  +  1 نقطة (النقطة المركزية ونقطتين في كل بُعد).
  • يقوم Luus–Jaakola بأخذ عينات من توزيع منتظم يحيط بالموقع الحالي ويستخدم صيغة بسيطة لتقليل نطاق أخذ العينات بشكل أسي.
  • البحث العشوائي هو عائلة ذات صلة من أساليب التحسين التي تأخذ عينات من كرة فائقة تحيط بالموقع الحالي.
  • التحسين العشوائي هو عائلة ذات صلة من أساليب التحسين التي تأخذ عينات من التوزيع الطبيعي المحيط بالموقع الحالي.

مراجع

  1. ^ هوك، ر. جيفيس، تا (1961). ""حلول البحث المباشر للمسائل العددية والإحصائية" . مجلة ACM . 8 (2): 212-229 . doi : 10.1145/321062.321069 . S2CID 10905054 . 
  2. ↑ ديفيدون، دبليو سي (1991). "طريقة المقياس المتغير للتقليل". مجلة SIAM للتحسين . 1 (1): 1-17 . CiteSeerX 10.1.1.693.272 . doi : 10.1137/0801001 . S2CID 1819475 .  
  3. ↑
  4. ↑ تورزون، في جيه (1997). "حول تقارب خوارزميات البحث عن الأنماط" (ملف PDF) . مجلة SIAM للتحسين . 7 (1): 1-25 . CiteSeerX 10.1.1.50.3173 . doi : 10.1137/S1052623493250780 . 
  5. ↑ دولان، إي دي؛ لويس، آر إم؛ توركزون، في جيه (2003). "حول التقارب المحلي للبحث عن الأنماط" (ملف PDF) . مجلة SIAM للتحسين . 14 (2): 567-583 . CiteSeerX 10.1.1.78.2407 . doi : 10.1137/S1052623400374495 . hdl : 2060/20000109966 . S2CID 4226940 .  
  6. ↑
  7. ↑
    • ماكينون، كيم (1999). "تقارب طريقة نيلدر-ميد سيمبلكس إلى نقطة غير مستقرة". مجلة SIAM للتحسين ، 9 : 148-158 . CiteSeerX 10.1.1.52.3900 . doi : 10.1137/S1052623496303482 . (ملخص الخوارزمية متاح عبر الإنترنت).