خوارزميات تعلم الآلة

هناك عدة طرق تستخدم في تعليم الآلة. في هذا المقال نستعرض بعضا منها. ملاحظه أن بعض الصور المستخدمة لا تتبع حقوق الطبع والنشر ونحن نعتذر لذلك ولكن استخدمت لغرض المعرفة العلمية.

عنقدة البيانات (Data clustering)

عنقدة البيانات هي عملية وضع البينات في مجموعات متماثلة. خوارزمية العنقدة تقسم مجموعة من البيانات إلى عدة مجموعات. حيث أن التشابه بين النقاط ضمن مجموعة معينة أكبر من التشابه بين نقطتين ضمن مجموعتين مختلفتين. فكره تجمع البيانات هي فكره بسيطه في طبيعتها وهي قريبه جدا من الإنسان في طريقه تفكيره حيث اننا كلما تعاملنا مع كمية كبيرة من البيانات نميل إلى تلخيص الكم الهائل من البيانات إلى عدد قليل من المجموعات اوالفئات، وذلك من أجل تسهيل عمليه التحليل.خوارزميات التجمع تستخدم على نطاق واسع ليس فقط لتنظيم وتصنيف البيانات وانما هي مفيده لضغط البيانات وبناء نموذج ترتيب البيانات. حيث أنه إذا كان بإمكاننا أن نجد مجموعات من البيانات، فانه بالإمكان بناء نموذج للمشكلة على أساس تلك المجموعات. تسمی هذه الخوازميات بتحليل العناقيد

هناك عدد من التقنيات المستخدمة في عملية تجميع البيانات، ومن هذه التقنيات (الخوارزميات) التي سوف يتم الحديث عنها بشكل مفصل:

خوارزمية العنقدة بالوسطاء المتعددين (K-means Clustering)

هي خوارزميه لجمع عدد من البيانات استادا إلى خصائص وسمات هذه البيانات، وتتم عمليه التجميع من خلال تقليل المسافات بين البيانات ومركز التجمع (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 ومركز التجمع الأول هي: والمسافة بين نفس الدواء ومركز التجمع الثاني هي: 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)

ال (Fuzzy C-means Clustering) تعتمد على الفكرة الأساسية من ال (k-means Clustering)، مع فارق واحد هو أن في ال (FCM) كل نقطة بيانات تنتمي إلى مجموعة على درجة من عضوية الصف، في حين أن كل نقطة بيانات في ال (KM) اما أن تنتمي المجموعة أو لا تنتمي.

توظف ال (FCM) تقسيم عشوائي (ضبابي)، كما أنه يمكن لنقطة معينة أن تنتمي لعدة مجموعات مع درجة من الانتماء التي يحددها عضوية الصفوف بين 0 و 1.

يسمح لمصفوفة العضوية (U) أن تكون فيها قيم العناصربين 0 و 1. مع ذلك، حاصل جمع درجات انتماء نقطة بيانات لجميع المجموعات دائما يعادل:

كما أن ال (Cost Function) لل (FCM) هو:.

حيث أن uij تكون بين 0 و 1، ci هي عبارة عن مركز التجمع في المجموعة الضبابية i، هي المسافة الاقليدية بين مركز التجمع i ونقطة البيانات j، كما أن هي عبارة عن (weighting exponent).

هنالك شروط ضرورية لايصال ال (Cost Function) للحد الأدنى وهي:

تعمل هذه الخوارزمية بشكل متكررمن خلال الشرطين السابقين إلى أن لا يلاحظ أي تحسن. في عملية (batch mode)، تحدد ال (FCM) مراكز التجمع ci ومصفوفة العضوية U باستخدام الخطوات التالية:

1. وضع قيم ابتدائية عشوائية بين 0 و 1 في عناصر مصفوفة العضوية U
2. حساب مراكز التجمع الضبابي ci، حيث أن i=1,……..,c.
3. حساب ال (Cost Function). ويتم التوقف اما إذا كانت نتيجة ال (Cost Function) ما دون قيمة تحمل معينة، أو أن التحسن في تلك النتيجة من خلال التكرار السابق ما دون حد معين.
4. حساب مصفوفة العضوية الجديدة U باستخدام المعادلة التالية:

