Jump to content
Sign in to follow this  
ABV

Genetic Algorithm

Recommended Posts

ABV

This is an example of a Genetic Algorithm. It has Roulette, Tournament or Elite policy selections. Due to my lack of GUI skills! You will have to comment out the appropriate line it the script to select the one you would like to use.

To use it enter a string into the target box and the GA will evolve an individual to match.

A simple example but all the GA elements are there

#include <GUIConstants.au3>
#include <GUIConstantsEx.au3>
#Include <GuiEdit.au3>
#include <WindowsConstants.au3>
#include <staticconstants.au3>
#include <ScrollBarConstants.au3>
#include <Array.au3>

Opt("GUIOnEventMode", 1)

Const $iPopulationSize  = 500   ;Size of the GA population.
Const $iMutationRate    = 0.3   ;Rate of mutaion 0.1 is 10% of population will be mutated.
Const $iBreedRate       = 0.8   ;Breed rate 50% of the population will be replaced with off spring. The Fittest will suvrvive into next generation.

Local $iTargetStringLength  = 0
Local $sTargetString        = ""
Local $sDisplayString       = ""
Local $iGeneration          = 0
Local $iBestIndex           = 0
local $sPopulation[$iPopulationSize][3];Invividual, Fitness, Roulette

#region GUI Start

$GUI = GUICreate("Toy Genetic Algorithm", 310, 500)
GUISetOnEvent($GUI_EVENT_CLOSE, "SpecialEvents")

$iInputLabel = GUICtrlCreateLabel ("Enter Your Target String here", 75, 10, 150, 20)
$sInputString = GUICtrlCreateInput("ABC", 100, 30, 100, 20)

$iOuputLabel = GUICtrlCreateLabel ("Genentic Algorithm Population Output", 75, 80, 250, 120)
$sOutput = _GUICtrlEdit_Create($GUI, "", 10, 110, 290, 300)


$OK_Btn = GUICtrlCreateButton("Go", 220, 450, 75, 20)
GUICtrlSetOnEvent($OK_Btn, "OKPressed")

GUISetState()

#EndRegion GUI End


While (1)
    Sleep(10)
Wend

Func SpecialEvents()
    ;Destroy the GUI including the controls
    GUIDelete()
    ;Exit the script
    Exit
EndFunc 

Func OKPressed()
    
    $iGeneration = 0
    $sTargetString = GUICtrlRead($sInputString)
    $iTargetStringLength = StringLen($sTargetString)
    
    PopulationInit($sPopulation,$iTargetStringLength, $iPopulationSize)
    PopulationFit($sPopulation,$iTargetStringLength, $iPopulationSize, $sTargetString)
    
    Do
        $iGeneration += 1
        
        ;***************************************************************************
        ;** Select one of the three selection methods. Elite, Tournament or Roulette
        ;***************************************************************************
        
        PopulationBreedTournament($sPopulation, $iPopulationSize, $iTargetStringLength)
        ;PopulationBreedElite($sPopulation, $iPopulationSize)
        ;PopulationBreedRoulette($sPopulation, $iPopulationSize, $iTargetStringLength)
        
        PopulationMutate($sPopulation)
        PopulationFit($sPopulation,$iTargetStringLength, $iPopulationSize, $sTargetString)
        $iBestIndex = PopulationBest($sPopulation, $iPopulationSize)
        PopulationDisplay($sPopulation, $sDisplayString, $iGeneration, $iBestIndex)
    
    Until (StringCompare($sPopulation[$iBestIndex][0],$sTargetString) = 0)

    _GUICtrlEdit_AppendText($sOutput,@CRLF & "**** Target Evolved ****")


EndFunc


