الحلقة: 1 – مقدمة عن خوارزمية Memetic Algorithm MA

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

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

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

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

وضمن هذه السلسلة الجديدة سنتطرق اليوم الى خوارزمية:

MA = Memetic Algorithm

mematic algorithm

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

 

مقدمة Introduction

بالعودة الى اواخر الستينيات, وبداية السبعينيات, نجد ان عددا من الباحثين كانوا قد اسسوا البداية لما يعرف الان بالخوارزميات التطورية evolutionary algorithms (EAs).

ضمن ما يقرب الاربعة عقود, كان جل اهتمام الباحثين ينصب على موضوعي البحث search  والامثلة optimization  وذلك على صعيد كل من العلوم التطبيقة والنظرية.

وقد تطورت هذه النظريات ليثبت بعضه فائدته في حيث يثبت البعض الاخر عدم فائدته.

وكان هذا هو الحال ايضا فيما يتعلق ببعض التقنيات المشابه مثل:

  • simulated annealing – محاكاة التلدين
  • Tabu search

وقد القي مصطلح “التجريبيات” metaheuristics على هذه المجموعة من التقنيات.

في اواخر الثمانينيات ظهر مصطلح “خوارزميات  Memetic algorithms (MAs) للوجود.

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

هذه المجموعة  الجديدة اصبحت تشمل على سبيل المثال: الخوارزميات التطورية EAs و محاكاة التلدين Simulated annealing SA

سبب التسمية

Questionmark.pngاما كلمة “Memetic”  فهي مشتقة من عبارة “Meme” وقد صاغ الاسم الدكتور R. Dawkins.

وقام بهذه التسمية بهدف الدلالة على وجود شيء مماثل للجين gene في سياق التطور الثقافي ايضا cultural evolution

 

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

 

ويوضح الاقتباس أعلاه الفلسفة المركزية لخوارزميات مMAs : التحسين الفردي بالإضافة إلى التعاون الجماعي بين السكان.

بشكل عام – وكما شرحنا في البداية عن مقاربة خوارزمية MA للخوارزميات الجينية من حيث الشبه والاختلاف – فإننا نجد بأن خوارزميات  Memetic algorithms تبني ثنائية للتطور الجيني والثقافي مع بعضهم البعض, وبذلك تسمح بنقل واختيار selection, وراثة inheritance  والتعديل على الميمات mems بالاضافة الى الجينات genes.

dual-evolution-system

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

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

والآن, بالاضافة للتعريف السابق لخوارزميات Memetic algorithms , بإمكاننا القول بأن MA عبارة عن استراتيجية بحث حيث تقوم مجموعة من العناصر الامثلية ضمن تجمع ما بالتعاون والتنافس.

كما تحدثنا سابقا, سنجد بأن خوارزميات MAs تشكل موضوعا ساخنا هذه الايام ضمن خووارزميات الذكاء الصناعي AI, وذلك بسبب نجاحها الواضح في حل العديد من مسائل الامثلة الصعبة hard optimization problems.

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

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

يتم تحقيق استغلال المعرفة المتاحة للمسألة قيد الدراسة ضمن خوارزميات MAs عبر دمج العديد من التقنيات مثل: التجريبات, خوارزميات التقريب approximation algorithms,  تقنيات البحث المحلي local search techniques…

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

 

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

Diagrammatic representation of MA

Diagrammatic representation of MA

الهدف الاساسي من مثل هذه التركيبة الهجيينة هو مايلي:

  • تسريع عملية البحث وايجاد النتائج الافضل, تلك النتائج التي قد تستغرق العملية التطورية في خوارزميات EA وقتا طويلا للوصول اليها
  • او بهدف الحصول على حلول قد يكون من غير الممكن الحصول عليها في حال اعتمدنا على الطريقة التطورية evolution method لوحدها, او في حال اعتمدنا على طرائق البحث المحلي لوحدها.

ومما سبق نجد بأن MA عبارة عن:

Global-local search hybrids

سنلاحظ ايضا فيما بعد بأن اغلب خوارزميات MA تستخدم تجريبات البحث المحلي heuristic local search بدلا من غيرها من الطرق المتاحة.

————————-

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

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

مع تحيات

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

 

فهرس سلسلة 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
خوارزميات MA Memetic algorithms – MAs
تجمع Population
فرد ضمن التجمع Individual – agent
الاختيار selection
مرحلة الاستبدال replacement stage
تابع الملائمة Fitness function
التصالب احادي النقطة Single point crossover
التصالب crossover
عامل اعادة تركيب recombination operator
اعادة تركيب او دمج recombination
الصفات features
عتبة threshold
منهج احتمالي probabilistic approach

 

References

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

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

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

5

 

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