الاستدلال الميتاهوريستي المتوازي

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

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

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

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

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

يمكن النظر إلى أساليب الاستدلال الميتاهوريستية لحل مشاكل التحسين على أنها عمليات تجوال عبر الأحياء لتتبع مسارات البحث عبر مجالات حل المشكلة المطروحة:

الخوارزمية: شيفرة زائفة عامة قائمة على المسار المتسلسل Generate( s (0)); // الحل الأولي t := 0; // الخطوة العددية طالما لم يتحقق معيار الإنهاء(s(t)) do s′( t ) := SelectMove(s( t )); // استكشاف الجوار if AcceptMove(s′( t )) then s( t ) := ApplyMove(s′( t )); t := t + 1; endwhile

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

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

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

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

الخوارزمية: شفرة زائفة فوقية تسلسلية قائمة على السكان توليد(P(0))؛ // المجموعة السكانية الأولية t := 0; // خطوة عددية طالما لم يتحقق معيار الإنهاء (P( t ))، قم بتقييم (P( t )); // تقييم المجموعة P′′( t ) := تطبيق عوامل التغيير(P′( t )); // توليد حلول جديدة P( t + 1) := Replace(P( t ), P′′( t )); // بناء المجموعة التالية t := t + 1; endwhile

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

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

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

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

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

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

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

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

• الخوارزميات التطورية الخلوية
• إنريكي ألبا

• جي. لوك، إي. ألبا، الخوارزميات الجينية المتوازية: النظرية والتطبيقات العملية، سبرينغر-فيرلاغ، رقم ISBN 978-3-642-22083-8يوليو 2011
• Alba E., Blum C., Isasi P., León C. Gómez JA (eds.)، تقنيات التحسين لحل المشكلات المعقدة، وايلي ، ISBN 978-0-470-29332-42009
• إي. ألبا، ب. دورونسورو، الخوارزميات الجينية الخلوية، سبرينغر-فيرلاغ ، ISBN 978-0-387-77609-52008
• N. Nedjah، E. Alba، L. de Macedo Mourelle، الحسابات التطورية الموازية، Springer-Verlag ، ISBN 3-540-32837-82006
• هاء ألبا، الميتاهيرستكس الموازية: فئة جديدة من الخوارزميات، وايلي ، ISBN 0-471-67806-6يوليو 2005
• مالبا
• JGDS
• ديمي
• xxGA
• مزمور-إيا
• باراديسو