;************************************************
;** Create a random start population
;************************************************
Func PopulationInit(ByRef $sPopulation, $iTargetStringLength, $iPopulationSize)
    
    Local $iIndexA
    Local $iIndexB
    Local $sRandomString
    Local $sRandomChar
        
    for $iIndexA = 0 to $iPopulationSize-1 Step 1
        $sRandomString = ""

        For $iIndexB = 0 to $iTargetStringLength-1 Step 1
            $sRandomChar = random(10,254,1)
            $sRandomString = $sRandomString & Chr($sRandomChar)
        Next
        
        $sPopulation[$iIndexA][0] = $sRandomString

    Next
    
EndFunc

;************************************************************************************************
;** Test the individual fitness by comparing each character ASCII value with the Target String
;************************************************************************************************
Func PopulationFit(ByRef $sPopulation, $iTargetStringLength, $iPopulationSize, $sTargetString)
    
    Local $iIndexA
    Local $iIndexB
    Local $sTestString
    Local $sTestChar
    Local $sTargetChar
    Local $SCharFit
    Local $sStringFitness
    Local $iMaxFitness 
    Local $iTotalFitness
    Local $sPopulationTemp[$iPopulationSize]
    Local $iMostUnfit
        
    $iBestIndex  = $iPopulationSize -1
    
    for $iIndexA = 0 to $iPopulationSize-1 Step 1
        
        $sStringFitness = 0 
        $SCharFit       = 0
        $sTestString = $sPopulation[$iIndexA][0]

        For $iIndexB = 0 to $iTargetStringLength-1 Step 1
            
            $sTargetChar = StringMid($sTargetString,($iIndexB+1),1)
            $sTestChar   = StringMid($sTestString,($iIndexB+1),1) 
            
            $SCharFit    = ABS(ASC($sTargetChar) - ASC($sTestChar))
            
            $sStringFitness = $sStringFitness + $SCharFit
        Next
        
        $sPopulation[$iIndexA][1] = $sStringFitness     

    Next
    ;Lowest is best at this point, the next set of instructions make the highest fitness best
    ;find worst individual
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulationTemp [$iIndexA] = $sPopulation[$iIndexA][1]
    Next
    
    $iMostUnfit = _ArrayMax($sPopulationTemp)
    
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulation[$iIndexA][1] = $iMostUnfit - $sPopulation[$iIndexA][1]
    Next

EndFunc

;************************************************
;** Tournament method
;** Two individuals of the population are taken at complete random 
;** keep the fittest as the first one, then do the 
;** same with another two individuals and keep the fittest.
;** From the fittest two individuals, we want to ensure their genes 
;** crossover to create 2 offspring 
;************************************************

Func PopulationBreedTournament(ByRef $sPopulation, $iPopulationSize, $iTargetStringLength)
    
    Local $iRandomAA
    Local $iRandomAB
    Local $iRandomBA
    Local $iRandomBB
    Local $iIndexA
    
    Local $iFitnessAA
    Local $iFitnessAB
    Local $iFitnessBA
    Local $iFitnessBB
    
    Local $sParentA
    Local $sParentB
    
    Local $sOffspringA
    Local $sOffspringB
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR
    Local $sPopulationTemp = $sPopulation
    ;make a copy of population
        
    for $iIndexA = 0 to INT(($iPopulationSize-1) *$iBreedRate) Step 1
    
        ;select some indiviuals on a random basis
        $iRandomAA = Random(0,($iPopulationSize-1),1)
        $iRandomAB = Random(0,($iPopulationSize-1),1)
        $iRandomBA = Random(0,($iPopulationSize-1),1)
        $iRandomBB = Random(0,($iPopulationSize-1),1)
        
        $iFitnessAA = $sPopulationTemp[$iRandomAA][1]
        $iFitnessAB = $sPopulationTemp[$iRandomAB][1]
        $iFitnessBA = $sPopulationTemp[$iRandomBA][1]
        $iFitnessBB = $sPopulationTemp[$iRandomBB][1]
        
        ;Determine fitter Individuals frmm random set   
        IF $iFitnessAA > $iFitnessAB Then;is AA fitter the AB
            $sParentA = $sPopulationTemp[$iRandomAA][0]
        Else 
            $sParentA = $sPopulationTemp[$iRandomAB][0]
        EndIf
        
        IF $iFitnessBA > $iFitnessBB Then;is BA fitter the BB
            $sParentB = $sPopulationTemp[$iRandomBA][0]
        Else 
            $sParentB = $sPopulationTemp[$iRandomBB][0]
        EndIf
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspringA = $sOffspringAL & $sOffspringBR
        $sOffspringB = $sOffspringBL & $sOffspringAR
        
        $sPopulation[$iRandomAA][0] = $sParentA
        $sPopulation[$iRandomAB][0] = $sParentB
        $sPopulation[$iRandomBA][0] = $sOffspringA
        $sPopulation[$iRandomBB][0] = $sOffspringB
        
    Next
    ;_arraydisplay($sPopulation)
