Schedule Genetic

gistfile1.py

#This was an attempt to do genetic algorithms in python for the 2012 MCM competition. 
#http://www.comap-math.com/mcm/index.html
#It usually works. 

#How many boats get passed through for each 10?
#Make a table
import random
import pygame
from operator import itemgetter, attrgetter

#Setting up pygame
sizes = 800,700

#Seeding the random machine for repeatable test
#seed=10
#random.seed(seed)


#Number of sites
Y=50
#150,225, 25, 100, 10 

#Length of river
miles = 225

#Number of hours !Switch back to 7.5 and half miles if possible
timePerDay=24
days=18
timelength=timePerDay*days

def fastBoat():
    return {'speed':8/2, 'days':0}

def slowBoat():
    return {'speed':4/2, 'days':0}

def blankBoat():
    return {'speed':-1, 'days':-1}

def randomBoat():
    return random.choice((slowBoat,fastBoat,blankBoat))()

def advanceState(currentState,choice):
    (time,riverState,sites,finishers)=currentState
    spotsWithIndex = [(i,riverState[i]) for i in range(len(riverState))]
    boats= filter(lambda boat: boat[1]['speed'] != -1,spotsWithIndex)
    hoursLeft = (timePerDay-1)-(time%timePerDay)
    claimedSites = map(lambda site: [False,site],sites)
    newRiverState = [blankBoat() for i in range(miles)]
    
    if hoursLeft==0:
        boats= map(lambda boat: (boat[0],
                                 {'speed': boat[1]['speed']
                                  , 'days':(boat[1]['days']+1)})
                   ,boats)
    
    def moveBoat(boat):
        finishedBoats=[]
        speed = boat[1]['speed']
        position = boat[0]
        if position >= miles -1:
            finishedBoats.append(boat[1])
        else:
            possibleSites = filter(lambda site: not site[0] and (0 <= site[1][0] - position <= speed*hoursLeft),claimedSites)
            if len(possibleSites)==0:             
                newRiverState[position]=boat[1]
            else:
                furthestSite = possibleSites[-1]
                distance = furthestSite[1][0]-position
                index=claimedSites.index(furthestSite)
                claimedSites[index][0]=True
                if distance > speed:
                    newRiverState[position+speed]=boat[1]
                else:
                    if position+distance == miles:
                        finishedBoats.append(boat[1])
                    else:
                        newRiverState[position+distance]=boat[1]
        return finishedBoats

        
    boats.reverse()
    
    map(lambda x:finishers.extend(x), (map(moveBoat,boats)))
    newRiverState[0]=choice
    return (time+1,newRiverState,sites,finishers)

def generateHistory(choices):
    riverState = [blankBoat() for i in range(miles)]
    riverState[0]=slowBoat()
    sites= [(int(miles/(Y+1))*i,blankBoat()) for i in range(1,Y+1)]
    sites.append((225,blankBoat()))
    currentState = (0,riverState,sites,[])
    history=[currentState]
    while(len(history) != timelength):
        nextState = advanceState(currentState,choices[len(history)]) 
#Pass in choice(len(history)-1) or osmething each time
        history.append(nextState)
        currentState=nextState
    return history

#distro parameters
slowPercent = 5 #must be int's
fastPercent = 5 #must be int's

def orginateChoice():
    distro = [blankBoat() for i in range(100-slowPercent-fastPercent)]
    distro.extend([slowBoat() for i in range(slowPercent)])
    distro.extend([fastBoat() for i in range(fastPercent)])
    return [random.choice(distro) for i in range(timelength)]

def mutate(choice):
    mutant = choice[:]
    mutant[random.randint(0,len(choice)-1)] = randomBoat()
    return mutant

#Max rotation
def rotate(choice):
    index = random.randint(0,random.randint(0,timelength-1))
    return choice[index:]+choice[0:index]

def repeat(choice):
    index= random.randint(1,timePerDay)
    return (choice[0:index]*(timelength))[0:timelength]

def combine(choiceA,choiceB):
    index = random.randint(0,len(choiceA)-1)
    return choiceA[0:index]+choiceB[index:]

def randomcombine(choiceA,choiceB):
    mutant = choiceA[:]
    for i in range(len(choiceB)):
        mutant[i] = random.choice((choiceA[i],choiceB[i]))    
    return mutant

def mixItems(choices):
    tops = map(itemgetter(0),choices)
    offspring = tops[:]
    for i in range(len(tops)):
        for j in range(10):
            offspring.append(mutate(tops[i]))

    for i in range(len(tops)):
        for j in range(10):
            offspring.append(rotate(tops[i]))

    for i in range(len(tops)):
        for j in range(10):
            offspring.append(repeat(tops[i]))

    for i in range(len(tops)):
                offspring.append(combine(
                        tops[random.randint(0,(len(tops)-1))],
                        tops[random.randint(0,(len(tops)-1))]))

    for i in range(len(tops)):
        offspring.append(randomcombine(
                        tops[random.randint(0,(len(tops)-1))],
                        tops[random.randint(0,(len(tops)-1))]))
    return offspring


#Number to test
testNumber = 100
generations = 20
numberOfWinners=10

#Start combining choices
outside = []
def startGeneRun():
    victims = [orginateChoice() for i in range(testNumber)]
    judged = map(lambda choice: (choice, measureChoice(choice)), victims)
    tops = sorted(judged,key=itemgetter(1))[-numberOfWinners:]    
    for i in range(generations):        
        print i," ",map(itemgetter(1),tops)
        victims = mixItems(tops)
        judged = map(lambda choice: (choice, measureChoice(choice)), victims)
        stops = sorted(judged,key=itemgetter(1))
        #Take the winners
        tops= stops[-numberOfWinners:]
    return tops

#Use the day stuff
def measureChoice(choice):
    history=generateHistory(choice)
    boatsSent= len(filter(lambda boat: boat['speed'] != -1,choice))
    boatsRecieved = len(history[-1][-1])
    finished = history[-1][-1]
    days = map(itemgetter('days'),finished)
    def outsideRanges(n):
        if n<6:
            return 6-n
        if n>18:
            return n-18
        return 0
    dayAverage= sum(map(lambda x: x,map(outsideRanges,days)))/len(days)
    boatsLost=boatsSent-boatsRecieved
    return boatsRecieved-(boatsLost+1)**2-(dayAverage+1)**2


#Display parameters
size= 1
red = (255,0,0)
blue = (0,0,255)

def displayChoice(choice):
    entireHistory = generateHistory(choice)
    screen= pygame.display.set_mode(sizes)
    running = 1 
    while running:
        event = pygame.event.poll()
        pygame.display.flip()
                
        for i in range(len(entireHistory)):
            (time, row, sites, finishers)=entireHistory[i]
            hoursLeft = (timePerDay-1) - (time % timePerDay)
            backgroundcolor = 255*hoursLeft/timePerDay
            mainbackground = (backgroundcolor,backgroundcolor,backgroundcolor)
            for j in range(len(row)):
                boat = row[j]
                width = 1 if j in map(lambda x: x[0], sites) else 0
                color = mainbackground
                if boat['speed']==2:
                    color = blue
                if boat['speed']==4:
                    color = red
                pygame.draw.rect(screen, color, (j*size,i*size,size+1,size+1),width)

        if event.type == pygame.QUIT:
            running = 0
            pygame.quit()


def runner():
    results = []
    for i in [50,150,225, 25, 100, 10 ]:
        Y = i
        results.append((i,startGeneRun()))
    return results

result = runner()