الحلقة 5 والأخيرة: Memetic Algorithm Applications تطبيقات الخوارزمية

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

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

تطبيقات خوارزمية MA

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

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

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

التطبيقات

• NP-hard Combinatorial Optimization problems
  تشكل مسائل الامثلة التقليدية من رتبة NP-hard التطبيق الاشهر والامثل لخوارزمية memetic algorithm.
  حيث حصدت الخوارزمية  رصيد نجاح كبير في حل هذا النوع من المسائل .
  من الامثلة على مسائل الامثلة من رتبة np-hard مايلي:
  1. graph partitioning
  2. Max independent set
  3. Bin-Packing
  4. Min Graph coloring
  5. Set covering
  6. Min generalized assignment
  7. Multidimensional Knapsack
  8. Set Partitioning
  9. Min Travelling Salesman Problem
• مسائل الجدولة Scheduling Problems
  بلا شكل, تعتبر مسائل الجدولة scheduling problems من اهم تطبيقات خوارزمية MA وذلك بسبب تطبيقاتها العملية. لذلك تستحق ان نذكرها على حدا ضمن تعداد مستقل, بالرغم بأنه كان من الممكن تصنيفها ضمن المسائل من رتبة NP-hard.
  تم استخدام خوارزمية MA لتعالج طيف واسع من مسائل الجدولة. بإمكاننا ان نذكر جزء منها:
  1. Maintenance scheduling جدولة الصيانة
  2. Open shop scheduling
  3. Flowshop scheduling
  4. Total tardiness single machine scheduling
  5. Single machine scheduling with setup-times and due-dates
  6. Parallel machine scheduling الجدولة المتوازية للآلات
  7. Project scheduling جدولة المشاريع
  8. Warehouse scheduling
  9. Production planning التخطيط للانتاج
  10. Timetableing جدولة البرنامج – الاسبوعي على سبيل المثال.
  11. Rostering
  12. Sport games scheduling جدولة الالعاب الرياضية
• الروبوتيك وتعلم الآلة Machine Learning and Robotics
  يعتبر كل من مجالي الروبوتيك وتعلم الآلة بمثابة مجالين متقاربين, ويعزى ذلك الى أن المهام المختلفة الي ينطوي عليها التحكم بالروبوتات, يتم تحقيقها عادة باستخدام شبكات الذكاء الصناعي NN او/ مع نظم التصنيف classifier systems.
  استخدمت خوارزميات MAs بكلا الحقلين, ويشار اليها عادة باسم “genetic hybrids”.
  فيما يلي سنورد امثلة على استخدامات خوارزميات MAs هذا المجال
  1. neural network training تدريب الشبكات العصبونية
  2. pattern recognition التعرف على النماذج
  3. pattern classification تصنيف النماذج
  4. Analysis of time series تحليل السلاسل الزمنية
     وفي مجال تطبيقاتها في عالم الروبوتيك, سنورد بعض الامثلة:
  5. reactive rulebase learning in mobile agents
  6. path planning تخطيط المسار
  7. manipulator motion planning
  8. time optimal control
• الكهرطيسية, الالكترونيات والهندسة Engineering, Electronics and Electromagnetics
  كذلك تم استخدام هذه الخوارزمية في كل من حقلي الهندسة والالكترونيات.
  على سبيل المثال, بالنسبة لمسائل الهندسة, فقد تم العمل في هذه المجالات:
  1. Structure optimization امثلة وتحسين الهيكل
  2. System modeling نمذجة النظام
  3. Fracture mechanics مكيانيكا الكسور
  4. Aeronautic design تصميم الطيران
  5. Trim loss minimization
  6. Traffic control
  7. Power planning تخطيط الطاقة
  8. Calibration of combustion engines معايرة محركات الاحتراق
  9. Process control
     اما بالنسبة للتطبيقات في كل من مجالي الكهرطيسية والالكترونات, فسنورد الامثلة التالي:
     1. Semiconductor manufacturing تصنيع انصاف النواقل
     2. Circuit design تصميم الدارة
     3. Circuit partitioning تقسيم الدارة
     4. Computer aided design التصميم بمساعدة الحاسوب
     5. Multilayered periodic strip grating
     6. Analogue network synthesis
     7. Service restoration
     8. Optical coating design
     9. Microwave imaging

