ح3: أَمثلة أسراب الطيور( العناصر) particle swarm optimization PSO – الخوارزمية

ملاحظة : الموضوع عبارة عن حلقة من حلقات سلسلة َأمثلة اسراب الطيور -(العناصر) Particle swarm optimization PSO

تتضمن هذه الحلقة شرح خوارزمية PSO

أمثلة اسراب العناصر particle swarm optimization PSO

في البداية سنبدأ بتعداد وذكر بعض النقاط التعريفية عن PSO

  • عبارة عن تجمع population  ويعتمد هذا التجمع في سلوكه بشكل اساسي على تقنيات الأمثلة المعتمدة على الاحصاء .
  • التجمع بدوره عبارة عن مجموعة من العناصر , التي تمثل – ضمن اي نظام يستخدم الخوارزمية – مجموعة من الحلول,وسندعو كل عنصر ب particle.   واذا ما رغبنا باسقاط الموضوع على الحياة الاجتماعية للحيوانات والطيور- كما وضحناها في الحلقة السابقة – فإن العنصر عندها سيمثل طائر … نحلة …أو نملة.
  • تم تطويرها هذا النموذج من قبل الدكتور Dr.Eberhart  و Dr.Kennedy  في عام 1995 , وهذا النموذج مستوحى من السلوك الاجتماعي لاسراب الطيور أو جماعات الأسماك أثناء تنقلها من مكان لآخر.
  • يوجد العديد من نقاط التشابه بين PSO وتقنيات الحوسبة التطورية الآخرى evolutionary computation techniques, على سبيل المثال “الخوارزميات الجينية Genetic Algorithm GA.

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

فعليا , ضمن خوارزمية PSO يتم البحث عن الحل الامثل عبر تتبع واتباع العناصر particles  الحالية الأفضل- بشكل مشابه لسلوكيات النحل والنمل على سبيل المثال.

على كل الاحوال , وبشكل مغاير للخوارزميات الجينية GA, فإن PSO لا تملك أدوات تطورية مثل التصالب crossover  والطفرة mutation .

 بمقارنة خوارزمية PSO مع الخوارزميات الجينية GA  فإن خوارزمية PSO تتميز بأنها

  • سهلة التطبيق والتنفيذ.
  • هنالك فقط عدد بسيط من المعاملات parameters ضمن الخوارزمية تحتاج إلى تهيئة وضبط.

وضمن الواقع العملي , فقد تم تطبيق PSO بنجاح في عدة مجالات (وقد ذكرناها بالتفصيل في الحلقة السابقة ) ومنها:

  1. أمثلة التوابع function optimization
  2. تدريب الشبكات العصبونية الصنعية artificial neural network training
  3. التحكم بالنظم الضبابية fuzzy system control
  4. وضمن العديد من المجالات التي تستخدم فيها ايضا الخوارزميات الجينية GA.

ضمن هذه الحلقة وما يليها من الحلقات سنتحدث عن الامور التالية:

  1. مقدمة بسيطة ولمحة عن الحياة الصنعية artificial life
  2. شرح الخوارزمية
  3. مقارنة بين الخوارزميات الجينية GA  وبين خوارزمية PSO
  4. الشبكات العصبونية الصنعية وخوارزمية PSO
  5. التحكم بمعاملاتparameters  خوارزمية PSO
  6. المصادر الموجودة على الانترنت

لمحة ومقدمة عن الحياة الصنعية Artificial life

إن عبارة “الحياة الصنعية” “Artificial life” – يشار لها عادة ب ALife – تستخدم لتوصيف البحوث التي تقوم على دراسة النظم التي من صنع الإنسان, والتي تملك بعض من الخصائص الأساسية للحياة.

 تتضمن ALife بحثين اساسيين :

  1. دراسات ALife ,والتي تهتم بتقنيات الحوسبة وكيف بإمكانها ان تخدم وتساعد في دراسة الظواهر البيولوجية.
  2. دراسات ALife , والتي تدرس التقنيات البيولوجية , وكيف بإمكانها ان تساعد في حل المسائل الحسابية .

سيتم التركيز ضمن هذا المقال على البحث الثاني.

فعليا , هنالك الكثير من التقنيات الحسابية المستوحاة من النظم البيولوجية. على سبيل المثال:

  1. الشبكات العصبونية الصنعية artificial neural network عبارة عن نموذج مبسط لدماغ الإنسان.
  2. والخوارزميات الجينية genetic algorithm  مستوحاة من تطورا لإنسان.

 

