خوارزمية محاكاة التلدين في الذكاء الاصطناعي Simulated Annealing: مقتبسة من المعادن!

هل فكرت يوميا من أين يأتي اسم خوارزميات الذكاء الاصطناعي؟ هل يأتيهم الهام بأسمائها؟ بعض أسماء الخوارزميات قد يكون مستلهما من الحياة الواقعية, مثل الخوارزمية التي سنخصص مقالنا للحديث عنها في الواقع لن تتوقع من أين أتى اسمها, نتحدث عن خوارزمية محاكاة التلدين Simulated Annealing, كما يشير اسمها فهي مستلهمة من عملية تلدين المعادن هذه العملية التي تحسن بنية وخصائص المعدن. ولكن ما علاقة خوارزمية محاكاة التلدين في الذكاء الاصطناعي وكيف تساهم في تحسين البحث لإيجاد أفضل الحلول وما مميزاتها, هذا ما سنعرفه في هذا المقال, اقرأ للنهاية.  

مفهوم خوارزمية محاكاة التلدين في الذكاء الاصطناعي

خوارزمية محاكاة التلدين هي خوارزمية تستخدم لتقريب القيم العليا والصغرى Global Optimization لوظيفة معينة في فضاء بحث واسع, مما يعني أنها تبحث عن حلا يكون مقبولا على مستوى النظام ككل، بدلا من التمركز على نقاط محلية فقط. 

تهدف الى إيجاد أفضل الحلول للمشكلات Optimization Problem عندما يكون إيجاد الحلول المثالية مكلفا حسابيا أو شبه مستحيل, فهي تعتبر الخوارزمية الأفضل عندما يأتي الأمر لإيجاد الحلول  العليا والدنيا للمشاكل. [1]

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

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

يتم تقييم كل حل بناء على درجة مختلفة، ويكمن هدف الخوارزمية في العثور على أفضل درجة أداء على مدى مراحل البحث. 

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

كيف تعمل الخوارزمية؟

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

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

لتوضيح ذلك أكثر, نبدأ باقتراح حل أولي نعبر عنه ب S0 ودرجة حرارة أولية t0، يتم اختيار الحل عشوائيا بشرط أن يتناسب مع معايير الحل المقبولة, ثم نختار قاعدة خفض درجة الحرارة المناسبة، وهي ثلاثة أنواع رئيسية: 

1. قاعدة الاختزال الخطي: 𝞪 - t = t.

2. قاعدة الاختزال الهندسي: 𝞪 * t = t

3. قاعدة الإنقاص البطيء: t = t / 1 + 𝞫t

تقل درجة الحرارة بمعدل مختلف بناء على هذه القواعد, وكل نموذج مختلف يستخدم قاعدة معينة من هذه القواعد تكون هي الأفضل في تحسينه, بالنسبة للقاعدة الثالثة يعتبر بيتا ثابتا.

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

تكرر هذه العملية عددا من المرات مع تخفيض درجات الحرارة بناء على الألفا, ولكن متى تتوقف الخوارزمية؟ تتوقف إما عند الوصول الى درجة حرارة محددة أو عند تحقيق الأداء المطلوب لعدد محدد من المعاملات Parameters.

تطبيقات خوارزمية محاكاة التلدين في الذكاء الاصطناعي

تم تطبيق خوارزمية محاكاة التلدين بنجاح على مجموعة واسعة من مشاكل البحث عن الحلول المثلى ومن بين هذه المشاكل: [3]

• مشكلة البائع المتجول TSP

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

• مشكلة توزيع المركبات VRP

تستخدم في حل مشكلة توزيع المركبات، حيث تسعى إلى تحسين جداول التوزيع لتقليل التكاليف وتحسين كفاءة استخدام المركبات.

• مشكلات الجدولة Scheduling Problems

 يمكن استخدامها في حل مشاكل الجدولة، مثل تحسين جداول الإنتاج أو جداول الزمن لتحقيق تسلسل أمثل للأحداث أو المهام.

إيجابياتها و سلبياتها 

في هذا القسم سنسلط الضوء على بعض من إيجابيات وسلبيات هذه الخوارزمية:[4]

• إيجابيات 

1. يمكنها التعامل مع أنظمة معقدة ووظائف تكلفة متغيرة بشكل عشوائي, أي أنها تستطيع أن تتكيف مع التقلبات والتغيرات في الظروف
2. يمكن الاعتماد عليها كليا للوصول الى الحل الأمثل للمشكلة المعنية بناء على الإحصائيات والتحليل
3. سهلة نسبيا, أي لا تتطلب الى مستوى عالي من البرمجة حتى في حالة المشاكل الكبيرة
4. توفر حلا جيدا للمشاكل وغالبا ما تكون النتائج مرضية تلبي الاحتياجات المطلوبة

• سلبيات

1. قد تكون خوارزمية محاكاة التلدين  زيادة غير ضرورية أو فائضة لحل المشاكل التي تتميز بطبيعة الطاقة السلسة أو وجود قليل من القيم الدنيا المحلية 
2.  استخدام هذه الخوارزمية بشكل متكرر مع جدول زمني يتناسب عكسيا مع اللوغاريتم 1/log(k يكون بطيء للغاية، خاصة إذا كانت وظيفة التكلفة صعبة التحسين أو تتطلب جهدا كبيرا للحوسبة

الخاتمة

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

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

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

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

المصادر

1. AI | Search Algorithms | Simulated Annealing | Codecademy
2. Understanding Simulated Annealing in Artificial Intelligence: Key Concepts Explained
3. Simulated Annealing | Saturn Cloud
4. Simulated Annealing. The well-known optimisation technique. | by Sanket Kotkar | Analytics Vidhya | Medium