Code center > Darwinbots Program Source Code

Genetic Distance is slow as hell

<< < (2/3) > >>

Numsgil:

--- Quote from: Botsareus on April 04, 2013, 04:36:34 PM ---1.) This will mean permanently expending the DNA to include markers for all robots.
1a.) How will we save these?
1b.) Now I am slowing down the simulation under any conditions.

--- End quote ---

You shouldn't need any extra data stored with the DNA.  The algorithm just works on arrays of objects (could be characters, could just as easily be DNA base pairs).  All you need is "is-equal" and "is-not-equal".  And if you're only running it on bots that've changed it shouldn't slow the sim down at all.


--- Quote ---2.) I am not seeing an algorithm in my head that will accurately correct for mutations to memorized structures, especially because I am planning to make translocation and amplification work.

--- End quote ---

Just set a dirty flag when you mutate the DNA.  If the dirty flag is set when you need the genetic distance, recompute it.  Otherwise use the cached value.

Botsareus:
[Small bump]

Sorry guys, I got distracted watching BioShock Infinite on YouTube  :P. I promise I'll have something on Tuesday.

Botsareus:
[bump]
Still a little slow, but I don't think people who are running the one with x50 point mutations will care much about genetic distance.

Botsareus:
[bump]

Added another algorithm called 'Simple Genetic Distance' Still about as slow as the first one, but always checks all robots per graph update and a little less accurate. Here it is:


--- Code: ---Public Function GeneticDistanceSimple(ByVal r1 As Integer, ByVal r2 As Integer) As Single
Dim b As Integer
Dim a As Integer
Dim mlst1() As Integer
Dim mlst2() As Integer
ReDim mlst1(UBound(rob(r1).DNA))
ReDim mlst2(UBound(rob(r2).DNA))
' match list is declared
Do 'loop until end of both DNA

    'special case different dna length
    If a > UBound(rob(r1).DNA) Then
        If mlst2(b) = 0 Then mlst2(b) = -2
        GoTo fine
    End If
    If b > UBound(rob(r2).DNA) Then
        If mlst1(a) = 0 Then mlst1(a) = -2
        GoTo fine
    End If

    If rob(r1).DNA(a).tipo = rob(r2).DNA(b).tipo And rob(r1).DNA(a).value = rob(r2).DNA(b).value Then
        'the data is the same, store -1
        mlst1(a) = -1
        mlst2(b) = -1
    Else
        'lets see if data picks up later
        Dim b2 As Integer
        For b2 = b + 1 To UBound(rob(r2).DNA)
            If rob(r2).DNA(b2).tipo = rob(r1).DNA(a).tipo And rob(r2).DNA(b2).value = rob(r1).DNA(a).value And mlst2(b2) < 1 Then
                'data does pickup later
                mlst1(a) = b2 + 1
                mlst2(b2) = a + 1
                b = b - 1
                GoTo fine
            End If
        Next
        'lets see if data picks up early
        For b2 = b - 1 To 0 Step -1
            If rob(r2).DNA(b2).tipo = rob(r1).DNA(a).tipo And rob(r2).DNA(b2).value = rob(r1).DNA(a).value And mlst2(b2) < 1 Then
                'data does pickup later
                mlst1(a) = b2 + 1
                mlst2(b2) = a + 1
                b = b - 1
                GoTo fine
            End If
        Next
        'the data is different, store -2
        If mlst1(a) < 1 Then mlst1(a) = -2
        If mlst2(b) < 1 Then mlst2(b) = -2
    End If

fine:
    a = a + 1
    b = b + 1
Loop Until a > UBound(rob(r1).DNA) And b > UBound(rob(r2).DNA)

Dim diff As Integer 'holds diff data counter

For a = 0 To UBound(rob(r1).DNA)
    If mlst1(a) = -2 Then
        diff = diff + 1
    ElseIf mlst1(a) > 0 Then 'data was moved
        If a > 0 Then
            If Abs(mlst1(a - 1) - mlst1(a)) > 1 Then 'only store if move unconsequtive
                diff = diff + 1
            End If
        Else 'should we store the move automaticaly?
            diff = diff + 1
        End If
    End If
Next

For a = 0 To UBound(rob(r2).DNA)
    If mlst2(a) = -2 Then
        diff = diff + 1
    ElseIf mlst2(a) > 0 Then 'data was moved
        If a > 0 Then
            If Abs(mlst2(a - 1) - mlst2(a)) > 1 Then 'only store if move unconsequtive
                diff = diff + 1
            End If
        Else 'should we store the move automaticaly?
            diff = diff + 1
        End If
    End If
Next

GeneticDistanceSimple = diff / (UBound(rob(r1).DNA) + UBound(rob(r2).DNA) + 2)
End Function

--- End code ---

I check twice r1 <--- ---> r2, and select for the smallest genetic distance, because the algorithm calculates differently based on what order the dna is introduced, left handed or right handed.

It is up to the user if he wants better accuracy per robot or better accuracy for population, both "Simple genetic distance" and "Genetic distance" graphs are included.

Botsareus:
It is happening people. I am running my first sexual reproduction sim. I will post it tomorrow and send a SVN package.  8)

edit:

I can not believe what I am looking at! I have an eco-system developing within 55000 cycles.
This is one of the coolest experiments I have ever ran.

Navigation

[0] Message Index

[#] Next page

[*] Previous page