EndFunc

;************************************************
;** Roulette method
;************************************************
Func PopulationBreedRoulette(ByRef $sPopulation, $iPopulationSize, $iTargetStringLength)
    
    Local $iACC = 0
    Local $iIndexA = 0
    Local $iIndexB = 0
    Local $iRouletteA
    Local $iRouletteB
    
    Local $iParentA
    Local $iParentB
    Local $sParentA
    Local $sParentB
    
    Local $sOffspring
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR

    _ArraySort($sPopulation, 0, 0, 0, 1)
    
    ;make a copy of population
    Local $sPopulationTemp = $sPopulation

    
    $sPopulationTemp[$iIndexA][2] = 0
    
    for $iIndexA = 1 to ($iPopulationSize-1) Step 1
        $iACC = $iACC + $sPopulationTemp[$iIndexA][1]
        $sPopulationTemp[$iIndexA][2] = $iACC
    Next
            
    for $iIndexA = 0 to INT(($iPopulationSize-1) * $iBreedRate) Step 1
        
        $iRouletteA = Random(0,$iACC,1)
        $iRouletteB = Random(0,$iACC,1)
        
        for $iIndexB = 0 to ($iPopulationSize-2) Step 1
            ;IF ($iRouletteA > $sPopulationTemp[$iIndexB][2]) AND ($iRouletteA < $sPopulationTemp[$iIndexB+1][2]) Then
            IF ($sPopulationTemp[$iIndexB][2] > $iRouletteA) Then
                $iParentA = $iIndexB
                ExitLoop
            EndIf
        Next
        
        for $iIndexB = 0 to ($iPopulationSize-2) Step 1
            ;IF ($iRouletteB > $sPopulationTemp[$iIndexB][2]) AND ($iRouletteB < $sPopulationTemp[$iIndexB+1][2]) Then
            IF ($sPopulationTemp[$iIndexB][2] > $iRouletteB) Then
                $iParentB = $iIndexB
                ExitLoop
            EndIf
        Next
        
        ;msgbox(1,"",$iParentA&","&$iRouletteA&","& $iParentB &","&$iRouletteB)
        $sParentA = $sPopulationTemp[$iParentA][0] 
        $sParentB = $sPopulationTemp[$iParentB][0] 
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspring = $sOffspringAL & $sOffspringBR
        
        ;replace upper section of population replacing weaker individuals
        $sPopulation[$iIndexA][0] = $sOffspring
    
    Next

    
EndFunc


