Posts Tagged Artificial Intelligence

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

facebook-group

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

 التحكم بمعاملات خوارزمية PSObees

نجد من الحلقات السابقة , وبعد الاطلاع على آلية عمل خوارزمية أمثلة اسراب العناصر (الطيور) نجد بأن هنالك مفتاحان أساسيان  ومهمان أثناء تطبيق خوارزمية PSO في مجال مسائل الأمثلة ألا وهما:

  1. طريقة تمثيل الحل representation of the solution
  2. طريقة صياغة تابع الملائمة fitness function

من أحد مزايا خوارزمية PSO بأن هذه الخوارزمية تتخذ الاعداد الحقيقية على انها العناصر. وهذا لا يشبه الخوارزميات الجينية GA , والتي تحتاج إلى التحول إلى الترميز الثنائي binary encoding, أو إلى استخدام المعاملات الجينية genetic operators.

على سبيل المثال : عندما نحاول البحث عن الحل للمسألة f(x) = x1^2 + x2^2+x3^2  , فإنه يمكن تمثيل العنصر على الشكل (x1, x2, x3) , وتابع الملائمة يكون بدوره عبارة عن f(x).  وبعد ذلك نقوم باستخدام الاجرائية المعيارية لايجاد الحل الامثل. وتكون عملية البحث عن الحل الامثل عبارة عن اجرائية متكررة,  ويتم التوقف في احد حالتين :

  1. عند الوصول إلى الحد الأعلى من التكرارات المسموح بها
  2. أو في حال وصلنا إلى تحقق شرط قيمة الخطأ الادنى المسموح به – وبذلك نكون قد اقتربنا من الحل الامثل.

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

عدد العناصر The number of partcles : العدد النموذجي يتراوح بين 20 – 40 عنصر. بشكل فعلي بالنسبة لأغلب المسائل فإن 10 عناصر عبارة عن عدد كافي لإيجاد نتائج جيدة. ولكن بالنسبة لبعض المسائل المختلفة أو ذات الحالات الخاصة , قد نحتاج لتجريب استخدام 100 او 200 عنصر لايجاد حل جيد.

أبعاد العناصر Dimension of particles : يتم تحديدها بحسب المسألة التي من المطلوب ايجاد حل امثل لها .

مجال العناصر Range of particles : يتم تحديده بحسب المسألة التي من المطلوب ايجاد حل امثل لها , بإمكانك تحديد مجالات مختلفة بحسب ابعاد العناصر. ( للتوضيح اكثر : مقصود بمجال العنصر أي مجال القيم التي من الممكن ان يتخذها العنصر خلال تغير قيمه اثناء دورات الخوارزمية).

Vmax : وتحدد الحد الأعلى للتغيرات التي يمكن ان تطرأ على عنصر خلال دورة واحدة. عادة ما نقوم بوضع مجال العنصر range of the particle  بشكل مماثل ل Vmax , على سبيل المثال : عندما يكون العنصر (x1, x2, x3) و X1 ينتمي إلى المجال [-10, 10]عندها فإن Vmax = 20.

عوامل التعلم Learning factors :  عادة ما تكون قيم c1 و c2 مساوية ل 2. على كل الأحوال,تم استخدام اعدادات اخرى ضمن عدة بحوث. ولكن عادة ما يتم اسناد قيم c1  و c2  إلى القيم ضمن المجال [0, 4].

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

النسخة العامة إزاء النسخة المحلية Global version vs.local version : لقد قدمنا وطرحنا نسختين من خوارزمية PSO. النسخة العامة و النسخة المحلية.

تعتبر النسخة العامةglobal version  اسرع ولكنها قد تأخذنا إلى نهاية محلية صغرى بالنسبة لبعض المسائل.

أما النسخة المحلية local version  ابطىء قليلا , ولكنها ليس من السهل ان تقع ضمن فخ النهاية المحلية الصغرى.

بإمكاننا استخدام النسخة العامة global version  للحصول على نتائج سريعة, واستخدام النسخة المحلية local version  لتشذيب نتائج البحث.

Global optimum and local optimum

Global optimum and local optimum

هنالك عامل اخر يدعى وزن القصور الذاتي inertia weight, الذي تم طرحه من قبل Shi و Eberhart. في حال كان يهمكم الاطلاع اكثر على هذا العامل بإمكانكم الاطلاع على البحث الذي قاما بنشره عام 1998.(عنوانه : A modified particle swarm optimizer)

في الختام:

لا تزال عملية تطوير خوارزمية PSO جارية لحد الآن. ولا تزال هنالك العديد من المجالات المجهولة لحد الآن في بحوث  PSO مثل “التحقق الرياضي من نظرية اسراب العناصر”.

ولكن بإمكانكم ايجاد الكثير من المعلومات المفيدة المتعلقة بهذه النظرية على الانترنت.

وإلى لقاء قادم مع خوارزمية أخرى من خوارزميات الذكاء الصنعي.

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

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

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

3 تعليقات

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

facebook-group

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

مقارنة خوارزمية PSO مع الخوارزميات الجينية GA

