هناك عدة طرق تستخدم في تعلم الاله. في هذا المقال نستعرض بعضا منها. ملاحظه أن بعض الصور المستخدمة لا تتبع حقوق الطبع والنشر و نحن نعتذر لذلك ولكن استخدمت لغرض المعرفة العلمية .
تجمع البيانات هي عملية وضع البيانات في مجموعات مماثلة. خوارزمية التجمع تقسم مجموعة من البيانات إلى عدة مجموعات. حيث أن التشابه بين النقاط ضمن مجموعة معينة أكبر من التشابه بين نقطتين ضمن مجموعتين مختلفتين. فكره تجمع البيانات هي فكره بسيطه في طبيعتها وهي قريبه جدا من الانسان في طريقه تفكيره حيث اننا كلما تعاملنا مع كميه كبيره من البيانات نميل إلى تلخيص الكم الهائل من البيانات إلى عدد قليل من المجموعات اوالفئات،وذلك من اجل تسهيل عمليه التحليل.خوارزميات التجمع تستخدم على نطاق واسع ليس فقط لتنظيم وتصنيف البيانات وانما هي مفيده لضغط البيانات وبناء نموذج ترتيب البيانات. حيث أنه اذا كان بامكاننا أن نجد مجموعات من البيانات، فانه بالامكان بناء نموذج للمشكلة على أساس تلك المجموعات.
هناك عدد من التقنيات المستخدمة في عملية تجميع البيانات، ومن هذه التقنيات(الخوارزميات) التي سوف يتم الحديث عنها بشكل مفصل:
هي خوارزميه لجمع عدد من البيانات استادا إلى خصائص وسمات هذه البيانات، وتتم عمليه التجميع من خلال تقليل المسافات بين البيانات ومركز التجمع (cluster centroid).
وتتم هذه الخوارزمية من خلال الخطوات التاليه :-
1-حساب احداثيات مراكز التجميع
2-حساب المساقه بين كل البيانات ومراكز التجميع.
3-تجميع البيانات وتنظيمها في مجموعات بناء على اقل المسافات بين المركز ونقاط البيانات.
4-اعاده تنفيذ الخطوات من 1 – 3 حتى الوصول إلى حاله الثبات
يعتمد أداء هذه الخوارزميه على المواقع الاوليه لمراكز التجمع (Centroid)، ومن المستحسن تنفيذ هذه الخوارزميه عدة مرات مع اختلاف المراكز في كل مرة عن المرات السابقة.
نفترض لدينا أربعة أنواع من الأدوية، وكل نوع من الأدوية لديه عدد من السمات، في هذا المثال كل نوع له سمتان.
| نوع الدواء (medicine) | مؤشر الوزن (Weight Index) | معامل الحموضة (pH) |
|---|---|---|
| A | 1 | 1 |
| B | 2 | 1 |
| C | 4 | 3 |
| D | 5 | 4 |
الهدف من هذا المثال، هو جمع أنواع هذه الأدوية في مجموعتين اعتمادا على سمات كل نوع من الأدوية، ولتحقيق هذا الهدف علينا تنفيذ خطوات خوارزمية التجميع التي سبق ذكرها.
1.القيم الابتدائية لمراكز التجمع: نفترض أن الدواء A والدواء B هما مراكز التجمع الأولى. لتكن c1 و c2 تدل على احداثيات المراكز، حيث أن(c1=(1,1و(c2=(2,1.
يبين الشكل 1.1 توزيع أنواع الأدوية المعبر عنها بالمعين الأزرق على المستوى الريكاردي، كما يبين مراكز التجمع الابتدائية، مع الأخذ بعين الاعتبار أن هذه المراكز تم افتراضها بشكل عشوائي.
2. المسافات بين النقاط والمراكز: نحسب المسافة بين مركز التجمع وكل نقطة من النقاط في المستوى. فينتج لدينا مصفوفة من المسافات.
كل عمود في مصفوفة المسافات يمثل نوع دواء واحد. الصف الأول من مصفوفة المسافات يتكون من المسافات بين كل نقطة ومركزالتجمع الأول، والصف الثاني يتكون من المسافات بين كل نقطة ومركزالتجمع الثاني. على سبيل المثال، المسافة بين الدواء C ومركز التجمع الأول هي: صورة:Motazrqw363.jpg والمسافة بين نفس الدواء ومركز التجمع الثاني هي: c ، الخ.
3. تجميع النقاط: نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. وهكذا، فان الدواء الأول (A) ينتدب إلى المجموعة الأولى، الدواء الثاني (B) إلى المجموعة الثانية، الدواء الثالث (C) إلى المجموعة الثانية، والدواء الرابع (D) يعود للمجموعة الثانية. ينتج لدينا مصفوفة المجموعات G التي تتكون من القيم 1 و 0 ، ويكون العنصر في مصفوفة المجموعات يساوي 1 فقط اذا كان الدواء مسند إلى تلك المجموعة.
4. التكرار الأول، تحديد مراكز التجمع: بعد معرفة عناصر كل مجموعة، نحسب مركز جديد لكل مجموعة اعتمادا على هذه العضويات الجديدة، كما يظهر في الشكل 1.2. المجموعة الأولى تتكون من عنصر واحد فقط،وتبقى احداثيات مركز التجمع الأول كما هي دون تغيير(c1=(1,1.أما المجموعة الثانية والتي تتكون من ثلاث عناصر، تتغير احداثيات مركز التجمع الثاني بالاعتماد على احداثيات العناصر الثلاثة:
5. التكرار الأول، المسافات بين النقاط والمراكز: في هذه الخطوة يتم حساب المسافة بين كل نقطة ومراكز التجمع الجديدة. كما في الخطوة الثانية، ينتج لدينا مصفوفة من المسافات.
6. التكرار الأول، تجميع النقاط: على غرار الخطوة الثالثة، نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة. بالعودة إلى مصفوفة المسافات الجديدة، ننقل الدواء الثاني (B) إلى المجموعة الأولى، بينما تبقى باقي الأدوية كما هي. تظهر مصفوفة المجموعات كالتالي
7. التكرار الثاني، تحديد مراكز التجمع: الان نقوم باعادة الخطوة الرابعة لحساب احداثيات مراكز التجمع الجديدة بالاعتماد على عملية التجميع في التكرار الأول. يتكون كل من المجموعة الأولى و الثانية من عنصرين، كما أن الاحدثيات الجديدة لمراكز التجمع تصبح
8. التكرار الثاني، المسافات بين النقاط والمراكز: نكرر الخطوة الثانية، فينتج لدينا مصفوفة مسافات جديدة كما يلي:
9. التكرار الثاني، تجميع النقاط: ، مرة أخرى نحيل كل نقطة إلى مركز تجمع بالاعتماد على أقل مسافة.
ينتج لدينا في النهاية . بمقارنة التجمع بين التكرار الأول والتكرار الثاني، نلاحظ أن المجموعات لم تتغير من حيث عناصرها. هذا يعني أن عملية الحسابات في ال(k-mean clustering) وصلت إلى حالة الثبات، وهذا يعني أن هذه الخوارزمية لم تعد بحاجة إلى المزيد من التكرار، وبالتالي حصلنا على النتيجة النهائية للتجميع.
ال(Fuzzy C-means Clustering) تعتمد على الفكرة الأساسية من ال(k-means Clustering)، مع فارق واحد هو أن في ال(FCM) كل نقطة بيانات تنتمي إلى مجموعة على درجة من عضوية الصف، في حين أن كل نقطة بيانات في ال(KM) اما أن تنتمي المجموعة أو لا تنتمي.
توظف ال(FCM) تقسيم عشوائي(ضبابي)، كما أنه يمكن لنقطة معينة أن تنتمي لعدة مجموعات مع درجة من الانتماء التي يحددها عضوية الصفوف بين 0 و 1.
يسمح لمصفوفة العضوية (U) أن تكون فيها قيم العناصربين 0 و 1. مع ذلك، حاصل جمع درجات انتماء نقطة بيانات لجميع المجموعات دائما يعادل: صورة:Motazrqw375.jpg
كما أن ال(Cost Function) لل(FCM) هو: .
حيث أن uij تكون بين 0 و 1 ، ci هي عبارة عن مركز التجمع في المجموعة الضبابية i ، هي المسافة الاقليدية بين مركز التجمع i ونقطة البيانات j ، كما أن هي عبارة عن (weighting exponent).
هنالك شروط ضرورية لايصال ال(Cost Function) للحد الأدنى وهي:
تعمل هذه الخوارزمية بشكل متكررمن خلال الشرطين السابقين إلى أن لا يلاحظ أي تحسن. في عملية (batch mode)، تحدد ال(FCM) مراكز التجمع ci ومصفوفة العضوية U باستخدام الخطوات التالية:
الخطوة الأولى : وضع قيم ابتدائية عشوائية بين 0 و 1 في عناصر مصفوفة العضوية U.
الخطوة الثانية: حساب مراكز التجمع الضبابي ci، حيث أن i=1,……..,c.
الخطوة الثالثة: حساب ال(Cost Function). ويتم التوقف اما اذا كانت نتيجة ال(Cost Function) ما دون قيمة تحمل معينة، أو أن التحسن في تلك النتيجة من خلال التكرار السابق ما دون حد معين.
الخطوة الرابعة: حساب مصفوفة العضوية الجديدة U باستخدام المعادلة التالية: صورة:Motazrqw380.jpg كما هو الحال في ال(KM)، يعتمد أداء ال(FCM) على قيم مصفوفة العضوية الابتدائية؛ فمن المستحسن أن تنفذ هذه الخوارزمية عدة مرات، في كل مرة تكون البداية بقيم نقاط بيانات مختلفة.
(Mountain Clustering)هي طريقة بسيطةلايجاد مراكز التجمعات بالاعتماد على حساب الكثافة من خلال ما يدعى بال(Mountain Function). كما يمكن استخدام هذه الطريقة لايجاد مراكز التجمعات بشكل تقريبي، مما يسهلاستخدامها كوسيلة ابتدائية قبل الدخول في مراحل تجميع أكثر تعقيدا.
في المرحلة الأولى من ال(Mountain Clustering) يتم تشكيل شبكة على البيانات في المستوى الديكارتي، حيث أن التقاطعات بين خطوط هذه الشبكة تشكل مراكز المجموعات.
المرحلة الثانية، يتم تتابع بناء ال(MF) والذي يمثل قياس كثافة البيانات. ذروة(ارتفاع) ال(MF) عند النقطة v؟V تعادل
حيث أن xi هي نقطة i من البيانات، و هو ثابت تطبيقي محدد، يتبين من المعادلة السابقة أن قياس كثافة البيانات يتأثر بكل النقاط xi في مجموعة البيانات، وقياس كثافة البيانات يتناسب عكسيا مع المسافة بين نقاط البيانات xiو النقطة الموجودة في الv(MF. الثابت يحدد الذروة والانحدار لل (MF) الناتج.
المرحلة الثالثة تنطوي على اختيار مراكز التجمعات عن طريق هدم ال(MF) بشكل تسلسلي. يحدد مركز التجمع الأول ci من خلال اختيار النقطة التي لها أعلى قياس للكثافة. يتم تحديد مركز التجمع الثاني من خلال القضاء على تأثير التجمع الأول. ويتم ذلك من خلال اعادة تشكيل ال(MF)، ويتم تشكيل ال(MF) الجديد من خلال
القيمة الطروحة في المعادلة السابقة تزيل أثر المجموعة الأولى. من الملاحظ أن بعد عملية الطرح تقل قيمة ال(MF) الجديدة mnew(v) لتصل إلى الصفر عند v=c1 .
بعد عملية الطرح، يتم اختيار مركز المجموعة الثانية من خلال تحديد النقطة التي يكون عندها أعلى قيمة لل(MF)الجديدة. تستمر هذه العملية حتى يتم تحديد عدد كاف من مراكز التجمع.
المشكلة في طريقة التجمع السابقة (Mountain Clustering) ، هي أن العمليات الحسابية تزداد طرديا بازدياد أبعاد المشكلة؛ وذلك لأنه _وكما ذكر سابقا_ يتم تقييم ال(Mountain Function) عند كل نقطة تقاطع في الشبكة على مستوى البيانات.
استطاعت خوارزمية ال (Subtractive Clustering) حل هذه المشكلة، وذلك بترشيح عدد من نقاط البيانات لتكون مراكز للمجموعات، بدلا من استخدام نقاط تقاطع خطوط الشبكة، كما هو الحال في ال(MC). وهذا يعني أن العمليات الحسابية أصبحت تتناسب مع حجم المشكلة بدلا من أبعادها.
خوارزمية ال(Subtractive clustering)، هي عمليه تحديد مراكز المجموعات التي تجمعها صفه مشتركه بين كل الاعضاء دون العلم بعدد المجموعات الموجوده لدينا.
وتعتمد هذه الطريقه على حساب كثافه البيانات عند كل نقطة ضمن مستوى معين، فاذا كانت كل نقطة مرشحة لتكون مركز تجمع، فانه يمكن قياس كثافة البيانات عند النقطة xi من المعادلة التالية:
حيث أن raثابت موجب يمثل قطر دائرة حول كل نقطة، يتم حساب الكثافة داخل هذه الدائرة، وكلما كبر هذا القطر اصبح لدينا عدد اقل من المجموعات، وكلما قل القطر زاد عدد المجموعات.
تم اختيار المركز الأول xc1 والذي كانت كثافة البيانات عنده أعلى ما يمكن Dc1 . بعد ذلك يتم حساب قيم الكثافات الجديدة عند كل نقطة xi من خلال
حيث أن rb ثابت موجب يمثل قطر دائرة حول كل نقطة، يتم حساب الكثافة داخل هذه الدائرة، وكلما كبر هذا القطر اصبح لدينا عدد اقل من المجموعات، وكلما قل القطر زاد عدد المجموعات. ودائما تكون قيمة rb أكبر من قيمة ra (غالبا يستخدم rb=1.5ra )، وذلك لتقليل قيم الكثافة عند النقاط المجاورة لنقطة المركز الأولى.
وتقوم خوارزمية ال ( Subtractive clustering) بالخطوات التاليه:
1 -ايجاد نقطه معينه موجوده في المجال تكون عندها الكثافه عاليه_ ويتم حساب الكثافة من المعادلة الأولى_ ومن ثم اختيار نقطه معينه كمركز، وذلك عن طريق وجودها بين عدد كبير من النقاط المجاورة .
2-يتم حذف نقاط البيانات.
3-ثم تبحث الخوارزمية عن مركز جديد، وذلك عن طريق حساب قيم الكثافة للنقاط الأخرى_كما في المعادلة الثانية_، وتستمر هذه العمليه حتى الانتهاء من كل النقاط، أو ايجاد عدد كاف(مناسب) من المجموعات.
أحد أبرز ميزات هذه الخوارزمية، هي أنها أكثر فعالية من الخوارزميات التي ذكرت سابقا، كما أنها الأسرع في تشكيل المجموعات.
ال(Cross Validation) هو عبارة عن عمليات حسابية واحصائية لتقسيم البيانات والعينات (samples) الى مجموعات فرعية. ويتم اجراء عملية التحليل في البداية على مجموعة فرعية واحدة، في حين نحتفظ بالمجموعات الفرعية الاخرى لاستخدامها لاحقا للتأكد من صحة التحليل الاولي .
المجموعة الفرعية الاولى يطلق عليها مجموعة التدريب(training set )، والمجموعات الفرعية الاخرى يطلق عليها مجموعات الاختبار والتحقق (testing and validation ).
المشكلة في استخدام الطرق السابقة انها لاتعطي مؤشرا عن كيفية تصرف المعلم (Learner)، عندما يطلب منه التنبؤ حول البيانات التي لم تكن جاهزة حتى الان. لاتقوم بعمليه التعميم لجميع البيانات المستقبليه (not generalized).
يمكن التغلب على هذه المشكلة من خلال عدم استخدام مجموعة البيانات بالكامل في عمليه التدريب، بعض البيانات نقوم بحذفها قبل اجراء عملية التدريب، وبعد اجراء عملية التدريب، البيانات التي تم حذفها يتم استخدامها في عملية الاختبار، وذلك لحساب الأداء (performance )، وهذه هي الفكرة الرئيسية لل(Cross validation).
انواع ال(Regression)
(linear regression)
سمي بالخطي لان العلاقة بين كل من المتغير x والمتغير y هي خطية، في هذه الحالة يتم محاولة ايجاد خط يصنف حميع نقاط البيانات.
(Quadratic regression)
سمي بذلك لانه متعلق بالمعادلات التربيعية من الدرجة الثانية، ويمثل منحنى يصنف نقاط بيانات معينة، ويحقق نتائج أفضل من ال(Linear regression). (Piecewise linear nonparametric regression)
في هذا النوع يتم تصنيف نقاط البيانات حسب وجودها في مستوى البيانات، والمشكلة في هذه الطريقة أنها صعبة التطبيق، كما أنه لا يمكن تعميمها لجميع البيانات، لان جميع البيانات تستخدم في عملية التدريب.
الشكل2.1: انواع ال(Regression)، (أ) (linear regression)، (ب) (Quadratic regression)، (ج)(Piecewise linear nonparametric regression)
طرق ال(Cross Validation)
هي من ابسط الطرق المستخدمة في ال(Cross Validation)، حيث أن البيانات تقسم إلى مجموعتين، المجموعة الأولى تستخدم للتدريب والثانية للاختبار، وبعد ذلك يتم تحديد ال(Regression) وفقا للبيانات المستخدمة في عملية التدريب، بعد ذلك ينكن تخمين أداء هذه الطريقة وتحديد نسبة الخطأ(error) من خلال البيانات المستخدة للاختبار.
ملاحظه: هناك اختلاف وتباين كبير في تقييم طرق ال(Cross Validation)، ويعتمد ذلك على نوع النقاط التي تم اختيارها في عملية التدريب والاختبار والطريقة التي يتم فيها تقسيم البيانات .
ميزاتها:
•بسيطة التنفيذ.
•لا تحتاج إلى وقت كبير في عمليه الحساب.
سيئاتها:
•تضيع جزء من بيانات التدريب، حيث يتم الزالة 30% من البيانات واستخدامها في عملية الاختبار .
طريقة عمل الخوارزمية
•اختيار 30% من البيانات بشكل عشوائي لاستخدامها في عملية الاختبار.
•استخدام كا تبقى من البيانات في عملية التدريب.
•اجراء عملية ال(regression).
•تخمين وحساب الاداء المستقبلي للعمليه بناء على البيانات المستخدمه في عمليه الاختبار.
الخطوه الاولى والثانيه:
كما يظهر لدينا في الشكل 2.2 أن النقاط باللون الاحمر تستخدم للاختبار. والنقاط باللون الازرق تستخدم للتدريب.
الخطوه الثالثه:
اجراء عملية (Regression) على مجموعة البيانات المستخدمة للتدريب، لاحظ وجود خط التصنيف الأخضر في الشكل 2.3.
الخطوه الرابعه:
تخمين أداء هذه الطريقة من خلال النقاط المستخدمة في عملية الاختبار. يمكننا بعد ذلك حساب نسبة الخطأ (Mean Square Error) لمعرفه أي من الطرق أفضل في استخدامها.
من خلال تطبيق الخطوات السابقة على أنواع ال(Regression) الأخرى يتبين لدينا ما يلي:
عند مقارنة نتائج الأنواع الثلاثة يتبين ان الخطأ عند ال(Quadratic regression) اقل شيء وهنا نعتبرها الافضل.
ملاحظه: عند تكرار العملية على نقاط اخرى لايشترط ان تكون النتيجة كما سبقت وانما من الممكن ان تختلف بناءا على طريقة تقسيم البيانات بين مجموعتي التدريب والاختبار.
الفكرة الرئيسية من هذه الطريقة هو أننا نقوم بالتدريب عدة مرات باستخدام كل النقاط، باستثناء نقطة واحدة تستخدم للاختبار، وفي كل مرة يتم استخدام نقطة أخرى لعملية الاختبار.
طريقة عمل الخوارزمية:
•لكل عينة k في المجموعة R.
•نقوم بحذف احداثيات النقطه (Xk ،Yk) من المجموعة.
•نقوم بعمليه التدريب على باقي النقاط في المجموعة.
•نقوم بحساب الخطأ (MSE) الناتج من هذه النقطه (Xk ،Yk).
•نقوم بتكرار من 1 – 4 لكل النقاط الموجوده في المجموعه R.
الخطوة الاولى:
كما نرى في الشكل 2.5، النقطة باللون الأحمر تمثل نقطة الاختبار.
الخطوة الثانية:
حذف احداثيات النقطة (Xk ،Yk) من المجموعة R قبل القيام بعملية التدريب، كما في الشكل 2.6.
الخطوة الثالثة:
نقوم بعملية التدريب على النقاط المتبقية في المجموعة R ، كما يظهر في الشكل 2.7.
الخطوة الرابعة:
حساب نسبة الخطأ (MSE) الناتج من النقطه (Xk ،Yk)، لاحظ الشكل 2.8.
الخطوة الخامسة:
•تكرار الخطوات الأربعة (1 – 4 ) لكل النقاط الموجودة في المجموعة R كما هو في الشكل 2.9.
•حساب الخطأ (MSE) الناتج من جميع النقاط.
تكرار الخطوات على الانواع لاخرى من ال(Regression)
عند المقارنه بين الطرق الثلاثه تبين ان اقل نسبة خطأ هوعند استخدام ال(LinearRegression)، وهي الافضل في عمليه التدريب.
ميزات استخدام ال(Leave one out):
•لاتضيع أي جزء من البيانات عند اجراء عمليه التدريب لان نقطه واحده تستخدم في عمليه الاحتبار في كل مرة.
سيائتها:
•عمليه تطبيق هذه الطريقة مكلفه مقارنه بالطرق الاخرى، لأنه يتم تكرار العمليات الحسابية عدة مرات بناءا على عدد النقاط.
3. (K-fold Cross Validation)
خلال هذه الطريقة يتم تقسيم البيانات بشكل عشوائي إلى k من المجموعات ومن ثم عملية التدريب لعدد k من المرات باستخدام جميع النقاط الموجوده باستثناء المجموعة k.
خطوات عمل الخوارزمية:
•تقسيم البيانات بشكل عشوائي إلى K من المجموعات.
•لكل مجوعه نقوم بالتدريب باستخدام كل النقاط التي لاتنتمي إلى هذه المجموعة.
•حساب مجموع نسبة الخطأ في هذه المجموعة.
•تكرار الخطوات من 2- 3 حتى ننتهي من جميع المجموعات.
•حساب الوسط(الmean) للمجموع الكلي للخطأ من كل المجموعات.
الخطوة الاولى:
تقسيم البيانات بشكل عشوائي إلى Kمن المجموعات.
في هذا المثال يتم تقسيم البيانات إلى ثلاث مجموعات، كما يظهر في الشكل 2.12.
المجموعه الاولى : اللون الاحمر المجموعه الثانيه : اللون الازرق المجموعه الثالثه : اللون الاخضر
الخطوة الثانية والثالثة:
في هذه المرحلة يتم تدريب جميع النقاط التي لا تنتمي إلى اللون الاحمر، كما هو في الشكل 2.13. حساب نسبة الخطأ في هذه المجموعة.
الخطوه الرابعة:
تكرار الخطوة الثانية والثالثة حتى ننتهي من جميع المجموعات، كما هو في الشكل 2.14.
الخطوه الخامسة:
حساب الوسط للمجموع نسب الخطأ لكل المجموعات.
عند تطبيق هذه الخوارزمية على ال((Piecewise linear nonparametric regression وال((quadratic regression فإن نسب الخطأ تكون كما يلي:
بعد المقارنه بين الطرق الثلاثه تبين ان اقل نسبة خطأ هوعند استخدام ال(Quadratic regression)، وهي الافضل في عمليه التدريب
ميزات استخدام ال(K-fold cross validation)
•اذا تم اختيار القيمه الصحيحه للمتغير k ، فانه يقلل استخدام البيانات في عملية الاختبار مقارنه مع ال(test set method)، ويقلل من التكلفه مقارنه مع ال(leave one out method).
ملاحظة:
لايوجد نظرية ثابتة لاختيار قيمه k، لكن الشائع هو اختيار k=10.
مخطط تنيفذ خوارزمية K-fold cross validation
هي عبارة عن طريقه تستخدم لحل المشكلات التي تحتوي على بيانات كبيره, كما أنها احدى الطرق التي تستخدم في حل المشكلات بشكل عام . حيث تعتمد هذه الطريقه على المبدأ الأساسي في تزاوج الجينات.
تقوم هذه الطريقه باختيار عينات من مشكله معينه والقيام بعمليه تزاوج بين هذه العينات, وهناك نوعان من عمليات التزاوج, احداهما خلط الجينات مع بعضها البعض من الاباء(Crossover) والثاني هو تغيير في الجينات لاحداث طفره (Mutation).
تتم عمليه التنفيذ من خلال ثلاثة مراحل(operator): تتم على أساس الانتقاء الطبيعي للعينات الاوليه.
1-عمليه الاختيار (selection)
وهي عمليه اختيار العينات ال بسبب وجود مجموعه من الكروموسامات الضعيفة وأخرى قوية ، فإن وجود الفرد أو عدمه يعتمد على ال(fitness function)
2-عمليه الخلط(crossover)
عمليه خلط ودمج بين اثنين من الآباء وذلك لإنتاج طفل جديد بمواصفات محسنه, وعاده تكون عمليه اختيار نقطه التقسيم عشوائية من خلال عملية تبادل الكروموسومات. في هذه العمليه يتم اختيار فردين من العينات الاوليه (initial population) التي تم اختيارها في الخطوه الاولى.
-إذا وجد لدينا
س1= 000000 و س2=111111
-فان ناتج عمليه الخلط
س1َ = 110000 و س2َ= 001111
وتكون النتيجة من هذه العملية (طفلين جديدين) وتدخل هذه العينة الجيل التالي لل(population)
-باعاده التزاوج بين الوالدين تكون العينات الجديدة أفضل من العينات القديمة.
-مثال على عمليه التزاوج
الوالد الأول
الوالد الثاني
الطفل الأول
3-الطفرة(Mutation)
عمليه تغير في بعض الكر وموسومات لوالد معين وإنتاج طفل جديد وهذه عمليه تسمى طفرة لان الطفل هو جديد لايحمل صفات من الأب أو الام
قبل إجراء عمليهMutation
بعد اجراء عمليه Mutation
ما هي طريقه عمل ألخوارزميه الجينية ؟
1-اختيار عينات(population) بشكل عشوائي
2-تحديد مايسمي (fitness) لهذه العينات وتكون باختيار علاقه معينه لحساب والتحكم من يعيش من هذه الكروموسامات ومن لايعيش
3-اختيار الوالدين(parent) من هذه العينات
4-إجراء عمليه(crossover) وهي عمليه الدمج والتزاوج لإنشاء جيل جديد من الأطفال(children) أي عينات جديدة منpopulation
5-إجراء عمليه (mutation) أي ما يسمى بالطفره على الأولاد
6-يتم حساب ( (fitness لهذه الأطفال
7-يتم اعاده إجراء الخطوات من 4-6 حتى الوصول إلى الحل الامثل(optimal )
ملاحظه:
•الكروموسوم ممكن ان يكون :-
-مجمعه من الخانات (Bit) :- الارقام الثنائيه (Binary number) أي 010.....1100
-الاعداد الحقيقه (Real number) : 43.3 -33 0.0
-تكرار من العناصر (permutation of element) : E11E3 E7 E1E15
•في البدايه يكون العمل على العينه (عينات يتم اختيارها) وليس على كل العينات
•نقوم بالتأكد من العينة الجديدة (الأطفال) سواء إذا كانت العينة ضمن الحل لهذه المشكلة أو لا عن طريق ما يسمى fitness function
fitness function
.هي التي تتحكم هل هذا الكروموسوم قوي أو ضعيف ونقوم بتحديها في البدايه
•في الجينات ليس بالضروري ان تكون العينه الناتجه هي الحل للمشكله بشكل نهائي (optimal) ولكن ممكن ان تكون قريبه من الحل او لا
•هناك أطفال لا علاقة لهم بالحل أي بعدين عن الحل الصحيح نقوم بعمليه تزاوج بينهم مره اخرى حتى نصل الحل القريب او النهائي
أمثله من الواقع على الخوارزميات الوراثيه
1-مشكله البائع المتجول (Traveling Salesman Problem TSP )
-وضعت الخوارزميات الجينية الحل لمشكلة البائع المتجول والهدف من ذلك هو إيجاد اقصر مسافة بين (س) مدن مختلفة.
-لو افترضنا ما يلي :-
•انوه يوجد (س) من المدن وفحص هذه المدن في الحل تكون عن طريق الاحتمالات وهذا يوجب حساب مضروب س (س!)
•لو افترضنا انه لدينا 30 جولة من المدن فعلينا حساب المجموع الكلي للمسافات أي 2.65*1032 من الجولات المختلة ولو افترضنا مليارات اضافيه من الثواني (second) واضافه مدينه جديده يسبب استهلال الوقت الكثير من الوقت من الحساب أي حساب مضروب 31 وهذا رقم كبير كثير وهذه مهمه مستحيله الحل
-الخوارزميات الوراثية يمكن استخدامها لإيجاد الحل بوقت اقل بكثير ورغم أنها لا تجد الحل الأمثل . ولكن تجد الحل الأمثل تقريبا 100 جولة باقل من دقيقه هناك بضع خطوات اساسية لحل مشكلة البائع المتجول
أولا : تشكيل وإنشاء مجموعه عشوائية من الجولات أو ما يسمي (population) والافضليه لربط المدن التي تكون قريبه من بعضها البعض
ثانيا: اختيار أفضل 2 من الأقصر جوالات من (population) وإجراء عمليه الجمع بينهم لإنشاء 2 طفل جديد من الجولات وتكون أفضل من الأول (الوالدين التي تم اختيارهم في البداية) ،
•وهنا نقوم بإجراء عمليه (mutated) على الجولات الجديدة أي الأطفال (new Children tour)ونقوم بعمل ذلك لمنع من وجود تماثل وتشابه بين كل الجولات
•والاطفال الجديده (new Children tour) نقوم بادخالها إلى (population) وذلك محل الجولات الطويله التي تاخد مسافه كبيره ووقت أكبر
•ونقوم بتكرار العملية أي إنشاء أطفال حتى الوصول إلي الهدف المرجو من العملية وهو المسافات الأقصر
•ومن القضايا المعقدة في الخوارزميات الوراثيه لحل مشكله البائع المتجول هي التشفير والترميز (encoding ) للجولات وإجراء عمليه الدمج الخلط(crossover)بينهم التي تستخدم والدين لإنشاء طفلين جديدين
• في الخوارزميات الوراثية يكون التشفير هو عبارة عن مجرد سلسله من الاعداد وعمليه الدمج والخلط تكون باختيار عشوائي نقطه فصل وتقاطع بين الأبوين . وفي هذه المثال نقطه التقاطع بين الثالثة والرابعة
الوالد الأول F A B | E C G D
الوالد الثاني D E A | C G B F
الطفل الأول F A B | C G B F
الطفل الثاني D E A | E C G D
•الصعوبة في مشكله البائع المتجول أن كل مدينه يجب أن تستخدم مره واحده فقط في الجولات
•إذا الحرف (Letters) المستخدم في المثال يمثل المدن ، الطفل الجديد المكون من خلال عمليه الدمج تكون خطأ لان الطفل الأول يذهب إلى المدن F و B مرتين ولايذهب إلى المدن D و E