الخوارزمية الجينية

الموسوعة الحرة

هوائي المركبة الفضائية ST5 التابعة لناسا لعام 2006. تم التوصل إلى هذا الشكل المعقد بواسطة برنامج تصميم حاسوبي تطوري لإنشاء أفضل نمط إشعاع. يُعرف هذا الهوائي باسم الهوائي المتطور .

الخوارزمية الجينية ( GA ) هي خوارزمية فوقية مستوحاة من عملية الانتقاء الطبيعي ، وتنتمي إلى فئة أوسع من الخوارزميات التطورية (EA) في علوم الحاسوب وبحوث العمليات . [ 1 ] تُستخدم الخوارزميات الجينية عادةً لتوليد حلول عالية الجودة لمسائل التحسين والبحث عبر عوامل مستوحاة من علم الأحياء ، مثل الانتقاء والتهجين والطفرة . [ 2 ] تشمل بعض الأمثلة على تطبيقات الخوارزميات الجينية تحسين أشجار القرار لتحسين الأداء، وحل ألغاز سودوكو ، [ 3 ] وتحسين المعلمات الفائقة ، والاستدلال السببي . [ 4 ]

المنهجية

مشاكل التحسين

في الخوارزمية الجينية، يتم تطوير مجموعة من الحلول المرشحة (تُسمى الأفراد أو الكائنات أو الأنماط الظاهرية ) لمسألة تحسينية نحو حلول أفضل. لكل حل مرشح مجموعة من الخصائص ( كروموسوماته أو نمطه الجيني ) التي يمكن تحويرها وتغييرها؛ تقليديًا، تُمثل الحلول بالنظام الثنائي كسلاسل من الأصفار والآحاد، ولكن توجد أيضًا ترميزات أخرى ممكنة. [ 5 ]

تبدأ عملية التطور عادةً من مجموعة من الأفراد المُولَّدين عشوائيًا، وهي عملية تكرارية ، حيث تُسمى المجموعة في كل تكرار " جيلًا" . في كل جيل، يتم تقييم كفاءة كل فرد في المجموعة؛ وعادةً ما تكون الكفاءة هي قيمة دالة الهدف في مسألة التحسين قيد الحل. يتم اختيار الأفراد الأكثر كفاءة عشوائيًا من المجموعة الحالية، ويتم تعديل جينوم كل فرد ( إعادة تركيبه وربما تحويره عشوائيًا) لتشكيل جيل جديد. ثم يُستخدم الجيل الجديد من الحلول المرشحة في التكرار التالي للخوارزمية . عادةً، تنتهي الخوارزمية عند الوصول إلى الحد الأقصى لعدد الأجيال، أو عند بلوغ مستوى كفاءة مُرضٍ للمجموعة.

تتطلب الخوارزمية الجينية النموذجية ما يلي:

  1. تمثيل جيني لمجال الحل،
  2. دالة لياقة لتقييم نطاق الحل.

يُمثَّل كل حل مرشح عادةً كمصفوفة من البتات (تُسمى أيضًا مجموعة بتات أو سلسلة بتات ). [ 5 ] ويمكن استخدام مصفوفات من أنواع وهياكل أخرى بنفس الطريقة تقريبًا. تكمن الميزة الرئيسية التي تجعل هذه التمثيلات الجينية ملائمة في سهولة محاذاة أجزائها نظرًا لحجمها الثابت، مما يُسهِّل عمليات التزاوج البسيطة . يمكن أيضًا استخدام تمثيلات ذات أطوال متغيرة، ولكن تنفيذ التزاوج يكون أكثر تعقيدًا في هذه الحالة. تُستكشف التمثيلات الشجرية في البرمجة الجينية ، بينما تُستكشف التمثيلات البيانية في البرمجة التطورية ؛ ويُستكشف مزيج من الكروموسومات الخطية والأشجار في برمجة التعبير الجيني .

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

التهيئة

يعتمد حجم المجموعة على طبيعة المشكلة، ولكنه عادةً ما يحتوي على مئات أو آلاف الحلول الممكنة. غالبًا ما يتم توليد المجموعة الأولية عشوائيًا، مما يسمح بتغطية النطاق الكامل للحلول الممكنة ( مساحة البحث ). في بعض الأحيان، قد يتم "زرع" الحلول في مناطق يُحتمل العثور فيها على حلول مثلى، أو يتم ضبط توزيع احتمالية أخذ العينات للتركيز على تلك المناطق ذات الأهمية الأكبر. [ 6 ]

اختيار

في كل جيل لاحق، يُختار جزء من المجموعة السكانية الحالية للتكاثر في جيل جديد. ويتم اختيار الحلول الفردية من خلال عملية تعتمد على الكفاءة ، حيث تكون الحلول الأكثر كفاءة (كما تُقاس بدالة الكفاءة ) أكثر عرضة للاختيار. تُقيّم بعض طرق الاختيار كفاءة كل حل وتختار أفضل الحلول بشكل تفضيلي. بينما تُقيّم طرق أخرى عينة عشوائية فقط من المجموعة السكانية، لأن العملية الأولى قد تستغرق وقتًا طويلاً.

تُعرَّف دالة اللياقة على التمثيل الجيني، وتقيس جودة الحل المُمثَّل. وتعتمد دالة اللياقة دائمًا على طبيعة المسألة. على سبيل المثال، في مسألة حقيبة الظهر، يُراد تعظيم القيمة الإجمالية للأشياء التي يمكن وضعها في حقيبة ظهر ذات سعة ثابتة. قد يكون تمثيل الحل عبارة عن مصفوفة من البتات، حيث يُمثِّل كل بت عنصرًا مختلفًا، وتُشير قيمة البت (0 أو 1) إلى ما إذا كان العنصر موجودًا في حقيبة الظهر أم لا. ليس كل تمثيل من هذا القبيل صالحًا، إذ قد يتجاوز حجم العناصر سعة حقيبة الظهر. وتكون لياقة الحل هي مجموع قيم جميع العناصر في حقيبة الظهر إذا كان التمثيل صالحًا، أو صفرًا في غير ذلك.

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

المؤثرات الجينية

تتمثل الخطوة التالية في توليد جيل ثانٍ من الحلول من تلك المختارة، من خلال مزيج من العوامل الوراثية : التهجين (يسمى أيضًا إعادة التركيب)، والطفرة .

لكل حل جديد يُراد إنتاجه، يُختار زوج من الحلول "الأبوية" للتكاثر من المجموعة المختارة سابقًا. وبإنتاج حل "ابن" باستخدام طريقتي التهجين والطفرة المذكورتين أعلاه، يُنشأ حل جديد يشترك عادةً في العديد من خصائص "والديه". ويُختار أبوان جديدان لكل ابن جديد، وتستمر العملية حتى يتم توليد مجموعة جديدة من الحلول ذات الحجم المناسب. مع أن طرق التكاثر القائمة على استخدام أبوين تُعتبر أقرب إلى علم الأحياء، إلا أن بعض الأبحاث [ 7 ] [ 8 ] تشير إلى أن استخدام أكثر من أبوين يُنتج كروموسومات ذات جودة أعلى.

تُؤدي هذه العمليات في نهاية المطاف إلى جيل جديد من الكروموسومات يختلف عن الجيل الأول. وبشكل عام، يرتفع متوسط ​​اللياقة البدنية لهذا الجيل نتيجةً لهذه العملية، حيث يتم اختيار أفضل الكائنات الحية من الجيل الأول للتكاثر، إلى جانب نسبة ضئيلة من الكائنات الأقل لياقة. وتضمن هذه الكائنات الأقل لياقة التنوع الجيني داخل المجموعة الجينية للآباء، وبالتالي تضمن التنوع الجيني للجيل اللاحق من الأبناء.

تتباين الآراء حول أهمية التهجين مقابل الطفرة. وتشير العديد من المراجع في كتاب فوغل (2006) إلى أهمية البحث القائم على الطفرة.

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

الأساليب الاستدلالية