;************************************************
;** Elite, best individuals go through, weakest are replaced by offspring
;************************************************
Func PopulationBreedElite(ByRef $sPopulation, $iPopulationSize)
    
    Local $iACC = 0
    Local $iIndexA = 0
    Local $iIndexB = 0
    Local $iRouletteA
    Local $iRouletteB
    
    Local $iParentA
    Local $iParentB
    Local $sParentA
    Local $sParentB
    
    Local $sOffspring
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR

    _ArraySort($sPopulation, 1, 0, 0, 1)
    
    ;make a copy of population
    Local $sPopulationTemp = $sPopulation

    
    for $iIndexA = 0 to INT(($iPopulationSize-2) * $iBreedRate) Step 1
        
        ;msgbox(1,"",$iParentA&","&$iRouletteA&","& $iParentB &","&$iRouletteB)
        $sParentA = $sPopulationTemp[$iIndexA][0] 
        $sParentB = $sPopulationTemp[$iIndexA+1][0] 
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspring = $sOffspringAL & $sOffspringBR
        
        ;replace upper section of population replacing weaker individuals
        $sPopulation[($iPopulationSize-1) - $iIndexA][0] = $sOffspring
    
    Next

    
EndFunc

;**************************************
;** Mutate a portion of the population
;**************************************

Func PopulationMutate(ByRef $sPopulation)
    
    Local $iIndexA
    Local $iIndexB
    
    Local $iRandomA
    
    Local $sRandomString
    Local $sRandomChar
    
    
    for $iIndexA = 0 to INT(($iPopulationSize-1)*$iMutationRate) Step 1
        $sRandomString = ""
                
        For $iIndexB = 0 to $iTargetStringLength-1 Step 1
            $sRandomChar = random(10,254,1)
            $sRandomString = $sRandomString & Chr($sRandomChar)
        Next
        
        $iRandomA = Random(0,($iPopulationSize-1),1)
        $sPopulation[$iRandomA][0] = $sRandomString

    Next
EndFunc

;**************************************
;** Find Best individual
;**************************************

Func PopulationBest(ByRef $sPopulation, $iPopulationSize)
    
    Local $iIndexA
    
    Local $sPopulationTemp[$iPopulationSize]
    
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulationTemp [$iIndexA] = $sPopulation[$iIndexA][1]
    Next
    
    $iIndexBest = _ArrayMaxIndex($sPopulationTemp)
    
    Return $iIndexBest
EndFunc


;************************************************
;** Send Contents of Population to GUI 
;************************************************
Func PopulationDisplay(ByRef $sPopulation, ByRef $sDisplayString, $iGeneration, $iBestIndex)
    
    Local $iIndexA
    
    _GUICtrlEdit_AppendText($sOutput,@CRLF & "************************************************************")
    _GUICtrlEdit_AppendText($sOutput,@CRLF & "Generation = " & $iGeneration & " Best Individual = " &$sPopulation[$iBestIndex][0])
    
;~  for $iIndexA = 0 to $iPopulationSize-1 Step 1
;~      _GUICtrlEdit_AppendText($sOutput, @CRLF & "Ind = " & $sPopulation[$iIndexA][0] & ", Fit = " & $sPopulation[$iIndexA][1])
;~  Next

EndFunc

Share this post


Link to post
Share on other sites
twitchyliquid64

I've always wanted to make a genetic algorithm.

great work! you must be very smart.


ongoing projects:-firestorm: Largescale P2P Social NetworkCompleted Autoit Programs/Scripts: Variable Pickler | Networked Streaming Audio (in pure autoIT) | firenet p2p web messenger | Proxy Checker | Dynamic Execute() Code Generator | P2P UDF | Graph Theory Proof of Concept - Breadth First search

Share this post


Link to post
Share on other sites
Skrip

Can you further explain how this works?


[left][sub]We're trapped in the belly of this horrible machine.[/sub][sup]And the machine is bleeding to death...[/sup][sup][/sup][/left]

Share this post


Link to post
Share on other sites
ABV

There is a pretty good overview at the link below

GA Tutorial

I developed this GA so it was fairly easy to follow. It's a basic implementation, not the best, but has all the elements

Share this post


Link to post
Share on other sites
ABV

I have changed the mutation algorithm to change a single character instead of the whole string

(Mutated a chromosome rather than an individual)

It will now solve "Hello World!" in 70 generations.

Generation = 70 Best Individual = Hello World!