تمتلك معظم التقنيات التطويرية الاجرائيات التالية :

  1. التوليد العشوائي للتجمع الأولي initial population
  2. حساب قيمة الملائمة fitness value  لكل عنصر. والتي تعتمد بشكل مباشر على البعد عن القيمة المثلى.
  3. انتاج التجمع اعتمادا على قيم الملائمة.
  4. في حال تحقق المتطلبات , عندها يتم التوقف , وإلا نعود للخطوة رقم 2.

من الاجرائية المذكورة انفاً, نجد بأن خوارزمية PSO تتشارك بعدد من النقاط المشتركة مع خوارزمية GA.

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

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

 تقوم العناصر particles  ضمن خوارزمية PSO بتحديث انفسها عبر الاستفادة من قيمة السرعة الداخلية. ايضا تمتلك العناصر ذاكرة, والتي تعتبر عنصر مهم ضمن الخوارزمية.

بمقارنة خوارزمية PSO مع الخوارزميات الجينية GAs , فإن الإلية التي تتم بها معالجة المعلومات مختلفة بشكل كبير ضمن خوارزمية PSO.

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

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

وبمقارنة PSO مع الخوارزميات الجينية GA , فإن كل العناصر ضمن خوارزمية PSO تميل لتتقارب باتجاه الحل الافضل بشكل سريع , حتى ضمن التجمعات المحلية الصغيرة (في معظم الأحيان).

عند هذه النقطة نكون قد انتهينا من هذه المقارنة المختصرة لخوارزميتنا مع الخوارزميات الجينية  وسوف تنابع في الحلقة القادمة ببحث صغير ومختصر حول  ” التحكم بمعاملات خوارزمية PSO

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

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

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

أضف تعليقاً

ح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. المصادر الموجودة على الانترنت

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

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

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

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

تعليق واحد

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

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

السلام عليكم ورحمة الله وبركاته

ارجو ألا اكون قد اطلت عليكم كثيرا

سنتناول في هذه الحلقة عدد من تطبيقات خوارزمية “أَمثلة اسراب العناصر” Particle Swarm Optimization PSO ,

وذلك على خلاف التسلسل المتبع في العادة , حيث في معظم الأحيان يتم شرح وتعداد تطبيقات اي خوارزمية في نهاية شرح الخوارزمية , ولكن هنا رغبت ان اقوم بعكس ذلك “ذكر التطبيقات قبل شرح الخوارزمية ” وذلك بهدف تبيان أهمية الخوارزمية ,والطيف الواسع من التطبيقات المتنوعة الذي تشمله.

فيما يلي تعداد وشرح بسيط لعدد من التطبيقات التي تعتمد على خوارزمية PSO:

التطبيقات باختصار

  1. الهوائي “الانتين” Antennas
  2. مجال الطب الحيوي – المجال البيولوجي -  Biomedical
  3. شبكات الاتصالات Communication Networks
  4. التجميع والتصنيف Clustering and Classification
  5. الأمثلة التوافقية Combinatorial optimization
  6. التحكم Control
  7. التصميم Design
  8. شبكات التوزيع Distribution networks
  9. الالكترونيات والكهرومغناطيسية  Electronics and Electromagnetics
  10. المحركات Engines and Motors
  11. الألعاب والترفيه Entertainment
  12. الأخطاء Faults
  13. المجال المالي Financial
  14. المجال العائم , والعصبي – العائم Fuzzy and Neuro-fuzzy
  15. الرسوميات والاظهار Graphic and Visualization
  16. الصور والفيديو Image and Video
  17. التعدين Metallurgy
  18. النمذجة Modeling
  19. الشبكات العصبونية neural networks
  20. التنبوء والتوقع Prediction and forecasting
  21. نظم ومحطات الطاقة Power systems and plants
  22. الروبوتات Robotics
  23. الجدولة Scheduling
  24. المجالات الأمنية والعسكرية Security and Military
  25. شبكات الاستشعار Sensor Networks
  26. معالجة الاشارة Signal Processing

 

تفصيل مجالات التطبيقات السابقة التي تستخدم خوارزمية PSO:

الهوائي “الانتين” Antennas

هنالك عدد هائل من تطبيقات تصميم الهوائي antenna design التي تعتمد على خوارزمية PSO .

تتضمن هذه التطبيقات :

1.            التحكم الأمثل Optimal Control
2.            التصميم الأمثل للهوائي (من مختف النواحي ) Optimal Design
3.            التصميم الأمثل لصفائح الهوائيات Antenna arrays design
4.            تصميم الهوائيات بمختلف انواعها : تصميم الهوائيات المستوية , تصميم هوائيات التصحيح, تصميم الهوائيات الصغيرة جدا, تصميم الهوائيات ذات الحزم المتعددة , تصميم الهوائيات العاكسة , تصميم الصفائح المتكيفة للهوائيات

مجال الطب الحيوي – المجال البيولوجي -  Biomedical

تستخدم هذه الخوارزمية في تطبيقات تمتد على مجال واسع ضمن المجال الطبي والبيولوجي وفي مجال الصيدلة.

تتضمن التطبيقات :