إضافةً إلى العمليات الرئيسية المذكورة أعلاه، يمكن استخدام طرق استدلالية أخرى لتسريع الحساب أو جعله أكثر دقة. تُعاقب طريقة الاستدلال الخاصة بالتنوع البيولوجي التزاوج بين الحلول المرشحة المتشابهة جدًا؛ مما يشجع تنوع المجموعات السكانية ويساعد على منع التقارب المبكر نحو حل أقل كفاءة. [ 9 ] [ 10 ]

إنهاء الخدمة

تتكرر هذه العملية الجيلية حتى يتم الوصول إلى شرط الإنهاء. ومن شروط الإنهاء الشائعة ما يلي:

  • تم التوصل إلى حل يفي بالمعايير الدنيا
  • عدد ثابت من الأجيال التي تم الوصول إليها
  • تم الوصول إلى الميزانية المخصصة (وقت الحساب/المال)
  • تصل كفاءة الحل الأعلى تصنيفًا إلى مستوى ثابت، أو تكون قد وصلت إليه بالفعل، بحيث لا تُنتج التكرارات المتتالية نتائج أفضل.
  • الفحص اليدوي
  • مزيج مما سبق

فرضية اللبنات الأساسية

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

  1. وصف لأسلوب استدلالي يقوم بالتكيف من خلال تحديد وإعادة تجميع "وحدات البناء"، أي المخططات منخفضة الترتيب ومنخفضة الطول المحدد ذات اللياقة الأعلى من المتوسط.
  2. فرضية مفادها أن الخوارزمية الجينية تقوم بالتكيف من خلال التنفيذ الضمني والفعال لهذه الطريقة الاستدلالية.

يصف غولدبيرغ الأسلوب الاستدلالي على النحو التالي:

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

على الرغم من عدم وجود إجماع حول صحة فرضية الوحدات البنائية، فقد خضعت هذه الفرضية للتقييم المستمر واستُخدمت كمرجع على مر السنين. على سبيل المثال، طُرحت العديد من خوارزميات تقدير التوزيع في محاولة لتوفير بيئة تُثبت فيها صحة هذه الفرضية. [ 12 ] [ 13 ] مع أن بعض فئات المسائل قد حققت نتائج جيدة ، إلا أن الشكوك لا تزال قائمة بشأن عمومية و/أو جدوى فرضية الوحدات البنائية كتفسير لكفاءة الخوارزميات الجينية. في الواقع، هناك قدر لا بأس به من الدراسات التي تحاول فهم حدود هذه الفرضية من منظور خوارزميات تقدير التوزيع. [ 14 ] [ 15 ] [ 16 ]

القيود

إن الاستخدام العملي للخوارزمية الجينية له قيود، خاصة بالمقارنة مع خوارزميات التحسين البديلة:

  • يُعدّ التقييم المتكرر لدالة اللياقة في المسائل المعقدة الجزء الأكثر صعوبةً وتقييدًا في خوارزميات التطور الاصطناعي. فإيجاد الحل الأمثل للمسائل المعقدة متعددة الأبعاد والأنماط يتطلب غالبًا تقييمات مكلفة للغاية لدالة اللياقة . في مسائل العالم الحقيقي، مثل مسائل تحسين الهياكل، قد يتطلب تقييم دالة واحدة عدة ساعات أو حتى عدة أيام من المحاكاة الكاملة. لا تستطيع طرق التحسين التقليدية التعامل مع هذا النوع من المسائل. في هذه الحالة، قد يكون من الضروري التخلي عن التقييم الدقيق واستخدام دالة لياقة تقريبية تتسم بالكفاءة الحسابية. من الواضح أن دمج النماذج التقريبية قد يكون أحد أكثر المناهج الواعدة لاستخدام الخوارزميات الجينية بفعالية لحل مسائل الحياة الواقعية المعقدة.
  • لا تتناسب الخوارزميات الجينية جيدًا مع التعقيد. بمعنى آخر، عندما يكون عدد العناصر المعرضة للطفرة كبيرًا، غالبًا ما يزداد حجم فضاء البحث بشكل أُسّي. هذا يجعل استخدام هذه التقنية في مشاكل مثل تصميم محرك أو منزل أو طائرة أمرًا بالغ الصعوبة . ولجعل هذه المشاكل قابلة للحل باستخدام البحث التطوري، يجب تبسيطها إلى أبسط تمثيل ممكن. لذا، نرى عادةً الخوارزميات التطورية تُشفّر تصاميم شفرات المراوح بدلًا من المحركات، وأشكال المباني بدلًا من مخططات البناء التفصيلية، وأجنحة الطائرات بدلًا من تصاميم الطائرات الكاملة. أما المشكلة الثانية المتعلقة بالتعقيد، فهي كيفية حماية الأجزاء التي تطورت لتمثل حلولًا جيدة من المزيد من الطفرات المدمرة، خاصةً عندما يتطلب تقييم ملاءمتها دمجها بشكل جيد مع أجزاء أخرى.
  • لا يُعتبر الحل "أفضل" إلا بالمقارنة مع الحلول الأخرى. ونتيجة لذلك، فإن معيار التوقف ليس واضحاً في كل مشكلة.
  • في العديد من المسائل، تميل الخوارزميات الجينية إلى التقارب نحو الحلول المثلى المحلية أو حتى نقاط عشوائية بدلاً من الحل الأمثل العالمي للمسألة. وهذا يعني أنها لا "تعرف" كيف تضحي باللياقة على المدى القصير لكسب لياقة على المدى الطويل. ويعتمد احتمال حدوث ذلك على شكل منحنى اللياقة : فبعض المسائل قد توفر صعودًا سهلاً نحو الحل الأمثل العالمي، بينما قد تسهل مسائل أخرى على الدالة إيجاد الحلول المثلى المحلية. ويمكن التخفيف من هذه المشكلة باستخدام دالة لياقة مختلفة، أو زيادة معدل الطفرة، أو باستخدام تقنيات اختيار تحافظ على تنوع مجموعة الحلول [ 17 ]، على الرغم من أن نظرية "لا غداء مجاني" [ 18 ] تثبت أنه لا يوجد حل عام لهذه المشكلة. ومن التقنيات الشائعة للحفاظ على التنوع فرض "عقوبة التخصص"، حيث تُضاف عقوبة إلى أي مجموعة من الأفراد ذوي التشابه الكافي (نصف قطر التخصص)، مما يقلل من تمثيل تلك المجموعة في الأجيال اللاحقة، ويسمح بالحفاظ على أفراد آخرين (أقل تشابهًا) في المجموعة. مع ذلك، قد لا تكون هذه الحيلة فعّالة، وذلك بحسب طبيعة المشكلة. ومن التقنيات الأخرى الممكنة استبدال جزء من المجموعة بأفراد مُولّدين عشوائيًا، عندما تكون معظم المجموعة متشابهة جدًا. يُعدّ التنوع مهمًا في الخوارزميات الجينية ( والبرمجة الجينية ) لأنّ تهجين مجموعة متجانسة لا يُنتج حلولًا جديدة. أما في استراتيجيات التطور والبرمجة التطورية ، فالتنوع ليس ضروريًا نظرًا للاعتماد الأكبر على الطفرة.
  • يُعدّ التعامل مع مجموعات البيانات الديناميكية أمرًا صعبًا، إذ تبدأ الجينومات بالتقارب مبكرًا نحو حلول قد لا تكون صالحة للبيانات اللاحقة. وقد اقتُرحت عدة طرق لمعالجة هذه المشكلة من خلال زيادة التنوع الجيني بطريقة ما ومنع التقارب المبكر، إما عن طريق زيادة احتمالية الطفرة عند انخفاض جودة الحل (ما يُعرف بالطفرة الفائقة المُحفَّزة )، أو عن طريق إدخال عناصر جديدة تمامًا، مُولَّدة عشوائيًا، إلى مجمع الجينات من حين لآخر (ما يُعرف بالمهاجرين العشوائيين ). ويمكن تطبيق استراتيجيات التطور والبرمجة التطورية باستخدام ما يُسمى "استراتيجية الفاصلة"، حيث لا يتم الاحتفاظ بالآباء ويتم اختيار آباء جدد من النسل فقط. وقد يكون هذا أكثر فعالية في المشكلات الديناميكية.
  • لا تستطيع الخوارزميات الجينية حل المشكلات التي يكون فيها مقياس الكفاءة الوحيد هو نتيجة ثنائية (نجاح/فشل) (مثل مشكلات اتخاذ القرار )، إذ لا توجد طريقة للتقارب نحو الحل (لا يوجد مسار للتسلق). في هذه الحالات، قد يجد البحث العشوائي حلاً بنفس سرعة الخوارزمية الجينية. مع ذلك، إذا سمح الوضع بتكرار تجربة النجاح/الفشل، مما قد يُعطي نتائج مختلفة، فإن نسبة النجاحات إلى الإخفاقات تُوفر مقياس كفاءة مناسبًا.
  • في بعض مسائل التحسين المحددة، قد تكون خوارزميات التحسين الأخرى أكثر كفاءة من الخوارزميات الجينية من حيث سرعة التقارب. تشمل الخوارزميات البديلة والمكملة استراتيجيات التطور ، والبرمجة التطورية ، والتقسية المحاكاة ، والتكيف الغاوسي ، وتسلق التلال ، وذكاء الأسراب (مثل: تحسين مستعمرات النمل ، وتحسين أسراب الجسيمات )، بالإضافة إلى الطرق القائمة على البرمجة الخطية الصحيحة . وتعتمد ملاءمة الخوارزميات الجينية على مدى معرفتنا بالمسألة؛ فالمسائل المعروفة غالبًا ما يكون لها مناهج أفضل وأكثر تخصصًا.

