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

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

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

“خوارزميات 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 مخصصة جديدة.

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

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

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

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

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

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

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

يُدعى بأن استخدام هذه الطريقة العمياء في اعادة تركيب العمليات 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

 

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