البحث المحظور: خروج من دائرة التكرار العشوائي

خالد زيان
(Khaled Ziane)

الحوار المتمدن-العدد: 5431 - 2017 / 2 / 13 - 00:04
المحور: تقنية المعلمومات و الكومبيوتر
    

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

تعتمد أغلب خوارزميات الأدلة العليا على عملية التكرار لتقليص متوسط الخطأ التربيعي Mean square error كنوع من الأمثَلة والتحسين وهي طريقة فعالة تندرج تحت اسم دالة الكفاءة Fitness -function- ، لكن أكبر مشكل قد يعترض هذا النوع من الخوارزميات هو تكرار نفس نتيجة الخطأ، بالعودة إليها كل مرة. فيلجأ المبرمجون عادة إلى إدراج حلقة "في حين While " مع علامة أكبر أو أصغر لتجنب هذه النتيجة، وبذلك يتمكن البرنامج من إيجاد حلول مغايرة، فتعاد العملية مرة أخرى بالنتيجة الجديدة، وبذلك يصبح تكرارا داخل التكرار!!. وبالتالي هي طريقة مضنية وتستغرق وقت في انتظار النتائج.

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

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

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

وقد أطلق غلوفر على هذه الخوارزمية اسم البحث المحظور أو بحث الطابو Tabu search في مقال له بعنوان "المسارات المستقبلية من أجل برمجة صحيحة ووصلات إلى الذكاء الاصطناعي"، الذي نُشر في دورية "حواسيب وبحوث العمليات" في عددها الثالث عشر عام 1986، الجزء الخامس منه، صفحة 533-549. تسمية الطابو جاءت هنا لتعني الشيء الممنوع، المأخوذة عن اللغة البولينيزية المستخدمة قديما عند سكان جزر بولينيزيا الفرنسية، والتي يقصد بها آنذاك الأشياء المقدسة أو المخيفة التي لا يمكن الاقتراب منها أو الوصول إليها.

مراجع:

1. Han. S, Li. J and Liu. Y : "Tabu search algorithm optimized ANN model for wind power prediction with NWP", Energy procedia 2011, 12: 733-740

2. Charon. I, Germa. A and Hudry. O : "Méthodes approchées définies par un voisinage" in Méthodes d’optimisation combinatoire, Paris : Masson, 1996, pp. 165-185.

3. Glover. F: "Future paths for integer programming and links to artificial intelligence", Computers & operations research 1986, 13 (5), pp. 533-549

#خالد_زيان (هاشتاغ)       Khaled_Ziane#          

---

ترجم الموضوع إلى لغات أخرى - Translate the topic into other languages

---

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

كيف تدعم-ين الحوار المتمدن واليسار والعلمانية على الانترنت؟

تابعونا على:

الفيسبوك

التويتر

اليوتيوب

RSS

الانستغرام

لينكدإن

تيلكرام

بنترست

تمبلر

بلوكر

فليبورد

الموبايل