जेनेटिक एल्गोरिदम टूर्नामेंट चयन

Question

मैं एक जेनेटिक एल्गोरिदम लिख रहा हूं और मैं रूले व्हील चयन से टूर्नामेंट चयन में जाने की योजना बना रहा हूं, लेकिन मुझे संदेह है कि मेरी समझ त्रुटिपूर्ण हो सकती है।

यदि मैं केवल जनसंख्या में एन/2 सर्वोत्तम समाधान चुन रहा हूं, तो निश्चित रूप से मैं आबादी से बहुत जल्दी बाहर निकलता हूं?

एल्गोरिथ्म के मेरे समझ है:

for(Member m in currentPopulation){ 
    Member randomMember1 = random member of currentPopulation which is then removed from currentPopulation 
    Member randomMember2 = as above; 
    //Mutate and crossover 

    if(randomMember1.getScore() > randomMember2.getScore()){ 
     nextGeneration.add(randomMember1); 
    } else { 
     nextGeneration.add(randomMember2); 
    } 
} 

मैं इस को सही ढंग से समझ रहा हूं?

Answer 1

टूर्नामेंट चयन में चयनित व्यक्तियों को आबादी से हटाया नहीं जाता है। आप कई टूर्नामेंट में भाग लेने के लिए एक ही व्यक्ति का चयन कर सकते हैं।

अपने कोड को थोड़ा करीब देखने के बाद, मुझे लगता है कि आपको एक और गलतफहमी है। आप आमतौर पर टूर्नामेंट के सभी सदस्यों को उत्परिवर्तित/क्रॉसओवर नहीं करेंगे। इसके बजाए, आप एक टूर्नामेंट करते हैं, जिसमें टूर्नामेंट के विजेता को उत्परिवर्तन/क्रॉसओवर से गुजरने के लिए एक व्यक्ति के रूप में चुना जा रहा है। इसका मतलब है कि उत्परिवर्तन के लिए आपका टूर्नामेंट आकार कम से कम 2 होना चाहिए, और क्रॉसओवर के लिए आकार कम से कम 3 जीतने के साथ कम से कम 3 होना चाहिए (या आप प्रत्येक अलग-अलग माता-पिता को क्रॉसओवर चुनने के लिए 2 अलग-अलग टूर्नामेंट कर सकते हैं)।

कुछ छद्म कोड मदद कर सकता है:

while (nextPopulation too small) { 
    Members tournament = randomly choose x members from currentPopulation 

    if(crossover){ 
     Member parents = select best two members from tournament 
     Member children = crossover(parents) 
     nextPopulation.add(children); 
    } else { 
     Member parent = select best one member from tournament 
     Member child = mutate(parent) 
     nextPopulation.add(child); 
    } 
} 

Answer 2

आप हर पीढ़ी में अपनी आबादी से n/2 व्यक्तियों का चयन कर रहे हैं, आप अंततः एक बिंदु तक पहुंच जाएगा जहां 1. की आबादी क्या आप चयन के अलावा करना चाहते हैं कि आपकी अगली पीढ़ी के लिए उत्परिवर्तन या क्रॉसओवर का उपयोग करके आम तौर पर उन लोगों पर जो टूर्नामेंट में विजेता थे।

तो, प्रत्येक पीढ़ी के लिए, आपके पास आकार की आबादी है - आप इसे अपने चयन के माध्यम से एन/2 में कम करते हैं, और फिर उन एन/2 सदस्यों को लगभग 2/2 सदस्यों के लिए पुन: पेश और/या उत्परिवर्तित करने के लिए आपकी अगली पीढ़ी (जो औसतन, उन लोगों की तुलना में 'फिटर' होगी जो पिछली पीढ़ी से प्रगति नहीं करती थीं)।

Answer 3

टूर्नामेंट चयन:

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

स्यूडोकोड:

choose k (the tournament size) individuals from the population at random 
choose the best individual from pool/tournament with probability p 
choose the second best individual with probability p*(1-p) 
choose the third best individual with probability p*((1-p)^2) 
and so on... 

नियतात्मक टूर्नामेंट चयन सबसे अच्छा व्यक्ति का चयन करता है (जब पी = 1) किसी भी टूर्नामेंट में। एक 1-रास्ता टूर्नामेंट (के = 1) चयन यादृच्छिक चयन के बराबर है।चयनित व्यक्ति को आबादी से हटाया जा सकता है कि चयन वांछित से किया जाता है, अन्यथा अगली पीढ़ी के लिए व्यक्तियों को एक से अधिक बार चुना जा सकता है। (स्टोकास्टिक) फिटनेस आनुपातिक चयन विधि की तुलना में, स्टॉचस्टिक शोर की कमी के कारण टूर्नामेंट चयन अक्सर अभ्यास में लागू होता है।

MatLab में टूर्नामेंट चयन:

Matepool=randi(PopLength,PopLength,2);%%select two individuals randomly for tournament and chooose the one with best fitness value 
%% number of tournament is equal to the number of population size 
for i=1:PopLength 
    if Fitness(Matepool(i,1))>= Fitness(Matepool(i,2)) 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,1),1:IndLength); 
    else 
     SelectedPop(i,1:IndLength)=CurrentPop(Matepool(i,2),1:IndLength); 
    end 
end