#include <GUIConstants.au3>
#include <GUIConstantsEx.au3>
#Include <GuiEdit.au3>
#include <WindowsConstants.au3>
#include <staticconstants.au3>
#include <ScrollBarConstants.au3>
#include <Array.au3>

Opt("GUIOnEventMode", 1)

Const $iPopulationSize  = 1000  ;Size of the GA population.
Const $iMutationRate    = 0.3   ;Rate of mutaion 0.1 is 10% of population will be mutated.
Const $iBreedRate       = 0.5   ;Breed rate 50% of the population will be replaced with off spring. The Fittest will suvrvive into next generation.

Local $iTargetStringLength  = 0
Local $sTargetString        = ""
Local $sDisplayString       = ""
Local $iGeneration          = 0
Local $iBestIndex           = 0
local $sPopulation[$iPopulationSize][3];Invividual, Fitness, Roulette

#region GUI Start

$GUI = GUICreate("Toy Genetic Algorithm", 310, 500)
GUISetOnEvent($GUI_EVENT_CLOSE, "SpecialEvents")

$iInputLabel = GUICtrlCreateLabel ("Enter Your Target String here", 75, 10, 150, 20)
$sInputString = GUICtrlCreateInput("ABC", 100, 30, 100, 20)

$iOuputLabel = GUICtrlCreateLabel ("Genentic Algorithm Population Output", 75, 80, 250, 120)
$sOutput = _GUICtrlEdit_Create($GUI, "", 10, 110, 290, 300)


$OK_Btn = GUICtrlCreateButton("Go", 220, 450, 75, 20)
GUICtrlSetOnEvent($OK_Btn, "OKPressed")

GUISetState()

#EndRegion GUI End


While (1)
    Sleep(10)
Wend

Func SpecialEvents()
    ;Destroy the GUI including the controls
    GUIDelete()
    ;Exit the script
    Exit
EndFunc 

Func OKPressed()
    
    $iGeneration = 0
    $sTargetString = GUICtrlRead($sInputString)
    $iTargetStringLength = StringLen($sTargetString)
    
    PopulationInit($sPopulation,$iTargetStringLength, $iPopulationSize)
    PopulationFit($sPopulation,$iTargetStringLength, $iPopulationSize, $sTargetString)
    
    Do
        $iGeneration += 1
        
        ;***************************************************************************
        ;** Select one of the three selection methods. Elite, Tournament or Roulette
        ;***************************************************************************
        
        PopulationBreedTournament($sPopulation, $iPopulationSize, $iTargetStringLength)
        ;PopulationBreedElite($sPopulation, $iPopulationSize)
        ;PopulationBreedRoulette($sPopulation, $iPopulationSize, $iTargetStringLength)
        
        PopulationMutate($sPopulation,$iTargetStringLength)
        PopulationFit($sPopulation,$iTargetStringLength, $iPopulationSize, $sTargetString)
        $iBestIndex = PopulationBest($sPopulation, $iPopulationSize)
        PopulationDisplay($sPopulation, $sDisplayString, $iGeneration, $iBestIndex)
        
;~      IF $iGeneration = 100 Then
;~          _ArrayDisplay($sPopulation)
;~          $iGeneration = 0
;~      EndIf
    
    Until (StringCompare($sPopulation[$iBestIndex][0],$sTargetString) = 0)

    _GUICtrlEdit_AppendText($sOutput,@CRLF & "**** Target Evolved ****")


EndFunc


;************************************************
;** Create a random start population
;************************************************
Func PopulationInit(ByRef $sPopulation, $iTargetStringLength, $iPopulationSize)
    
    Local $iIndexA
    Local $iIndexB
    Local $sRandomString
    Local $sRandomChar
        
    for $iIndexA = 0 to $iPopulationSize-1 Step 1
        $sRandomString = ""

        For $iIndexB = 0 to $iTargetStringLength-1 Step 1
            $sRandomChar = random(32,126,1);random(10,254,1)
            $sRandomString = $sRandomString & Chr($sRandomChar)
        Next
        
        $sPopulation[$iIndexA][0] = $sRandomString

    Next
    