المتغيرات

تمثيل الكروموسومات

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

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

تتضمن طرق أخرى استخدام مصفوفات من الأعداد الحقيقية بدلاً من سلاسل البتات لتمثيل الكروموسومات. تشير نتائج نظرية المخططات إلى أنه كلما صغر حجم الأبجدية، كان الأداء أفضل بشكل عام، ولكن كان من المفاجئ للباحثين في البداية الحصول على نتائج جيدة باستخدام كروموسومات ذات قيم حقيقية. وقد فُسِّر ذلك بأن مجموعة القيم الحقيقية في مجموعة محدودة من الكروموسومات تُشكِّل أبجدية افتراضية (عندما يكون الانتقاء وإعادة التركيب هما السائدان) ذات عدد عناصر أقل بكثير مما هو متوقع من تمثيل الفاصلة العائمة. [ 19 ] [ 20 ]

يمكن توسيع نطاق مشكلة الخوارزمية الجينية المتاحة من خلال ترميز أكثر تعقيدًا لمجموعات الحلول، وذلك بدمج عدة أنواع من الجينات المشفرة بشكل غير متجانس في كروموسوم واحد. [ 21 ] يتيح هذا النهج حل مسائل التحسين التي تتطلب نطاقات تعريف متباينة للغاية لمعلمات المسألة. على سبيل المثال، في مسائل ضبط المتحكمات المتتالية، يمكن أن ينتمي هيكل حلقة التحكم الداخلية إلى منظم تقليدي بثلاثة معلمات، بينما يمكن أن تُنفذ الحلقة الخارجية متحكمًا لغويًا (مثل نظام ضبابي) له وصف مختلف جوهريًا. يتطلب هذا الشكل من الترميز آلية تهجين متخصصة تُعيد تركيب الكروموسوم قسمًا قسمًا، وهو أداة مفيدة لنمذجة ومحاكاة الأنظمة التكيفية المعقدة، وخاصة عمليات التطور.

كان أحد أهم توسعات نطاق الحلول المتاحة للخوارزمية الجينية (GA) مدفوعًا بالحاجة إلى جعل التمثيلات قابلة للتكيف مع مستويات متفاوتة من المعرفة حول حالات الحل. استُلهمت التمثيلات ذات الأطوال المتغيرة من ملاحظة أن التطور في الطبيعة يميل إلى التقدم من الكائنات الحية الأبسط إلى الأكثر تعقيدًا، مما يشير إلى أساس منطقي لاعتماد هياكل مرنة. [ 22 ] أما الدافع الثاني، والأكثر عملية، فهو أن معظم المشكلات الهندسية والمعرفية في العالم الحقيقي لا تتوافق بطبيعتها مع هياكل معرفية جامدة. [ 23 ]

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

النخبوية

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

التنفيذ المتوازي

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

الخوارزميات الجينية التكيفية

تُعدّ الخوارزميات الجينية ذات المعاملات التكيفية (الخوارزميات الجينية التكيفية، AGAs) نوعًا آخر مهمًا وواعدًا من الخوارزميات الجينية. وتُحدد احتمالات التزاوج (pc) والطفرة (pm) بشكل كبير درجة دقة الحل وسرعة التقارب التي يمكن أن تحققها الخوارزميات الجينية. وقد قام الباحثون بتحليل تقارب الخوارزميات الجينية تحليليًا. [ 25 ] [ 26 ]

بدلاً من استخدام قيم ثابتة لـ pc و pm ، تستخدم الخوارزميات الجينية التكيفية (AGAs) معلومات المجموعة في كل جيل، وتُعدّل قيم pc و pm بشكل تكيفي للحفاظ على تنوع المجموعة ودعم قدرة التقارب. في الخوارزمية الجينية التكيفية (AGA) [ 27 ] ، يعتمد تعديل pc و pm على قيم لياقة الحلول. وهناك أمثلة أخرى على متغيرات AGA: تُعد طريقة التكبير المتتالي مثالاً مبكراً لتحسين التقارب [ 28 ] . في الخوارزمية الجينية التكيفية القائمة على التجميع ( CAGA ) [ 29 ] ، من خلال استخدام تحليل التجميع لتقييم حالات التحسين للمجموعة، يعتمد تعديل pc و pm على هذه الحالات. تستخدم الأساليب الحديثة متغيرات أكثر تجريداً لتحديد pc و pm . ومن الأمثلة على ذلك مبادئ الهيمنة والهيمنة المشتركة [ 30 ] ، وخوارزمية LIGA (الخوارزمية الجينية الاستيفائية المُستوية)، التي تجمع بين خوارزمية جينية مرنة وبحث A* مُعدّل لمعالجة تباين فضاء البحث [ 31 ] .

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

هذا يعني أن قواعد التباين الجيني قد تحمل معنى مختلفًا في الحالة الطبيعية. على سبيل المثال ، إذا تم تخزين الخطوات بترتيب متسلسل ، فقد يؤدي العبور إلى جمع عدد من الخطوات من الحمض النووي للأم، وإضافة عدد من الخطوات من الحمض النووي للأب، وهكذا. يشبه هذا إضافة متجهات من المرجح أن تتبع نمطًا محددًا في المشهد الظاهري. وبالتالي، يمكن زيادة كفاءة العملية بشكل كبير. علاوة على ذلك، يتيح عامل الانعكاس إمكانية وضع الخطوات بترتيب متسلسل أو أي ترتيب مناسب آخر يُحسّن البقاء أو الكفاءة. [ 32 ]

يُعرف نوع التباين الذي يتطور فيه السكان ككل بدلاً من أفرادهم الأفراد باسم إعادة تركيب مجموعة الجينات.

طُوِّرت عدة صيغ لتحسين أداء الخوارزميات الجينية في المسائل ذات درجة عالية من التفاعل الجيني، أي عندما تتكون لياقة الحل من مجموعات فرعية متفاعلة من متغيراته. تهدف هذه الخوارزميات إلى تعلم هذه التفاعلات الظاهرية المفيدة (قبل استغلالها). وبذلك، فهي تتوافق مع فرضية الوحدات البنائية في الحد من إعادة التركيب التخريبي بشكل تكيفي. من الأمثلة البارزة على هذا النهج: mGA [ 33 ] ، و GEMGA [ 34 ] ، وLLGA [ 35 ] .

