والان ننتقل الى المرحله الثانيه او العمليه الثانيه و هى عمليه Crossover ومعناها هنا عمليه التزاوج وهذه العمليه تسمح بتكوين او خلق عنصرين جديدين من عناصر موجوده سابقا بهدف الحصول على خصائص لهذين العنصرين ( الابناء ) offspring احسن من حضائص العناصر السابقة (الاباء ) parents
ويتم اختيار هولاء العناصر التى سوف تشارك فى عمليه Crossover بالنسبه لى fitness و ينتج لدينا زوج من offspring مختلفين عن الاباء ومختلفين عن بعضها البعض .
والان سوف نقوم بعمل عمليه Crossover بين اول عنصرين من ال mating pool الموجوده فى الجدول السابق وهما 110 , 011 .
وعمليه ال Crossover تبدا باختيار عشوائى للعناصر من individual 1 الى individual (L-1) وL تعنى طول السلسله او الكروموثوم قيمتها سابقا تساوى 3 ولذلك سنختار من 1 الى 3-1=2 .
فلنفترض اننا اخترنا 2 و هذه النقطه تسمى ب Crossover point وفى هذه العمليه يتم قسم او فصل كل عنصر عند هذه النقطه وسيعطى لنا جزء fragment و باقى remainder والعمليه موضحه كما يلى
ومن خلال الجدول التالى سيتضح لنا مراحل تكوين الجيل الاول generation 0
ومن الجدول السابق نلاحظ ان ال mating pool
هو خطوه وسيطه intermediate فى عمليه تحويل الجيل رقم 0 الى الجيل رقم 1
وقمنا بعمل عمليه crossover لنسبه محدده من الجيل وفرضنا انها فى هذا المثال تساوى 50%
وهذا معناه اننا قمنا بعمل هذه العمليه على فردين من مجموع افراد الجيل وهم اربعه والنسبه الباقيه هى التى قامت فى عمليه reproduction فقط ولتكوين ال mating pool
وبمقارنه الجيل الجديد مع الجيل القديم يتتضح لنا
· نسبه التوافق average fitness تحسنت من 3 الى 4.25
· افضل عنصر فى الجيل من 6 الى 7
· وأسوأ عنصر فى الجيل من 1 الى 2
وفى هذا المثال قمنا بشرج الالجوريثم الوراثى على نوعين من العمليات وهما
· Fitness-proportional reproduction
· Crossover
وبعد ذلك سيقوم البرنامج او الالجوريثم بعملية تكرار لهذه العمليات لكل جيل حتى يتم الانتقال الى جيل جديد مع حدوث تحسين فى الصفات وذلك حتى يتحقق معيار نهايه البرنامج ويسمى termination criterion
هذه الخطوات السابقه يقوم بها الالجوريثم او البرنامج ولا نرى منها شيئا اما ما نقوم به نحن هو
· تقييم كل فرد فى الجيل للحصول على ال fitness
ومن معلومات ال fitness التى حصلنا عليها يمكننا تحديد نسب العمليات التى سيقوم بها الالجورثيم مثل
· Reproduction probability (Pr %)
· Crossover probability (Pc %)
· Mutation probability (Pm %)
وهذه العمليه الاخيره بعمليه التحول وسنتحدث عنها لاحقا
وفى النهايه نقوم بحديد معيار النهايه ومن الممكن ان يحدد على اساس اكبر عدد من الاجيال المطلوبه او على اساس الخصائص المطلوبه ومثلا فى هذا المثال نختار ان افضل استراتيجيه مطلوبه هى 111 والتى عند الحصول عليها سوف يتوقف البرنامج
اما عمليه التحول او mutation ونقوم بعملها على كروموثوم طوله ثابت ويكون استعمال هذه الطريقه فى الالجوريثم محدود وال mutation عمليه لا تزاوجيه asexual ونقوم بها على فرد واحد فقط ويكون اختياره عشوائى ايضا من الفرد رقم واحد فى الكرموثوم الى الفرد L وعند هذا الفرد المطلوب القيام بعمليه تحوله تكون ال mutation point
واذا كان نظام الاعداد لدينا ثنائى binary فانه عمليه تحوله تعنى مقلوبه complement
وعلى سبيل المثال اخترنا مثلا الفرد 4 للقيام بعمليه التحول 010 و اختارنا نقطه التحول وهى 2 اى نقوم بعمل مقلوب للبت الثانى و يكون الفرد بعد التحول 000
ونلاحظ هنا ان عملية التحول تؤدى الى زيادة التنوع genetic diversity لأفراد الجيل وذلك بانتاج عنصر جديدة مثل 000
وهى عملية ثانوية للاحتفاظ بالتنوع المفقود نتيجة العمليات السابقة
وهناك اربعة خطوات لتجهيز الالجوريثم العادى
Conventional genetic algoritm وذلك لحل المسائل المتعدده
1- determining the representation scheme
[right]وهى التى يتم فيها وضع جميل الاحتمالات الممكنه التى من الممكن ان تكون حل للمشكله الموجوده لدينا وتحديد ايضا حجم الجيل
The population size (M)
2-determining the fitness measurement
ويتم ذلك من اختبار كل فرد لدينا ضد الظروف الطبيعيه او ظروف المشكله constrain وبعد ذلك نقوم بايجاد قيمه ال fitness الخاصة به من ال objective function وهذا يكون من خلال عمليات ال optimization
3 – determining the parameters and variables controlling the algorithm
وهى نسب العمليات المختلفه فى البرنامج
Pr , Pm , Pc
4 – determining the way of designating the result and the criterion for terminating the algorithm
وفى هذه الخطوة نقوم بتحديد معايير نهايه البرنامج و كما ذكرنا تكون مبنيه على اساسين وهما اما ان يكون مطلوب عديد من الاجيال نود الحصول عليه
Maximum number of generation (G) و نتوقع ان هذا كافى حتى نحصل على الخصائص المطلوبه وذلك يساعد فى تقليل وقت الالجوريثم
وأما ان نحدد الخصائص المطلوبه ويقوم الالجوريثم بالبحث عنها
اما فيوجد هناك ثلاث خطوات لتنفيذ الالجوريثم وهى
1 – randomly created an initial population of a fixed length string
2- iteratively perform the following substeps on the population of string until the termination criterion has satisfied
a – evaluate the fitness of each individual in the population
b – create a new population of string by applying at least the first two of the following three operations . and the operations are applied to individual string (S) in the population chosen with a probability based on fitness
I – copy existing individuals string to the new population
II – create two new strings by genetically recombining randomly chosen substring from two existing string (crossover)
III – create new string from an existing string my randomly mutating the character at one position in the string
3 – the last step is to get the best individual string that appeared in any generation (the best so far individual) is designated as the result of the genetic algorithm
this result may represented a solution to the problem
وهذه الخطوات موضحه فى ال flow chart التالى
ونلاحظ فى هذا المخطط السابق عدم ظهور عمليه ال mating pool وذلك لانها عمليه وسيطه هدفها الانتقال من جيل الى جيل
وهذه كانت مقدمه مفيده عن عمليات البرمجه باستخدام الجينات الواثيه ومن يريد استفاده اكثر فليرسل لى وشكرا على متابعتكم