سنناقش هنا نمط اخر من النظم البيولوجية – النظم الاجتماعية social systems – وبشكل خاص , السلوك التعاوني للأفراد أثناء تفاعلهم مع بيئتهم ومع بعضهم البعض.

وقد دعا احدهم هذه الدراسة ب”ذكاء السرب ” Swarm Intelligence.

وقد جرت العديد من محاولات محاكاة هذه السلوكيات الاجتماعية ونمذجتها. واحد اشهر الامثلة على هذه المحاكيات هي التالية:

  1. floys
  2. boids

كلا “المحاكيين ” تم انشائهما لتفسير الحركة المنظمة لاسراب الطيور , او لتجمعات السمك.

وتم استخدام هذين المحاكيين ضمن الرسوميات المتحركة في الكمبيوتر وغير ذلك من المجالات.

بشكل عام هنالك سلوكين من سلوكيات الاسراب اوحت الكثير لمجال الحسابات الذكية في عالم الكمبيوتر,الا وهما:

  • امثلة مستعمرات النمل Ant colony optimization(ACO)
  • امثلة اسراب  العناصر Particle swarm optimization (PSO)

الخوارزمية The Algorithm

كما ذكرنا سابقاً, فإن خوارزمية PSO تقوم على محاكاة سلوك اسراب الطيور.

لنفترض السيناريو التالي:

لدينا مجموعة من الطيور التي تبحث بشكل عشوائي عن الطعام ضمن منطقة ما.

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

في البداية , كل الطيور تجهل مكان قطعة الطعام. ولكنها تعلم كم يبعد الطعام عنها بعد كل جولةiteration .

إذن : ماهي الاستراتيجية المثلى لايجاد الطعام؟

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

تعلمت خوارزمية PSO من السيناريو السابق, واستخدمته لحل مسائل الامثلة Optimization problems .

ضمن PSO , كل حل مفرد عبارة عن “طير” bird ضمن فضاء الحلول.وسندعوه بعنصر “particle“.

لكل عنصر من العناصر قيمة ملائمة fitness value ,- اي تدل على مدى ملائمة هذا الجزء للحل-, ويتم تقييم قيم الملائمة هذه عبر تابع يدعى بتابع الملائمة fitness function . التقييم هنا يهدف إلى حساب مقدار قرب هذا الجزيء من الحل الامثل.

وكذلك تملك العناصر سرعات  velocities, وتقود هذه السرعات بدورها هذه العناصر الطائرة.

تطير العناصر ضمن فضاء المسألة عبر اتباع العناصر الأفضل لحد الآن.

يتم تهيئة خوارزمية PSO بمجموعة من العناصر العشوائية (حلول), ومن ثم يتم البحث عن الحل الأفضل عبر تحديث هذه الأجيال.

ضمن كل جولة – دورة Iteration – , يتم تحديث كل عنصر من العناصر ضمن التجمع عبر اتباع القيم الفضلى التالية:

pbest” : وتمثل أفضل قيمة ملائمة التي وصل لها العنصر i لحد هذه اللحظة

gbest” : وتمثل افضل قيمة ملائمة ضمن السرب , اي افضل عنصر ضمن السرب كله.

“lbest” : عندما ياخذ عنصر ضمن السرب موقعه ضمن التجمع , وكما هو الحال بالنسبة لجيرانه, عندها فإن أفضل قيمة ضمن هذا التجمع الجزئي تمثل أفضل قيمة محلية وتدعى lbest.

بعد ايجاد القيم الافضل best values  , تعدل العناصر من سرعتها ومواضعها وفق المعادلتين a  و b.

v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[]) (a)
present[] = persent[] + v[] (b)

حيث أن v[] : تمثل سرعة العنصر particle velocity.

persent[] : يمثل وضعية العنصر i في اللحظة k

pbest[]  : تمثل افضل وضعية للعنصر الحالي من السرب.

 gbest[] : تمثل افضل وضعية  ضمن السرب كله.

rand () : عدد عشوائي يقع ضمن المجال (0,1)

c1, c2  : معاملات التسارع  , وعادة ما تحمل القيم c1 = c2 = 2.

وبالتالي , وكما نلاحظ من المعادلات مايلي :

ضمن المعادلة الأولى : تتأثر السرعة الناتجة عن المعادلة الاولى بثلاث عوامل وهي :

  1. السرعة في اللحظة السابقة
  2. افضل وضعية قد مر بها العنصر على الاطلاق
  3. افضل وضعية على مستوى السرب ككل.

