البرمجة باستخدام الجينات الوراثية الجزء الاخير


#1

والان ننتقل الى المرحله الثانيه او العمليه الثانيه و هى عمليه 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 وذلك لانها عمليه وسيطه هدفها الانتقال من جيل الى جيل

وهذه كانت مقدمه مفيده عن عمليات البرمجه باستخدام الجينات الواثيه ومن يريد استفاده اكثر فليرسل لى وشكرا على متابعتكم


(eng_hamad) #2

السلام عليكم ورحمة الله وبركاته
شكرا لك يا مهندس احمد على هذه المواضيع المتميزة

وان شاء الله بمواضيع اخرى متميزة;)


#3

شكرا لك اخى العزيز على اهتمامك


#4

شكرا لك اخى العزيز على اهتمامك بالموضوع