مجالات المشكلة

تشمل المشكلات التي تبدو مناسبة بشكل خاص للحل باستخدام الخوارزميات الجينية مشكلات الجدولة الزمنية ، وتعتمد العديد من حزم برامج الجدولة على هذه الخوارزميات . كما تم تطبيق الخوارزميات الجينية في الهندسة . [ 36 ] غالبًا ما تُستخدم الخوارزميات الجينية كنهج لحل مشكلات التحسين الشامل .

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

من أمثلة المشكلات التي حلتها الخوارزميات الجينية: المرايا المصممة لتوجيه ضوء الشمس إلى جامع شمسي، [ 37 ] والهوائيات المصممة لالتقاط إشارات الراديو في الفضاء، [ 38 ] وطرق المشي للشخصيات الحاسوبية، [ 39 ] والتصميم الأمثل للأجسام الديناميكية الهوائية في حقول التدفق المعقدة. [ 40 ]

ينصح سكينا في كتابه "دليل تصميم الخوارزميات" بعدم استخدام الخوارزميات الجينية لأي مهمة:

من غير الطبيعي تمامًا نمذجة التطبيقات باستخدام عوامل وراثية مثل الطفرة والتهجين على سلاسل البتات. تُضيف البيولوجيا الزائفة مستوىً آخر من التعقيد بينك وبين مشكلتك. ثانيًا، تستغرق الخوارزميات الجينية وقتًا طويلًا جدًا في حل المشكلات المعقدة. [...] ويمكن أن يكون التشبيه بالتطور - حيث يتطلب إحراز تقدم ملحوظ ملايين السنين - مناسبًا تمامًا.

[...]

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

— ستيفن سكينا [ 41 ] : 267

تاريخ

في عام 1950، اقترح آلان تورينج "آلة تعلم" تحاكي مبادئ التطور. [ 42 ] بدأ استخدام المحاكاة الحاسوبية للتطور في وقت مبكر من عام 1954 مع عمل نيلز آل باريسيلي ، الذي كان يستخدم الحاسوب في معهد الدراسات المتقدمة في برينستون، نيو جيرسي . [ 43 ] [ 44 ] لم يحظَ منشوره عام 1954 باهتمام واسع. ابتداءً من عام 1957، [ 45 ] نشر عالم الوراثة الكمية الأسترالي أليكس فريزر سلسلة من الأبحاث حول محاكاة الانتقاء الاصطناعي للكائنات الحية ذات المواقع الجينية المتعددة التي تتحكم في سمة قابلة للقياس. انطلاقًا من هذه البدايات، أصبحت المحاكاة الحاسوبية للتطور من قِبل علماء الأحياء أكثر شيوعًا في أوائل الستينيات، ووُصفت هذه الأساليب في كتب فريزر وبورنيل (1970) [ 46 ] وكروسبي (1973). [ 47 ] تضمنت محاكاة فريزر جميع العناصر الأساسية للخوارزميات الجينية الحديثة. بالإضافة إلى ذلك، نشر هانز يواكيم بريمرمان سلسلة من الأبحاث في ستينيات القرن الماضي، اعتمدت أيضًا على مجموعة من الحلول لمسائل التحسين، تخضع لعمليات إعادة التركيب والطفرة والاختيار. كما تضمنت أبحاث بريمرمان عناصر من الخوارزميات الجينية الحديثة. [ 48 ] ومن الرواد الأوائل البارزين الآخرين ريتشارد فريدبيرغ، وجورج فريدمان، ومايكل كونراد. وقد أعاد فوغل (1998) نشر العديد من الأبحاث المبكرة. [ 49 ]

على الرغم من أن باريسيلي، في بحثه الذي نشره عام 1963، قد حاكى تطور القدرة على لعب لعبة بسيطة، [ 50 ] إلا أن التطور الاصطناعي لم يصبح أسلوبًا معترفًا به على نطاق واسع في مجال التحسين إلا نتيجةً لأعمال إنجو ريشنبرغ وهانز -بول شفيل في ستينيات وسبعينيات القرن العشرين ، حيث تمكن فريق ريشنبرغ من حل مشكلات هندسية معقدة من خلال استراتيجيات التطور . [ 51 ] [ 52 ] [ 53 ] [ 54 ] وثمة نهج آخر تمثل في تقنية البرمجة التطورية التي ابتكرها لورانس ج. فوغل ، والتي طُرحت لتوليد الذكاء الاصطناعي. استخدمت البرمجة التطورية في الأصل آلات الحالة المحدودة للتنبؤ بالبيئات، واستخدمت التباين والاختيار لتحسين منطق التنبؤ. وقد اكتسبت الخوارزميات الجينية شعبية واسعة بفضل أعمال جون هولاند في أوائل سبعينيات القرن العشرين، ولا سيما كتابه " التكيف في الأنظمة الطبيعية والاصطناعية" (1975). بدأ عمله بدراساتٍ حول الأوتوماتا الخلوية ، أجراها هولاند وطلابه في جامعة ميشيغان . وقدّم هولاند إطارًا رسميًا للتنبؤ بجودة الجيل التالي، يُعرف باسم نظرية مخطط هولاند . وظلّ البحث في الخوارزميات الجينية نظريًا إلى حد كبير حتى منتصف ثمانينيات القرن العشرين، عندما عُقد المؤتمر الدولي الأول للخوارزميات الجينية في بيتسبرغ، بنسلفانيا .

المنتجات التجارية

في أواخر ثمانينيات القرن العشرين، بدأت شركة جنرال إلكتريك ببيع أول منتج في العالم للخوارزمية الجينية، وهي عبارة عن مجموعة أدوات قائمة على الحواسيب المركزية مصممة للعمليات الصناعية. [ 55 ] وفي عام 1989، أصدرت شركة أكسيليس برنامج إيفولفر ، وهو أول منتج تجاري في العالم للخوارزمية الجينية لأجهزة الكمبيوتر المكتبية. كتب جون ماركوف، كاتب التكنولوجيا في صحيفة نيويورك تايمز، [ 56 ] عن إيفولفر في عام 1990، وظل البرنامج الخوارزمية الجينية التجارية التفاعلية الوحيدة حتى عام 1995. [ 57 ] بيع برنامج إيفولفر لشركة باليسيد في عام 1997، وتُرجم إلى عدة لغات، وهو حاليًا في نسخته السادسة. [ 58 ] منذ تسعينيات القرن العشرين، أُضيفت إلى برنامج ماتلاب ثلاث خوارزميات استدلالية للتحسين بدون مشتقات (التلدين المحاكي، وتحسين سرب الجسيمات، والخوارزمية الجينية) وخوارزميتان للبحث المباشر (البحث البسيط، والبحث النمطي). [ 59 ]

الحقول الأصلية

الخوارزميات الجينية هي مجال فرعي:

الخوارزميات التطورية

