الحلقة 2: Memetic Algorithm

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

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

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

كتذكرة ومخلص للحلقة السابقة, نذكر بأن خوارزمية MA عبارة عن خوارزمية هجينة, تجمع سلوكيات الخوارزميات التطورية EA من حيث قاعدة البحث العام, وبين تقنيات وتجريبات البحث المحلي local search heuristics techniques.

وإن احد الميزات التي سبب هذه الشهرة والنجاح لخوارزميات MA هي التالية:

على عكس طرائق الحساب التطورية التقليدية traditional evolutionary  computation (EC) methods, فإن خوارزميات MAs تهتم باستغلال جميع المعرفة المتاحة حول المسألة قيد الدراسة. وهي نقطة تم اهمالها لزمن طويل ضمن الخوارزميات التطورية EAs .

dual-evolution-system

نتابع الآن شرحنا لخوارزمية Memetic algorithm

قالب خوارزمية MA

The MA search template

كما ذكرنا سابقا, فإن خوارزمية MAs تحاول مزج عدة مفاهيم من عدة تجرييبات وخوارزميات مثل EAs, SA -على سبيل الذكر وليس الحصر مع بعضها البعض.

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

إن MAs وبشكل مشابه لخوارزميات EA قائمة بشكل اساسي على التجمع. وهذا يعني بأن الخوارزمية تحافظ على تجمع Population من الحلول الخاصة بالمسألة قيد المعالجة.  ذلك يعني بأن التجمع يحوي على عدة حلول مقترحة بآن واحد.

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

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

ولزيادة توضيح هذه النقطة، من الضروري أولا الاطلاع على قالب مبدئي high-level template  للحدث الاساسي ضمن التجمع في خوارزمية MA.

الترميز الاساسي لخوارزمية MA ادناه عبارة عن ترميز عام جدا وغير تفصيلي.

كما هو موضح بالشكل ادناه

MA high-level template.JPG

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

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

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

الاختيار selection

ntse-selection-procedure.jpg

وهو يمثل المكون الاول, وبدوره مسؤول ( بالتعاون مع مرحلة الاستبدال replacement stage ) عن جوانب المنافسة بين العناصر – الافراد – الموجودة ضمن التجمع.

تتم عملية الاختيار هذه عبر الاستفادة من المعلومات التي يوفرها تابع توجيه محدد ad hoc guiding function  ( يسمى بتابع الملائمة fitness function بعرف مصطلحات الخوارزميات التطورية).   حيث يتم قياس مدى جودة الافراد ضمن التتجمع, وبالتالي يتم اختيار عناصر محددة لاعادة الانتاج وذلك اعتمادا على قياس مدى جودتها.

 

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

  • تابع الملائمة او الجودة fitness function ( حيث تزداد احتمالية اختيار فرد كلما ازدادت جودته او ملائمته).
  • الاعتماد على rank-based methods اي تعتمد على ترتيب الفرد ضمن التجمع. بحيث تزداد احتمالية اختيار فرد محدد على موقعه ترتيبه ضمن التجمع بعد ترتيب كافة العناصر ضمن التجمع.
  • طرائق تعتمد على المسابقة Tournament-based methods: حيث يعتمد اختيار الافراد على اساس التنافس المباشر ضمن مجموعات جزئية من الافراد الموجودين ضمن التجمع

 

 الاستبدال Replacement  

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

عملية الاستبدال تقوم على اساس خواص محددة.  على سبيل المثال: عادة ما يتم ذلك عبر اختيار الافراد الافضل ( تبعا الى قيمة تابع الملائمة fitness function) من كل من التجمعين الجديد والحالي ( تدعى هذه الاستراتيجية بالتبديل باسم “plus”).ا

هنالك طريقة اخرى, حيث يتم اختيار العناصر الافضل من الجيل الجديد ويتم ادخالهم ضمن التجمع عبر استبدالهم اسوء العناصر الموجودة فيه ( تدعى هذه الاستراتيجية باسم “comma”)

 

مرحلة اعادة الانتاج reproduction stage

ربما كان الجانب الاكثر اثارة للاهتمام خلال عملية توليد الجيل تكمن في مرحلة اعادة الانتاج reproduction phase.

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

ومع ذلك, فإن الوضع الأكثر شيوعا ينطوي على استخدام اثنين فقط من العمليات, الا وهي التالية:

  1. الدمج او اعادة التركيب recombination
  2. الطفرة mutation

1.2procedure generate new population.JPG

parent and childrenعملية اعادة التركيب او الدمج recombination  عبارة عن عملية تمثل عملية التعاون المتبادل بين عدة افراد individual  ( عادة اثنين منهم, ولكن ممكن القيام بالعملية مع عدد اكبر من الافراد).

ويتم ذلك من خلال بناء افراد جدد باستخدام المعلومات الواردة في عدد من الاباء المختارين.

 

ملاحظة:

يطلق مصطلح offspring على الافراد الناتجين من عملية اعادة التركيب recombination.

 

تسمى عملية اعادة التركيب recombination  باسم عملية الارسال transmitting في حال كان الافراد الناتجين offspring من عملية اعادة التركيب مكونين بشكل كامل من المعلومات التي تم اخذها من والديهم.

 

وتمثل هذه الحالة الحالة الكلاسكية من عمليات اعادة التركيب المطبقة عادة على السلاسل المؤلفة من بتات bitstrings

عادة يستخدم التصالب crossover بهدف تحقيق  عملية اعادة التركيب  recombination .

فيما يلي عدة امثلة على عمليات ارسال transmitting من خلال عمليات التصالب احادي النقطة single-pint crossover او التصالب الموحد uniform crossover .

Fig-2-Crossover-single-point-Source-43.png

توضح الصورة ادناه اشكال التصالب المذكورة انفا

Fig-6-Illustration-of-examples-of-one-point-two-points-and-uniform-crossover-methods.png

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

 

يقال عن عامل اعادة تركيب recombination operator  بأنه properly assorting – مشكل صحيح ان جازت الترجمة- اذا وفقط اذا استطاع ان ينتج احفاد يحملون اي تركيبة من الصفات المتوافقة الماخوذة من الأباء.
ويقال عن عملية التشكيل assortment بأنها ضعيفة weak في حال كان من الضروري انجاز عدة عمليات اعادة تشكيل recombination ضمن الفرد الناتج offspring من اجل تحقيق التوافق المذكور اعلاه.

 

يتضمن الشرح الذي ذكرناه عن عملية اعادة التركيب عدة مفاهيم مثيرة للاهتمام, مثل مفهومي

  • الصفات المرتبطة related features
  • التعاون cooperation

سنتحدث عن هذه النقاط ونشرحها بعد قليل. اما الآن فدعونا نتحدث عن بقية العمليات التي تم ذكرها انفا, الا وهي عملية الطفرة mutation.

الطفرة Mutation

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

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

الخلاصة, فإن عملية الطفرة تقوم بتوليد حل جديد وذلك عبر تعديل حل موجود.

يمكن للتعديل ان يكون عشوائيا – وهي الحالة الغالبة – او من الممكن ان يُطرح مع معلومات المسألة المطلوب معالجتها بحيث يحيز البحث الى اماكن جيدة من فضاء  البحث.

——————————-

سنتوقف عند هذا القدر ضمن هذه الحلقة, لنتابع ان شاء الله في حلقات قادمة المزيد عن استراتيجية وخوارزمية 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

 

 

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

 

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