EndFunc

;************************************************************************************************
;** Test the individual fitness by comparing each character ASCII value with the Target String
;************************************************************************************************
Func PopulationFit(ByRef $sPopulation, $iTargetStringLength, $iPopulationSize, $sTargetString)
    
    Local $iIndexA
    Local $iIndexB
    Local $sTestString
    Local $sTestChar
    Local $sTargetChar
    Local $SCharFit
    Local $sStringFitness
    Local $iMaxFitness 
    Local $iTotalFitness
    Local $sPopulationTemp[$iPopulationSize]
    Local $iMostUnfit
        
    $iBestIndex  = $iPopulationSize -1
    
    for $iIndexA = 0 to $iPopulationSize-1 Step 1
        
        $sStringFitness = 0 
        $SCharFit       = 0
        $sTestString = $sPopulation[$iIndexA][0]

        For $iIndexB = 0 to $iTargetStringLength-1 Step 1
            
            $sTargetChar = StringMid($sTargetString,($iIndexB+1),1)
            $sTestChar   = StringMid($sTestString,($iIndexB+1),1) 
            
            $SCharFit    = ABS(ASC($sTargetChar) - ASC($sTestChar))
            
            $sStringFitness = $sStringFitness + $SCharFit
        Next
        
        $sPopulation[$iIndexA][1] = $sStringFitness     

    Next
    ;Lowest is best at this point, the next set of instructions make the highest fitness best
    ;find worst individual
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulationTemp [$iIndexA] = $sPopulation[$iIndexA][1]
    Next
    
    $iMostUnfit = _ArrayMax($sPopulationTemp)
    
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulation[$iIndexA][1] = $iMostUnfit - $sPopulation[$iIndexA][1]
    Next

EndFunc

;************************************************
;** Tournament method
;** Two individuals of the population are taken at complete random 
;** keep the fittest as the first one, then do the 
;** same with another two individuals and keep the fittest.
;** From the fittest two individuals, we want to ensure their genes 
;** crossover to create 2 offspring 
;************************************************

Func PopulationBreedTournament(ByRef $sPopulation, $iPopulationSize, $iTargetStringLength)
    
    Local $iRandomAA
    Local $iRandomAB
    Local $iRandomBA
    Local $iRandomBB
    Local $iIndexA
    
    Local $iFitnessAA
    Local $iFitnessAB
    Local $iFitnessBA
    Local $iFitnessBB
    
    Local $sParentA
    Local $sParentB
    
    Local $sOffspringA
    Local $sOffspringB
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR
    ;make a copy of population
    
    _ArraySort($sPopulation, 1, 0, 0, 1)
    
    ;_arraydisplay($sPopulation)
        
    for $iIndexA = 0 to INT(($iPopulationSize-1) *$iBreedRate) Step 1
    
        ;select some indiviuals on a random basis, pick from best half...
        $iRandomAA = Random(0,($iPopulationSize-1),1)
        $iRandomAB = Random(0,($iPopulationSize-1),1)
        $iRandomBA = Random(0,($iPopulationSize-1),1)
        $iRandomBB = Random(0,($iPopulationSize-1),1)
        
        $iFitnessAA = $sPopulation[$iRandomAA][1]
        $iFitnessAB = $sPopulation[$iRandomAB][1]
        $iFitnessBA = $sPopulation[$iRandomBA][1]
        $iFitnessBB = $sPopulation[$iRandomBB][1]
        
        ;Determine fitter Individuals frmm random set   
        IF $iFitnessAA > $iFitnessAB Then;is AA fitter the AB
            $sParentA = $sPopulation[$iRandomAA][0]
        Else 
            $sParentA = $sPopulation[$iRandomAB][0]
        EndIf
        
        IF $iFitnessBA > $iFitnessBB Then;is BA fitter the BB
            $sParentB = $sPopulation[$iRandomBA][0]
        Else 
            $sParentB = $sPopulation[$iRandomBB][0]
        EndIf
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspringA = $sOffspringAL & $sOffspringBR
        $sOffspringB = $sOffspringBL & $sOffspringAR
        
        $sPopulation[$iRandomAA][0] = $sParentA
        $sPopulation[$iRandomAB][0] = $sParentB
        
        $sPopulation[($iPopulationSize-1) - $iIndexA][0] = $sOffspringB
        $sPopulation[($iPopulationSize-2) - $iIndexA][0] = $sOffspringA
        
    Next
    ;_arraydisplay($sPopulation)