كما هو الحال في ال (KM)، يعتمد أداء ال (FCM) على قيم مصفوفة العضوية الابتدائية؛ فمن المستحسن أن تنفذ هذه الخوارزمية عدة مرات، في كل مرة تكون البداية بقيم نقاط بيانات مختلف

خوارزمية عنقدة التجمعات أو الجبل (Mountain Clustering)

(Mountain Clustering)هي طريقة بسيطة لإيجاد مراكز التجمعات بالاعتماد على حساب الكثافة من خلال ما يدعى بال (Mountain Function). كما يمكن استخدام هذه الطريقة لإيجاد مراكز التجمعات بشكل تقريبي، مما يسهل استخدامها كوسيلة ابتدائية قبل الدخول في مراحل تجميع أكثر تعقيدا.

في المرحلة الأولى من ال (Mountain Clustering) يتم تشكيل شبكة على البيانات في المستوى الديكارتي، حيث أن التقاطعات بين خطوط هذه الشبكة تشكل مراكز المجموعات.

المرحلة الثانية، يتم تتابع بناء ال (MF) والذي يمثل قياس كثافة البيانات. ذروة (ارتفاع) ال (MF) عند النقطة v؟V تعادل

حيث أن xi هي نقطة i من البيانات، وs هو ثابت تطبيقي محدد، يتبين من المعادلة السابقة أن قياس كثافة البيانات يتأثر بكل النقاط xi في مجموعة البيانات، وقياس كثافة البيانات يتناسب عكسيا مع المسافة بين نقاط البيانات xiو النقطة الموجودة في الv(MF. الثابت يحدد الذروة والانحدار لل (MF) الناتج.

المرحلة الثالثة تنطوي على اختيار مراكز التجمعات عن طريق هدم ال (MF) بشكل تسلسلي. يحدد مركز التجمع الأول ci من خلال اختيار النقطة التي لها أعلى قياس للكثافة. يتم تحديد مركز التجمع الثاني من خلال القضاء على تأثير التجمع الأول. ويتم ذلك من خلال إعادة تشكيل ال (MF)، ويتم تشكيل ال (MF) الجديد من خلال

القيمة الطروحة في المعادلة السابقة تزيل أثر المجموعة الأولى. من الملاحظ أن بعد عملية الطرح تقل قيمة ال (MF) الجديدة mnew(v) لتصل إلى الصفر عند v=c1.

بعد عملية الطرح، يتم اختيار مركز المجموعة الثانية من خلال تحديد النقطة التي يكون عندها أعلى قيمة لل(MF)الجديدة. تستمر هذه العملية حتى يتم تحديد عدد كاف من مراكز التجمع.

خوارزمية ال (Subtractive Clustering)

المشكلة في طريقة التجمع السابقة (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. ثم تبحث الخوارزمية عن مركز جديد، وذلك عن طريق حساب قيم الكثافة للنقاط الأخرى_كما في المعادلة الثانية_، وتستمر هذه العملية حتى الانتهاء من كل النقاط، أو إيجاد عدد كاف (مناسب) من المجموعات.

أحد أبرز ميزات هذه الخوارزمية، هي أنها أكثر فعالية من الخوارزميات التي ذكرت سابقا، كما أنها الأسرع في تشكيل المجموعات.

تقييم خوارزميات التعليم

تقییم خورازمیات التعلیم بالاشراف (Supervised Learning Evaluation)

ال (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)

التقييم بالتقسيم النسبي لمجموعة البيانات split validation

هي من ابسط الطرق المستخدمة في ال (Cross Validation)، حيث أن البيانات تقسم إلى مجموعتين، المجموعة الأولى تستخدم للتدريب والثانية للاختبار، وبعد ذلك يتم تحديد ال (Regression) وفقا للبيانات المستخدمة في عملية التدريب، بعد ذلك ينكن تخمين أداء هذه الطريقة وتحديد نسبة الخطأ(error) من خلال البيانات المستخدة للاختبار.

ملاحظه: هناك اختلاف وتباين كبير في تقييم طرق ال (Cross Validation)، ويعتمد ذلك على نوع النقاط التي تم اختيارها في عملية التدريب والاختبار والطريقة التي يتم فيها تقسيم البيانات.

ميزاتها:

1. بسيطة التنفيذ.
2. لا تحتاج إلى وقت كبير في عمليه الحساب.

سيئاتها:

تضيع جزء من بيانات التدريب، حيث يتم الزالة 30% من البيانات واستخدامها في عملية الاختبار.

طريقة عمل الخوارزمية

1. اختيار 30% من البيانات بشكل عشوائي لاستخدامها في عملية الاختبار.
2. استخدام كا تبقى من البيانات في عملية التدريب.
3. إجراء عملية ال (regression).
4. تخمين وحساب الأداء المستقبلي للعمليه بناء على البيانات المستخدمة في عمليه الاختبار.

الخطوة الأولى والثانية:

كما يظهر لدينا في الشكل 2.2 أن النقاط باللون الأحمر تستخدم للاختبار. والنقاط باللون الأزرق تستخدم للتدريب.

الخطوة الثالثة:

إجراء عملية (Regression) على مجموعة البيانات المستخدمة للتدريب، لاحظ وجود خط التصنيف الأخضر في الشكل 2.3.

الخطوة الرابعة:

تخمين أداء هذه الطريقة من خلال النقاط المستخدمة في عملية الاختبار. يمكننا بعد ذلك حساب نسبة الخطأ (Mean Square Error) لمعرفه أي من الطرق أفضل في استخدامها.

من خلال تطبيق الخطوات السابقة على أنواع ال (Regression) الأخرى يتبين لدينا ما يلي:

عند مقارنة نتائج الأنواع الثلاثة يتبين ان الخطأ عند ال (Quadratic regression) اقل شيء وهنا نعتبرها الأفضل.

ملاحظه: عند تكرار العملية على نقاط أخرى لايشترط ان تكون النتيجة كما سبقت وانما من الممكن ان تختلف بناء على طريقة تقسيم البيانات بين مجموعتي التدريب والاختبار.

ترك عنصر خارجا Leave one out

الفكرة الرئيسية من هذه الطريقة هو أننا نقوم بالتدريب عدة مرات باستخدام كل النقاط، باستثناء نقطة واحدة تستخدم للاختبار، وفي كل مرة يتم استخدام نقطة أخرى لعملية الاختبار.

طريقة عمل الخوارزمية:

•لكل عينة 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):

•لاتضيع أي جزء من البيانات عند إجراء عمليه التدريب لان نقطه واحده تستخدم في عمليه الاحتبار في كل مرة.

سيائتها:

•عمليه تطبيق هذه الطريقة مكلفه مقارنه بالطرق الأخرى، لأنه يتم تكرار العمليات الحسابية عدة مرات بناء على عدد النقاط.

التقییم باستخدام التحزيم المتشابك (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

الخوارزميات الوراثية (Genetic algorithm)

هي عبارة عن طريقه تستخدم لحل المشكلات التي تحتوي على بيانات كبيرة، كما أنها إحدى الطرق التي تستخدم في حل المشكلات عمومًا. حيث تعتمد هذه الطريقة على المبدأ الأساسي في تزاوج الجينات.

تقوم هذه الطريقة باختيار عينات من مشكله معينه والقيام بعمليه تزاوج بين هذه العينات، وهناك نوعان من عمليات التزاوج، إحداهما خلط الجينات مع بعضها البعض من الاباء(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

وصلات داخل ویکی

• تعليم الآلة
• تحليل العناقيد