ما هي الاختلافات بين الخوارزميات الجينية المحاكاة والخوارزميات الوراثية؟

Question

ما هي الاختلافات ذات الصلة ، من حيث الأداء وحالات الاستخدام ، بين الصلب المحاكاة (مع البحث بين الفول) والخوارزميات الوراثية؟

أعلم أنه يمكن اعتبار SA على أنه GA حيث يكون حجم السكان واحدًا فقط ، لكنني لا أعرف الفرق الرئيسي بين الاثنين.

أيضًا ، أحاول التفكير في موقف سيتفوق فيه SA GA أو GA على SA. مثال واحد بسيط فقط سيساعدني على الفهم سيكون كافياً.

Answer 1

بالمعنى الدقيق للكلمة ، هذين الأمرين-محاكاة الصلب (SA) و الخوارزميات الوراثية ليست خوارزميات ولا غرضها "تعدين البيانات".

كلاهما الوفاة-زوجان من المستويات فوق "الخوارزمية" على مقياس التجريد. بمعنى آخر ، يشير كلا المصطلحين إلى استعارات عالية المستوى-واحدة مستعارة من المعادن والآخر من البيولوجيا التطورية. في التصنيف الفوقي ، SA هو أ طريقة واحدة الدولة و GA هو أ طريقة السكان (في فئة فرعية جنبا إلى جنب مع PSO ، ACO ، وآخرون ، يشار إليها عادة باسم الوفاة المستوحاة من الناحية البيولوجية).

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

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

أي تقنية حل لحل مشاكل الغطاء ، بغض النظر عن الخوارزمية ، ستتألف بشكل أساسي من هذه الخطوات (والتي عادة ما يتم ترميزها ككتلة واحدة داخل حلقة متكررة):

1. قم بتشفير التفاصيل الخاصة بالمجال في دالة التكلفة (إنها التقليل من القيمة التي يتم إرجاعها من هذه الوظيفة التي تشكل "حلًا" لمشكلة C/O) ؛

2. تقييم وظيفة التكلفة التي تمر في "تخمين" أولي (لبدء التكرار) ؛

3. استنادًا إلى القيمة التي تم إرجاعها من وظيفة التكلفة ، قم بإنشاء حل مرشح لاحق (أو أكثر من واحد ، اعتمادًا على meta-heuristic) إلى وظيفة التكلفة ؛

4. تقييم كل حل مرشح عن طريق تمريره في مجموعة وسيطة ، إلى وظيفة التكلفة ؛

5. كرر الخطوات (3) و (4) حتى يتم استيفاء بعض معيار التقارب أو الوصول إلى الحد الأقصى لعدد التكرار.

يتم توجيه التعريفيات الوصفية إلى الخطوة (3) أعلاه ؛ وبالتالي ، تختلف SA و GA في كيفية توليد حلول مرشح للتقييم حسب وظيفة التكلفة. وبعبارة أخرى ، هذا هو المكان المناسب للتطلع إلى فهم كيف تختلف هاتين المفصلين.

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

---

فكيف يولد SA و GA حلول المرشح؟

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

p = e((-highCost - lowCost)/temperature)

أو في بيثون:

p = pow(math.e, (-hiCost - loCost) / T)

مصطلح "درجة الحرارة" هو متغير تتحلل قيمته أثناء تقدم التحسين-وبالتالي ، فإن احتمال أن يقبل SA حل أسوأ مع زيادة عدد التكرار.

بعبارة أخرى ، عندما تبدأ الخوارزمية في التكرار ، تكون T كبيرة جدًا ، والتي تسبب الخوارزمية للانتقال إلى كل حل مرشح تم إنشاؤه حديثًا ، سواء كان أفضل أو أسوأ من الحل الحالي-على سبيل المثال ، مشي عشوائي في مساحة الحل. مع زيادة عدد التكرار (أي ، حيث تبرد درجة الحرارة) يصبح البحث الخوارزمية عن مساحة الحل أقل تساهلاً ، حتى عند t = 0 ، يكون السلوك متطابقًا مع خوارزمية تسلق التل بسيطة (أي الحلول الأفضل فقط من الحلول الأفضل من التيار يتم قبول الحل).

الخوارزميات الوراثية تختلف جدا. لسبب واحد-وهذا شيء كبير-إنه لا يولد حلًا مرشحًا واحدًا بل "سكانهم" بأكمله. يعمل مثل هذا: GA يدعو وظيفة التكلفة على كل عضو (حل المرشح) للسكان. ثم يصنفهم ، من الأفضل إلى الأسوأ ، التي تم طلبها بالقيمة التي تم إرجاعها من وظيفة التكلفة ("الأفضل" لها أدنى قيمة). من هذه القيم المرتبة (وحلول المرشحين المقابلة لها) يتم إنشاء السكان التاليين. يتم إنشاء أعضاء جدد من السكان في الأساس واحدة من ثلاث طرق. يشار إلى الأول عادةً باسم "النخبوية" ، وفي الواقع يشير عادة إلى أخذ أعلى حلول المرشحين في المرتبة ونقلها مباشرة-غير معدل-إلى الجيل القادم. عادةً ما يشار إلى الطريقتين الأخريين من الأعضاء الجدد من السكان باسم "طفرة" و "كروس". عادةً ما تتضمن الطفرة تغييرًا في عنصر واحد في متجه حل المرشح من السكان الحاليين لإنشاء متجه حل في السكان الجدد ، على سبيل المثال ، [4 ، 5 ، 1 ، 0 ، 2] => [4 ، 5 ، 2 ، 0 ، 2]. إن نتيجة عملية التقاطع تشبه ما يمكن أن يحدث إذا كان بإمكان المتجهات ممارسة الجنس-على سبيل المثال ، وهو متجه طفل جديد تتألف عن عناصره من بعض من كل من والدين.

هذه هي الاختلافات الخوارزمية بين GA و SA. ماذا عن الاختلافات في الأداء؟

في الممارسة العملية: (يقتصر ملاحظاتي على مشكلات التحسين التوافقي) GA دائمًا يتفوق على SA (إرجاع قيمة عائد "أفضل" من وظيفة التكلفة-وهي قيمة قريبة من الحد الأدنى العالمي لمساحة الحل) ، ولكن في أعلى مستوى تكلفة الحساب. بقدر ما أدرك ، فإن الكتب المدرسية والمنشورات التقنية تقرأ نفس الاستنتاج من القرار.

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

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

Answer 2

من الصعب حقًا مقارنة الاثنين منذ أن استلهموا من مجالات مختلفة ..

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

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

Answer 3

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

أعتقد أن الفرق الأكبر بين الاثنين هو فكرة التقاطع في GA ، وبالتالي فإن أي مثال على مهمة التعلم المناسبة لـ GA من SA سوف يتوقف على معنى التقاطع في هذا الموقف وكيف يتم تنفيذه.

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

أعتقد أنه من الصعب التوصل إلى حالة مقنعة لأحدها على الآخر لأنها حقًا خوارزميات متشابهة تمامًا ، وربما تم تطويرها من نقاط انطلاق مختلفة تمامًا.