1.            تحليل رعاش الإنسان من أجل تشخيص مرض الشلل الرعاشي – باركنسون Parkinson’s disease
2.            تصنيف السرطان cancer classification
3.            أمثلة الحركة الميكانيكية الحيوية للإنسان human movement biomechanics
4.            التنبوء بالبقاء على قيد الحياة والنجاة Survival prediction
5.            تجمع الجينات gene clustering
6.            تحديد عوامل النسخ ضمن الحمض النوويDNA  .  identification of transcription factor binding sites in DNA
7.            اختيار العلامات البيولوجية biomarker selection
8.            التنبوء ببنية البروتين protein structure prediction
9.            تصميم الأدوية Drug design
10.          التنبوء ببنية البروتين  protein structure prediction
11.          تحيليل البيانات المغناطيسة للدماغ analysis of brain magnetoencephalography data
12.          تحديد البنية الثانوية ل RNA
13.          التحليل الكهربائي  electroencephalogram analysis
14.          القياسات الحيوية – البيولوجية biometrics

شبكات الاتصالات Communication Networks

للخوارزمية تطبيقات كثيرة في مجال أَمثلة شبكات الاتصالات.

تتضمن التطبيقات :

  1. شبكات البلوتوث Bluetooth networks
  2. الضبط التلقائي لشبكات نظام الاتصالات المتنقلة العالمية auto-tuning for universal mobile telecommunication system networks
  3. التوضع الأمثل لمعدات شبكات الاتصالات المتنقلة optimal equipment placement in mobile communication
  4. التوجيه routing
  5. شبكات الرادار radar networks
  6. شبكات peer to peer
  7. التحكم بشبكات TCP
  8. شبكات الاتصال عن بعد
  9. الشبكات اللاسلكية wireless networks
  10. حجز عرض الحزمة- النطاق  bandwidth reservation

 التجميع والتصنيف Clustering and Classification

هنالك كم جيد من تطبيقات التجميع clustering  والتصنيف classification  , بالاضافة إلى التنقيب عن المعلومات data mining  التي تعتمد على خوارزمية PCA.

تتضمن التطبيقات:

1.            التجميع clustering
2.            التجميع ضمن قواعد المعطيات الضخمة
3.            التجميع الديناميكي dynamic clustering
4.            تقليص الأبعاد dimensionality reduction
5.            التصنيف المعتمد على البرمجة الجينية  genetic-programming-based classification
6.            التجميع العائم fuzzy clustering
7.            التصنيف الهرمي للبيانات البيولوجية  classification of hierarchical biological data
8.            تصنيف نوع الرقاقات الكهربائية electrical wafer sort classification
9.            تجميع المعلومات والوثائق document and information clustering
10.          التنقيب عن المعلومات data mining
11.          اختيار الملامح والميزات الاساسية feature selection

الأمثلة التوافقية  Combinatorial optimization

تتضمن التطبيقات التالية:

1.            التخطيط الطابقي floor planning
2.            مسألة البائع المتجول travelling-sales man problems
3.            مسألة السارق والحقيبة packing and knapsack
4.            مسائل الحصول على الطريق الأمثل path optimization
5.            knights cover problem
6.            مسألة توضع N ملكة n-queens problem
7.            مسائل التوضع الأمثل layout optimization
8.            مسألة توجيه العربة vehicle routing
9.            تخطيط المدن urban planning

التحكم Control

تمثل تطبيقات التحكم أحد القطاعات الأكثر استثمارا وتطبيقا لخوارزمية PSO.

تتضمن التطبيقات:

1.            توليد آليات التحكم الآلي
2.            تصميم وحدات التحكم  design of controllers
3.            التحكم ومراقبة تدفق حركة المرور traffic flow control
4.            التحكم التنبؤي  predictive control
5.            PI and PID controllers
6.            التحكم بالمحركات عبر الأمواج فوق صوتية  ultrasonic motor control
7.            التحكم بالانظمة ومحطات الطاقة power plants and systems control
8.            التحكم بنظم الفوضى control of chaotic systems
9.            التحكم بالاجرائيات process control
10.          التحكم بالاحتراق combustion control
11.          التحكم بالهبوط الآلي  automatic landing control

التصميم Design

تتضمن تطبيقات التصميم ما يلي :

1.            التصميم المفاهيمي conceptual design
2.            worst case electronic design
3.            تصميم الفلاتر filter design
4.            تصميم الهوائي antenna design
5.            تصميم مكبرات الصوت ذات النطاق العريض   CMOS wideband amplifier design
6.            تصميم المحركات  motor design
7.            تصميم الدارات المنطقية  logic circuits design
8.            تصميم نظم الطاقة power systems
9.            تصميم خطوط النقل transmission lines
10.          التصميم الميكانيكي mechanical design
11.          …

الشبكات المتوزعة Distribution networks

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

تتضمن التطبيقات :

1.            التخطيط لشبكات البث transmission network planning
2.            توسيع واعادة تعريف الشبكات  network reconfiguration and expansion
3.            الشبكات الميكروية micro-grids
4.            تنظيم الجهد voltage regulation
5.            ادارة الازدحام congestion management
6.            …

الالكترونيات والكهرومغناطيسية  Electronics and Electromagnetic

تتضمن التطبيقات:

1.            خلايا الوقود fuel cells
2.            متحكمات درجة الحرارة FPGA-based temperature control
3.            متحكمات نظم نقل التيار المتقطع  AC transmission system control
4.            مرشحات الميكرويف microwave filters
5.            تصميم وأمثلة RF IC  RF IC design & optimization
6.            أمثلة وتحسين اشباه الموصلات semiconductor optimization
7.            تصميم مكبرات الصوت amplifier design
8.            voltage flicker measurement
9.          تركيب الدارات circuit synthesis
10.          تصميم الدارات الالكترونية digital circuit design
11.          …

