الخوارزميات التطورية واستخدامها بالتوليد التلقائي و إيجاد الحلول الأفضل

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

خوارزميات البحث التطورية

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

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

 المكونات الأساسية للاستراتيجيات التطورية

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

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

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

 يستخدم مايسمى بالنمط الجيني (genotype) للبحث وتقييم الحلول المولدة ومن ثم يتم تحويل النمط الجيني الى النمط الظاهري (phenotype) وهو العناصر أو المكونات المولدة فمثلا قد يمثل النمط الجيني سلسلة من الأرقام الدالة على شكل المنحني المميز لتوضع مجموعة من النقط في الفضاء ثلاثي الأبعاد بينما يكون النمط الظاهري هو تصميم لكرسي.

لشرح فكرة تمثيل المحتوى سوف نطرح المثال التالي:
يمكن تمثيل محتوى مرحلة من لعبة ماريو (Super Mario Bros.) كالتالي:
1- بشكل مباشر (direct) حيث يكون عدد المتغيرات مساو لمساحة المرحلة كما في الشكل

untitled

حيث يحتوي كل موقع في المصفوفة على نوع مكون اللعبة المتواجد.

2- بشكل غير مباشر (indirect) كقائمة بمواقع وخصائص اللعبة المختلفة مثل عدد و نوع الأعداء والمنصات والحفر والتلال
3- وبشكل أكثر غير مباشرة كمستودع لأنماط يمكن اعادة استخدامها مثل النقود والتلال وكذلك قائمة بكيفية توزيع هذه الأنماط على خريطة المرحلة
4- وأكثر طريقة غير مباشرة هي كرقم عشوائي

هذه التمثيلات المختلفة سوف تؤدي إلى مجالات بحث مختلفة جداً. من السهل الاعتقاد أن أفضل تمثيل هو الأكثر مباشرة الذي يمكن من  التحكم  بشكل كامل بالنمط الظاهري (الخيار الأول). إلا أنه يجب الانتباه أنه كلما توسع مجال البحث كان من الصعب البحث بفعالية عن حل جيد بسبب العدد الكبير من الاحتمالات الممكنة وهذا مايسمى بلعنة الأبعاد (curse of dimensionality).

من ناحية أخرى الخيار الأخير يعتبر أيضاً غير محبذ وذلك لأنه ينطوي على ما يدعى بمستوى منخفض جداً من “المحلية” مما يعني أن تغيير صغير في النمط الجيني (التمثيل المختار) سوف ينتج عنه تغيير غير متوقع في النمط الظاهري (التمثيل الحقيقي) مما يجعل توابع كهذه تتصرف بشكل عشوائي.

 تابع التقييم: تابع التقييم هو التابع الذي يربط كل محتوى يتم توليده (أو جزء منه) بقيمة تدل على جودة هذا المكون. خرج هذا التابع يمكن أن يدل على سبيل المثال على مدى إمكانية لعب المرحلة المتولدة أو مدى جودة المرحلة بشكل عام. ويعد إيجاد تابع التقييم المناسب من أصعب المهمات لتطوير استراتيجيات بحث فعالة

يتم عادة التمييز بين توابع التقييم التالية:

توابع التقييم المباشرة:

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

الميزات المستنتجة يمكن أن تكون عدد الطرق الممكنة للخروج من المتاهة, عدد الطلقات التي يطلقها المسدس… الخ.

توابع التقييم المعتمدة على المحاكاة:

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

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

توابع التقييم التفاعلية:

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

خوارزمية البحث

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

 كيفية عمل الخوارزمية

 لتوضيح كيفية عمل الخوارزمية التطويرية لنأخذ المثال التالي:

كمثال بسيط على عمل الخوارزمية لنفترض أننا نريد توليد جملة “Hello world” من مجموعة من الأحرف العشوائية مثل “jiKnp4bqpmmAbp” معنى ذلك أن الخوارزمية التطورية سوف تبدأ من مجموعة من الأحرف العشوائية “jiKnp4bqpmmAbp” التي تعتبر الجيل الأول ثم سوف تقوم الخوارزمية بتطبيق طفرة تغيير لإنتاج جيل جديد ثم تقييم هذا الجيل باستخدام مايسمى بتابع التقييم. لنفرض أنه لدينا تابع التقييم هو عدد الحروف المتواجدة في مكانها الصحيح . لنفرض أيضا أنه لتطبيق الطفرة الوراثية سوف تقوم باختيار حرف واحد من مجموعة الأحرف بشكل عشوائي ونغيره لحرف آخر. مبدأ  عمل الخورزمية هو كالتالي: أولا نقوم بحساب التقييم للمصدر وهو مجموعة الأحرف “jiKnp4bqpmmAbp” ،ثانياً نقوم بالاستخدام الطفرة الوراثية لتغيير مجموعة الأحرف ثالثاً نقوم بحساب التقييم من خلال تابع التقييم لمجموعة الأحرف الجديدة، في حال كان التقييم الحالي أفضل من التقييم السابق نقوم بتغيير المصدر ليصبح مجموعة الأحرف الجديدة وإلا نقوم بالتخلص من المجموعة الجديدة ونقوم بتكرار الخطوات السابقة حتى نحصل على الحل الأمثل.

