[2, 8, 7, 4, 5, 3, 6, 9, 0, 1]
I chose to use 25 genes as being roughly 10*log(10) of the form:
[a,b] where a and b are positions on the list and the gene is expressed by comparing items in the list at those positions and swapping them if the number at the lower position is greater than the one at the higher position. "His" dna is:
[[1, 4], [7, 9], [2, 6], [0, 7], [1, 7], [6, 8], [3, 5], [3, 8], [2, 4], [2, 3], [5, 7], [0, 6], [6, 9], [8, 9], [0, 2], [3, 6], [4, 8], [0, 1], [5, 6], [7, 9], [4, 6], [1, 3], [4, 7], [6, 7], [3, 5]]
So working on the given list:
[2, 8, 7, 4, 5, 3, 6, 9, 0, 1] original list
[2, 5, 7, 4, 8, 3, 6, 9, 0, 1] swapped items 1 and 4 (0 indexed) because the rightmost is less than the leftmost of the two
[2, 5, 7, 4, 8, 3, 6, 1, 0, 9] swapped 7 and 9...
[2, 5, 6, 4, 8, 3, 7, 1, 0, 9] etc...
[1, 5, 6, 4, 8, 3, 7, 2, 0, 9]
[1, 2, 6, 4, 8, 3, 7, 5, 0, 9]
[1, 2, 6, 4, 8, 3, 0, 5, 7, 9]
[1, 2, 6, 3, 8, 4, 0, 5, 7, 9]
[1, 2, 6, 3, 8, 4, 0, 5, 7, 9]
[1, 2, 6, 3, 8, 4, 0, 5, 7, 9]
[1, 2, 3, 6, 8, 4, 0, 5, 7, 9]
[1, 2, 3, 6, 8, 4, 0, 5, 7, 9]
[0, 2, 3, 6, 8, 4, 1, 5, 7, 9]
[0, 2, 3, 6, 8, 4, 1, 5, 7, 9]
[0, 2, 3, 6, 8, 4, 1, 5, 7, 9]
[0, 2, 3, 6, 8, 4, 1, 5, 7, 9]
[0, 2, 3, 1, 8, 4, 6, 5, 7, 9]
[0, 2, 3, 1, 7, 4, 6, 5, 8, 9]
[0, 2, 3, 1, 7, 4, 6, 5, 8, 9]
[0, 2, 3, 1, 7, 4, 6, 5, 8, 9]
[0, 2, 3, 1, 7, 4, 6, 5, 8, 9]
[0, 2, 3, 1, 6, 4, 7, 5, 8, 9]
[0, 1, 3, 2, 6, 4, 7, 5, 8, 9]
[0, 1, 3, 2, 5, 4, 7, 6, 8, 9]
[0, 1, 3, 2, 5, 4, 6, 7, 8, 9]
This finished result is pretty typical that 2 items are 1 position out of order...
A lot of times it gets it perfectly and the worst I've seen it do is 4 items needing to be swapped 1 position.
Testing this dna on 100 random lists gives that this will be the average result.
**finding the dna**
To find this above sequence of dna I:
1. Created 10 sort worms with random dna
Then repeat these steps below for 1000 generations
2. "Breed" all worms each worm with every other, where every new worm gets each gene from one of its parents to make its dna.
3. Reduce this list of worms to the 5 best performers as the average root mean squared of how out of order the list is after he uses his dna on 100 random lists.
4. Add 5 more random worms to the 5 you're left with.
At the end this worm above was the best performer.
**Source Code**
import random
class creature():
def __init__(self):
self.dna = []
def new(self, dnalength, listlength):
self.dnalength = dnalength
self.listlength = listlength
crudelist = []
for i in range(0, listlength-1):
for j in range(i+1, listlength):
crudelist.append([i,j])
random.shuffle(crudelist)
self.dna = crudelist[0:dnalength]
def childof(self, a, b):
self.dnalength = a.dnalength
self.listlength = a.listlength
for i in range(0, len(a.dna)):
g = random.randint(0, 1)
if g == 0:
self.dna.append(a.dna[i])
else:
self.dna.append(b.dna[i])
def statictest(self, numtimes, testlist):
avep = 0
for i in range(0, numtimes):
testlist = self.usegenes(testlist)
p = self.checklist(testlist)
avep += p
return avep*1.0 / numtimes
def testme(self, numtimes):
avep = 0
for i in range(0, numtimes):
testlist = []
for j in range(0, self.listlength):
testlist.append(random.random())
testlist = self.usegenes(testlist)
p = self.checklist(testlist)
avep += p
return avep*1.0 / numtimes
def checklist(self, testlist):
totalscore = 0
for i in range(0, len(testlist)):
lessthan = 0
for j in range(0, len(testlist)):
if testlist[j] < testlist[i]:
lessthan +=1
score = (i - lessthan)**2.0
totalscore +=score
return totalscore**.5
def usegenes(self, testlist):
for j in range(0, self.dnalength):
if testlist[self.dna[j][0]] > testlist[self.dna[j][1]]:
temp = testlist[self.dna[j][0]]
testlist[self.dna[j][0]] = testlist[self.dna[j][1]]
testlist[self.dna[j][1]] = temp
return testlist
def main():
creatures = []
numcreatures = 400
survivors = 5
dnalength = 25
listlength = 10
numtests = 100
generations = 3000
testlist = []
performance = []
for j in range(0, listlength):
testlist.append(random.random())
for i in range(0, numcreatures):
c = creature()
c.new(dnalength, listlength)
creatures.append(c)
for i in range(0, generations):
performance = []
creatures2 = []
for j in range(0, len(creatures)):
c = creatures[j]
performance.append([c.testme(numtests), j])
performance = sorted(performance)
for j in range(0, survivors):
creatures2.append(creatures[performance[j][1]])
for j in range(0, survivors):
c = creature()
c.new(dnalength, listlength)
creatures2.append(c)
creatures = creatures2
max = len(creatures)
for k in range(0, max-1):
for l in range(k+1, max):
c = creature()
c.childof(creatures[k], creatures[l])
creatures.append(c)
print(performance)
print(creatures[0].dna)
main()
No comments:
Post a Comment