المحركات Engines and Motors

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

وتتضمن التطبيقات :

1.            تصنيف معطيات المحرك engine data classification
2.            التحكم بعزم دوران القاطرة
3.            التحكم بمحركات السيارات الكهربائية والهجينة motor control in electric and hybrid vehicles
4.            التحكم بسرعة المحركات
5.            التحكم المباشر بعزم دروان المحركات direct motor torque control
6.            تقدير الخطأ
7.            أمثلة الاحتراق الداخلي للمحركات optimization of internal combustion engines
8.            تحسين وأمثلة نظم الدفع الالكتروني النووي  optimization of nuclear electric propulsion systems
9.            …

الألعاب والترفيه Entertainment

إن لكل من الألعاب  وتوليد الموسيقى كان لها ايضا نصيب من التطبيقات التي تسخدم PSO.

في مجال الألعاب , يوجد التطبيقات التالية:

1.            مسألة السجين iterated prisoner dilemma
2.            تعلم العزف المنفرد   Pong
3.            …

أما في مجال الموسيقى :

فقد استخدمت خوازمية PSO في مجال ارتجال الموسيقى التفاعلية interactive music improvisation

 الأخطاء Faults

هنالك عدد من التطبيقات في مجال تشخيص واكتشاف الأخطاء ومحاولة معالجتها , استخدمت بدورها خوارزمية PSO وتتضمن ما يلي :

1.            تشخيص اخطاء مولدات التوربينات البخارية fault diagnosis of steam-turbine generators
2.            الدارات التي تسترد حالتها الأصلية بعد فشل أحد مكوناتها circuits that automatically recover from component failure
3.            التصنيف التلقائي للخطأ في رقائق أشباه الموصلات automatic defect classification in semiconductor wafers
4.            انظمة الطاقة المتسامحة بالنسبة للاخطاء fault-tolerant power systems
5.            استعادة الحساسات المفقودة  missing sensors restoration
6.            تشخيص الاخطاء في الدارات الرقمية fault diagnosis in digital circuits
7.            توليد نماذج اختبار الدارات test pattern generation for circuits
8.            اكتشاف اخطاء البرمجيات software fault detection
9.            تشخيص اخطاء محولات الطاقة power transformers fault diagnosis
10.          امثلة نظم الاصلاح optimization of repairable systems
11.          تشخيص اعطال المحركات diagnosis of faults in motors

المجال المالي Financial

هنالك عدد من التطبيقات المالية والاقتصادية التي تستخدم خوارزمية PSO وتتضمن ما يلي :

1.            نظم التحذيرات المبكرة للمخاطر المالية financial risk early warning
2.            نظم صنع قرار الاستثمار investment decision-making
3.            تسعير وتثمين الخيارات option pricing
4.            …

المجال العائم , والعصبي – العائم Fuzzy and Neuro-fuzzy

هنالك عدد من المسائل في المجال النظم الضبابية fuzzy systems  والنظم العصبية – الضبابية neuro-fuzzy systems والتحكم بها , قد استفادت من خوارزمية PSO في عدة مجالات تتضمن :

1.            تصميم الشبكات العصبية – الضبابية design of neuro-fuzzy networks
2.            استخراج القواعد الضبابية  fuzzy rule extraction
3.            نظم التحكم الضبابي  fuzzy control
4.            امثلة توابع العلاقات membership functions optimization
5.            النمذجة الضبابية fuzzy modeling
6.            التصنيف الضبابي fuzzy classification
7.            تصميم النظم الهرمية الضبابية design of hierarchical fuzzy systems
8.            ادارة قوائم الانتظار – الارتال – الضبابية fuzzy queue management
9.            …

الرسوميات والاظهار Graphic and Visualization

تتضمن التطبيقات :

1.            التمثيل البياني للشبكات  graphic presentation of networks
2.            تقليص الابعاد dimensionality reduction
3.            اكتشاف التصادم والتضارب في نماذج الرسومات البيانية collision detection in graphic models
4.            تركيب الانسجة texture synthesis
5.            التمثيل البياني التفاعلي لاسراب العناصر interactive particle swarms
6.            الرسومات البيانية ثلاثية الابعاد 3D graphics
7.            …

الصور والفيديو Image and Video

تتضمن تطبيقات الصور التي استخدمت خوازمية PSO ما يلي :

1.            التعرف على القزحية iris recognition
2.            تصنيف الفواكه بحسب جودتها لدرجات مختلفة fruit quality grading
3.            تحديد الوجه والتعرف عليه face detection and recognition
4.            تقسيم وتجزئة الصورة  image segmentation
5.        تحديد اماكن العلاج في صور الاشعة السينية لتقويم الاسنان locating treatment planning landmarks in orthodontic x-ray images
6.            تصنيف الصور image classification
7.            دمج الصور image fusion
8.        كشف الاخطاء defect detection
9.            استعادة الصور image retrieval
10.          اكتشاف الانسان ضمن صور الاشعة تحت الحمراء الملتقطة  human detection in infrared imagery
12.          تصنيف البكسلات pixel classification
13.          اكتشاف وتحديد الاغراض detection of objects
14.          كشف وتتبع المشاة  pedestrian detection and tracking
15.          تركيب النسيج texture synthesis
16.          مطابقة المشاهد scene matching
17.          تحسين التباين contrast enhancement
18.          التعرف على الحروف character recognition
19.          مطابقة الاشكال shape matching
20.          التخلص من الضوضاء في الصور image noise cancellation

