VirtualRobot/GeneticSort.py at master · helloworldC2/VirtualRobot · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import random
import Jobs

class Chromosome(object):

    def __init__(self,genes):
        self.genes = genes
        self.fitness = 0


def inList(i,l):
    for j in l:
        if j==i:return True
    return False

def combine(a,b):
    new = []
    for i in range(len(a)):
        if not inList(min(a[i],b[i]),new):
            new.append(min(a[i],b[i]))
        else:
            new.append(max(a[i],b[i]))
    return new


def geneticSort(l,worker):
    chromosomes = []
    jobs = []
    lastBest = None
    for i in range(10):
        random.shuffle(l,random.random)
        chromosomes.append(Chromosome(list(l)))

    generations = 0
    while True:
        generations +=1
        for c in chromosomes:
            c.fitness = 0
            for i in range(len(c.genes)-1):
                if c.genes[i]<=c.genes[i+1]:c.fitness+=1
                if c.fitness > len(c.genes)-2:
                    print "Done in",generations,"generations with",len(chromosomes),"individuals"
                    for i,t in enumerate(c.genes):
                        if lastBest[i]!=t:
                            jobs.append(Jobs.JobGoTo(i))
                            jobs.append(Jobs.JobPickUpTreasure(i))
                        for i,t in enumerate(c.genes):
                             if lastBest[i]!=t:
                                jobs.append(Jobs.JobGoTo(i))
                                jobs.append(Jobs.JobPlaceTreasure(i,t))
                    jobs.append(Jobs.JobIdle())
                    return jobs

        chromosomes.sort(key=lambda x: x.fitness, reverse=True)
        for i in range(len(chromosomes)/2):
           chromosomes[i*2].genes = combine(chromosomes[i*2].genes,chromosomes[i*2+1].genes)

        for i in range(5):
            random.shuffle(l,random.random)
            chromosomes.append(Chromosome(list(l)))

        if lastBest!=None:
            for i,t in enumerate(chromosomes[0].genes):
                if lastBest[i]!=t:
                    print "pick up",lastBest[i],t
                    jobs.append(Jobs.JobGoTo(i))
                    jobs.append(Jobs.JobPickUpTreasure(i))
            for i,t in enumerate(chromosomes[0].genes):
                 if lastBest[i]!=t:
                    print "Place",lastBest[i],t
                    jobs.append(Jobs.JobGoTo(i))
                    jobs.append(Jobs.JobPlaceTreasure(i,t))
        else:
            for i,t in enumerate(chromosomes[0].genes):
                print "initial",i,t
                jobs.append(Jobs.JobGoTo(i))
                jobs.append(Jobs.JobPlaceTreasure(i,t))

        lastBest = chromosomes[0].genes