Stokastisk universell provtagning

SUS exempel

Stokastisk universal sampling ( SUS ) är en teknik som används i genetiska algoritmer för att välja potentiellt användbara lösningar för rekombination. Det introducerades av James Baker.

SUS är en utveckling av fitness proportionate selection (FPS) som inte uppvisar någon partiskhet och minimal spridning. Där FPS väljer flera lösningar från populationen genom upprepade slumpmässiga urval, använder SUS ett enda slumpmässigt värde för att ta ett urval av alla lösningar genom att välja dem med jämnt fördelade intervall . Detta ger svagare medlemmar av befolkningen (beroende på deras kondition) en chans att bli vald.

FPS kan ha dåliga prestationer när en medlem av befolkningen har en riktigt stor kondition i jämförelse med andra medlemmar. Med hjälp av en kamliknande linjal utgår SUS från ett litet slumpmässigt tal och väljer nästa kandidater från resten av befolkningen som återstår, vilket inte tillåter de starkaste medlemmarna att mätta kandidatutrymmet.

Beskriven som en algoritm, ser pseudokod för SUS ut så här:

    
        
        
            
      SUS(  Population  ,  N  )  F  := total kondition för  Population  N  := antal avkommor att hålla  P  := avstånd mellan pekarna (  F  /  N  )  Start  := slumptal mellan 0 och  P  Pekare  := [  Start  +  i  *  P  |  i  i  [0..(  N  -1)]]  returnerar  RWS(  Population  ,  Pointers  ) RWS(  Population  ,  Points  )  Behåll  = []  för  P  i  Points  I  := 0  medan  fitnesssumman av  Population  [0..  I  ] <  P  I  ++ lägg till  Population  [  I  ] till  Keep  return  Keep 

Där 0 Population [ .. I ] är uppsättningen av individer med array-index 0 till (och inklusive) I .

Här beskriver RWS() huvuddelen av fitnessproportionellt urval (även känt som " rouletthjulsval ") – i sant fitnessproportionellt val är parametern Points alltid en (sorterad) lista med slumptal från 0 till F . Algoritmen ovan är avsedd att vara illustrativ snarare än kanonisk.

Se även

• Fitness proportionellt urval
• Belöningsbaserat urval