أما تطبيقات الفيديو فتتضمن :

1.            امثلة ملفات الفيديو من نمط MPEG MPEG optimization
2.            تقدير الحركة motion estimation
3.            تتبع الاغراض object tracking
4.            تتبع وضعية الجسم body posture tracking\
5.            كشف حوادث المرور

التعدين Metallurgy

تتضمن التطبيقات ما يلي :

  1. تعظيم الاستفادة من عملية صناعة الصلب optimization of steel-making process
  2. النمذجة في عملية التلبيد modelling in sintering process

النمذجة Modeling

تتضمن التطبيقات :

  1. عكس النماذج الصوتية تحت الماء inversion of underwater acoustic models
  2. نمذجة موسيقا MIDI modeling MIDI music
  3. نماذج ارضاء العملاء customer satisfaction models
  4. نماذج الاحتكاك friction models
  5. ultra-wideband channel modeling
  6. chaotic time series modeling
  7. التعرف على نماذج ARMAX identifying ARMAX models
  8. تحديد النماذج اللاخطية nonlinear model identification
  9. التعرف على النظم اللاخطية nonlinear system identification
  10. اختيار النموذج model selection
  11. انظمة ومحطات الطاقة power plants and systems

 الشبكات العصبونية neural networks

تستخدم الشبكات العصبونية بالتشارك مع خوارزمية PSO في عديد من التطبيقات وتتضمن مايلي :

  1. عكس الشبكات العصبونية inversion of neural networks
  2. التحكم بالشبكات العصبونية فيما يخص الاجرائايت اللاخطية neural network control for nonlinear processes
  3.  شبكات الغاز العصبونية  neural gas networks
  4. تدريب الشبكات العصبونية ذات التغذية المتقدمة feedforward neural network training
  5. تصميم الشبكات العصبونية الدورية design of recurrent neural networks
  6. الشبكات العصبونية الخلوية cellular neural networks
  7. الشبكات العصبونية الموجية wavelet neural networks
  8. متحكمات الخلايا العصبية neuron controllers

التنبوء والتوقع Prediction and forecasting

تتضمن التطبيقات مايلي:

  1. التنبوء بجودة المياه وتصنيفها water quality prediction and classification
  2. النماذج البيئية  ecological models
  3. تنبوءات الارصاد الجوية meteorological predictions
  4. التنبوء بالحمل الكهربائي electric load forecasting
  5. التنبوء بالسلاسل الزمنية time series prediction
  6. التنبوء وتوقع هجرات الفيلة predictions of elephant migrations
  7. التنبوء بمدى خشونة السطح المطحون في نهاية الطحن   prediction of surface roughness in end milling
  8. توقعات تدفق المياه الجارية stream-flow forecast
  9. التنبوء بتدفق حركة السير في الأماكن المدنية urban traffic flow forecasting

نظم ومحطات الطاقة Power systems and plants

هنالك عدد من التطبيقات التي تتعامل مع توليد الطاقة ونظم الطاقة التي تستخدم وتستفيد من خوارزمية PSO وتتضمن التطبيقات مايلي :

  1. حماية محولات الطاقة power transformer protection
  2. التنبوء بالحمل  load forecasting
  3. أمثلة وتحسين اداء نظم الطاقة power system performance optimization
  4. التحكم بالجهد الثانوي secondary voltage control
  5. التحكم بالطاقة وامثلتها  power control and optimization
  6. التحكم بالنظم الكهروضوئية   control of photovoltaic systems
  7. التحكم الواسع النطاق بمحطات الطاقة   large-scale power plant control
  8. تحليل جودة اشارات الطاقة analysis of power quality signals
  9. توليد المخططات واعادة الهيكلة generation planning and restructuring
  10. نظم توليد الطاقة الهجينة hybrid power generation systems
  11. الاستراتيجيات المثلى لتوليد الكهرباء  optimal strategies for electricity production
  12. تقليص خسارة الطاقة power loss minimization

الروبوتات Robotics

تتضمن التطبيقات مايلي :

  1. التحكم والتخطيط للحركة motion planning and control
  2. تشغيل الروبوتات robot running
  3. تعليم الروبوت بدون مشرف unsupervised robotic learning
  4. تخطيط المسار path planning
  5. تجنب العقبات , obstacle avoidance
  6. اسراب الروبوتات swarm robotics
  7. التحكم بملاحة المركبات الغير مأهولة unmanned vehicle navigation
  8. لعب كرة القدم soccer playing
  9. روبوتات النقل  transport robots
  10. معرفة مكان مصدر الرائحة odor source localization
  11. التحكم الصوتي للروبوتات voice control of robots

الجدولة Scheduling