1

 إذا أردنا كتابة الخوارزمية بطريقة أكثر دقة فإننا سنعرفها تبعاً للخطوات التالية:

1- تهيئة مجموعة من الأفراد بشكل عشوائي
2- تقييم جميع الأفراد بحيث يتم إسناد قيمة لكل فرد وفقاً لتابع التقييم
3- ًيتم فرز الأفراد حسب القيم المسندة إليهم تصاعديا
4- يتم حذف الأفراد الأسوء
5- يتم استبدال الأفراد المحذوفة بأفراد جديدة
6- يتم تغيير عدد من الأفراد الجديدة عن طريق خلط الأفراد مع بعضها (crossover) كاستبدال جزء من سلسلة محارف بجزء من سلسلة مأخوذ من فرد آخر أو عن طريق طفرة التغيير (mutation) المناسبة كاختيار موقع في السلسلة بشكل عشوائي و استبدال المحرف بآخر مختار عشوائياً.
7- إذا كان الجيل الحالي يحوي أفراد ذات نوعية جيدة أو قد وصلنا إلى الحد لأقصى من عدد مرات التكاثر يتم إنهاء عملية البحث وإلا نستمر بالبحث

 يوضح الشكل التالي الخطوات السابقة بشكل مبسط:

2

 أمثلة تطبيقية:

 مثال ١: التوليد الآلي للألعاب اللوحية

التوليد التلقائي للمحتوى هو استخدام خوارزميات للتوليد. المحتوى المولد قد يكون مراحل، خرائط، قواعد، شخصيات، قصص، وكل ما يمكن أن  تحتويه اللعبة. تعد هذه الخوارزميات مفيدة لعدد من المهام كتوليد عدد لانهائي من المراحل، التوليد بوتيرة أسرع من المصممين، إمكانية التعديل التلقائي للمحتوى حسب مستوى و شخصية اللاعب، وتوليد خيارات غير متوقعة تساعد على الابتكار.

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

 كمثال بسيط سنأخذ عملية توليد ألعاب لوحية كلعبة الشطرنج:

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

توابع التقييم: يمكن تقييم هذه الألواح المتولدة عن طريق استخدام أنظمة تستخدم خوارزميات تقوم بمحاكاة اللعبة تبعاً للقواعد المولدة. تلعب هذه الأنظمة ضد بعضها والتقييم النهائي للوح مولد قد يتضمن مقدار يدل على مدى توازن اللعبة (يمكن تمثيله بالفرق بين عدد المرات التي ربح فيها  كل لاعب) و مقدار آخر يحدد ما إذا كان للعبة نهاية و مقدار يدل على مدى كون اللعبة ممتعه.

خوارزمية البحث: يمكن استخدام خوارزمية جينية قياسية كالتي تم شرحها سابقا

yavalath_nestorgames
أول لعبة لوحية مصممة بشكل كامل عن طريق الحاسوب باستخدام الخوارزميات التطورية

مثال٢: توليد قواعد لتوليد الأشجار في نظم الـ l-systems

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

تمثيل المحتوى: يمكن تمثيل قواعد التوليد كسلسلة من الرموز المعبرة عن الطرف الأيمن من القاعدة. لاحظ أنه يجب مراعاة بعض الشروط ليكون التمثيل صحيحاً بالحد الأدنى كأن يكون عدد رموز الإدخال و الإخراج من المكدس متساوٍ.

تابع التقييم: يمكن استخدام مجموعة من توابع التقييم كتحويل القواعد المتولدة للشكل الظاهري و طرحا لعدد من المستخدمين لإعطائها تقييم يدل   على مدى جمالها أو محاكاتها للواقع. أو يمكن برمجة تابع تقييم وفقاً لعدد من النظريات المعرفة للأشجار كوجود حد أدنى من التناظر بين الأفرع و كون الشكل الناتج محاك للأشجار في كونها منبثقة للأعلى.

خوارزمية البحث: يمكن استخدام خوارزمية جينية قياسية كالتي تم شرحها سابقا

trees
أمثلة عن بعض الأشجار المتولدة بقواعد تم تطويرها بخوارزميات البحث

المراجع

  1. Evolving Hello World. http://www.electricmonk.nl/log/2011/09/28/evolutionary-algorithm-evolving-hello-world/
  2. On Genetic Algorithms and Lindenmayer Systems. http://www.cs.stir.ac.uk/~goc/papers/GAsandL-systems.pdf
  3. Evolutionary Game Design. http://www.doc.ic.ac.uk/~sgc/papers/browne_cig11.pdf
Advertisements

اترك رد

إملأ الحقول أدناه بالمعلومات المناسبة أو إضغط على إحدى الأيقونات لتسجيل الدخول:

WordPress.com Logo

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   / تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   / تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   / تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   / تغيير )

Connecting to %s