EndFunc

;************************************************
;** Roulette method
;************************************************
Func PopulationBreedRoulette(ByRef $sPopulation, $iPopulationSize, $iTargetStringLength)
    
    Local $iACC = 0
    Local $iIndexA = 0
    Local $iIndexB = 0
    Local $iRouletteA
    Local $iRouletteB
    
    Local $iParentA
    Local $iParentB
    Local $sParentA
    Local $sParentB
    
    Local $sOffspring
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR

    _ArraySort($sPopulation, 0, 0, 0, 1)
    
    ;make a copy of population
    Local $sPopulationTemp = $sPopulation

    
    $sPopulationTemp[$iIndexA][2] = 0
    
    for $iIndexA = 1 to ($iPopulationSize-1) Step 1
        $iACC = $iACC + $sPopulationTemp[$iIndexA][1]
        $sPopulationTemp[$iIndexA][2] = $iACC
    Next
            
    for $iIndexA = 0 to INT(($iPopulationSize-1) * $iBreedRate) Step 1
        
        $iRouletteA = Random(0,$iACC,1)
        $iRouletteB = Random(0,$iACC,1)
        
        for $iIndexB = 0 to ($iPopulationSize-2) Step 1
            ;IF ($iRouletteA > $sPopulationTemp[$iIndexB][2]) AND ($iRouletteA < $sPopulationTemp[$iIndexB+1][2]) Then
            IF ($sPopulationTemp[$iIndexB][2] > $iRouletteA) Then
                $iParentA = $iIndexB
                ExitLoop
            EndIf
        Next
        
        for $iIndexB = 0 to ($iPopulationSize-2) Step 1
            ;IF ($iRouletteB > $sPopulationTemp[$iIndexB][2]) AND ($iRouletteB < $sPopulationTemp[$iIndexB+1][2]) Then
            IF ($sPopulationTemp[$iIndexB][2] > $iRouletteB) Then
                $iParentB = $iIndexB
                ExitLoop
            EndIf
        Next
        
        ;msgbox(1,"",$iParentA&","&$iRouletteA&","& $iParentB &","&$iRouletteB)
        $sParentA = $sPopulationTemp[$iParentA][0] 
        $sParentB = $sPopulationTemp[$iParentB][0] 
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspring = $sOffspringAL & $sOffspringBR
        
        ;replace upper section of population replacing weaker individuals
        $sPopulation[$iIndexA][0] = $sOffspring
    
    Next

    
EndFunc