الخوارزميات التطورية هي فرع من فروع الحوسبة التطورية .

  • تُطوّر استراتيجيات التطور (ES، انظر ريتشنبرغ، 1994) الأفراد عن طريق الطفرات وإعادة التركيب الوسيطة أو المنفصلة. صُممت خوارزميات استراتيجيات التطور خصيصًا لحل المشكلات في مجال القيم الحقيقية. [ 60 ] وهي تستخدم التكيف الذاتي لضبط معلمات التحكم في البحث. وقد أدى إزالة العشوائية من التكيف الذاتي إلى ظهور استراتيجية التطور التكيفية لمصفوفة التغاير المعاصرة ( CMA-ES ).
  • تعتمد البرمجة التطورية على مجموعات من الحلول، وتعتمد بشكل أساسي على الطفرة والاختيار، وتعتمد على تمثيلات عشوائية. وتستخدم هذه البرمجة التكيف الذاتي لضبط المعلمات، ويمكن أن تشمل عمليات تباين أخرى مثل دمج المعلومات من عدة آباء.
  • تستبدل خوارزمية تقدير التوزيع (EDA) عوامل التكاثر التقليدية بعوامل موجهة بالنموذج. تُستخلص هذه النماذج من المجموعة باستخدام تقنيات التعلم الآلي، وتُمثل كنماذج بيانية احتمالية، يمكن من خلالها أخذ عينات من حلول جديدة [ 61 ] [ 62 ] أو توليدها من خلال التهجين الموجه. [ 63 ]
  • البرمجة الجينية (GP) هي تقنية مشابهة شاع استخدامها بفضل جون كوزا، حيث يتم فيها تحسين برامج الحاسوب بدلاً من معلمات الدوال. غالباً ما تستخدم البرمجة الجينية هياكل بيانات داخلية شجرية لتمثيل برامج الحاسوب بهدف التكيف، بدلاً من هياكل القوائم الشائعة في الخوارزميات الجينية. تتعدد أنواع البرمجة الجينية، منها البرمجة الجينية الديكارتية ، وبرمجة التعبير الجيني ، والتطور النحوي ، والبرمجة الجينية الخطية ، وبرمجة التعبير المتعدد ، وغيرها.
  • تُعدّ خوارزمية التجميع الجيني (GGA) تطورًا للخوارزمية الجينية (GA)، حيث يُحوّل التركيز من العناصر الفردية، كما في الخوارزميات الجينية التقليدية، إلى مجموعات أو مجموعات فرعية من العناصر. [ 65 ] تقوم فكرة هذا التطور، الذي اقترحه إيمانويل فالكناور، على أن حلّ بعض المشكلات المعقدة، مثل مشكلات التجميع أو التقسيم ، حيث يجب تقسيم مجموعة من العناصر إلى مجموعات منفصلة بطريقة مثلى، يُمكن تحقيقه بشكل أفضل بجعل خصائص مجموعات العناصر مُكافئة للجينات. تشمل هذه المشكلات تعبئة الصناديق ، وموازنة الخطوط، والتجميع وفقًا لمقياس المسافة، والأكوام المتساوية، وغيرها، والتي أثبتت الخوارزميات الجينية التقليدية ضعف أدائها فيها. إن جعل الجينات مُكافئة للمجموعات يعني وجود كروموسومات ذات أطوال متغيرة عمومًا، وعوامل جينية خاصة تُعالج مجموعات العناصر بأكملها. بالنسبة لتعبئة الصناديق تحديدًا، تُعتبر خوارزمية التجميع الجيني المُهجّنة مع معيار الهيمنة لمارتيلو وتوث، أفضل تقنية حتى الآن.
  • الخوارزميات التطورية التفاعلية هي خوارزميات تطورية تستخدم التقييم البشري. وعادةً ما تُطبق في المجالات التي يصعب فيها تصميم دالة لياقة حسابية، على سبيل المثال، تطوير الصور والموسيقى والتصاميم والأشكال الفنية لتناسب التفضيلات الجمالية للمستخدمين.

ذكاء السرب

يُعدّ ذكاء الأسراب مجالاً فرعياً من الحوسبة التطورية .

  • تستخدم خوارزمية تحسين مستعمرات النمل ( ACO ) العديد من النمل (أو العوامل) المجهزة بنموذج الفيرومون للتنقل عبر مساحة الحل وإيجاد المناطق المنتجة محليًا.
  • على الرغم من اعتبارها خوارزمية لتقدير التوزيع ، [ 66 ] فإن خوارزمية تحسين سرب الجسيمات (PSO) هي طريقة حسابية لتحسين متعدد المعاملات، وتعتمد أيضًا على نهج قائم على السكان. يتحرك سرب من الحلول المرشحة (الجسيمات) في فضاء البحث، ويتأثر تحرك الجسيمات بأفضل موقع معروف لها، بالإضافة إلى أفضل موقع معروف للسرب ككل. ومثل الخوارزميات الجينية، تعتمد خوارزمية PSO على تبادل المعلومات بين أفراد المجموعة. في بعض المسائل، غالبًا ما تكون خوارزمية PSO أكثر كفاءة حسابية من الخوارزميات الجينية، لا سيما في المسائل غير المقيدة ذات المتغيرات المستمرة. [ 67 ]

خوارزميات الحوسبة التطورية الأخرى

الحوسبة التطورية هي مجال فرعي من أساليب الاستدلال الميتاهوريستية .

  • الخوارزمية الميمية ، والتي تُعرف أيضاً بالخوارزمية الجينية الهجينة، هي طريقة تعتمد على السكان، حيث تخضع الحلول لمراحل تحسين محلية. وتستمد فكرة الخوارزميات الميمية من الميمات ، التي تتميز بقدرتها على التكيف الذاتي، على عكس الجينات. وقد أثبتت هذه الخوارزميات كفاءتها العالية في بعض المجالات مقارنةً بالخوارزميات التطورية التقليدية.
  • الخوارزميات البكتريولوجية (BA) مستوحاة من علم البيئة التطوري ، وتحديدًا من التكيف البكتيري. يُعنى علم البيئة التطوري بدراسة الكائنات الحية في سياق بيئتها، بهدف اكتشاف كيفية تكيفها. يقوم هذا العلم على فكرة أساسية مفادها أنه في بيئة غير متجانسة، لا يوجد فرد واحد يُناسب البيئة بأكملها. لذا، من الضروري التفكير على مستوى الجماعة. يُعتقد أيضًا أن الخوارزميات البكتريولوجية يُمكن تطبيقها بنجاح على مشاكل تحديد المواقع المعقدة (مثل هوائيات الهواتف المحمولة، والتخطيط الحضري، وما إلى ذلك) أو استخراج البيانات. [ 68 ]
  • تتكون الخوارزمية الثقافية (CA) من مكون السكان المطابق تقريبًا لمكون الخوارزمية الجينية، بالإضافة إلى مكون معرفي يسمى فضاء المعتقدات.
  • التطور التفاضلي (DE) مستوحى من هجرة الكائنات الفائقة. [ 69 ]
  • يهدف التكيف الغاوسي (أو التكيف الطبيعي، ويُختصر بـ NA لتجنب الخلط مع الخوارزمية الجينية) إلى تعظيم إنتاجية تصنيع أنظمة معالجة الإشارات. ويمكن استخدامه أيضًا في التحسين البارامتري العادي. ويعتمد على نظرية معينة صالحة لجميع مناطق القبول وجميع التوزيعات الغاوسية. وتعتمد كفاءة التكيف الغاوسي على نظرية المعلومات ونظرية كفاءة معينة، حيث تُعرَّف كفاءته بأنها المعلومات مقسومة على العمل اللازم للحصول عليها. [ 70 ] ولأن التكيف الغاوسي يُعظِّم متوسط ​​اللياقة بدلاً من لياقة الفرد، فإنه يُنعم سطح البيانات بحيث تختفي الفجوات بين القمم. ولذلك، لديه "طموح" لتجنب القمم المحلية في سطح بيانات اللياقة. كما يتميز التكيف الغاوسي بقدرته على تسلق القمم الحادة من خلال تكييف مصفوفة العزوم، لأنه قد يُعظِّم اضطراب ( متوسط ​​المعلومات ) التوزيع الغاوسي مع الحفاظ على متوسط ​​اللياقة ثابتًا.

طرق أخرى للاستدلال الميتاهيورستيكي