• مسائل الامثلة الجزيئية Molecular Optimization Problems
  لقد اخترنا هذا التصنيف الخاص من المسائل الحسابية, التي تتضمن مسائل امثلة غير خطية, لمساعدة القارئ على تحديد التوجه العام لهذا النوع من التطبيقات.
  لسوء الحظ, فإن تطبيقات الخوارزمية في هذا المجال, كان يشار اليها ايضا باسم اخر, الا وهو ‘genetic’, بالرغم من كون الخوارزميات المطبقة قريبة جدا من روح وطبيعة خوارزمية MA.
  تعتبر حاليا تطبيقات خوارزمية MA بهذا المجال ناشطة بشكل كبير, ويتم هندسة العديد منها في هذا المجال بشكل مستمر.
  سنذكر من هذه التطبيقات:
  1. Clustering gene-expression profile
  2. Interring phylogenetic trees
• المزيد من التطبيقات الاخرى other applications
  بالاضافة الى التطبيقات التي تم ذكرها سابقا, فقد تم استخدام خوارزمية MA في العديد من التطبيقات الاخرى, على سبيل الذكر لا الحصر سنذكر عددا منها:
  1. Medicine الطب
  2. Economics الاقتصاد
  3. Oceanography علم المحيطات
  4. Mathematics الرياضيات
  5. Imaging science and speech processing معالجة الصور ومعالجة الكلام

 

التوجهات المستقبلية للخوارزمية

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

يعود سبب هذا الاعتقاد لعدة اسباب اهمها تحقيق خوارزمية MA سجل عظيم بسبب تطبيقها الفعال على عدة مسائل, واظهارها نتائج جيدة

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

وما ذكرناه من تطبيقات في هذه الحلقة ماهو الا غيض من فيض

——————-

وبهذا المخلص عن تطبيقات خوارزمية 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
خوارزميات ميماتيك	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

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
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

 

الحلقة 4: Memetic Algorithm Design التصميم

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

قبل البدء بهذه الحلقة, هنالك ملاحظة جديرة بالانتباه, الا وهي:

“خوارزميات MA ليست عبارة عن قطع صغيرة من الكود, وانما هي عبارة عن نظم كبيرة”

مراجعة:

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

ملاحظة:

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

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

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

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

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

 

اول نقطة يجب النظر اليها بعين الاعتبار هي:

طريقة تمثيل الحلول representation of solutions.

تنبيه:

من الضروري ان ننوه لنقطة هامة هنا, هنالك فرق بين:

• تمثيل الحل representation
• و ترميز الحل codification

حيث ان ترميز الحل codification يشير الى الطريقة التي سيتم عبرها تخزين الحلول بشكل داخلي, ويتم اختيارها مع الاخذ بعين الاعتبار لعدة نقاط تشمل:

• محدودية الذاكرة الحاسوبية memory limitations.
• مدى تعقيد عمليات المعالجة التي يتطلبها هذا التمثيل manipulation complexity.
• نقاط اخرى تتعلق بالموارد المتاحة.

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

يجب الانتباه الى ان عملية اختيار تمثيل محدد لا يعد اجرائية منفصلة, وانما له علاقة قوية بمهمة اختيار العملياتoperators  الملائمة من اجل مرحلة اعادة الانتاج.

تذكرة: نقصد بالعمليات مثل: التصالب crossover, الطفرة mutation, …

في الواقع, ومن وجهة نظر قائمة على اساس العمليات operator-based  – التي سيتم استخدامها في مرحلة اعادة الانتاج reproductive operator – فإن تواجد اكثر من عملية قد يعني انه قد نحتاج الى القيام بعدة تمثيلات مختلفة للمسألة قيد الحل, وذلك بالاطوار المختلفة من مرحلة اعادة الانتاج reproductive phase.

 

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

