عملية التقاطع في الخوارزمية الجينية لـ TSP

Question

أحاول حل مشكلة البائع المتجول (TSP) مع الخوارزمية الجينية.الجينوم الخاص بي هو تبديل لرأس في الرسم البياني (مسار للبائع).

كيف يجب أن أقوم بعملية التقاطع على الجينوم الخاص بي؟

أين يمكنني العثور على تطبيقات لمشكلتي في C#؟

Answer 1

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

والفكرة الرئيسية هي لتمثيل التقليب كما تسلسله انعكاس، أي لكل عنصر i، مخزن في a[i] كيف العديد من العناصر أكبر من i هي على يسار i في التقليب. على عكس التمثيل المباشر، والقيد الوحيد على a[i] هو محلي، أي a[i] لا يمكن أن يكون أكبر من N - i. وهذا يعني أن انتقال بسيط من اثنين من سلاسل انعكاس صالحة تنتج دائما اثنين من سلاسل انعكاس صالحة - لا حاجة لمعالجة خاصة من تكرار العناصر

.

Answer 2

وبدلا من استخدام القياسية GA تقنية عبر أكثر من (ك <لأ href = "https://stackoverflow.com/questions/1544055/rossover-operation-in-genetic-algorithm-for-tsp/1544326#1544326" > حددها MusiGenesis )، فإنه من الأفضل استخدام أمر عبر أكثر لمسألة البائع المتجول .

والنهج المعتاد لا تعمل بشكل جيد لTSP لأن وظيفة اللياقة البدنية حساسة للغاية لمواقف النسبية للمدن مختلفة في مسار تطور بدلا من مناصبهم المطلقة. على سبيل المثال، إذا كنت تقوم بزيارتها جميع العواصم الأوروبية، وأقصر الطرق لا تعتمد حقا على ما إذا كنت زيارة براتيسلافا 1، 2، أو 9. ما هو أكثر أهمية هو أن أزوره <لأ href = "http://maps.google.co.uk/maps؟f=q&source=s_q&hl=en&geocode=&q=vienna+to+bratislava&sll=53.800651،-4.064941&sspn=18.252022 ، 28.959961 & أي = UTF8 & ض = 10 "يختلط =" noreferrer نوفولو "> على الفور قبل أو مباشرة بعد زيارة فيينا بدلا من زيارة هلسنكي وأثينا و6 عواصم أخرى بينهما.

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

Answer 3

هنا برنامج C# نهج لما تبحث عنه.

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

لا يرتبط بشكل مباشر ولكنه جدير بالملاحظة لمن ينظر إلى GA، هو التجربة الأصلية "النهائية" في جورجيا التجربة الأصلية "النهائية" في جورجيا بواسطة البروفيسور.ألدرمان (من شهرة RSA)، الذي استخدم جزيئات الحمض النووي الفعلية [في برنامج C - مجرد مزاح] لحل مشكلة الرسم البياني ذات الصلة، وهي مشكلة الرسوم البيانية هاميلتون.

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

Answer 4

والغرض من التقاطع هو توسيع فضاء البحث التطوري من خلال الجمع بين مجموعات الجينية الجديدة.

ومعايير الحقيقي الوحيد المطلوب لعملية تطورية هي أن المنتج من عبور يحتوي على أجزاء من كلا الوالدين، ويمثل الجينوم صالح.

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

Answer 5

وهنا هو بلدي التنفيذ الدقيق للما يسمى طريقة "كروس تعيين جزئيا" في GA لTSP.

هنا هو الورقة التي يشرح تعيين جزئيا كروس في النظرية وأدناه هو قانون بلدي.

//construct a new individual with the genes of the parents
//method used is cross over mapping
//note that Individual datastrucuture contains an integer array called Genes which            //contains the route.
//
public Individual Breed(Individual father, Individual mother)
{
    int[] genes = new int[father.Genes.Length];
    int[] map = new int[father.Genes.Length + 1]; //create a map to map the indices
    int crossoverPoint1 = rand.Next(1, father.Genes.Length - 2); //select 2 crossoverpoints, without the first and last nodes, cuz they are always thje same
    int crossoverPoint2 = rand.Next(1, father.Genes.Length - 2);
    father.Genes.CopyTo(genes, 0); //give child all genes from the father
    for (int i = 0; i < genes.Length; i++) //create the map
    {
        map[genes[i]] = i;
    }
    //int[] genesToCopy = new int[Math.Abs(crossoverPoint1 - crossoverPoint2)]; //allocate space for the mother genes to copy
    if (crossoverPoint1 > crossoverPoint2) //if point 1 is bigger than point 2 swap them
    {
        int temp = crossoverPoint1;
        crossoverPoint1 = crossoverPoint2;
        crossoverPoint2 = temp;
    }
    //Console.WriteLine("copy mother genes into father genes from {0} to {1}", crossoverPoint1, crossoverPoint2);
    for (int i = crossoverPoint1; i <= crossoverPoint2; i++) //from index one to the 2nd
    {
        int value = mother.Genes[i];
        int t = genes[map[value]]; //swap the genes in the child
        genes[map[value]] = genes[i];
        genes[i] = t;
        t = map[genes[map[value]]]; //swap the indices in the map
        map[genes[map[value]]] = map[genes[i]];
        map[genes[i]] = t;
    }
    Individual child = new Individual(genes);
    return child;
}

Answer 6

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

مثال:

قبل:أBCDFجي إتش

بعد:أفيدكبجي إتش

Answer 7

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

AAAAAAAAAA
BBBBBBBBBB

وطريقة واحدة لإعادة تجميع هذه السلاسل "الأم" اثنين هو اختيار عشوائيا نقطة تقاطع (مثلا، موقف 3)، مما أدى إلى هذه المتتاليات "الطفل" اثنين:

AAABBBBBBB
BBBAAAAAAA

وأو، هل يمكن اختيار عشوائيا نقطتين كروس (قل و 3 و 8)، مما أدى إلى هذه المتتاليات اثنين:

AAABBBBBAA
BBBAAAAABB

لالمرح وتقلب إضافي، يمكنك أيضا إدخال إمكانية الطفرات نقطة في بعض الأحيان:

AAABBBABAA
BBBAAAAABB

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