تندرج أساليب الاستدلال الميتاهوريستية بشكل عام ضمن أساليب التحسين العشوائي .

  • التلدين المحاكي (SA) هو أسلوب تحسين عالمي ذو صلة، يجوب فضاء البحث باختبار طفرات عشوائية على حل فردي. تُقبل الطفرة التي تزيد من كفاءة الحل دائمًا، بينما تُقبل الطفرة التي تُقلل منها احتماليًا بناءً على الفرق في الكفاءة وانخفاض معامل درجة الحرارة. في مصطلحات التلدين المحاكي، يُشار إلى البحث عن أقل طاقة بدلًا من أعلى كفاءة. يمكن أيضًا استخدام التلدين المحاكي ضمن خوارزمية جينية قياسية، وذلك بالبدء بمعدل طفرات مرتفع نسبيًا ثم خفضه تدريجيًا وفقًا لجدول زمني محدد.
  • تتشابه خوارزمية البحث المحظور (TS) مع خوارزمية التلدين المحاكي في كونهما تجوبان فضاء الحلول عن طريق اختبار طفرات حلٍّ مُحدد. بينما تُولّد خوارزمية التلدين المحاكي حلاً واحداً مُطَفَّراً فقط، تُولّد خوارزمية البحث المحظور العديد من الحلول المُطَفَّرة وتنتقل إلى الحل ذي الطاقة الأقل من بينها. ولمنع التكرار وتشجيع حركة أكبر عبر فضاء الحلول، تُحفظ قائمة محظورة تضم حلولاً جزئية أو كاملة. ويُمنع الانتقال إلى حلٍّ يحتوي على عناصر من هذه القائمة، التي تُحدَّث باستمرار مع تجوال الحل في فضاء الحلول.
  • التحسين الأمثل (EO): على عكس الخوارزميات الجينية التي تعمل مع مجموعة من الحلول المرشحة، يُطوّر التحسين الأمثل حلاً واحداً ويُجري تعديلات محلية على أسوأ مكوناته. يتطلب هذا اختيار تمثيل مناسب يسمح بتحديد مقياس جودة ("اللياقة") لكل مكون من مكونات الحل. يقوم مبدأ هذه الخوارزمية على التحسين التدريجي من خلال إزالة المكونات منخفضة الجودة بشكل انتقائي واستبدالها بمكون مُختار عشوائياً. وهذا يتعارض تماماً مع الخوارزمية الجينية التي تختار الحلول الجيدة سعياً منها إلى إيجاد حلول أفضل.

طرق التحسين العشوائي الأخرى

  • تُنتج طريقة الإنتروبيا المتقاطعة (CE) حلولاً مرشحة عبر توزيع احتمالي مُعَلم. ويتم تحديث المعلمات عبر تقليل الإنتروبيا المتقاطعة، وذلك لإنتاج عينات أفضل في التكرار التالي.
  • يدعو تحسين البحث التفاعلي (RSO) إلى دمج تقنيات التعلم الآلي شبه الرمزية في خوارزميات البحث لحل مسائل التحسين المعقدة. تشير كلمة "تفاعلي" إلى الاستجابة الفورية للأحداث أثناء البحث من خلال حلقة تغذية راجعة داخلية لضبط المعلمات الأساسية ذاتيًا. تشمل المنهجيات ذات الأهمية في البحث التفاعلي التعلم الآلي والإحصاء، ولا سيما التعلم المعزز ، والتعلم النشط أو تعلم الاستعلام ، والشبكات العصبية ، والخوارزميات فوق الحدسية .

انظر أيضاً

