المسرد · method
الخوارزمية الجينية
ميتاهيوريستيك قائم على السكان يحاكي الانتقاء الطبيعي والتوريث الجيني، ويُطور مجموعة من الحلول المرشحة بشكل تكراري عبر عمليات الانتقاء والتقاطع والطفرة.
Genetic AlgorithmGAالخوارزمية التطوريةEvolutionary Algorithmميتاهيوريستيك قائم على السكان
الخوارزمية الجينية قدمها هولاند (1975) ونشرها على نطاق واسع غولدبيرغ (1989)، وهي ميتاهيوريستيك قائم على السكان. تحتفظ الخوارزمية بعدة حلول مرشحة (أفراد) في آن واحد؛ يُرمَّز كل فرد ككروموسوم (ثنائي، صحيح، تبديل، أو قيمة حقيقية). تطبق كل تكرار ثلاث عمليات جوهرية: الانتقاء (عجلة الروليت، البطولة، الترتيب)، التقاطع (نقطة واحدة، عدة نقاط، موحد، PMX/OX للتبديلات)، والطفرة (قلب البت، التبديل، العكس). تُشتق دالة الملاءمة من الدالة الهدف وتقود ضغط الانتقاء. تحافظ النخبوية (Elitism) على أفضل الأفراد، وآليات التنوع (niching، crowding) تمنع التقارب المبكر. ترتكز نظرية التقارب على نظرية المخططات (هولاند 1975)، بينما يُظهر نظرية No Free Lunch (وولبرت وماكريدي 1997) أن لا ميتاهيوريستيك يهيمن على جميع المسائل. التمديد متعدد الأهداف NSGA-II (ديب براتاب أغاروال مياريفان 2002) هو المعيار الصناعي لتقريب جبهة باريتو. تتطلب مسائل التبديل (TSP، الجدولة) عمليات متخصصة. لا تضمن الخوارزمية الجينية الأمثلية العالمية لكنها تقدم حلولًا جيدة في وقت معقول وتُفضَّل للمسائل التوافقية والصحيحة المختلطة والصندوق الأسود. مراجع: غولدبيرغ (1989)، أيبن وسميث (2015).
Örnek
ورشة أثاث بها 30 مهمة على 6 آلات تبحث عن ترتيب يقلل زمن الإنجاز الكلي (makespan). تستغرق البرمجة الصحيحة الدقيقة ساعات في الحالات الكبيرة؛ خوارزمية جينية بحجم سكان 80، ترميز التبديل، تقاطع OX، وطفرة التبديل تصل في 200 جيل و14 دقيقة إلى makespan أقل بنسبة 22 بالمئة من الهيوريستيك الابتدائي. الحل ليس مثبتًا أنه الأمثل لكنه جيد بما يكفي للجدولة اليومية وقابل للتطبيق من قِبل مخطط الورشة.