الانتقاء

الانتقاء
اي فرد في المجتمع الابتدائي هو عبارة عن قيد يتكون في برنامجنا من الحقول الاتية:
fitness chromosome

قيمته من استدعاء الدالة round(rand)
قيمته تأتي من استدعاء دالة fitness
أفراد المجتمعات التي تأتي بعد المجتمع الابتدائي أيضا لها نفس الحقول إلا أن طريقة ملئ مواقع (جينات) جزء الكروموسوم هي الي تختلف عن المجتمع الابتدائي المجتمع الابتدائي هو عبارة عن قيد يتكون في برنامجنا من الحقول الاتية:
fitness chromosome


(انتقاء , تزاوج, طفرة)
قيمته تأتي من استدعاء دالة fitness
سيكون هناك دالة للانتقاء و دالة للتزاوج و دالة للطفرة, في كل اسبوع سنقوم ببرمجة احد هذه الدوال, هذا الاسبوع هو اسبوع دالة الانتقاء.
الدوال التي نحتاجها لتوليد مجتمع جديد
هناك عدد من الدوال التي نحتاج الى بناءها لتوليد مجتمع اخر غير المجتمع الابتدائي و السبب في ذلك ان عملية توليد الكروموسومات في المجتمعات الجديدة تحتاج الى ثلاث دوال تستدعى بالترتيب الاتي:
1- دالة لاختيار فردين من المجتمع السابق
2- دالة لاجراء تزاوج بين الفردين المختارين في الخطوة السابقة و ناتج هذه الخطوة سيكون كروموسومين جديدين تسمى الاطفال
3- مراعاة ان هناك احتمالية لحدوث طفرة على الطفلين الناتجين
بعد توليد الكروموسوم يتم حساب كفاءه من خلال استدعاء الدالة fitness, كما في المخطط الاتي:










بالاضافة الى الدوال الثلاثة التي اشرنا لها هناك دالة ترتبط بالدوال الثلاثة و تسمى دالة الاحتمالية :

