الحلقة 3: Memetic Algorithm Strategy الاستراتيجية

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

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

اسم الكتاب:

The Selfish Gene

Book by Richard Dawkins

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

الكتاب باللغة الانكليزية, وللأسف لا يوجد نسخ مترجمة عربية.

ان اسعفنا الوقت, قد نعمد الى ترجمته او تلخيصه ان شاء الله.

مراجعة

اما الآن:

نتابع سلسلتنا هذه حول خوارزمية memetic algorithm, حيث تحدثنا في حلقات سابقة عن المفهوم الاساسي للخوارزمية, بالاضافة شرح مبسط عن هيكلية الخوارزمية الاساسي

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

وبأن هنالك ثلاث عناصر اساسية في الخطوة المتعلقة بتشكيل التجمع وتوليد تجمع جديد new population, الا وهي:

  1. الاختيار selection
  2. اعادة الانتاج reproduction
  3. الاستبدال replacement

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

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

اما في هذه الحلقة, فسوف نتابع السلسلة بالحديث عن الاستراتيجية المتبعة في خوارزمية memetic algorithm.

الاستراتيجية

كما ذكرنا سابقا فإن MA تتميز باستغلالها الكبير لكافة المعلومات المتواجدة في فضاء البحث مما يساعد على ايجاد حلول افضل.

وبذلك يكون الهدف الاساسي من استراتيجية معالجة المعلومات هذه هي القدرة على استغلال تقنيات البحث العامة القائمة على اساس البحث في التجمع من اجل البحث عن مناطق جيدة من فضاء البحث global search ,  جنبا الى جنب مع الاستفادة المتكررة من تجريبيات البحث المحلي local search heuristic  من اجل ايجاد حلول محلية مثلى local optimum.
تسمى هذه التقنية في خوارزميات MAs ب ” المحسنات المحلية” Local-improvers.Diagrammatic representation of MA

الشكل ادناه يوضح  بشكل عام خوارزمية local-improvers المستخدمة ضمن خوارزمية memetic algorithm, حيث كما هو واضح فإنه بعد تطبيق العمليات  – selection, crossover or mutation – فإنه تتم مقارنة مدى ملائمة الحل الجديد بالنسبة للحل الحالي, وفي حال كان الحل الجديد افضل, عندها يتم استخدامه. كما هو موضح بالشكل 1.3

1.3 local improver.JPG

على كل الاحوال, فإن خوارزمية المحسنات المحلية local-improver algorithm يمكن استخدامها في اي جزء من اجزاء الاجرائية الخاصة بتوليد الاجيال generation of new population. وذلك لكونها عبارة عن عملية اضافية operator مثلها مثل بقية العلميات التي تجري ضمن التجمع.

على سبيل المثال, يمكن اضافتها بعد الانتهاء من اي عملية اخرى مثل علمية اعادة التركيب recombination او بعد عملية الطفرة  mutation operator. او حتى من الممكن استخدامها وتطبيقها بعد مرحلة اعادة الانتاج reproductive stage.

كما ذكرنا سابقا, فإن عملية الاستفادة من المحسنات المحلية  local-improver تعد من اهم مزايا خوارزميات MAs.

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

 

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

1.4 ma.JPG

هنالك بعض التعليقات والشروح المتعلقة بقالب الخوارزمية المذكور ويجب ذكرها.

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

بالبداية, اجرائية توليد الجيل الاولي Generate-Initial-Population process : مسؤولة عن انشاء وتكوين عناصر وافراد المجموعة الاولية من التجمع pop .

يمكن تحقيق ذلك عبر توليد اعدادات عشوائية للتجمع في البداية او عبر استخدام آليات معقدة اكثر ( على سبيل المثال ممكن استخدام بعض التجريبيات  الخاصة بتشكيل عناصر جديدة constructive heuristic) وذلك عبر استخدام مجموعة من الاعدادات عالية الجودة التي تستخدم كاساس لتوليد الجيل الاولي من التجمع.

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

1.5 generate inital poplutaion.JPG

هنالك ايضا نقطة مثيرة للاهتمام ذكرت بالمخطط 1.4: الا وهي اجرائية اعادة بدء التجمع Restart-Population process.

تعد هذه الاجرائية مهمة جدا من اجل الاستخدام الافضل للموارد الحسابية  computational resources.

على سبيل المثال: لننظر مثلا الى الحالة التي قد يصل اليها التجمع population  الى مرحلة تصبح فيها عملية توليد الحلول الجديدة المحسنة مستحيلة.  وهي الحالة التي يصبح فيها تقريبا كل الافراد المتواجدين ضمن التجمع مشابهيين لبعضهم البعض.

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