اي ان عملية اختيار التمثيل representation مرتبطة بالعملياتoperator التي ستطبق على هذا التمثيل.

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

من أجل حل هذه المسألة, يمكننا اللجوء إلى:

• استخدام العمليات الحالية operator
• أو تصميم عمليات Operator مخصصة جديدة.

 وفي الحالة الأولى، يمكن أن تكون خطة العمل المقترح كالتالي:

• سنبدأ من بمجموعة من العمليات المتواجدة حاليا
  في الخطوة الاولى, يتم العمل على تحديد تمثيل المسألة representation التي يتم معالجتها بواسطة كل من هذه العمليات.
• استخدام اي المعايير المطروحة لقياس مدى جودة التمثيل الحاليcurrent representation .
• اختيار العملية W_i من المجموعة المذكورة سابقا, بحيث تكون عملية معالجة التمثيل بواسطة هذه العملية اكثر جودة.

تدعى هذه الطريقة:بالتحليل العكسي للعمليات inverse analysis of operators, وسبب التسمية يعود الى استخدام نوع من الهندسة العكسية inverse engineering من اجل تقييم الفائدة المحتملة من كل عملية Operator.

سيكون البديل لهذا التحليل العكسي مايعرف باسم التحليل المباشر direct analysis, وهي الطريقة التي يتم بها تصميم العمليات الجديدة.

ويمكن القيام بذلك على النحول التالي

• تحديد عدة اشكال مختلفة للتمثيل للمسألة قيد الدراسة
• استخدام اي من المعايير المطروحة لقياس مدى جودة التمثيل الحالي representation.
• إنشاء عمليات جديدة
  
  على اساس التمثيل الموجود

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

يُدعى بأن استخدام هذه الطريقة العمياء في اعادة تركيب العمليات Operators بإنها تمنع التقارب convergence السريع للحلول دون المستوى ضمن فضاء الحل.

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

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

تُدعى العمليات المستخدمة في اعادة انتاج جيل جديد, والتي تستخدم المعرفة المتعلقة بالمسالة قيد الحل باسم: التجريبيات heuristic او باسم العمليات الهجيبة hybrid.

في هذه العمليات, يتم استخدام معلومات المسألة قيد المعالجة لتوجيه عملية انتاج الجيل الجديد offspring.

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

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

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

من المثير للاهتمام بإنه لايزال هنالك مجال كبير للبحث في طرائق وجوانب التصميم في خوارزمية MA.

مما يفتح الباب امام القارئ امام مجموعة من الاحتمالات الجيدة لتصميم خوارزمية MA عبر دراسة التجريبات metaheuristics الموجودة حاليا.

———————————

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

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

مع تحيات

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

 

فهرس سلسلة 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

 

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
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

 

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

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

اثناء اعدادنا لهذه السلسلة عن خوارزمية 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.

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

وبذلك نكون قد شرحنا الخطوات الاساسية والخوارزمية العامة ل 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

 

الحلقة 2: Memetic Algorithm

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

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

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

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

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

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

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

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

The MA search template

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

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

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

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

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

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

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

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

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

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

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

الاختيار selection

وهو يمثل المكون الاول, وبدوره مسؤول ( بالتعاون مع مرحلة الاستبدال 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

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

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

 

ملاحظة:

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

 

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

 

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

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

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

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

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

 

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

 

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

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

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

الطفرة Mutation

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

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

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

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

——————————-

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

 

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

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

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

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

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

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

MA = Memetic Algorithm

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

 

مقدمة Introduction

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

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

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

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

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

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

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

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

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

سبب التسمية

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

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

 

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

 

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

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

وكما كان الحال بالنسبة للخوارزميات التطورية الكلاسيكية 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

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

• تسريع عملية البحث وايجاد النتائج الافضل, تلك النتائج التي قد تستغرق العملية التطورية في خوارزميات 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