دالة الاحتمالية flip:
وظيفة الدالة :
هذه الدالة تسمح بوقوع حدث ما أو لا تسمح اعتماداً على احتمالية معيّنة probability, لذلك فهي دالة منطقية مخرجاها اما true (نعبر عنه ب1 في ماتلاب بالضبط مثل لغة سي) او false (نعبر عنه ب0 في ماتلاب) تستخدم هذه الدالة عادةً في الدوال الآتية :
- دالة التزاوج : السماح بحدوث تزاوج أو لا.
- دالة الطفرة :للسماح بحدوث طفرة على احد الأفراد أو لا.
- دالة انتقاء المجموعات في حالة تساوي الصلاحيات كما سنشرحه لاحقا.
ملاحظة : ما هي الاحتمالية probability ؟
الاحتمالية هي عدد حقيقي حيث 0 ? probability ? 1 .
الصفر يعني أنَّ نسبة حدوث الشيء هي 0%.
الواحد يعني أنَّ نسبة حدوث الشيء هي 1%.
0.5 تعادل %50 هذا الاحتمال في حالة أنّنا نريد حدوث شيء ما باحتمالية متساوية.
احتمالية التزاوج (pc) مثلاً يفضل أن تكون كبيرة بحيث أنَّ 0.6 ? pc ? 0.9,أمّا احتمالية الطفرة (pm) يفضّل أن تكون قليلة للسيطرة على الطفرات.
برمجة دالّة الاحتمالية : function f=flip(p)
if p==1.0
f=1;
else
f=(rand<=p);
end
1-مدخلات الدالة : عدد عشري اسمه p يمثل الاحتمالية حيث 0 ? p ? 1
2-مخرجات الدالة (f) : اما 0 معناها الدالة لا تسمح باجراء المطلوب
او 1 معناها الدالة وافقت على تنفيذ الاجراء الذي استدعاها
3-شرح برمجة الدالة: اذا كانت الاحتمالية =1 معناها 100% سيتم المطلوب لذلك فان مخرج الدالة اي المغيرf سيكون 1 اما ان كانت الاحتمالية اقل من الواحد (جزء else) نقوم بتوليد عدد عشري عشوائي بين 1و 0 عن طريق الدالة rand و نقارنه مع الاحتمالية p نتيجة هذه المقارنه ستخزن في فاذا كان العدد الذي ولدته اقل او يساوي p معناها ناتج الشرط true و المغيرf سيكون 1 و عند عدم تحقق الشرط فان المتغيرf سيكون قيمته 0 يتم ذلك بخطوة واحدة هي: f=(rand<=p);
دالة الانتقاء :
هناك عدة انواع من الانتقاء تتعرفون عليها في مادة التطبيقات لكن في مشروعنا سوف نختار طريقة تسمى انتقاء المجموعات الثنائية وتسمى بهذا الاسم لانها تختار فردين بصورة عشوائية و تقارن بينهم و تختار الافضل حسب المسألة, في مشروعنا الافضل هو االاعلى صلاحية لان كلما زاد النسبة المئوية للنظام معناها ان النظام يتمكن من تشخيص حالان اكثر بصورة صحيحة..
هؤلاء الافراد تستخدمهم دالة التزاوج في الخطوة التالية اي انه احتاج الى زوجين نختارهم عن طريق دالة الانتقاء هذه الدالة كلما استدعيها راح تختار زوج واحد لذلك حتى اختار زوجين احتاج انه استدعيها مرتين
تعمل هذه الطريقة على توليد رقمين مختلفين بين 1 و حجم المجتمع ps بصورة عشوائية هذه الارقام تمثل موقع الفرد في المجتمع يعني index :
أي ان الرقم الاول يمثل موقع الفرد الاول في المجتمع (الذي هو مصفوفة قيود) و الرقم الثاني يمثل موقع الفرد الثاني في المجتمع.
بعد ان حصلنا على مواقع الافراد المختارة نقارن بين صلاحياتهم و نختار الفرد الاعلى صلاحية .اذا صادف ان الفردين لهم نفس الصلاحية نستدعي دالة الاحتمالية التي شرحناها سابقا للحكم بين الفردين المختارين.
Algorithm binset
input : pop , ps
output : person
begin
repeat % ps دوارة اختيار فردين مختلفين كل فرد عبارة عن رقم بين 1 و %
Let ind1 be random index from population ;
Let ind2 be random index from population ;
until ind1 <> ind2 <------ (شرط التوقف )
% مقارنة الافراد واختيار الفرد الاقل صلاحية %
if fitness of ind1 = fitness of ind2 then % صلاحية الفرد الاول = صلاحية الفرد الثاني %
f=flip(0.5);
if f
person=ind1;
else
person=ind2;
end
else
if fitness of ind1 > fitness of ind2 then
person = ind1
else
person = ind2
end
end
خلاصة القول :
هذه الدالة تحتاج كمدخلات المجتمع الذي اختار افراد منه (pop)و حجم المجتمع (ps الذي يمثل عدد المواقع و الافراد فيه) اما مخرجاتها ستكون الزوج او الفرد الذي يشارك لاحقا في عملية التزاوج و المسمى هنا person. انتقاء المجموعات الثنائية يقوم باختيار فردين من المجتمع الحالي و ذلك عن طريق تسلسل الفرد (index) في المجتمع شرط أن يكون تسلسل الفرد الأول ? تسلسل الفرد الثاني ثمَّ يختار الفرد الأفضل صلاحية. إذا كانت الصلاحيات متساوية سيتم اختيار احد الأفراد باحتمالية متساوية (و ذلك عن طريق الدالة flip
لكن لماذا يتم اختيار index بدلاً من قيد كامل (فرد) ؟
السبب يعود إلى كون المجتمع عبارة عن مصفوفة قيود و أي موقع من مواقعها يمكن أن نعرف محتواه عن طريق index كأي مصفوفة أخرى. لنأخذ المتجه الآتي :
15 20 1 2 9 7
A =

للوصول إلى القيمة 20 في المتجه نقول A(5) .
افرض أنَّ دالة الانتقاء اختارت الفرد رقم 3 في المجتمع الآتي,يمكن الوصول إلى محتوياته و هي chromosome و fitness و كالآتي :
fitness chromosome
4 1 0 0
5 0 0 1
7 1 0 1
7 1 0 1



1 0 1
pop(3).chromosome سوف نحصل على قيم جينات الكروموسوم و هي
pop(3).fitness سوف نحصل من خلالها على صلاحية الفرد الثالث وهي 7
امثلة لتوضيح طريقة عمل دالة انتقاء المجموعات الثنائية:
بفرض ان لدينا المجتمع الاتي (مثال عام):
Fitness chromosome Index
4 1 0 0 1
5 0 0 1 2
7 1 0 1 3
7 1 0 1 4



اختيار الزوج الاول : عند استدعاء الدالة سوف يتم تنفيذ الخطوات الاتية:
1- اختيار فردين من المجتمع بتوليد رقمين عشوائيين يمثلان مواقع الافراد
لنفرض ان الرقم الاول كان 3 و الرقم الثاني كان 4 فهذا يعني انه الان اختار الفردين الثالث و الرابع
2- الان لاختيار الزوج الاول سيتم مقارنه صلاحيات الفردين الثالث و الرابع حيث ان
صلاحية الفرد الثالث =7 و صلاحية الفرد الرابع =7
بما ان الصلاحيتان متساويتان يتم حل المشكلة باستدعاء الدالة flip لتختار اما الفرد الثالث او الرابع عشوائيا
حالة أخرى :
نفرض ان الفرد الأول كان 4 و مقدار صلاحيته =7
و الفرد الاخر الذي تم اختياره هو الفرد رقم 1 في المجمع و صلاحيته =4
فان الدالة سوف تختار الفرد الرابع لانه اعلى صلاحية.
اختيار الزوج الثاني: ببساطة يتم ذلك عن طريق استدعاء الدالة مرة ثانية

اجانب العملي :
1- إضافة الدالة flip و الكود موجود في هذه المحاضرة.
2- بناء الدالة binset عن طريق الخوارزمية الموجودة في هذه المحاضرة أيضا و استدعائها مرتين بعد دوارة طباعة المجتمع الابتدائي