تتضمن التطبيقات مايلي :

  1. جدولة التشغيل الامثل لمحطات الطاقة optimal operational planning of energy plants
  2. جدولة توليد الطاقة power generation scheduling
  3. جدولة المهام في نظم الكمبيوتر الموزعة tasks scheduling in distributed computer system
  1. جدولة المشاريع project scheduling
  2. جدولة القطارات train scheduling
  3. جدولة الجداول الزمنية timetable scheduling
  4. جدولة الانتاج production scheduling
  5. جدولة التصنيع manufacturing scheduling

المجالات الأمنية والعسكرية Security and Military

تتضمن التطبيقات مايلي :

  1. أمن الشبكات network security
  2. كشف التسلل intrusion detection
  3. الترميز وتفكيك الشفرات cryptography and cryptanalysis
  4. تحديد الحدود الأمنة في نظم الطاقة security border identification in power systems
  5. تحديد اهداف الاسلحة weapon-target assignment
  6. أمثلة وتحسين فعالية الصواريخ missile effectiveness optimization

شبكات الاستشعار Sensor Networks

تتضمن التطبيقات مايلي :

  1. تصميم شبكات الاستشعار اللاسلكية wireless sensor network design
  2. تحديد الموقع المستهدف في شبكات الاستشعار اللاسلكية  estimation of target position in wireless sensor networks
  3. تشكيل الكتل في شبكات الاستشعار اللاسلكية cluster formation in wireless sensor networks
  4. الارسال متعدد التوجيه في شبكات الاستشعار اللاسلكية  multicast routing in wireless sensor networks
  5. تحديد مصدر الرائحة odor source localization
  6. امثلة شبكات استشعار الفيديو اللاسلكية wireless video sensor networks optimization
  7. شبكات الاستشعار المتحركة المعتمدة على نظم الاسراب  swarm based mobile sensor networks
  8. جدولة الحساسات لتتبع الاهداف sensor scheduling for target tracking
  9. التوضع الانسب للحساسات المتوزعة والتخطيط الطبولوجي   distributed sensor placement and topology planning

معالجة الاشارة Signal Processing

تتضمن التطبيقات مايلي :

  1. التعرف على نماذج الاشارة المسطحة
  2. تصميم الفلاتر من نوع IIR design of IIR filters
  3. أمثلة فلاتر العناصر particle filter optimization
  4. المرشحات المتكيفة اللاخطية nonlinear adaptive filters
  1. صفائف كوستاك Costas arrays
  2. الامواج الصغرية wavelets
  3. الكشف والتحديد الاعمى blind detection
  4.  الفصل الأعمى للمصادر blind source separation
  5. ضبط وتوليف المرشحات التماثلية analogue filter tuning
  6. تحديد مواقع المصادر الصوتية localization of acoustic sources
  7. تحديد المصادر المتوزعة للرائحة distributed odor source localization
  8. ترميز الكلام speech coding

وبذلك نكون قد ذكرنا عدد لا بأس به من التطبيقات التي تستخدم خوارزمية PSO , لندرك بذلك اهمية هذه الخوارزمية المذهلة في معظم التطبيقات المتقدمة والذكية.

المرجع التالي يحوي بدوره إلى عدد كبير من المراجع يخص كل تطبيق من التطبيقات المذكورة سابقاً.

An Analysis of Publications on Particle Swarm Optimisation Applications

أمل ان تكونوا قد استفدتم.

سنتناول في الحلقة القادمة شرح للخوارزمية.

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

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

أضف تعليقاً

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

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

تحوي هذه الحلقة عن مقدمة وشرح عن الأسس الطبيعية التي انطلقت منها هذه الخوارزمية:

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

فظهرت ضمن هذا المجال عدد من الخوارزميات مثل

  • خوارزمية مثلة أسراب الطيور – العناصر   PSO Particle swarm optimization
  • خوارزمية أمثلة مستعمرات النمل  Ant colony optimization ACO

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

النحل:

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

bees looking for new nest

وهناك تتجمع النحلات حول الملكة ومن ثم ترسل الملكة مجموعة تتألف من حوالي 20-50  نحلة كشافة بهدف إيجاد أفضل وأقرب مكان مناسب للعش الجديد.

واختيار النحلات الكشافة ليس عشوائياً, بل تتمير بأنها تمثل النحلات الأكثر خبرة ضمن التجمع.

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

ولتخبر النحلات الكشافة صديقاتها ضمن التجمع عن المكان الذي اوجدته تستخدم رقصة – تشبه رقصة الاهتزاز- تحوي معلومات تمثل اتجاه وبعد المكان .

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

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

البحث عن بيت جديد قد يستغرق عدة ايام

وعندما تتفق جميع فرق الكشافة على المكان النهائي , فإن التجمع بأكمله يقلع ليرحل إلى الوجهة الهدف.

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

يتميز العش الجيد بعدد من المواصفات مثل :

  • ان يكون كبيراً بما فيه الكفاية ليستوعب السرب كله (حوالي 15 لتر من الحجم)
  • ان يكون محميا بشكل جيد من الاعداء
  • يؤمن كمية معينة من الدفء عبر اشعة الشمس
  • ان يكون بعيدا عن النحلات.

نلاحظ كيف ان سلوك النحل قد وفر الكثير من الجهد والوقت ووصل عبر الاجماع إلى قرار مثالي.

