Introduction to Genetic Algorithms
عمليه تطوير او نشاه هذه العمليه تتكون من ثلاث نقاط مهمه
- الكائن الموجود لديه القدره على اعاده انتاج نفسه
- يوجد جيل من هولاء الكائنات القادره على اعاده انتاج نفسها
- يوجد بعض الاختلافات بين هذه الكائنات
ولنأخد مثال على ال genetic algorithm
وتكون اغلب الامثله او المشاكل هى عمليات optimization problems وفى هذا المثال المطلوب هو ايجاد افضل استراتيجيه لسلسه من اربع مطاعم ماكولات ويكون التفضيل على الاساس الاتى
- السعر
- المشروب
- السرعه فى الخدمه
ولنفترض للتبسيط ان فى هذه الاسس تحتوى على احتمالين فقط اى 2 bit مثلا السعر عالى= 0 او منخفض= 1 المشروب كولا = 1 او خمور = 0 سرعه الخدمه سريعه =1 او بطيئه = 0 ومن هذا يتتضح لنا ان كل الاحتمالات المتاحه هى عباره عن سلسله character string طولها = 3 و عرضها = 2 وقيم k هى 0 او 1 وبالتالي
L = 3 ,k = 2 اذن عدد الاحتمالات المتاحه = 2^3 = 8 وتسمى هذه الاحتمالات business strategies
اولا سنقوم باختيار جيل عشوائى من هولاء الثمانى احتمالات الممكنه و السوال هنا لماذا قمنا بذلك و الاجابه هذا يعتمد على حس و ذكاء المبرمج حيث يكون متوقع نتائج البحث التى سوف يحصل عليها و لذلك يحاول ان يضيق خيارات البحث على البرنامج حتى يحصل على النتائج بسرعه و بعد اخذ هذا الجيل العشوائى initial random population يكون لدينا الجيل رقم 0 generation وهذا الجيل يسمى الجيل العشوائى الابتدائى initial random generation ولذلك يجب على المبرمج ايضا من خلال خبرته ان يحدد العدد الافراد فى الجيل Population size = M = 4 for each generation
وسنقوم الان باختبار كل فرد individual فى هذا الجيل ضد خصائص طبيعيه معينه والتى نحصل عليها من عمليات ال optimization و تسمى داله الخصائص بى objective function و هذا بغرض معرفه هل متوافق هذا الفرد مع ما نود الحصول عليه ام لا ؟ ومدى التوافق اسمه ال fitness او يسمى ايضا profit ويتم الحصول على هذا ال fitness بالتعويض فى ال objective function بعد التاكد من ان هذا الفرد لا يخالف الشروط المفروضه و التى تسمى constrains
فعلى سبيل المثال هنا أخذنا ال fitness of each individual الرقى العشرى المساوى للرقم الثنانى الذى يرمز لكود كل فرد ونلاحظ ان افضل استراتيجيه هى 110 والذى يقابلها اعلى fitness و العكس بالنسبه لاسوء استراتيجيه 001
والان سنبدا فى تطبيق مبدا داروين وهو البقاء للاصلح و لكن لابد من ايجاد اولا ما يسمى ال relative fitness ويساوى ال fitness المقابل لكل عنصر مقسوما على المجموع ال fitness
ومن الجدول السابق ان العنصر الذى لديه fitness =6 سوف يعطى لنا نص من مجموع نسبه اختياره ان ان فرصه اختياره كبيرة اى انه فرد صالح فى الجيل و لذلك سيتم تكراره فى الجيل القادم و اختفاء العنصر الغير صالح و الذى يعطى fitness=1 .
فى عام 1989 قم العالم جولدبرج Goldberg (1989)
بعرض هذه القيم السابقه فى صوره طريقه مفيده و تسمى roulette wheel او العجله الدواره وهى عباره عن قرص مقسم الى عدد من القطاعات وكل فرد من الجيل يشغل قطاع معين و يكون حجم هذا القطاع متناسب مع ال fitness لكل فرد individual
Roulette wheel
والان سنقوم بعمليه انتاج ما يسمى Mating pool
وهذه مرحله انتقاليه من الجيل رقم 0 الى الجيل رقم 1
و يتضح لنا هذا فى الجدول التالى
ومن الجدول السابق يتتضح لنا ان العنصر المقابل لل fitness=0.25 قد ظهر مره واحده والعنصر المقابل ل fitness=0.50 قد ظهر مرتين وذلك لانه عنصر صالح والعنصر fitness=0.08 قد اختفى تماما لانه عنصر غير صالح و تطبيقا لمبدا داروين فان البقاء للاصلح والعنصر fitness=0.17 سوف يظهر مره واحده
ونلاحظ ان هذه العمليه ادت الى تحسين فى
average fitness .
والمره القادمه انشاء الله سنبدا فى عمليه Crossover