ضمن المعادلة الثانية : إن كل عنصر ضمن السرب سيغير موضعه إلى موضع جديد , هذا التغير مرتبط بشكل وثيق بالسرعة.

المخطط البياني التالي يبين الية انتقال العنصر ضمن السرب

باختصار : إن خوارزمية PSO تتالف من ثلاث خطوات تتكرر حتى ينتهي الحد الأعلى للتكرارات , او تتحقق أحد شروط التوقف:

  • حساب قيمة الملائمة لكل عنصر من العناصر ضمن السرب
  • تحديث قيم الملائمة pBest لكل عنصر , وكذلك تحديث أفضل قيمة ملائمة عامة gBest
  • تحديث سرعة وموضع كل عنصر ضن السرب

الكود الرمزي التالي يمثل الاجرائية التي تعمل بها الخوارزمية :

حلقة 1: من اجل كل عنصر كرر

  1. هيأ العنصر

نهاية حلقة 1.

كرر  من اجل كل عنصر 2:

  1. حساب قيمة الملائمة
  2. في حال كانت قيمة الملائمة المحسوبة أفضل من “افضل قيمة ملائمة للعنصر  pBest ” وذلك ضمن القيم المخزنة في تاريخ العنصر , عندها (اي في حال تحقق الشرط), اسند قيمة الملائمة الحالية إلى pBest لتصبح افضل قيمة ملائمة للعنصر.

نهاية حلقة2.

يتم تحديد العنصر صاحب أفضل قيمة ملائمة وذلك بالنسبة لكل العناصر , ويتم اسناده ليكون gBest

كرر من اجل كل العناصر 3:

  1. يتم حساب سرعة العنصر وفق المعادلة a
  2. يتم تحديث موقع العنصر وذلك وفق المعادلة b

نهاية تكرار  3:

يتم اجراء الخطوات التالية بشكل متكرر حتى يتحقق الحد الاعلى من التكرارات – المحدد ضمن ترميز الخوارزمية –أو ان تتحقق شروط التوقف

وبذلك يتم الحصول على الحل الافضل

Pseudocode for PSO

إلى هنا تنتهي حلقة هذا اليوم , لنلتقي بالحلقة القادمة حيث نناقش ونطرح بقية البنود التي تم طرحها في بداية هذه الحلقة وللتذكير سندرجها مرة ثانية:

  1. مقدمة بسيطة ولمحة عن الحياة الصنعية artificial life
  2. شرح الخوارزمية
  3. مقارنة بين الخوارزميات الجينية GA  وبين خوارزمية PSO
  4. الشبكات العصبونية الصنعية وخوارزمية PSO
  5. التحكم بمعاملاتparameters  خوارزمية PSO
  6. المصادر الموجودة على الانترنت

لتنابع في الحلقة القادمة انطلاقا من البند الثالث “ المقارنة مع الخوارزميات الجينية

وإلى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

 بعض المراجع التي تمت الاستفادة منها:

Advertisements

, , , , , , , , , , , , ,

  1. #1 by NeRmeen Nasser on يناير 28, 2013 - 11:47 ص

    EXTRA thx ^^

  2. #2 by Nuha Elamin on يوليو 19, 2017 - 3:59 ص

    شرح مفيد وسلس
    المعادلة(b) لتحديد موقع العنصر لم تذكر اعتقد هي

    x[i] = x[i] + v[i] ……………………b

    حيث:
    الموضع الجديد للعنصر يحسب بدلالة الموقع السابق زائد سرعة العنصر التي تم حسابها في المعادلة الاولى

    • #3 by schwarztiger on يوليو 19, 2017 - 7:57 ص

      مشكورة, ويسعدها استفادتك من الدرس
      وعلى فكرة, تم ذكر المعادلة ضمن فقرة
      “إذن : ماهي الاستراتيجية المثلى لايجاد الطعام؟”
      حيث تم ادراجها مع غيرها من المعادلات بالشكل التالي:
      v[] = v[] + c1 * rand() * (pbest[] – present[]) + c2 * rand() * (gbest[] – present[]) (a)
      present[] = persent[] + v[] (b)
      مع الشرح المفصل لكل عنصر ضمن المعادلات
      😉

اترك رد

Please log in using one of these methods to post your comment:

WordPress.com Logo

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   / تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   / تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   / تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   / تغيير )

Connecting to %s

%d مدونون معجبون بهذه: