بحاجة الى مساعدة للتكيف مع خوارزمية وراثية إلى " حل " بائع السفر على روبي

Question

لقد قمت للتو بتنزيل مكتبة آي آي 4 آر http://ai4r.rubyforge.org/ وأنا أستخدم الخوارزمية الجينية للحصول على مسار جيد من أماكن متعددة ، تماما مثل هذا:

http://ai4r.rubyforge.org/geneticAlgorithms.html

ولكن أنا بحاجة إلى أن تكون قادرة على تعيين مدينة البداية.

أي فكرة عن كيفية استخدام هذا على "ثابت" مدينة البداية?

Answer 1

بشكل عام ، لا تنظر إلى التنفيذ الخاص بـ Ruby ، يمكنك فقط إزالة مدينة البداية ، وافترض أن الحافة الأولى التي تم اتباعها هي من مدينة البداية إلى ما تنتجه GA.فقط تأكد من تضمين الميزة الأولى في وظيفة التكلفة / اللياقة.

Answer 2

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

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

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

Answer 3

الجواب الذي ستحصل عليه من الجا إلى تسب هو دورة ، وهذا يعني أن المدينة الأولى هي على التي تريدها.على سبيل المثال ، إذا كان الجواب [3 4 2 6 1 5], ، وأريد أن تكون المدينة الأولى 2 ثم يمكنني" طرح " الحل [2 6 1 5 3 4].

على الرغم من أنه يمكنك تقليل مشكلتك بمقدار 1 إذا قمت في وظيفة التقييم بتحديد المدينة الأولى.في هذه الحالة يجب أن تأخذ في الاعتبار أنه يجب تعديل الأفراد لحساب هذا.على سبيل المثال ، إذا قمت بتعيين المدينة الأولى إلى #2 (مشكلة 6 مدن) وكان لديك فرد [1 2 3 4 5] (6 مدن ناقص واحد).الفرد لتقييم هو [2 1 3 4 5 6].