سؤال تفصيلي عند تطبيق الخوارزمية الوراثية على بائع السفر

StackOverflow https://stackoverflow.com/questions/2542174

سؤال

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

على سبيل المثال ، بالنظر إلى كروموسوم 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7 ، حيث يمثل كل جين فهرس المدينة على الرسم البياني/الخريطة ، كيف نحسب لياقته (أي مجموع مجموعها المسافات التي تم نقلها) ، على سبيل المثال ، لا توجد حافة/صلة مباشرة بين المدينة 2 و 8. هل نتبع نوعًا من الخوارزمية الجشعية للعمل على طريق بين 2 و 8 ، وإضافة مسافة هذا الطريق إلى المجموع؟

تبدو هذه المشكلة شائعة جدًا عند تطبيق GA على TSP. أي شخص قام بذلك قبل مشاركة تجربتك. شكرًا.

هل كانت مفيدة؟

المحلول

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

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

أعتقد أن الصياغة الأصلية للمشكلة تتضمن حواف بين جميع العقد ، لذلك هذا غير قضية.

نصائح أخرى

هذا هو النوع الدقيق من المشكلة ، وقد تم تطبيق طرق التقاطع المتخصصة وطرق الطفرة على حلول GA لمشاكل TSP. انظر الى هذا سؤال.

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

(أو العكس ، قم بتعيينه للياقة صفر إذا كانت اللياقة العليا تعني أن كروموسون أكثر ملاءمة للمهمة)

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

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى StackOverflow
scroll top