وقد تم استخدام ذكاء النحل في عدة خوارزميات مثل Bees algorithm  و  Swarming (honey bee)

النمل:

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

بإمكان مستعمرة النمل ايجاد أقرب مصدر للغذاء عن العش , وذلك دون امتلاك اي نملة بحد ذاتها اي معلومة عن مكان الطعام.

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

وبالتالي , فإن النملات اللاتي يرجعن أولا إلى العش فإنهن يكن مرشحات بشكل اكبر لأن يكن قد سلكن الطريق الأقصر. عندها فإن عددا اكبر من النملات سيتتبعن الطريق القصير, مما يعزز مادة “الفرمون” المفرزة .

وبهذه الطريقة يحل النمل عبر سلوكه الجماعي مسألة مهمة باستخدام هذا الاسلوب التطوري.

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

وقد تم استخدام ذكاء النمل في عدة خوارزميات مثل Ant colony, Ant colony optimization, Ant mill, Ant robotics, and Artificial Ants

نلاحظ مما سبق ذكاء كبير ضمن مثل هذه السلوكيات الجماعية التي غالبا ما ينتج عنها قرار حكيم وناحج.

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

ارجو ان تكونوا قد استفدتم عبر هذه المقطفات عن بعض السلوكيات الاجتماعية التي تعتبر المصدر الاساسي الذي استوحيت منه عدد من النظريات التطورية .

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

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

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

, , , , , , , , , ,

أضف تعليقاً

أمثلة أسراب الطيور( العناصر) particle swarm optimization PSO

أمثلة أسراب الطيور( العناصر) particle swarm optimization PSO

وهي احد الخوارزميات التي استوحيت من السلوكيات الاجتماعية الجماعية المتطورة لبعض الكائنات الحية مثل النمل والنحل.

وقد برهنت هذه الخوارزميات فعاليتها – كما هي في الطبيعة – وكان لها شق كبير من التطبيقات الرائعة والفعالة التي شملت شتى المجالات.

سنطرح ضمن سلسلة PSO عدد من الحلقات المترابطة التي تتحدث عن هذه الخوارزمية : اسسها – تطبيقاتها – شرحها …

تحوي سلسلة الحلقات القادمة ما يلي :

مع تمنياتي لكم بالتوفيق والاستفادة

, , , , , , , , ,

4 تعليقات

الخوارزميات الجينية (الحلقة 3 )

facebook-group

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

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

3: المكون الثالث يتجلى بالعمليات الجينية Genetic Operators

تنبع أهمية العمليات الجينية من إيجاد حلول لم تكن موجودة سابقاً في فضاء الحلول

ومن أهم العمليات الجينية :

-          التصالب crossover or recombination

-          الطفرة mutation

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

وكبداية , سنبدأ بشرح عملية التصالب أولاً crossover:وهي عملية منتجة , أي تنطلق من كروموزومين (صبغيين )–حلين – من الجيل الحالي – جيل الآباء – لتعطي بشكل عام حلين أبناء two offspring .

بينما الطفرة , هي عملية يتم فيها إجراء تبديل – تغيّر – على بعض جينات كروموزوم(صبغي ) ما .

ننوه هنا إلى أن نتجير كل من عمليتي التصالب crossover والطفرة mutation  تعتمد بشكل أساسي على أسلوب الترميز المستخدم للمسألة , وتتغير بتغيره ,ولتوضيح هذه الفكرة , سنذكر هنا بعض الأساليب الشهيرة في تنجيز الطفرة و التصالب, وذلك وفقاً لترميز محدد سابقاً

مثلاً في حال :

   1: الترميز الثنائي Binary Encoding

لدينا طيف واسع من أساليب التصالب crossover  الممكنة,نذكر منها :

   - التصالب بنقطة وحيدة Single point crossover

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

الرسم التوضيحي التالي يبين آلية العملية السابقة:

 

 

11001011+11011111 = 11001111

Chromosome parent A

11001011

Chromosome parent B

11011111

Offspring  C

11001111

Offspring  D

11011011

 

- التصالب وفق نقطتين Two point crossover

في البداية يتم اختيار نقطتي تصالب , حيث يتم هنا نسخ من بداية الكروموزوم (الصبغي ) لأول نقطة تصالب من أحد الوالدين للابن , ومن ثم الجزء من السلسلة الثنائية انطلاقاً من أول نقطة تصالب لثاني نقطة تصالب , يتم نسخها نسخها من الوالد الثاني , بينما بقية السلسلة الثنائية للابن الناتج يتم اخذها من الأب الأول وذلك من ثاني نقطة تصالب لنهاية الأب.

 إليكم الرسم التوضيحي التالي :

 
 

 

11001011 + 11011111 = 11011111

Chromosome parent A

11001011

Chromosome parent B

11011111

Offspring  C

11011111

Offspring  D

11001011

 

- Uniform crossover

ويتم في هذا النوع من التصالب اختيار بتات بشكل عشوائي ونسخها من الوالد الأول أو الوالد الثاني للأبن.

وربّ رسمة خيرُ من ألف جملة توضيحية :

11001011 + 11011101 = 11011111

Chromosome parent A

11001011

Chromosome parent B

11011101

Offspring  C

11011111

Offspring  D

11001001

 

-التصالب الحسابي Arithmetic crossover

