التحسين العشوائي

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

يُنسب اسم التحسين العشوائي إلى ماتياس ^{[ 1 ]} الذي قدم عرضًا مبكرًا له مصحوبًا بتحليل رياضي أساسي. يعمل التحسين العشوائي من خلال الانتقال بشكل متكرر إلى مواقع أفضل في فضاء البحث، والتي يتم اختيارها باستخدام، على سبيل المثال، التوزيع الطبيعي المحيط بالموقع الحالي.

يترك${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$لتكن دالة اللياقة أو التكلفة التي يجب تقليلها.${\displaystyle x\in \mathbb {R} ^{n}}$تحديد موقع أو حل مرشح في فضاء البحث. يمكن وصف خوارزمية RO الأساسية على النحو التالي:

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

تتوافق هذه الخوارزمية مع استراتيجية تطور (1+1) ذات حجم خطوة ثابت.

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

أجرى بابا ^{[ 2 ]} وسوليس وويتس ^{[ 3 ]} تحليلات رياضية لإثبات أن التقارب نحو منطقة محيطة بالقيمة المثلى أمر لا مفر منه في ظل بعض الشروط البسيطة لمتغيرات التحسين المتدرج باستخدام توزيعات احتمالية أخرى لأخذ العينات. وقد استنتج دوريا ^{[ 4 ]} تقديرًا لعدد التكرارات اللازمة للوصول إلى القيمة المثلى. إلا أن هذه التحليلات تعرضت لانتقادات من خلال تجارب عملية أجراها سارما ^{[ 5 ]،} الذي استخدم متغيرات التحسين الخاصة ببابا ودوريا على مسألتين من العالم الحقيقي، مُظهرًا أن الوصول إلى القيمة المثلى يتم ببطء شديد، بل إن هذه الطرق لم تكن قادرة على إيجاد حل ذي ملاءمة كافية، إلا إذا بدأت العملية من نقطة قريبة جدًا من القيمة المثلى.

• البحث العشوائي هو عائلة وثيقة الصلة من أساليب التحسين التي تأخذ عينات من كرة فائقة بدلاً من التوزيع الطبيعي.
• تُعد طريقة Luus–Jaakola طريقة تحسين وثيقة الصلة تستخدم توزيعًا منتظمًا في أخذ العينات وصيغة بسيطة لتقليل نطاق أخذ العينات بشكل أسي.
• تتخذ عملية البحث عن الأنماط خطوات على طول محاور مساحة البحث باستخدام أحجام خطوات متناقصة بشكل أسي.
• التحسين العشوائي