مراجع

  1. ↑ بيتروفسكي، آلان؛ بن حميدة، سناء (2017). الخوارزميات التطورية . جون وايلي وأولاده. ص  30. ISBN 978-1-119-13638-5.
  2. ↑ ميتشل 1996 ، ص 2.
  3. ↑ جرجس، فراس؛ زوين، جيرمان؛ عازار، دانييل (12 مارس 2018). "الخوارزميات الجينية مع معالجة الحلول المثلى المحلية لحل ألغاز سودوكو" . وقائع المؤتمر الدولي للحوسبة والذكاء الاصطناعي 2018. ICCAI 2018. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 19-22 . doi : 10.1145/3194452.3194463 . ISBN  978-1-4503-6419-5. S2CID 44152535 . 
  4. ↑ بوركهارت، مايكل سي؛ رويز، غابرييل (2023). "التمثيلات العصبية التطورية لتعلم تأثيرات العلاج غير المتجانسة" . مجلة علوم الحاسوب . 71 102054. doi : 10.1016/j.jocs.2023.102054 . S2CID 258752823 . 
  5. 1 2 ويتلي 1994 ، ص. 66.
  6. ^ لوكي رودريغيز، ماريا. مولينا-باينا، خوسيه؛ جيمينيز-فيلتشيز، ألفونسو؛ أروزو-أزوفرا، أنطونيو (2022). "تهيئة اختيار الميزة للبحث عن التصنيف (ثانية 3)" . مجلة أبحاث الذكاء الاصطناعي . 75 : 953– 983. دوى : 10.1613/jair.1.14015 .
  7. ↑ إيبن، إيه إي وآخرون (1994). "الخوارزميات الجينية مع إعادة التركيب متعدد الآباء". PPSN III: وقائع المؤتمر الدولي للحوسبة التطورية. المؤتمر الثالث حول حل المشكلات المتوازية من الطبيعة: 78-87 . ISBN 3-540-58484-6.
  8. ↑ تينغ، تشوان كانغ (2005). "حول متوسط ​​زمن التقارب للخوارزميات الجينية متعددة الآباء بدون اختيار". التقدم في الحياة الاصطناعية: 403-412 . ISBN 978-3-540-28848-0.
  9. ↑ ديب، كاليانموي؛ سبيرز، ويليام م. (1997). "C6.2: طرق التنوع البيولوجي". دليل الحوسبة التطورية . منشورات معهد الفيزياء. S2CID 3547258 . 
  10. ↑ شير، عوفر م. (2012). "التخصص في الخوارزميات التطورية". في: روزنبرغ، غريغورز؛ باك، توماس؛ كوك، جوست ن. (محررون). دليل الحوسبة الطبيعية . سبرينغر برلين هايدلبرغ. ص 1035-1069 . doi : 10.1007/978-3-540-92910-9_32 . ISBN  9783540929093.
  11. ↑ غولدبيرغ 1989 ، ص 41.
  12. ↑ هاريك، جورج ر.؛ لوبو، فرناندو ج.؛ ساستري، كومارا (1 يناير 2006). "تعلم الربط عبر النمذجة الاحتمالية في الخوارزمية الجينية المدمجة الموسعة (ECGA)". التحسين القابل للتوسع عبر النمذجة الاحتمالية . دراسات في الذكاء الحسابي. المجلد 33. الصفحات 39-61 . doi : 10.1007/978-3-540-34954-9_3 . ISBN   978-3-540-34953-2.
  13. ^ بيليكان، مارتن؛ غولدبرغ، ديفيد E.؛ كانتو باز، إريك (1 يناير 1999). BOA: خوارزمية التحسين بايزي . جيكو'99. ص 525 – 532. ISBN  9781558606111.{{cite book}}تم |journal=تجاهله ( مساعدة )
  14. ↑ كوفين، ديفيد؛ سميث، روبرت إي. (1 يناير 2008). "التعلم بالربط في خوارزميات تقدير التوزيع". الربط في الحوسبة التطورية . دراسات في الذكاء الحسابي. المجلد 157. الصفحات 141-156 . doi : 10.1007/978-3-540-85068-7_7 . ISBN   978-3-540-85067-0.
  15. ↑ إتشيغوين، كارلوس؛ مينديبورو، ألكسندر؛ سانتانا، روبرتو؛ لوزانو، خوسيه أ. (8 نوفمبر 2012). "حول تصنيف مسائل التحسين في ظل تقدير خوارزميات التوزيع". الحوسبة التطورية . 21 (3): 471-495 . doi : 10.1162/EVCO_a_00095 . ISSN 1063-6560 . PMID 23136917. S2CID 26585053 .   
  16. ↑ سادوفسكي، كريستوف ل.؛ بوسمان، بيتر أ.ن.؛ ثيرينز، ديرك (1 يناير 2013). "حول جدوى معالجة الارتباط لحل مشكلة MAX-SAT". وقائع المؤتمر السنوي الخامس عشر حول الحوسبة الجينية والتطورية . Gecco '13. الصفحات 853-860 . doi : 10.1145/2463372.2463474 . hdl : 1874/290291 . ISBN  9781450319638. S2CID 9986768 . 
  17. ↑ طاهردانكو، محمد؛ بازيريش، مهسا؛ يزدي، مهران؛ باقري، محمد هادي (19 نوفمبر 2012). "خوارزمية فعالة لتحسين الدوال: خوارزمية الخلايا الجذعية المعدلة" . المجلة الأوروبية المركزية للهندسة . 3 (1): 36-50 . doi : 10.2478/s13531-012-0047-8 .
  18. ↑ وولبرت، د.هـ، ماكريدي، و.ج، 1995. نظريات لا غداء مجاني للتحسين. معهد سانتا فيه، SFI-TR-05-010، سانتا فيه.
  19. ↑ غولدبيرغ، ديفيد إي. (1991). "نظرية الأبجديات الافتراضية". حل المشكلات المتوازية من الطبيعة . سلسلة محاضرات في علوم الحاسوب. المجلد 496. الصفحات 13-22 . doi : 10.1007/BFb0029726 . ISBN   978-3-540-54148-6.{{cite book}}تم |journal=تجاهله ( مساعدة )
  20. ↑ يانيكو، سي زد؛ ميشاليفيتش، زد. (1991). "مقارنة تجريبية بين التمثيلات الثنائية وتمثيلات الفاصلة العائمة في الخوارزميات الجينية" (ملف PDF) . وقائع المؤتمر الدولي الرابع حول الخوارزميات الجينية : 31-36 . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022. تم الاطلاع عليه في 2 يوليو 2013 .
  21. ↑ باتراسكو، م.؛ ستانكو، أ.ف.؛ بوب، ف. (2014). "هيلغا: خوارزمية جينية غير متجانسة تحاكي الحياة لنمذجة ومحاكاة تطور السكان". الحوسبة اللينة . 18 (12): 2565-2576 . doi : 10.1007/s00500-014-1401-y . S2CID 29821873 . 
  22. ↑ غولدبيرغ، دي إي، كورب، بي، وديب، ك. (1989). الخوارزميات الجينية الفوضوية: الدافع والتحليل والنتائج الأولية. الأنظمة المعقدة، 3(5)، 493-530. الرقم الدولي الموحد للدوريات 0891-2513.
  23. ↑ دافيدور، ي. (1991). الخوارزميات الجينية والروبوتات: استراتيجية استدلالية للتحسين. سلسلة وورلد ساينتيفيك في الروبوتات والأنظمة الذكية: المجلد 1.
  24. ↑ بالوجا، شوميت؛ كاروانا، ريتش (1995). إزالة العوامل الوراثية من الخوارزمية الجينية القياسية (ملف PDF) . المؤتمر الدولي للتعلم الآلي . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.
  25. ↑ ستانات، و. (2004). "حول تقارب الخوارزميات الجينية - منهج حساب التفاضل والتكامل" . نظرية الاحتمالات والحقول ذات الصلة . 129 : 113-132 . doi : 10.1007/s00440-003-0330-y . S2CID 121086772 . 
  26. ↑ شارابوف، ر. ر.؛ لابشين، أ. ف. (2006). "تقارب الخوارزميات الجينية". التعرف على الأنماط وتحليل الصور . 16 (3): 392-397 . doi : 10.1134/S1054661806030084 . S2CID 22890010 . 
  27. ↑ سرينيفاس، م.؛ باتنايك، ل. (1994). "الاحتمالات التكيفية للتهجين والطفرة في الخوارزميات الجينية" (ملف PDF) . معاملات IEEE في الأنظمة والإنسان وعلم التحكم الآلي . 24 (4): 656-667 . رمز Bibcode : 1994ITSMC..24..656S . doi : 10.1109/21.286385 . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.
  28. ↑ كوون، واي دي؛ كوون، إس بي؛ جين، إس بي؛ كيم، جي واي (2003). "خوارزمية جينية محسّنة للتقارب مع طريقة التكبير المتتالي لحل مسائل التحسين المستمر". الحوسبة والهياكل . 81 (17): 1715-1725 . doi : 10.1016/S0045-7949(03)00183-4 .
  29. ↑ تشانغ، ج.؛ تشونغ، هـ.؛ لو، و. ل. (2007). "التزاوج التكيفي القائم على التجميع واحتمالات الطفرة للخوارزميات الجينية". معاملات IEEE في الحوسبة التطورية . 11 (3): 326-335 . Bibcode : 2007ITEC...11..326Z . doi : 10.1109/TEVC.2006.880727 . S2CID 2625150 . 
  30. ↑ بافاي، جي؛ جيتا، تي في (2019). "عوامل تهجين جديدة تستخدم مبادئ الهيمنة والهيمنة المشتركة لتسريع تقارب الخوارزميات الجينية". الحوسبة اللينة . 23 (11): 3661-3686 . doi : 10.1007/s00500-018-3016-1 . S2CID 254028984 . 
  31. ↑ لي، جيه سي إف؛ زيمرلي، دي؛ يونغ، بي. (2022). "كهربة ريفية مرنة متصلة بشبكة باستخدام خوارزمية جينية استيفائية مستوية" . الطاقة والذكاء الاصطناعي . 10 100186. Bibcode : 2022EneAI..1000186L . doi : 10.1016/j.egyai.2022.100186 . S2CID 250972466 . 
  32. ↑ انظر على سبيل المثال التطور باختصار مؤرشف في 15 أبريل 2016 في Wayback Machine أو مثال في مشكلة البائع المتجول ، على وجه الخصوص استخدام عامل إعادة تركيب الحافة .
  33. ↑ غولدبيرغ، دي إي؛ كورب، بي؛ ديب، ك. (1989). "الخوارزميات الجينية الفوضوية : تحليل الدوافع، والنتائج الأولية" . الأنظمة المعقدة . 5 (3): 493-530 . 
  34. ↑ التعبير الجيني: الحلقة المفقودة في الحوسبة التطورية
  35. ↑ هاريك، ج. (1997). تعلم الربط لحل المشكلات ذات الصعوبة المحدودة بكفاءة باستخدام الخوارزميات الجينية (أطروحة دكتوراه). قسم علوم الحاسوب، جامعة ميشيغان، آن أربور.
  36. ↑ توموياغا ب، تشيندريش م، سومبر أ، سودريا-أندريو أ، فيلافافيلا-روبلز ر. إعادة تشكيل أنظمة توزيع الطاقة الأمثل وفقًا لمبدأ باريتو باستخدام خوارزمية جينية قائمة على NSGA-II. مجلة Energies. 2013؛ 6(3):1439-1455.
  37. ↑ غروس، بيل (2 فبراير 2009). "نظام طاقة شمسية يتتبع الشمس" . TED . تم الاطلاع عليه في 20 نوفمبر 2013 .
  38. ↑ هورنبي، جي إس؛ ليندن، دي إس؛ لون، جي دي، تصميم الهوائيات الآلي باستخدام الخوارزميات التطورية (PDF)
  39. ↑ "حركة مرنة تعتمد على العضلات للكائنات ثنائية الأرجل" .
  40. ↑ إيفانز، ب.؛ والتون، س.ب. (ديسمبر 2017). "التحسين الديناميكي الهوائي لمركبة إعادة دخول فائقة السرعة تعتمد على حل معادلة بولتزمان-بي جي كي والتحسين التطوري" . نمذجة الرياضيات التطبيقية . 52 : 215-240 . doi : 10.1016/j.apm.2017.07.024 . ISSN 0307-904X . 
  41. ↑ سكينا، ستيفن (2010). دليل تصميم الخوارزميات ( الطبعة الثانية). سبرينغر ساينس + بيزنس ميديا . ISBN  978-1-849-96720-4.
  42. ↑ تورينج، آلان م. (أكتوبر 1950). "آلات الحوسبة والذكاء". مجلة مايند . LIX (238): 433– 460. doi : 10.1093/mind/LIX.236.433 .
  43. ^ باريتشيلي، نيلز آل (1954). "نماذج رقمية من عمليات التطور". الطرق : 45 – 68.
  44. ↑ باريسيلي، نيلز آل (1957). "عمليات التطور التكافلي التي تحققت بواسطة طرق اصطناعية". ميثودوس : 143-182 .
  45. ↑ فريزر، أليكس (1957). "محاكاة الأنظمة الوراثية بواسطة الحواسيب الرقمية الآلية. الجزء الأول: مقدمة" . المجلة الأسترالية للعلوم البيولوجية 10 ( 4): 484-491 . Bibcode : 1957AuJBS..10..484F . doi : 10.1071/BI9570484 .
  46. ↑ فريزر، أليكس ؛ بورنيل، دونالد (1970). نماذج الحاسوب في علم الوراثة . نيويورك: ماكجرو هيل. ISBN 978-0-07-021904-5.
  47. ↑ كروسبي، جاك ل. (1973). المحاكاة الحاسوبية في علم الوراثة . لندن: جون وايلي وأولاده. ISBN 978-0-471-18880-3.
  48. ↑ 27/02/1996 - توفي هانز بريمرمان، الأستاذ الفخري والرائد في علم الأحياء الرياضي بجامعة كاليفورنيا في بيركلي، عن عمر يناهز 69 عامًا
  49. ↑ فوغل، ديفيد ب.، محرر. (1998). الحوسبة التطورية: السجل الأحفوري . نيويورك: مطبعة IEEE. ISBN 978-0-7803-3481-6.
  50. ↑ باريسيلي، نيلز آل (1963). "الاختبار العددي لنظريات التطور. الجزء الثاني: اختبارات أولية للأداء، والتكافل، والحياة الأرضية". مجلة Acta Biotheoretica . 16 ( 3-4 ): 99-126 . doi : 10.1007/BF01556602 . S2CID 86717105 . 
  51. ^ ريشينبرج، إنجو (1973). استراتيجية التطور . شتوتغارت: هولزمان فروبوج. رقم ISBN 978-3-7728-0373-4.
  52. ^ شويفيل، هانز بول (1974). Numerische Optimierung von Computer-Modellen (أطروحة دكتوراه) .
  53. ^ شويفيل، هانز بول (1977). التحسين العددي لقفازات نماذج الكمبيوتر في استراتيجية التطور : مع إحدى القواعد الأساسية في تسلق التلال وإستراتيجية السقوط . بازل؛ شتوتغارت: بيركهاوزر. رقم ISBN  978-3-7643-0876-6.
  54. ^ شويفيل، هانز بول (1981). التحسين العددي لنماذج الكمبيوتر (ترجمة عام 1977 Numerische Optimierung von Computor-Modellen mittels der Evolutionsstrategie . Chichester؛ نيويورك: Wiley. ISBN 978-0-471-09988-8.
  55. ↑ الداوودي، نمير (2008). منهج لتصميم نظام طيار آلي لطائرة هليكوبتر بدون طيار باستخدام الخوارزميات الجينية والتقسية المحاكاة . ص 99. ISBN  978-0549773498– عبر كتب جوجل.
  56. ↑ ماركوف، جون (29 أغسطس 1990). "ما هو أفضل جواب؟ إنه البقاء للأصلح" . نيويورك تايمز . تم الاطلاع عليه في 13 يوليو 2016 .
  57. ↑ روجيرو، موراي أ. (1 أغسطس 2009) خمسة عشر عامًا وما زال العد مستمرًا. مؤرشف في 30 يناير 2016 في أرشيف الإنترنت . Futuresmag.com. تم الاطلاع عليه في 7 أغسطس 2013.
  58. ↑ إيفولفر: تحسين متطور للجداول الإلكترونية . باليسيد. تم الاطلاع عليه بتاريخ 2013-08-07.
  59. ^ لي لين. سالديفار، ألفريدو آلان فلوريس؛ باي، يون؛ تشن، يي؛ ليو، كونفينج؛ لي ، يون (2019). "معايير لتقييم خوارزميات التحسين والقياس المعياري لمُحسِّنات MATLAB الخالية من المشتقات للوصول السريع للممارسين" . الوصول إلى IEEE . 7 : 79657– 79670. بيب كود : 2019IEEEA...779657L . دوى : 10.1109/ACCESS.2019.2923092 . S2CID 195774435 . 
  60. ↑ كوهون، ج. وآخرون (2002). الخوارزميات التطورية للتصميم الفيزيائي لدوائر VLSI (ملف PDF) . سبرينغر، الصفحات 683-712، 2003. ISBN  978-3-540-43330-9تمت أرشفة الملف (PDF) من النسخة الأصلية في 9 أكتوبر 2022.{{cite book}}تم |journal=تجاهله ( مساعدة )
  61. ^ بيليكان، مارتن؛ غولدبرغ، ديفيد E.؛ كانتو باز، إريك (1 يناير 1999). BOA: خوارزمية التحسين بايزي . جيكو'99. ص 525 – 532. ISBN  9781558606111.{{cite book}}تم |journal=تجاهله ( مساعدة )
  62. ↑ بيليكان، مارتن (2005). خوارزمية التحسين البايزي الهرمي : نحو جيل جديد من الخوارزميات التطورية ( الطبعة الأولى). برلين [ua]: سبرينغر. ISBN   978-3-540-23774-7.
  63. ↑ ثيرينز، ديرك (11 سبتمبر 2010). "خوارزمية الشجرة الجينية للربط". حل المشكلات المتوازية من الطبيعة، PPSN XI . ص 264-273 . doi : 10.1007/978-3-642-15844-5_27 . ISBN  978-3-642-15843-8.
  64. ↑ فيريرا، سي (2001). "برمجة التعبير الجيني: خوارزمية تكيفية جديدة لحل المشكلات" (ملف PDF) . الأنظمة المعقدة . 13 (2): 87-129 . arXiv : cs/0102027 . Bibcode : 2001cs........2027F . مؤرشف (ملف PDF) من الأصل في 9 أكتوبر 2022.
  65. ↑ فالكناور، إيمانويل (1997). الخوارزميات الجينية ومسائل التجميع . تشيتشستر، إنجلترا: جون وايلي وأولاده المحدودة. ISBN 978-0-471-97150-4.
  66. ↑ زلوخين، مارك؛ بيراتاري، ماورو؛ ميوليو، نيكولاس؛ دوريغو، ماركو (1 أكتوبر 2004). "البحث القائم على النموذج للتحسين التوافقي: دراسة نقدية". حوليات بحوث العمليات . 131 ( 1-4 ): 373-395 . CiteSeerX 10.1.1.3.427 . doi : 10.1023/B:ANOR.0000039526.52305.af . ISSN 0254-5330 . S2CID 63137 .   
  67. ↑ رانيا حسن، بابك كوهانيم، أوليفييه دي ويك، جيرهارد فينتر (2005) مقارنة بين تحسين سرب الجسيمات والخوارزمية الجينية
  68. ^ بودري، بينوا؛ فرانك فلوري؛ جان مارك جيزيكيل ؛ إيف لو ترون (مارس-أبريل 2005). “تحسين حالة الاختبار التلقائي: خوارزمية بكتريولوجية” (PDF) . برامج آي إي إي إي . 22 (2): 76– 82. بيب كود : 2005ISoft..22b..76B . دوى : 10.1109/MS.2005.30 . S2CID 3559602 . أرشفة (PDF) من النسخة الأصلية في 9 أكتوبر 2022 . تم الاسترجاع في 9 أغسطس 2009 . 
  69. ↑ سيفيتشي أوغلو، ب. (2012). "تحويل الإحداثيات الديكارتية المركزية الجغرافية إلى إحداثيات جيوديسية باستخدام خوارزمية البحث التفاضلي". الحوسبة وعلوم الأرض . 46 : 229-247 . Bibcode : 2012CG.....46..229C . doi : 10.1016/j.cageo.2011.12.011 .
  70. ↑ كيلستروم، ج. (ديسمبر 1991). "حول كفاءة التكيف الغاوسي". مجلة نظرية التطبيقات الأمثلية . 71 (3): 589-597 . doi : 10.1007/BF00941405 . S2CID 116847975 . 

فهرس

موارد

دروس تعليمية