وفي هذا النوع من التصالب يتم تنجيز بعض العمليات الحسابية وذلك لإنشاء أبناء جدد

11001011 + 11011111 = 11001001 (AND)

الطفرة Mutation

في حالة الترميز الثنائي , تكون الطفرة , ببساطة , ما هي إلا عملية عكس لأحد البتات في الكروموزم (الصبغي ), حيث يتم اختيار البت ثم قلبه

مثال توضيحي:

11001001 => 10001001

  2: ترميز التباديل Permutation Encoding

   - التصالب بنقطة وحيدة Single point crossover

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

والهدف من الإجراء السابق هو الحفاظ على مفهوم التباديل ,وعدم تكرار الرموز في السلسلة الجينية.

ملاحظة :

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

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

الطفرة Mutation

ويتم تنجيزها هنا ببساطة عبر تغير الترتيب في السلسلة الممثلة للكروموزوم , حيث يتم اختيار رمزين من الكروموزوم ويتم إجراء التبديل بينهما .

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

  3: ترميز القيمة Value Encoding

كل عمليات التصالب المتاحة في الخوارزميات الجينية يمكن تنجيزها هنا .

 

الطفرة Mutation

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

 

(1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)

 

2: ترميز الشجرة Tree Encoding

التصالب :

يتم اختيار نقطة تصالب من كلا الوالدين ,ويتم تقسيم كل من الوالدين عند نقطة التصالب المختارة , ومن ثم يتم تبادل الاجزاء تحت نقطة التصالب تلك بين الوالدين , لإنتاج ابنين جدد new offspring

الإجراء السابق موضح في الرسم التالي إدناه:

الطفرة Mutation

ويمكن تخيلها على انها تديل العمليات أو الأعداد أو … وذلك حسب المسألة المطروحة , أي باختصار العقد التي يتم اختيارها من الشجرة , يتم اجراء التبديل عليها .

 الانتقاء Selection

ومما اتضح لنا سابقاً من الخطوط العريضة التي تسير وفقها الخورزميات الجينية,فإن الكروموزومات (الصبغيات )  الآباء التي تخضع لعملية التصالب , يتم اختارها –انتقائها – وفق آلية محددة من التجمع الحالي .

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

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

عجلة الروليت Roulette wheel Selection  ,انتقاء بولتزمان Boltzman selection  , tournament selection  ,انتقاء الحالة المستقرة Steady state selection  …إلخ

سنورد فيمايلي شرح لطريقة عجلة الروليت في الانتقاء:

1-      اختيار عجلة الروليت Roulette Wheel Selection

يتم اختيار الوالدين في هذه الطريقة اعتماداً على قيم صلاحياتهم,فكلما ازدادت قيمة صلاحية الكروموزوم , كلما ازداد احتمال اختياره .

وحتى نتعرف لآلية عمل هذه الطريقة دعونا نتخيل أمامنا عجلة الروليت , بحيث تتوضع كل الكروموزومات الموجودة في التجمع فيها , ولكن وفق قطاعات تتناسب مع قيم صلاحياتها , حيث يحتل الكروموزوم ذو الصلاحية الأكبر ,القطاع الأكبر , وبتضح لنا ذلك من الصورة أدناه:

 ومن ثم يرمَ حجر المقامرة ضمن العجلة ,وحسب القطاع الذي سيقع فيه سيتم اختيار الكروموزوم الموافق,وبالتالي فإن الكروموزوم ذو القطاع الأكبر –الصلاحية الأكبر- سيكون عرضة للاختيار أكثر من مرة .

باختصار ,يمكننا تلخيص الاجرائية السابقة وفق الخوارزمية التالية:

1:(المجموع) حساب مجموع قيم صلاحية كل الكروموزومات الموجودة ضمن التجمع ولنرمز له ب S.

2: (الاختيار) توليد عدد عشوائي   rضمن المجال [0,S]

3: (حلقة)نمر بحلقة على الكروموزومات ضمن التجمع ونقوم بحساب مجموع قيم الصلاحيات أثناء هذا المرور, وعندما نصل لقيمة لهذا المجموع أكبر من r   عندها نتوقف , ونعيد الكروموزوم الذي وصلنا عنده وأدى لكسر الحلقة.

ملاحظة : بالطبع فإن الخطوة رقم 1  نتفذ مرة واحدة فقط من أجل كل تجمع.

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

وبهذا القدر سنكتفي هذا اليوم لنتابع معاً في الحلقة القادمة المزيد المزيد عن الخوارزميات الجينية

ولنتابع – إن شاء الله – في مناقشة مبدأ الخوارزميات الجينية  ,والإشارة إلى أهمية كل من عمليتي التصالب والطفرة بشكل عملي…

ونحن بانتظار تعليقاتكم الكريمة , ونقدكم الكريم البناء لهذا الموضوع.

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

المحررون : م.نور 

فهرس سلسلة الخوارزميات الجينية :

  1. الخوارزميات الجينية ( الحلقة الأولى)
  2. الخوارزميات الجينية ( الحلقة الثانية)
  3. الخوارزميات الجينية ( الحلقة الثالثة)
  4. الخوارزميات الجينية ( الحلقة الرابعة والأخيرة)

, , , , , ,

8 تعليقات

تابع

Get every new post delivered to your Inbox.