ستساعدك المقالة التالية: كيف يمكن للخوارزميات التطورية تحسين الفرز؟
يتم فرز مجموعة غير مرتبة من العناصر عن طريق وضعها بترتيب تصاعدي (أو تنازلي) رتيب. تتطلب كفاءة فرز مجموعات البيانات الضخمة ، من حيث الوقت والذاكرة المستخدمة ، تطورات في خوارزميات الفرز وتطبيقاتها في الحوسبة الحديثة. يمكن استخدام نماذج التعلم الآلي لتحسين خوارزميات الفرز هذه. من خلال تحليل البيانات التجريبية ، يتيح التعلم الآلي إنشاء خوارزميات قابلة للتكيف. من أجل اختيار خوارزمية اعتمادًا على خصائص مجموعة البيانات ، تستعرض هذه المقالة الخوارزميات التطورية. فيما يلي المواضيع التي سيتم تناولها.
جدول المحتويات
- الفرز في التعلم الآلي
- الخوارزميات الجينية المستخدمة لتحسين الفرز
- مزايا استخدام الخوارزمية الجينية
منذ فجر أجهزة الكمبيوتر ، لفت التصنيف الانتباه باعتباره نشاطًا أساسيًا للبيانات. دعونا نفهم خوارزميات الفرز.
الفرز في التعلم الآلي
تتضمن عملية الفرز وضع البيانات بترتيب معين. تحدد خوارزمية الفرز تقنية ترتيب البيانات بترتيب معين. قد يكون البحث عن البيانات عالي الكفاءة عند الاحتفاظ بالبيانات بطريقة مرتبة ، وهذا هو سبب أهمية الفرز. يمثل تمثيل البيانات بطرق أكثر قابلية للفهم استخدامًا آخر للفرز.
قد تحتاج خوارزميات فرز البيانات إلى مساحة أكبر قليلاً للمقارنة والتخزين قصير المدى لبعض مكونات البيانات. يُزعم أن هذه الخوارزميات تُفرز في مكانها ، على سبيل المثال ، داخل المصفوفة نفسها ، ولا تشغل أي مساحة إضافية. يشار إليه بالفرز الموضعي. مثال على الفرز الموضعي هو نوع الفقاعة. ولكن بالنسبة لبعض خوارزميات الفرز ، فإن مقدار المساحة التي يستخدمها البرنامج أكبر من أو يساوي عدد العناصر المراد فرزها. يُعرَّف الفرز غير الموضعي بأنه الفرز مع احتياج مساحة أكبر أو مساوية. مثال على الفرز غير في المكان هو دمج الفرز.
بناءً على التأثيرات بعد فرز البيانات ، يتم تصنيف خوارزميات الفرز هذه على أنها مستقرة وغير مستقرة. على سبيل المثال ، عندما نرغب في الحفاظ على تسلسل العناصر في tuple ، فإن استقرار الخوارزمية مهم.
إذا كانت خوارزمية الفرز تستخدم عناصر تم “فرزها” مسبقًا في القائمة التي يجب فرزها ، فيُقال إنها قابلة للتكيف. بمعنى آخر ، أثناء الفرز ، ستهدف الخوارزميات التكيفية إلى تجنب إعادة ترتيب العناصر إذا كانت قائمة المصادر تحتوي بالفعل على جزء منها مرتبة. يقال إن الخوارزمية التي تتجاهل العناصر التي تم فرزها مسبقًا غير قابلة للتكيف. للتأكد من أن العناصر مرتبة بشكل صحيح ، فإنهم يحاولون دفع كل عنصر إلى ترتيب جديد.
لماذا التحسين مطلوب؟
على الرغم من أن تحسين البرنامج قد تم أتمتة بشكل كبير بواسطة تقنية المترجم ، إلا أنه لا يزال هناك الكثير من المشاركة البشرية لإنتاج كود عالي الجودة. هناك سببان لهذا التأكيد:
- عمليات التنفيذ غير المتسقة للمترجمين.
- لا تحتوي برامج التحويل البرمجي التقليدية على معلومات دلالية ، مما يحد من قدرتها على تغيير البيانات.
تحقق من هنا
الخوارزميات الجينية المستخدمة لتحسين الفرز
لا يمكن إيجاد الخوارزمية المثلى إلا من خلال البحث لعدم وجود نماذج تحليلية لأداء خوارزميات الفرز من حيث المعلمات المعمارية للآلة. بالإضافة إلى ذلك ، استند البحث السابق حول تصنيف التعقيد إلى الافتراض الخاطئ بأن الوصول إلى كل قطعة يستغرق نفس القدر من الوقت بالنظر إلى التكنولوجيا الحديثة.
في الخوارزمية الجينية ، تحدد قيم المعلمات لأساسيات الفرز والاختيار ، بالإضافة إلى تكوينها ، مساحة البحث. الهدف من البحث هو العثور على الفرز الهرمي الذي يناسب الميزات المعمارية للجهاز وخصائص مجموعة الإدخال.
يمثل التشابه بين التركيب الجيني وسلوك الكروموسومات في السكان أساسًا للخوارزميات الجينية. أساس GAs على أساس هذه المقارنة هو كما يلي.
- يتنافس أفراد السكان على الموارد ويتزاوجون.
- ثم يتزاوج الأفراد المتعاقبون (الأصلح) لإنجاب عدد أكبر من الأطفال مقارنة بالأفراد الآخرين.
- ينجب الآباء أحيانًا أطفالًا أفضل من أي من الوالدين ؛ وذلك لأن الجينات من الآباء “الأصلح” تنتشر عبر الجيل.
- نتيجة لذلك ، يصبح كل جيل قادم أكثر صداقة للبيئة.
يتم استخدام أساسيات الفرز والاختيار كعقد قائمة على الشجرة في المخطط. لإنشاء أطفال جدد وتغيير السكان ، يتم استخدام عوامل وراثية. العمليتان اللتان تستخدمهما غالبية الخوارزميات الجينية هما التقاطع والطفرة.
عبور
يتم تداول الأشجار الفرعية من مختلف الأشجار أثناء العبور. هدف Crossover هو إنتاج ذرية جديدة تؤدي أداءً أفضل من والديهم. عندما يرث الأطفال الجدد أفضل الأشجار الفرعية من الوالدين ، فمن المحتمل أن يحدث هذا. في معظم الحالات ، يتم استخدام نقطة تقاطع واحدة ، مع اختيار نقطة التقاطع عشوائيًا.
طفره
يقوم هذا المشغل بإجراء تعديلات على شجرة واحدة فقط. يعطي تباين السكان. لا يمكن أن يظل السكان كما هو بعد أي جيل معين بسبب الطفرة. تسمح هذه الاستراتيجية للبحث بالهروب جزئيًا من أوبتيما المحلية. في محاولة لتحديد قيم أفضل ، تعدل الطفرة قيم المعلمات. التعديلات التالية ممكنة مع عامل الطفرة:
- قم بتغيير قيم المعلمات بشكل عشوائي عند فرز واختيار العقد الأساسية.
- Switch شجرتين فرعيتين.
- بما في ذلك شجرة فرعية جديدة.
- خذ شجرة فرعية. باستخدام هذه التقنية ، يمكن التخلص من الأشجار الفرعية غير الضرورية.
وظيفة اللياقة البدنية
يتم تحديد احتمالية تكاثر الفرد من خلال وظيفة اللياقة البدنية. تزداد احتمالية تكاثر الكائن الحي وتطوره مع اللياقة. ستكون وظيفة اللياقة هي الأداء. ولكن عند تصميم وظيفة اللياقة ، تم أخذ العاملين التاليين في الاعتبار:
- الهدف هو خوارزمية الفرز التي تعمل بشكل جيد مع جميع المدخلات المحتملة. لذلك ، فإن اللياقة الأساسية للشجرة هي متوسط أدائها. يتم تعيين عقوبة على الأشجار ذات الأداء المتغير عن طريق زيادة الملاءمة الأساسية برقم يعتمد على الانحراف المعياري لأدائها أثناء فرز مدخلات الاختبار ؛ ومع ذلك ، فإن خوارزمية الفرز يجب أن تعمل بشكل جيد باستمرار عبر المدخلات هي أيضًا هدف.
- تباين اللياقة البدنية للسكان مهم في الأجيال الأولى. بمعنى آخر ، تعمل بعض أشجار الفرز بشكل أفضل من غيرها. نظرًا لأن هذه الأشجار القليلة لديها احتمالية أكبر للتكاثر ، فإن معظم الأطفال سيكونون أحفادهم إذا كانت وظيفة اللياقة البدنية لدينا تتناسب بشكل مباشر مع أداء الشجرة. هؤلاء المتحدرين سيشكلون في النهاية غالبية السكان. قد ينشأ تقارب سابق لأوانه من هذا ، مما قد يقيد الخوارزمية من التحقيق في أجزاء من مساحة البحث خارج المنطقة المجاورة للأشجار المناسبة للغاية. لحل هذه المشكلة ، تستفيد وظيفة اللياقة لدينا من ترتيب الأداء أو ترتيب أشجار فرز السكان. يتم تجاهل الفرق المطلق في الأداء بين الأشجار عند تطبيق تصنيف الأداء ، وبالتالي ، فإن الأشجار ذات الأداء المنخفض لديها احتمالية أعلى للتكاثر من الأشجار ذات الأداء العالي. هذا يلغي مسألة التقارب المبكر والتقارب إلى المستوى الأمثل المحلي.
مزايا وعيوب استخدام الخوارزميات الجينية
هناك بعض فوائد استخدام الخوارزميات الجينية على طرق التحسين الأخرى.
- يمكن التعبير عن خوارزميات الفرز في شكل شجرة باستخدام العناصر الأولية ، حيث تمثل كل بدائية عقدة. نتيجة لذلك ، يمكن استخدام الخوارزميات الجينية ببساطة لاستكشاف عالم الأشجار المحتملة للحصول على أفضل بنية شجرة وقيم المعلمات المرتبطة بكل عقدة.
- تحافظ الخوارزميات الجينية على أفضل الأشجار الفرعية وتزيد من فرصها في التكاثر. نظرًا لأن الشجرة الفرعية هي أيضًا خوارزمية فرز ، يمكن لخوارزميات الفرز الاستفادة من ذلك.
تعد الخوارزمية الجينية أداة واعدة لحل المشكلات ، ولكن بها بعض العيوب التي قد تؤدي إلى عدم الكفاءة.
- من الصعب ضبط الإعدادات بدقة. إنه يستلزم تحديد العديد من المعلمات مثل حجم السكان ومعدل الطفرة ومدة التشغيل القصوى ، بالإضافة إلى إنشاء خوارزميات للاختيار وإعادة التركيب والطفرة. إن العثور على بدائل قابلة للتطبيق لهذه مهمة صعبة مع القليل من الدعم النظري أو بدونه.
- ليس هناك ما يضمن حدوث تقارب. ليس هناك ما يضمن أن الخوارزمية ستعثر على أفضل مستوى عالمي. من الممكن أن يتم القبض عليه في واحدة من أوبتيما المحلية.
خاتمة
يعد اختيار خوارزمية التطور المناسبة قرارًا حاسمًا. تحدد خوارزمية التطور عدد الأطفال الذين سيتم إنتاجهم ، وعدد أعضاء الجيل الحالي الذين سيتم استبدالهم ، وما إلى ذلك. من خلال هذه المقالة ، فهمنا متطلبات التحسين في الفرز واستخدام GA لتحسين خوارزميات الفرز.