;************************************************
;** Elite, best individuals go through, weakest are replaced by offspring
;************************************************
Func PopulationBreedElite(ByRef $sPopulation, $iPopulationSize)
    
    Local $iACC = 0
    Local $iIndexA = 0
    Local $iIndexB = 0
    Local $iRouletteA
    Local $iRouletteB
    
    Local $iParentA
    Local $iParentB
    Local $sParentA
    Local $sParentB
    
    Local $sOffspring
    Local $sCrossOver
    Local $sOffspringAL
    Local $sOffspringAR
    Local $sOffspringBL
    Local $sOffspringBR

    _ArraySort($sPopulation, 1, 0, 0, 1)
    
    ;make a copy of population
    Local $sPopulationTemp = $sPopulation

    
    for $iIndexA = 0 to INT(($iPopulationSize-2) * $iBreedRate) Step 1
        
        ;msgbox(1,"",$iParentA&","&$iRouletteA&","& $iParentB &","&$iRouletteB)
        $sParentA = $sPopulationTemp[$iIndexA][0] 
        $sParentB = $sPopulationTemp[$iIndexA+1][0] 
        
        $sCrossOver = Random(1,($iTargetStringLength),1)
        
        $sOffspringAL = StringLeft($sParentA,$sCrossOver)
        $sOffspringAR = StringRight($sParentA,($iTargetStringLength - $sCrossOver))
        
        $sOffspringBL = StringLeft($sParentB,$sCrossOver)
        $sOffspringBR = StringRight($sParentB,($iTargetStringLength - $sCrossOver))
        
        $sOffspring = $sOffspringAL & $sOffspringBR
        
        ;replace upper section of population replacing weaker individuals
        $sPopulation[($iPopulationSize-1) - $iIndexA][0] = $sOffspring
    
    Next

    
EndFunc

;**************************************
;** Mutate a portion of the population
;**************************************

Func PopulationMutate(ByRef $sPopulation, $iTargetStringLength)
    
    Local $iIndexA
    Local $iIndexB
    
    Local $iRandomA
    
    Local $sRandomString
    Local $sString
    Local $sRandomChar
    
    
    for $iIndexA = 0 to INT(($iPopulationSize-1)*$iMutationRate) Step 1
        $sMutateString = ""
                
;~      For $iIndexB = 0 to $iTargetStringLength-1 Step 1
;~          $sRandomChar = random(10,254,1)
;~          $sMutateString = $sMutateString & Chr($sRandomChar)
;~      Next
        
        $iRandomA = Random(0,($iPopulationSize-1),1)
        
        $sRandomChar = random(32,126,1)
        
        $sString = $sPopulation[$iRandomA][0]
        
        $sMutatePos = Random(1,($iTargetStringLength),1)
        
        $sMutateAL = StringLeft($sString,($sMutatePos-1))
        $sMutateAR = StringRight($sString,($iTargetStringLength - ($sMutatePos)))
        
        $sMutateString = $sMutateAL & chr($sRandomChar) & $sMutateAR
        
        ;msgbox(1,$sString,$sMutateAL &","& chr($sRandomChar) &","& $sMutateAR)
        
        $sPopulation[$iRandomA][0] = $sMutateString

    Next
EndFunc

;**************************************
;** Find Best individual
;**************************************

Func PopulationBest(ByRef $sPopulation, $iPopulationSize)
    
    Local $iIndexA
    
    Local $sPopulationTemp[$iPopulationSize]
    
    for $iIndexA = 0 to ($iPopulationSize-1) Step 1
        $sPopulationTemp [$iIndexA] = $sPopulation[$iIndexA][1]
    Next
    
    $iIndexBest = _ArrayMaxIndex($sPopulationTemp)
    
    Return $iIndexBest
EndFunc


;************************************************
;** Send Contents of Population to GUI 
;************************************************
Func PopulationDisplay(ByRef $sPopulation, ByRef $sDisplayString, $iGeneration, $iBestIndex)
    
    Local $iIndexA
    
    _GUICtrlEdit_AppendText($sOutput,@CRLF & "************************************************************")
    _GUICtrlEdit_AppendText($sOutput,@CRLF & "Generation = " & $iGeneration & " Best Individual = " &$sPopulation[$iBestIndex][0])
    
;~  for $iIndexA = 0 to $iPopulationSize-1 Step 1
;~      _GUICtrlEdit_AppendText($sOutput, @CRLF & "Ind = " & $sPopulation[$iIndexA][0] & ", Fit = " & $sPopulation[$iIndexA][1])
;~  Next

EndFunc

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×