बिक्री विक्रेता

Question

यात्रा करने के लिए आनुवांशिक एल्गोरिदम लागू करते समय एक विस्तृत प्रश्न मैंने इस पर विभिन्न सामग्री पढ़ी और सिद्धांत और अवधारणाओं को समझ लिया, हालांकि, पेपर में से कोई भी गुणसूत्र की फिटनेस की गणना करने के विवरण का वर्णन नहीं करता है (जो एक मार्ग का प्रतिनिधित्व करता है) आसन्न शहरों (गुणसूत्र में) शामिल है जो सीधे किनारे (ग्राफ में) से जुड़े नहीं हैं।

उदाहरण के लिए, गुणसूत्र 1 | 3 | 2 | 8 | 4 | 5 | 6 | 7, जिसमें प्रत्येक जीन ग्राफ/मानचित्र पर किसी शहर की अनुक्रमणिका का प्रतिनिधित्व करता है, हम इसकी फिटनेस की गणना कैसे करते हैं (यानी दूरी की कुल राशि यात्रा की गई) यदि, कहें, शहर 2 और 8 के बीच कोई सीधा किनारा/लिंक नहीं है। क्या हम 2 से 8 के बीच एक मार्ग बनाने के लिए कुछ प्रकार के लालची एल्गोरिदम का पालन करते हैं, और इस मार्ग की दूरी को जोड़ते हैं समूचा?

जीएस को टीएसपी लागू करते समय यह समस्या काफी आम लगती है। कोई भी जिसने इसे पहले किया है कृपया अपना अनुभव साझा करें। धन्यवाद।

Answer 1

यदि आपके ग्राफ पर 2 और 8 के बीच कोई लिंक नहीं है, तो शास्त्रीय यात्रा विक्रेता समस्या के लिए इसमें 2 | 8 या 8 | 2 के साथ कोई गुणसूत्र अमान्य है। यदि आपको 2 और 8 के बीच कोई अन्य मार्ग मिलता है, तो संभवतः आप "प्रत्येक स्थान पर एक बार" आवश्यकता का उल्लंघन करने जा रहे हैं।

एक वास्तव में डोडी-लेकिन-व्यावहारिक समाधान उन नोड्स के बीच किनारों को अविश्वसनीय रूप से उच्च दूरी के साथ, या यहां तक ​​कि अगर आपकी भाषा का समर्थन करता है तो भी शामिल है। इस तरह, आपका मानक कम से कम फिटनेस फ़ंक्शन स्वाभाविक रूप से उन्हें छीन लेगा।

मुझे लगता है कि समस्या के मूल निर्माण में सभी नोड्स के बीच किनारों को शामिल किया गया है, इसलिए यह एक गैर-मुद्दा है।

Answer 2

यह सही प्रकार की समस्या है, विशेष क्रॉसओवर और उत्परिवर्तन विधियों को टीएसपी समस्याओं के लिए जीए आधारित समाधानों के लिए लागू किया गया है। यह question देखें।

Answer 3

यदि गुणसूत्र वैध समाधान का प्रतिनिधित्व नहीं करता है तो यह समस्या को हल करने के लिए पूरी तरह से अनुपयुक्त है। तो आप फिटनेस का ऑर्डर कैसे करते हैं इसके आधार पर। यानी यदि कोई निचली संख्या अधिक फिटनेस का प्रतिनिधित्व करती है (संभवतया एक अच्छा विचार जब फिटनेस कुल लागत का प्रतिनिधित्व करता है) तो आप इसे अधिकतम मान निर्दिष्ट करेंगे और उस क्रोमोसोन पर किसी और फिटनेस गणना को तोड़ देंगे जब आप एक जीन अनुक्रम प्राप्त करते हैं जो अमान्य है।

(या इसके विपरीत, यह शून्य के एक फिटनेस आवंटित करता है, तो एक उच्च फिटनेस का मतलब है एक chromosone इस काम के लिए अधिक उपयुक्त है)

तथापि के रूप में अन्य लोगों ने बताया है कि यह सुनिश्चित करना है कि अवैध chromosones न पाए जाते हैं बेहतर हो सकता है । हालांकि यदि वह स्वयं एक अत्यधिक कॉम्पेक्स प्रक्रिया है तो उन्हें अनुमति देता है और यह सुनिश्चित करता है कि टूटी हुई क्रोमोसोन लगातार पीढ़ियों में इसे बनाने की संभावना नहीं है, यह एक स्वीकार्य दृष्टिकोण हो सकता है।