تدعى هذه الظاهرة باسم ظاهرة التقارب convergence, ويمكن التعرف عليها وتحديدها من خلال استخدام مقاييس  مثل مقياس Shannon’s entropy.

threshold-graphic-zoom.jpg

وبحسب القياس في حال وصل الى مقدار محدد دون عتبة threshold محددة مسبقا, عندها يعتبر التجمع في مرحلة انحدار.

تعتمد تحديد قيمة هذه العتبة threshold على طريقة تمثيل المسألة قيد الحل ( عدد القيم ضمن المتحول, القيود …).

هنالك طريقة احتمالية probabilistic approach  تستخدم لتحديد فيما اذا كان التجمع قد تقارب.  على سبيل المثال هنالك مهنج Bayesian.

اذن, ماان يعتبر التجمع population بإنه تقارب دون الحد الادنى المسموح به, حتى تشرع عملية اعادة بدء التجمع بالعمل restart population process.

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

هنالك استراتيجية نموذجية تكمن في ابقاء جزء من التجمع الحالي كما هو – هذا الجزء ممكن ان يبلغ من الصغر حتى يصل الى فرد واحد, الا وهو افضل حل ضمن التجمع الحالي – واستبدال الحلول المتبقية بحلول جديدة يتم توليدها من الصفر كما هو موضح في الشكل 1.6.

1.6.JPG

من الواضح بإنه من الممكن تصور بعض التعديلات على قالب الخوارزمية.

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

 

وبذلك نكون قد شرحنا الخطوات الاساسية والخوارزمية العامة ل memetic algorithm.

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

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

———————————

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

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

مع تحيات

م. نور الصباحي

فهرس سلسلة Memetic Algorithm

  1. الحلقة الاولى – مقدمة عن خوارزمية Memetic Algorithm MA
  2. الحلقة الثانية – خوارزمية Memetic Algorithm MA
  3. الحلقة الثالثة – استراتيجية خوارزمية Memetic Algorithm
  4. الحلقة الرابعة – تصميم خوارزمية Memetic Algorithm
  5. الحلقة الخامسة والاخيرة – تطبيقات خوارزمية Memetic Algorithm

 

الخوارزميات التطورية Evolutionary algorithms – EA
الامثلة Optimization
البحث Search
محاكاة التلدين Simulated annealing – SA
التجريبيات metaheuristics
التطور الثقافي cultural evolution
جينات genes
ميم meme
طرائق الحساب التطورية evolutionary  computation (EC) methods
خوارزميات التقريب approximation algorithms
تقنيات البحث المحلي local search techniques
خوارزميات ميماتيك Memetic algorithms – MAs
تجمع Population
فرد ضمن التجمع Individual – agent
الاختيار selection
مرحلة الاستبدال replacement stage
تابع الملائمة Fitness function
التصالب احادي النقطة Single point crossover
التصالب crossover
عامل اعادة تركيب recombination operator
اعادة تركيب او دمج recombination
الصفات features
عتبة threshold
منهج احتمالي probabilistic approach
ارسال transmitting
محسنات محلية Local-improvers

 

 

 

Clever Algorithms: Nature-Inspired Programming Recipes

http://www.cleveralgorithms.com/nature-inspired/physical/memetic_algorithm.html

1

A study on the use of “self-generation” in memetic algorithms
N Krasnogor, S Gustafson – Natural Computing, 2004 – Springer

2

New Optimization Techniques in Engineering  – Chapter 1 : Memetic Algorithms
http://www.lcc.uma.es/~ccottap/papers/IntroMAs.pdf

3

A Gentle Introduction to Memetic Algorithms
Pablo Moscato

Departamento de Engenharia de Sistemas,

Faculdade de Engenharia Eletrica, Universidade Estadual de Campinas,

Carlos Cotta

Departamento de Lenguajes y Ciencias de la Computacion,

Escuela Tecnica Superior de Ingeniera Informatica, Universidad de Malaga,

4

Handbook of Bioinspired Algorithms and Applications
Edited by Stephan Olariu & Albert Y. Zomaya

5

https://www.quora.com/Whats-the-difference-between-memetic-algorithm-and-genetic-algorithm

6
The Selfish Gene
Book by Richard Dawkins
7

 

Advertisements

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

  1. أضف تعليق

اترك رد

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 مدونون معجبون بهذه: