Class optimzation

.gitignore

.idea/
*.swp

README

This is for class only, do not copy manipulate. No warranty is provided.

Files:
optimization.py - Base file containing all examples with minimal modifications for correctness.
optimization2.py - The last altered state for problem 2, see accompanying otuput2
optimization3.py - Altered methods with the prefix better_ are implemented.
optimization4.py - Contains the patched genetic optimize method

output - The basic output from running optimzation.py ( the examples )
output2 - The several iterations of testing domain variations with functions
output3 - The output for the patched versions of annealing and hill-climb
output4 - The output for the patched version of the genetic optimize.

README - This file
schedule.txt - Necessary file for input.

optimzation.py

#!/usr/bin/env python
"""
@author Luke
@file optimzation.py
@description class stuff
"""

import time
import random
import math
people = [('Seymour','BOS'),
    ('Franny', 'DAL'),
    ('Zooey', 'CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]
    
destination = 'LGA'

flights = {}

for line in file('schedule.txt'):
    origin, dest, depart, arrive, price = line.strip().split(',')
    flights.setdefault((origin,dest),[])
    flights[(origin,dest)].append((depart,arrive,int(price)))
    
def getminutes(t):
    x = time.strptime(t,'%H:%M')
    return x[3]*60+x[4]
    
def printschedule(r):
    for d in range(len(r)/2):
        name = people[d][0]
        origin=people[d][1]
        out=flights[(origin,destination)][r[d]]
        ret=flights[(destination,origin)][r[d+1]]
        print '%10s%10s %5s-%5s %3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2])

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60

    for d in range(len(sol)/2):
    # Get the inbound and outbound flights
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[2*d])]
        returnf=flights[(destination,origin)][int(sol[2*d+1])]

    # Total price is the price of all outbound and return flights
        totalprice+=outbound[2]
        totalprice+=returnf[2]

    # Track the latest arrival and earliest departure
        if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
        if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

    # Every person must wait at the airport until the latest person arrives.
  # They also must arrive at the same time and wait for their flights.
    totalwait=0  
    for d in range(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait+=latestarrival-getminutes(outbound[1])
        totalwait+=getminutes(returnf[0])-earliestdep  

        # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep: totalprice+=50

    return totalprice+totalwait

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60
    for d in xrange(len(sol)/2):
        # Get the inbound and outbound flights
        origin = people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        
        # Total price is the price of all outbound and return flights
        totalprice = totalprice + outbound[2]
        totalprice = totalprice + returnf[2]
        
        # Track the latest arrival and earliest departure
        if latestarrival < getminutes(outbound[1]):
            latestarrival=getminutes(outbound[1])
        if earliestdep > getminutes(returnf[0]):
            earliestdep = getminutes(returnf[0])
        
    """
    Every person must wait at the airport until the latest person arrives.
    They also must arrive at the same time and wait for their flights.
    """
    totalwait = 0
    for d in xrange(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait = totalwait + latestarrival - getminutes(outbound[1])
        totalwait = totalwait + getminutes(returnf[0]) - earliestdep
        
    # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep:
        totalprice = totalprice + 50
    return totalprice+totalwait

def randomoptimize(domain,costf):
    best = 999999999
    bestr = None
    for i in xrange(1000):
        # Cretae a random solution
        r = [random.randint(domain[1][0], domain[1][1]) for i in range(len(domain))]
    cost = costf(r)
    if cost < best:
        best = cost
        bestr = r
    return r
    
def hillclimb(domain,costf):
    # Create a random solution
    sol=[random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    
    while True:
        neighbors = []
        for j in range(len(domain)):
            
            # One way in each direction
            if sol[j] > domain[j][0]:
                # Add one to the jth element in the list (sol)
                neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
            if sol[j] < domain[j][1]:
                # Subtract one from the jth element in the list
                neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])
        current = costf(sol)
        best = current
        for j in xrange(len(neighbors)):
            cost = costf(neighbors[j])
            if cost < best:
                best = cost
                sol=neighbors[j]
        if best==current:
            break
    return sol

def annealingoptimize(domain, costf, T=10000.0,cool=0.95,step=1):
    # Initialize the values randomly
    vec=[float(random.randint(domain[1][0],domain[1][1])) for i in xrange(len(domain))]
    
    while T>0.1:
        # Choose one of the indexes
        i = random.randint(0,len(domain)-1)
        
        # Choose a direction to change it
        direction = random.randint(-step,step)
        
        # Create a new list with one of the values changed
        vecb = vec[:]
        vecb[1] = vecb[1] + direction
        if vecb[1] < domain[1][0]:
            vecb[1] = domain[1][0]
        elif vecb[1] > domain[1][1]:
            vecb[1] = domain[1][1]
        
        # Calculate the current cost and the new cost
        ea = costf(vec)
        eb = costf(vecb)
        p = pow(math.e, (-eb-ea)/T)
        
        # Is it better, or does it make the probability cutoff?
        if (eb < ea or random.random() < p):
            vec = vecb
        
        # Decrease the temperature
        T = T*cool
    return vec
    
        
def geneticoptimize(domain,costf,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
    def mutate(vec):
        i=random.randint(0,len(domain)-1)
        if random.random()<0.5 and vec[i]>domain[i][0]:
            return vec[0:i]+[vec[i]-step]+vec[i+1:] 
        elif vec[i]<domain[i][1]:
            return vec[0:i]+[vec[i]+step]+vec[i+1:]
  
  # Crossover Operation
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]

  # Build the initial population
    pop=[]
    for i in xrange(popsize):
        vec=[random.randint(domain[i][0],domain[i][1]) 
            for i in range(len(domain))]
        pop.append(vec)
  
  # How many winners from each generation?
    topelite=int(elite*popsize)
  
  # Main loop 
    for i in xrange(maxiter):

        scores = []
        for v in pop:
            if v:
                scores.append((costf(v),v))
        scores.sort()
        ranked=[v for (s,v) in scores]
    
    # Start with the pure winners
        pop=ranked[0:topelite]
    
    # Add mutated and bred forms of the winners
        while len(pop)<popsize:
            if random.random()<mutprob:

                # Mutation
                c=random.randint(0,topelite)
                pop.append(mutate(ranked[c]))
            else:
      
        # Crossover
                c1=random.randint(0,topelite)
                c2=random.randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))
    
        # Print current best score
        #print scores[0][0]
    
    return scores[0][1]
        

    
        
if __name__ == "__main__":
    
    print "Guess Example\n-----------"
    example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    print example_list
    print schedulecost(example_list)
    printschedule(example_list)
    # #---------------------------------------------
    print "Random Search Exampel\n--------------"
    domain = [(0,8)] * (len(people) * 2)
    random_example = randomoptimize(domain,schedulecost)
    print random_example
    print schedulecost(random_example)
    printschedule(random_example)
    #---------------------------------------------
    print "Hill Climb Search Example\n----------------"
    hill_climb_example = hillclimb(domain,schedulecost)
    print hill_climb_example
    print schedulecost(hill_climb_example)
    printschedule(hill_climb_example)
    #---------------------------------------------
    print "Simmulated Annealing Search Example\n------------------"
    annealing_example = annealingoptimize(domain,schedulecost)
    annealing_example = map(int,annealing_example)
    print annealing_example
    print schedulecost(annealing_example)
    printschedule(annealing_example)
	#---------------------------------------------
    print "Genetic Optimization\n------------------"
    genetic_example = geneticoptimize(domain, schedulecost)
    print genetic_example
    print schedulecost(genetic_example)
    printschedule(genetic_example)
    #---------------------------------------------
    print "Ranked list of solutions and costs\n------------------"
    best = [7,5,2,3,1,6,1,6,7,1,0,3]
    print "best"
    print best
    print schedulecost(best)
    printschedule(best)

optimzation2.py

# A module that implements optimization. From the provided data.
# author: Christer Karlsson
# version:
# date:   10-09-08
#
# This is an implemenation of the code from the 5th chapter in
# 'Programming Collective Intelligence' by, Toby Segaran
import time
import random
import math

people = [('Seymour','BOS'),
          ('Franny','DAL'),
          ('Zooey','CAK'),
          ('Walt','MIA'),
          ('Buddy','ORD'),
          ('Les','OMA')]
# Laguardia
destination='LGA'

# Loading the flight data file containing
# origin, destination, departure time, arrival time and price
# for a set of flights,
flights={}
# 
for line in file('schedule.txt'):
  origin,dest,depart,arrive,price=line.strip().split(',')
  flights.setdefault((origin,dest),[])

  # Add details to the list of possible flights
  flights[(origin,dest)].append((depart,arrive,int(price)))

# Utility function that calculates how many minutes into a
# given day that time is. 
def getminutes(t):
  x=time.strptime(t,'%H:%M')
  return x[3]*60+x[4]

# Presents the solution as a table of persons and flights
def printschedule(r):
  for d in range(len(r)/2):
    name=people[d][0]
    origin=people[d][1]
    out=flights[(origin,destination)][int(r[d])]
    ret=flights[(destination,origin)][int(r[d+1])]
    print '%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,
                                                  out[0],out[1],out[2],
                                                  ret[0],ret[1],ret[2])

# Cost function, goal is to find a set of inputs (flights) that
# minimizes this function. We calcuate over:
# Price:             Total price of all tickets
# Travel time:       Total time everyone spends on a plane
# Waiting time:      Total time spent at an airport
# Departure time:    Extra cost for early flights for missing out on sleep
# Car rental period: Penalty for late return
def schedulecost(sol):
  totalprice=0
  latestarrival=0
  earliestdep=24*60

  for d in range(len(sol)/2):
    # Get the inbound and outbound flights
    origin=people[d][1]
    outbound=flights[(origin,destination)][int(sol[2*d])]
    returnf=flights[(destination,origin)][int(sol[2*d+1])]
    
    # Total price is the price of all outbound and return flights
    totalprice+=outbound[2]
    totalprice+=returnf[2]
    
    # Track the latest arrival and earliest departure
    if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
    if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])
  
  # Every person must wait at the airport until the latest person arrives.
  # They also must arrive at the same time and wait for their flights.
  totalwait=0  
  for d in range(len(sol)/2):
    origin=people[d][1]
    outbound=flights[(origin,destination)][int(sol[d])]
    returnf=flights[(destination,origin)][int(sol[d+1])]
    totalwait+=latestarrival-getminutes(outbound[1])
    totalwait+=getminutes(returnf[0])-earliestdep  

  # Does this solution require an extra day of car rental? That'll be $50!
  if latestarrival>earliestdep: totalprice+=50
  
  return totalprice+totalwait

# Random search function
# Takes two input:
# Domain: a list of 2tuples that specify the min and max for each variable.
# costf:  the cost function that will be used.
def randomoptimize(domain,costf):
  best=999999999
  bestr=None
  for i in range(0,1000):
    # Create a random solution
    r=[float(random.randint(domain[i][0],domain[i][1])) 
       for i in range(len(domain))]
    
    # Get the cost
    cost=costf(r)
    
    # Compare it to the best one so far
    if cost<best:
      best=cost
      bestr=r 
  return r

# Hill Climbing function
# Start with a random solution and check if neighbors
# solution are better (think gradient following)
def hillclimb(domain,costf):
  # Create a random solution
  sol=[random.randint(domain[i][0],domain[i][1])
      for i in range(len(domain))]
  # Main loop
  while 1:
    # Create list of neighboring solutions
    neighbors=[]
    
    for j in range(len(domain)):
      # One away in each direction
      if sol[j]>domain[j][0]:
        neighbors.append(sol[0:j]+[sol[j]+1]+sol[j+1:])
      if sol[j]<domain[j][1]:
        neighbors.append(sol[0:j]+[sol[j]-1]+sol[j+1:])

    # See what the best solution amongst the neighbors is
    current=costf(sol)
    best=current
    for j in range(len(neighbors)):
      cost=costf(neighbors[j])
      if cost<best:
        best=cost
        sol=neighbors[j]

    # If there's no improvement, then we've reached the top
    if best==current:
      break
  return sol

# Simulated Anneling Function
# Start with a random solution, and a variable repr. temp
# We can go uphill for a while depending on the temperature.
def annealingoptimize(domain,costf,T=10000.0,cool=0.95,step=1):
  # Initialize the values randomly
  vec=[float(random.randint(domain[i][0],domain[i][1])) 
       for i in range(len(domain))]
  
  while T>0.1:
    # Choose one of the indices
    i=random.randint(0,len(domain)-1)

    # Choose a direction to change it
    dir=random.randint(-step,step)

    # Create a new list with one of the values changed
    vecb=vec[:]
    vecb[i]+=dir
    if vecb[i]<domain[i][0]: vecb[i]=domain[i][0]
    elif vecb[i]>domain[i][1]: vecb[i]=domain[i][1]

    # Calculate the current cost and the new cost
    ea=costf(vec)
    eb=costf(vecb)
    p=pow(math.e,(-eb-ea)/T) # Probability that a higher cost solution is accepted

    # Is it better, or does it make the probability
    # cutoff?
    if (eb<ea or random.random()<p):
      vec=vecb      

    # Decrease the temperature
    T=T*cool
  return vec

# Genetic Algorithms function
# Start with a set of random solutions
# Rank the set of solutions according to the costs
# Create a new population (the next generation)
# and re-rank the new set of solutions
def geneticoptimize(domain,costf,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
  def mutate(vec):
    i=random.randint(0,len(domain)-1)
    if random.random()<0.5 and vec[i]>domain[i][0]:
      return vec[0:i]+[vec[i]-step]+vec[i+1:] 
    elif vec[i]<domain[i][1]:
      return vec[0:i]+[vec[i]+step]+vec[i+1:]
  
  # Crossover Operation
  def crossover(r1,r2):
    i=random.randint(1,len(domain)-2)
    return r1[0:i]+r2[i:]

  # Build the initial population
  pop=[]
  for i in range(popsize):
    vec=[random.randint(domain[i][0],domain[i][1]) 
         for i in range(len(domain))]
    pop.append(vec)
  
  # How many winners from each generation?
  topelite=int(elite*popsize)
  
  # Main loop 
  for i in range(maxiter):
    scores=[(costf(v),v) for v in pop]
    scores.sort()
    ranked=[v for (s,v) in scores]
    
    # Start with the pure winners
    pop=ranked[0:topelite]
    
    # Add mutated and bred forms of the winners
    while len(pop)<popsize:
      if random.random()<mutprob:

        # Mutation
        c=random.randint(0,topelite)
        pop.append(mutate(ranked[c]))
      else:
      
        # Crossover
        c1=random.randint(0,topelite)
        c2=random.randint(0,topelite)
        pop.append(crossover(ranked[c1],ranked[c2]))
    
    # Print current best score
    print scores[0][0]
    
  return scores[0][1]
  
  
if __name__ == "__main__":
    domain=[(0,9)]*(len(people)*2)
    print "Hill Climbing"
    hillclimb_values = hillclimb(domain,schedulecost)
    print schedulecost(hillclimb_values)
    printschedule(hillclimb_values)

optimzation3.py

#!/usr/bin/env python
"""
@author Luke
@file optimzation.py
@description class stuff
"""

import time
import random
import math
people = [('Seymour','BOS'),
    ('Franny', 'DAL'),
    ('Zooey', 'CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]
    
destination = 'LGA'

flights = {}

for line in file('schedule.txt'):
    origin, dest, depart, arrive, price = line.strip().split(',')
    flights.setdefault((origin,dest),[])
    flights[(origin,dest)].append((depart,arrive,int(price)))
    
def getminutes(t):
    x = time.strptime(t,'%H:%M')
    return x[3]*60+x[4]
    
def printschedule(r):
    for d in range(len(r)/2):
        name = people[d][0]
        origin=people[d][1]
        out=flights[(origin,destination)][r[d]]
        ret=flights[(destination,origin)][r[d+1]]
        print '%10s%10s %5s-%5s %3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2])

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60

    for d in range(len(sol)/2):
    # Get the inbound and outbound flights
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[2*d])]
        returnf=flights[(destination,origin)][int(sol[2*d+1])]

    # Total price is the price of all outbound and return flights
        totalprice+=outbound[2]
        totalprice+=returnf[2]

    # Track the latest arrival and earliest departure
        if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
        if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

    # Every person must wait at the airport until the latest person arrives.
  # They also must arrive at the same time and wait for their flights.
    totalwait=0  
    for d in range(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait+=latestarrival-getminutes(outbound[1])
        totalwait+=getminutes(returnf[0])-earliestdep  

        # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep: totalprice+=50

    return totalprice+totalwait

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60
    for d in xrange(len(sol)/2):
        # Get the inbound and outbound flights
        origin = people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        
        # Total price is the price of all outbound and return flights
        totalprice = totalprice + outbound[2]
        totalprice = totalprice + returnf[2]
        
        # Track the latest arrival and earliest departure
        if latestarrival < getminutes(outbound[1]):
            latestarrival=getminutes(outbound[1])
        if earliestdep > getminutes(returnf[0]):
            earliestdep = getminutes(returnf[0])
        
    """
    Every person must wait at the airport until the latest person arrives.
    They also must arrive at the same time and wait for their flights.
    """
    totalwait = 0
    for d in xrange(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait = totalwait + latestarrival - getminutes(outbound[1])
        totalwait = totalwait + getminutes(returnf[0]) - earliestdep
        
    # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep:
        totalprice = totalprice + 50
    return totalprice+totalwait

def randomoptimize(domain,costf):
    best = 999999999
    bestr = None
    for i in xrange(1000):
        # Cretae a random solution
        r = [random.randint(domain[1][0], domain[1][1]) for i in range(len(domain))]
    cost = costf(r)
    if cost < best:
        best = cost
        bestr = r
    return r
    
def hillclimb(domain,costf):
    # Create a random solution
    sol=[random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    
    while True:
        neighbors = []
        for j in range(len(domain)):
            
            # One way in each direction
            if sol[j] > domain[j][0]:
                # Add one to the jth element in the list (sol)
                neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
            if sol[j] < domain[j][1]:
                # Subtract one from the jth element in the list
                neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])
        current = costf(sol)
        best = current
        for j in xrange(len(neighbors)):
            cost = costf(neighbors[j])
            if cost < best:
                best = cost
                sol=neighbors[j]
        if best==current:
            break
    return sol
    
def better_hillclimb(domain,costf):
    # Generate three random states
    sol1 = [random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    sol2 = [random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    sol3 = [random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    def climb(sol):
        while True:
            neighbors = []
            for j in range(len(domain)):

                # One way in each direction
                if sol[j] > domain[j][0]:
                    # Add one to the jth element in the list (sol)
                    neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
                if sol[j] < domain[j][1]:
                    # Subtract one from the jth element in the list
                    neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])
            current = costf(sol)
            best = current
            for j in xrange(len(neighbors)):
                cost = costf(neighbors[j])
                if cost < best:
                    best = cost
                    sol=neighbors[j]
            if best==current:
                break
        return sol
    
    climb1 = (climb(sol1))
    cost1 = costf(climb1)
    print "First Climb: %d" % cost1
    climb2 = (climb(sol2))
    cost2 = costf(climb2)
    print "Second Climb: %d" % cost2
    climb3 = (climb(sol3))
    cost3 = costf(climb3)
    print "Third Climb: %d" % cost3
    minimum = min(cost1,cost2,cost3)
    print "Minimum: %d" % minimum
    if cost1==minimum:
        return climb1
    elif cost2 == minimum:
        return climb2
    elif cost3 == minimum:
        return climb3
    else:
        raise RuntimeError("An error has occurred.")



    
def better_annealingoptimize(domain, costf, T=10000.0,cool=0.95,step=1):
    # We'll use three random state spaces
    vecs=[[float(random.randint(domain[1][0],domain[1][1])) for i in xrange(len(domain))] for x in xrange(3)]
    sols = []
    for vec in vecs:
        while T>0.1:
            # Choose one of the indexes
            i = random.randint(0,len(domain)-1)

            # Choose a direction to change it
            direction = random.randint(-step,step)

            # Create a new list with one of the values changed
            vecb = vec[:]
            vecb[1] = vecb[1] + direction
            if vecb[1] < domain[1][0]:
                vecb[1] = domain[1][0]
            elif vecb[1] > domain[1][1]:
                vecb[1] = domain[1][1]

            # Calculate the current cost and the new cost
            ea = costf(vec)
            eb = costf(vecb)
            p = pow(math.e, (-eb-ea)/T)

            # Is it better, or does it make the probability cutoff?
            if (eb < ea or random.random() < p):
                vec = vecb

            # Decrease the temperature
            T = T*cool
        sols.append(vec)
    cost1 = costf(sols[0])
    print "First Cost: %d" % cost1
    cost2 = costf(sols[1])
    print "Second Cost: %d" % cost2
    cost3 = costf(sols[2])
    print "Third Cost: %d" % cost3
    minimum = min(cost1,cost2,cost3)
    if cost1 == minimum:
        return sols[0]
    elif cost2 == minimum:
        return sols[1]
    elif cost3 == minimum:
        return sols[2]
    else:
        raise RuntimeError("Something wrong has occurred.")
    
def annealingoptimize(domain, costf, T=10000.0,cool=0.95,step=1):
    # Initialize the values randomly
    vec=[float(random.randint(domain[1][0],domain[1][1])) for i in xrange(len(domain))]
    
    while T>0.1:
        # Choose one of the indexes
        i = random.randint(0,len(domain)-1)
        
        # Choose a direction to change it
        direction = random.randint(-step,step)
        
        # Create a new list with one of the values changed
        vecb = vec[:]
        vecb[1] = vecb[1] + direction
        if vecb[1] < domain[1][0]:
            vecb[1] = domain[1][0]
        elif vecb[1] > domain[1][1]:
            vecb[1] = domain[1][1]
        
        # Calculate the current cost and the new cost
        ea = costf(vec)
        eb = costf(vecb)
        p = pow(math.e, (-eb-ea)/T)
        
        # Is it better, or does it make the probability cutoff?
        if (eb < ea or random.random() < p):
            vec = vecb
        
        # Decrease the temperature
        T = T*cool
    return vec
    
        
def geneticoptimize(domain,costf,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
    def mutate(vec):
        i=random.randint(0,len(domain)-1)
        if random.random()<0.5 and vec[i]>domain[i][0]:
            return vec[0:i]+[vec[i]-step]+vec[i+1:] 
        elif vec[i]<domain[i][1]:
            return vec[0:i]+[vec[i]+step]+vec[i+1:]
  
  # Crossover Operation
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]

  # Build the initial population
    pop=[]
    for i in xrange(popsize):
        vec=[random.randint(domain[i][0],domain[i][1]) 
            for i in range(len(domain))]
        pop.append(vec)
  
  # How many winners from each generation?
    topelite=int(elite*popsize)
  
  # Main loop 
    for i in xrange(maxiter):

        scores = []
        for v in pop:
            if v:
                scores.append((costf(v),v))
        scores.sort()
        ranked=[v for (s,v) in scores]
    
    # Start with the pure winners
        pop=ranked[0:topelite]
    
    # Add mutated and bred forms of the winners
        while len(pop)<popsize:
            if random.random()<mutprob:

                # Mutation
                c=random.randint(0,topelite)
                pop.append(mutate(ranked[c]))
            else:
      
        # Crossover
                c1=random.randint(0,topelite)
                c2=random.randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))
    
        # Print current best score
        #print scores[0][0]
    
    return scores[0][1]
        

    
        
if __name__ == "__main__":
    
    # print "Guess Example\n-----------"
    # example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    # print example_list
    # print schedulecost(example_list)
    # printschedule(example_list)
    # #---------------------------------------------
    # print "Random Search Exampel\n--------------"
    domain = [(0,8)] * (len(people)*2)
    # random_example = randomoptimize(domain,schedulecost)
    # print random_example
    # print schedulecost(random_example)
    # printschedule(random_example)
    #---------------------------------------------
    print "Hill Climb Search Example\n----------------"
    hill_climb_example = better_hillclimb(domain,schedulecost)
    print hill_climb_example
    print schedulecost(hill_climb_example)
    printschedule(hill_climb_example)
    #---------------------------------------------
    print "Simmulated Annealing Search Example\n------------------"
    annealing_example = better_annealingoptimize(domain,schedulecost)
    annealing_example = map(int,annealing_example)
    print annealing_example
    print schedulecost(annealing_example)
    printschedule(annealing_example)
    #---------------------------------------------
    #     print "Genetic Optimization\n------------------"
    #     genetic_example = geneticoptimize(domain, schedulecost)
    #     print genetic_example
    #     print schedulecost(genetic_example)
    #     printschedule(genetic_example)
    #---------------------------------------------
    # print "Ranked list of solutions and costs\n------------------"
    # best = [7,5,2,3,1,6,1,6,7,1,0,3]
    # print "best"
    # print best
    # print schedulecost(best)
    # printschedule(best)

optimzation4.py

#!/usr/bin/env python
"""
@author Luke
@file optimzation.py
@description class stuff
"""

import time
import random
import math
people = [('Seymour','BOS'),
    ('Franny', 'DAL'),
    ('Zooey', 'CAK'),
    ('Walt','MIA'),
    ('Buddy','ORD'),
    ('Les','OMA')]
    
destination = 'LGA'

flights = {}

for line in file('schedule.txt'):
    origin, dest, depart, arrive, price = line.strip().split(',')
    flights.setdefault((origin,dest),[])
    flights[(origin,dest)].append((depart,arrive,int(price)))
    
def getminutes(t):
    x = time.strptime(t,'%H:%M')
    return x[3]*60+x[4]
    
def printschedule(r):
    for d in range(len(r)/2):
        name = people[d][0]
        origin=people[d][1]
        out=flights[(origin,destination)][r[d]]
        ret=flights[(destination,origin)][r[d+1]]
        print '%10s%10s %5s-%5s %3s %5s-%5s $%3s' % (name,origin,out[0],out[1],out[2],ret[0],ret[1],ret[2])

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60

    for d in range(len(sol)/2):
    # Get the inbound and outbound flights
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[2*d])]
        returnf=flights[(destination,origin)][int(sol[2*d+1])]

    # Total price is the price of all outbound and return flights
        totalprice+=outbound[2]
        totalprice+=returnf[2]

    # Track the latest arrival and earliest departure
        if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
        if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

    # Every person must wait at the airport until the latest person arrives.
  # They also must arrive at the same time and wait for their flights.
    totalwait=0  
    for d in range(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait+=latestarrival-getminutes(outbound[1])
        totalwait+=getminutes(returnf[0])-earliestdep  

        # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep: totalprice+=50

    return totalprice+totalwait

def schedulecost(sol):
    totalprice=0
    latestarrival=0
    earliestdep=24*60
    for d in xrange(len(sol)/2):
        # Get the inbound and outbound flights
        origin = people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        
        # Total price is the price of all outbound and return flights
        totalprice = totalprice + outbound[2]
        totalprice = totalprice + returnf[2]
        
        # Track the latest arrival and earliest departure
        if latestarrival < getminutes(outbound[1]):
            latestarrival=getminutes(outbound[1])
        if earliestdep > getminutes(returnf[0]):
            earliestdep = getminutes(returnf[0])
        
    """
    Every person must wait at the airport until the latest person arrives.
    They also must arrive at the same time and wait for their flights.
    """
    totalwait = 0
    for d in xrange(len(sol)/2):
        origin=people[d][1]
        outbound=flights[(origin,destination)][int(sol[d])]
        returnf=flights[(destination,origin)][int(sol[d+1])]
        totalwait = totalwait + latestarrival - getminutes(outbound[1])
        totalwait = totalwait + getminutes(returnf[0]) - earliestdep
        
    # Does this solution require an extra day of car rental? That'll be $50!
    if latestarrival>earliestdep:
        totalprice = totalprice + 50
    return totalprice+totalwait

def randomoptimize(domain,costf):
    best = 999999999
    bestr = None
    for i in xrange(1000):
        # Cretae a random solution
        r = [random.randint(domain[1][0], domain[1][1]) for i in range(len(domain))]
    cost = costf(r)
    if cost < best:
        best = cost
        bestr = r
    return r
    
def hillclimb(domain,costf):
    # Create a random solution
    sol=[random.randint(domain[i][0],domain[i][1]) for i in xrange(len(domain))]
    
    while True:
        neighbors = []
        for j in range(len(domain)):
            
            # One way in each direction
            if sol[j] > domain[j][0]:
                # Add one to the jth element in the list (sol)
                neighbors.append(sol[0:j] + [sol[j]+1] + sol[j+1:])
            if sol[j] < domain[j][1]:
                # Subtract one from the jth element in the list
                neighbors.append(sol[0:j] + [sol[j]-1] + sol[j+1:])
        current = costf(sol)
        best = current
        for j in xrange(len(neighbors)):
            cost = costf(neighbors[j])
            if cost < best:
                best = cost
                sol=neighbors[j]
        if best==current:
            break
    return sol

def annealingoptimize(domain, costf, T=10000.0,cool=0.95,step=1):
    # Initialize the values randomly
    vec=[float(random.randint(domain[1][0],domain[1][1])) for i in xrange(len(domain))]
    
    while T>0.1:
        # Choose one of the indexes
        i = random.randint(0,len(domain)-1)
        
        # Choose a direction to change it
        direction = random.randint(-step,step)
        
        # Create a new list with one of the values changed
        vecb = vec[:]
        vecb[1] = vecb[1] + direction
        if vecb[1] < domain[1][0]:
            vecb[1] = domain[1][0]
        elif vecb[1] > domain[1][1]:
            vecb[1] = domain[1][1]
        
        # Calculate the current cost and the new cost
        ea = costf(vec)
        eb = costf(vecb)
        p = pow(math.e, (-eb-ea)/T)
        
        # Is it better, or does it make the probability cutoff?
        if (eb < ea or random.random() < p):
            vec = vecb
        
        # Decrease the temperature
        T = T*cool
    return vec
    
        
def geneticoptimize(domain,costf,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
    def mutate(vec):
        i=random.randint(0,len(domain)-1)
        if random.random()<0.5 and vec[i]>domain[i][0]:
            return vec[0:i]+[vec[i]-step]+vec[i+1:] 
        elif vec[i]<domain[i][1]:
            return vec[0:i]+[vec[i]+step]+vec[i+1:]
  
  # Crossover Operation
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]

  # Build the initial population
    pop=[]
    for i in xrange(popsize):
        vec=[random.randint(domain[i][0],domain[i][1]) 
            for i in range(len(domain))]
        pop.append(vec)
  
  # How many winners from each generation?
    topelite=int(elite*popsize)
  
  # Main loop 
    for i in xrange(maxiter):

        scores = []
        for v in pop:
            if v:
                scores.append((costf(v),v))
        scores.sort()
        ranked=[v for (s,v) in scores]
    
    # Start with the pure winners
        pop=ranked[0:topelite]
    
    # Add mutated and bred forms of the winners
        while len(pop)<popsize:
            if random.random()<mutprob:

                # Mutation
                c=random.randint(0,topelite)
                pop.append(mutate(ranked[c]))
            else:
      
        # Crossover
                c1=random.randint(0,topelite)
                c2=random.randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))
    
        # Print current best score
        #print scores[0][0]
    
    return scores[0][1]

def better_geneticoptimize(domain,costf,popsize=50,step=1, mutprob=0.2,elite=0.2,maxiter=100):
# Mutation Operation
    def mutate(vec):
        i=random.randint(0,len(domain)-1)
        if random.random()<0.5 and vec[i]>domain[i][0]:
            return vec[0:i]+[vec[i]-step]+vec[i+1:]
        elif vec[i]<domain[i][1]:
            return vec[0:i]+[vec[i]+step]+vec[i+1:]

            # Crossover Operation
    def crossover(r1,r2):
        i=random.randint(1,len(domain)-2)
        return r1[0:i]+r2[i:]

        # Build the initial population
    pop=[]
    for i in xrange(popsize):
        vec=[random.randint(domain[i][0],domain[i][1])
             for i in range(len(domain))]
        pop.append(vec)

        # How many winners from each generation?
    topelite=int(elite*popsize)

    # Main loop
    best_score = 999999
    count=0

    for i in xrange(maxiter):

        scores = []
        for v in pop:
            if v:
                scores.append((costf(v),v))
        scores.sort()
        ranked=[v for (s,v) in scores]

        # Start with the pure winners
        pop=ranked[0:topelite]

        # Add mutated and bred forms of the winners
        while len(pop)<popsize:
            if random.random()<mutprob:

                # Mutation
                c=random.randint(0,topelite)
                pop.append(mutate(ranked[c]))
            else:

            # Crossover
                c1=random.randint(0,topelite)
                c2=random.randint(0,topelite)
                pop.append(crossover(ranked[c1],ranked[c2]))

                # Print current best score
                #print scores[0][0]
        if scores[0][0] < best_score:
            best_score = scores[0][0]
            count = 0
        if count >=10:
            return scores[0][1]
        count = count + 1
        print "I have seen %d, %d times" % (best_score, count)


    return scores[0][1]
    
        
if __name__ == "__main__":
    
    # print "Guess Example\n-----------"
    # example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    # print example_list
    # print schedulecost(example_list)
    # printschedule(example_list)
    # #---------------------------------------------
    # print "Random Search Exampel\n--------------"
    domain = [(5, 8), (2, 4), (1, 6), (7, 8), (1, 2), (3, 4), (4, 5), (5, 6), (7, 8), (0, 1), (0, 2), (0, 5)]
    # random_example = randomoptimize(domain,schedulecost)
    # print random_example
    # print schedulecost(random_example)
    # printschedule(random_example)
    #---------------------------------------------
    # print "Hill Climb Search Example\n----------------"
    # hill_climb_example = hillclimb(domain,schedulecost)
    # print hill_climb_example
    # print schedulecost(hill_climb_example)
    # printschedule(hill_climb_example)
    # #---------------------------------------------
    # print "Simmulated Annealing Search Example\n------------------"
    # annealing_example = annealingoptimize(domain,schedulecost)
    # annealing_example = map(int,annealing_example)
    # print annealing_example
    # print schedulecost(annealing_example)
    # printschedule(annealing_example)
	#---------------------------------------------
    print "Genetic Optimization\n------------------"
    genetic_example = better_geneticoptimize(domain, schedulecost)
    print genetic_example
    print schedulecost(genetic_example)
    printschedule(genetic_example)
    #---------------------------------------------
    # print "Ranked list of solutions and costs\n------------------"
    # best = [7,5,2,3,1,6,1,6,7,1,0,3]
    # print "best"
    # print best
    # print schedulecost(best)
    # printschedule(best)

output

Guess Example
-----------
[1, 4, 3, 2, 7, 3, 6, 3, 2, 4, 5, 3]
5285
   Seymour       BOS  8:04-10:11  95 12:08-14:05 $142
    Franny       DAL 12:19-15:25 342 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189  9:58-12:56 $249
      Walt       MIA  9:15-12:29 225 16:50-19:26 $304
     Buddy       ORD 16:43-19:00 246 10:33-13:11 $132
       Les       OMA 11:08-13:07 175 15:07-17:21 $129
Random Search Exampel
--------------
[3, 7, 3, 8, 6, 1, 7, 5, 7, 7, 8, 4]
6569
   Seymour       BOS 11:16-13:29  83 17:03-18:03 $103
    Franny       DAL 16:52-20:48 448 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 18:17-21:04 $259
      Walt       MIA 18:23-21:35 134 15:23-18:49 $150
     Buddy       ORD 15:58-18:40 173  7:50-10:08 $164
       Les       OMA  7:39-10:24 219 16:35-18:56 $144
Hill Climb Search Example
----------------
[4, 3, 3, 3, 4, 3, 3, 2, 6, 1, 1, 6]
2591
   Seymour       BOS 12:34-15:02 109 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 10:32-13:16 $139
      Walt       MIA 11:28-14:40 248 12:37-15:05 $170
     Buddy       ORD 12:44-14:17 134 10:33-13:11 $132
       Les       OMA 11:08-13:07 175 11:07-13:24 $171
Simmulated Annealing Search Example
------------------
[5, 3, 4, 1, 3, 1, 4, 2, 0, 0, 7, 3]
4653
   Seymour       BOS 13:40-15:37 138 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 12:20-16:34 $500
     Zooey       CAK 12:08-14:59 149  8:19-11:16 $122
      Walt       MIA  7:34- 9:40 324 11:08-14:38 $262
     Buddy       ORD 11:01-12:39 260  7:50-10:08 $164
       Les       OMA  7:39-10:24 219 12:31-14:02 $234
Genetic Optimization
------------------
3803
3444
3444
3393
3393
3260
3260
3209
3209
3209
3209
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
3172
   Seymour       BOS 12:34-15:02 109 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 10:32-13:16 $139
      Walt       MIA 11:28-14:40 248  8:23-11:07 $143
     Buddy       ORD  8:25-10:34 157  9:11-10:42 $172
       Les       OMA  9:15-12:03  99  8:04-10:59 $136
Ranked list of solutions and costs
------------------
best
[7, 5, 2, 3, 1, 6, 1, 6, 7, 1, 0, 3]
4394
   Seymour       BOS 17:11-18:30 108 13:39-15:30 $ 74
    Franny       DAL 13:54-18:02 294  9:49-13:51 $229
     Zooey       CAK  9:15-12:14 247 10:32-13:16 $139
      Walt       MIA 11:28-14:40 248  8:23-11:07 $143
     Buddy       ORD  8:25-10:34 157 15:04-17:23 $189
       Les       OMA 15:03-16:42 135  8:04-10:59 $136

output2

if __name__ == "__main__":
    
    # print "Guess Example\n-----------"
    # example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    # print example_list
    # print schedulecost(example_list)
    # printschedule(example_list)
    # #---------------------------------------------
    # print "Random Search Exampel\n--------------"
    domain = [(0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8), (0, 8)]
    # random_example = randomoptimize(domain,schedulecost)
    # print random_example
    # print schedulecost(random_example)
    # printschedule(random_example)
    #---------------------------------------------
    print "Hill Climb Search Example\n----------------"
    hill_climb_example = hillclimb(domain,schedulecost)
    print hill_climb_example
    print schedulecost(hill_climb_example)
    printschedule(hill_climb_example)
    #---------------------------------------------
    print "Simmulated Annealing Search Example\n------------------"
    annealing_example = annealingoptimize(domain,schedulecost)
    annealing_example = map(int,annealing_example)
    print annealing_example
    print schedulecost(annealing_example)
    printschedule(annealing_example)
	#---------------------------------------------
    print "Genetic Optimization\n------------------"
    genetic_example = geneticoptimize(domain, schedulecost)
    print genetic_example
    print schedulecost(genetic_example)
    printschedule(genetic_example)
    #---------------------------------------------
    # print "Ranked list of solutions and costs\n------------------"
    # best = [7,5,2,3,1,6,1,6,7,1,0,3]
    # print "best"
    # print best
    # print schedulecost(best)
    # printschedule(best)Hill Climb Search Example
----------------
[5, 3, 5, 0, 1, 2, 6, 5, 0, 0, 1, 6]
4587
   Seymour       BOS 13:40-15:37 138 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 14:20-17:32 $332
     Zooey       CAK 13:40-15:38 137  6:58- 9:01 $238
      Walt       MIA  6:25- 9:30 335  8:23-11:07 $143
     Buddy       ORD  8:25-10:34 157  9:11-10:42 $172
       Les       OMA  9:15-12:03  99 15:07-17:21 $129
Simmulated Annealing Search Example
------------------
[0, 0, 0, 0, 2, 5, 5, 0, 0, 0, 6, 7]
5701
   Seymour       BOS  6:17- 8:26  89  6:39- 8:09 $ 86
    Franny       DAL  6:12-10:22 230  6:09- 9:49 $414
     Zooey       CAK  6:08- 8:06 224  6:58- 9:01 $238
      Walt       MIA  6:25- 9:30 335  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169 14:19-17:09 $190
       Les       OMA 13:37-15:08 250 14:05-15:47 $226
Genetic Optimization
------------------
[7, 5, 5, 5, 6, 6, 6, 0, 0, 0, 0, 0]
3003
   Seymour       BOS 17:11-18:30 108 13:39-15:30 $ 74
    Franny       DAL 13:54-18:02 294 14:20-17:32 $332
     Zooey       CAK 13:40-15:38 137 13:37-15:33 $142
      Walt       MIA 14:01-17:24 338 15:23-18:49 $150
     Buddy       ORD 15:58-18:40 173 15:04-17:23 $189
       Les       OMA 15:03-16:42 135 15:07-17:21 $129
if __name__ == "__main__":
    
    # print "Guess Example\n-----------"
    # example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    # print example_list
    # print schedulecost(example_list)
    # printschedule(example_list)
    # #---------------------------------------------
    # print "Random Search Exampel\n--------------"
    domain = [(0, 2), (0, 4), (0, 6), (0, 8), (0, 2), (0, 4), (0, 5), (0, 6), (0, 8), (0, 1), (0, 2), (0, 5)]
    # random_example = randomoptimize(domain,schedulecost)
    # print random_example
    # print schedulecost(random_example)
    # printschedule(random_example)
    #---------------------------------------------
    print "Hill Climb Search Example\n----------------"
    hill_climb_example = hillclimb(domain,schedulecost)
    print hill_climb_example
    print schedulecost(hill_climb_example)
    printschedule(hill_climb_example)
    #---------------------------------------------
    print "Simmulated Annealing Search Example\n------------------"
    annealing_example = annealingoptimize(domain,schedulecost)
    annealing_example = map(int,annealing_example)
    print annealing_example
    print schedulecost(annealing_example)
    printschedule(annealing_example)
	#---------------------------------------------
    print "Genetic Optimization\n------------------"
    genetic_example = geneticoptimize(domain, schedulecost)
    print genetic_example
    print schedulecost(genetic_example)
    printschedule(genetic_example)
    #---------------------------------------------
    # print "Ranked list of solutions and costs\n------------------"
    # best = [7,5,2,3,1,6,1,6,7,1,0,3]
    # print "best"
    # print best
    # print schedulecost(best)
    # printschedule(best)

Hill Climb Search Example
----------------
[8, 3, 0, 8, 2, 2, 0, 1, 7, 1, 1, 5]
6436
   Seymour       BOS 18:34-19:36 136 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290  6:09- 9:49 $414
     Zooey       CAK  6:08- 8:06 224 18:17-21:04 $259
      Walt       MIA 18:23-21:35 134  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169  9:11-10:42 $172
       Les       OMA  9:15-12:03  99  6:19- 8:13 $239
Simmulated Annealing Search Example
------------------
[3, 2, 1, 0, 2, 3, 2, 0, 1, 4, 0, 3]
4040
   Seymour       BOS 11:16-13:29  83  9:58-11:18 $130
    Franny       DAL  9:08-12:12 364  7:57-11:15 $347
     Zooey       CAK  8:27-10:45 139  6:58- 9:01 $238
      Walt       MIA  6:25- 9:30 335  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169 10:33-13:11 $132
       Les       OMA 11:08-13:07 175  9:31-11:43 $210
Genetic Optimization
------------------
[2, 1, 1, 1, 1, 2, 1, 0, 0, 0, 0, 0]
2947
   Seymour       BOS  9:45-11:50 172  8:23-10:28 $149
    Franny       DAL  7:53-11:37 433  7:57-11:15 $347
     Zooey       CAK  8:27-10:45 139  8:19-11:16 $122
      Walt       MIA  7:34- 9:40 324  8:23-11:07 $143
     Buddy       ORD  8:25-10:34 157  9:11-10:42 $172
       Les       OMA  9:15-12:03  99  8:04-10:59 $136
        
if __name__ == "__main__":
    
    # print "Guess Example\n-----------"
    # example_list = [1,4,3,2,7,3,6,3,2,4,5,3]
    # print example_list
    # print schedulecost(example_list)
    # printschedule(example_list)
    # #---------------------------------------------
    # print "Random Search Exampel\n--------------"
    domain = [(5, 8), (2, 4), (1, 6), (7, 8), (1, 2), (3, 4), (4, 5), (5, 6), (7, 8), (0, 1), (0, 2), (0, 5)]
    # random_example = randomoptimize(domain,schedulecost)
    # print random_example
    # print schedulecost(random_example)
    # printschedule(random_example)
    #---------------------------------------------
    print "Hill Climb Search Example\n----------------"
    hill_climb_example = hillclimb(domain,schedulecost)
    print hill_climb_example
    print schedulecost(hill_climb_example)
    printschedule(hill_climb_example)
    #---------------------------------------------
    print "Simmulated Annealing Search Example\n------------------"
    annealing_example = annealingoptimize(domain,schedulecost)
    annealing_example = map(int,annealing_example)
    print annealing_example
    print schedulecost(annealing_example)
    printschedule(annealing_example)
	#---------------------------------------------
    print "Genetic Optimization\n------------------"
    genetic_example = geneticoptimize(domain, schedulecost)
    print genetic_example
    print schedulecost(genetic_example)
    printschedule(genetic_example)
    #---------------------------------------------
    # print "Ranked list of solutions and costs\n------------------"
    # best = [7,5,2,3,1,6,1,6,7,1,0,3]
    # print "best"
    # print best
    # print schedulecost(best)
    # printschedule(best)Hill Climb Search Example
----------------
[8, 3, 3, 5, 1, 2, 6, 6, 8, 0, 0, 2]
4985
   Seymour       BOS 18:34-19:36 136 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 13:37-15:33 $142
      Walt       MIA 14:01-17:24 338  8:23-11:07 $143
     Buddy       ORD  8:25-10:34 157  9:11-10:42 $172
       Les       OMA  9:15-12:03  99 15:07-17:21 $129
Simmulated Annealing Search Example
------------------
[4, 3, 4, 2, 4, 2, 4, 2, 4, 2, 4, 3]
3564
   Seymour       BOS 12:34-15:02 109 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 12:20-16:34 $500
     Zooey       CAK 12:08-14:59 149  9:58-12:56 $249
      Walt       MIA  9:15-12:29 225 12:37-15:05 $170
     Buddy       ORD 12:44-14:17 134  9:11-10:42 $172
       Les       OMA  9:15-12:03  99 12:31-14:02 $234
Genetic Optimization
------------------
[8, 3, 3, 7, 2, 3, 4, 5, 7, 0, 0, 0]
5032
   Seymour       BOS 18:34-19:36 136 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 16:33-18:15 $253
      Walt       MIA 17:07-20:04 291  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169 10:33-13:11 $132
       Les       OMA 11:08-13:07 175 12:31-14:02 $234

output3

Hill Climb Search Example
----------------
First Climb: 5418
Second Climb: 6174
Third Climb: 2591
Minimum: 2591
[4, 3, 3, 3, 4, 3, 3, 4, 7, 2, 7, 2]
2591
   Seymour       BOS 12:34-15:02 109 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 10:32-13:16 $139
      Walt       MIA 11:28-14:40 248 12:37-15:05 $170
     Buddy       ORD 12:44-14:17 134 10:33-13:11 $132
       Les       OMA 11:08-13:07 175 11:07-13:24 $171
Simmulated Annealing Search Example
------------------
First Cost: 5566
Second Cost: 5476
Third Cost: 6501
[8, 3, 1, 7, 2, 4, 2, 1, 1, 0, 8, 2]
5476
   Seymour       BOS 18:34-19:36 136 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290  7:57-11:15 $347
     Zooey       CAK  8:27-10:45 139 16:33-18:15 $253
      Walt       MIA 17:07-20:04 291  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169 12:08-14:47 $231
       Les       OMA 12:18-14:56 172  9:31-11:43 $210

output4

Genetic Optimization
------------------
I have seen 5271, 1 times
I have seen 5118, 1 times
I have seen 5032, 1 times
I have seen 5032, 2 times
I have seen 5032, 3 times
I have seen 5032, 4 times
I have seen 5032, 5 times
I have seen 5032, 6 times
I have seen 5032, 7 times
I have seen 5032, 8 times
I have seen 5032, 9 times
I have seen 5032, 10 times
[8, 3, 3, 7, 2, 3, 4, 5, 7, 0, 0, 0]
5032
   Seymour       BOS 18:34-19:36 136 10:33-12:03 $ 74
    Franny       DAL 10:30-14:57 290 10:51-14:16 $256
     Zooey       CAK 10:53-13:36 189 16:33-18:15 $253
      Walt       MIA 17:07-20:04 291  9:25-12:46 $295
     Buddy       ORD  9:42-11:32 169 10:33-13:11 $132
       Les       OMA 11:08-13:07 175 12:31-14:02 $234

schedule.txt

LGA,OMA,6:19,8:13,239
OMA,LGA,6:11,8:31,249
LGA,OMA,8:04,10:59,136
OMA,LGA,7:39,10:24,219
LGA,OMA,9:31,11:43,210
OMA,LGA,9:15,12:03,99
LGA,OMA,11:07,13:24,171
OMA,LGA,11:08,13:07,175
LGA,OMA,12:31,14:02,234
OMA,LGA,12:18,14:56,172
LGA,OMA,14:05,15:47,226
OMA,LGA,13:37,15:08,250
LGA,OMA,15:07,17:21,129
OMA,LGA,15:03,16:42,135
LGA,OMA,16:35,18:56,144
OMA,LGA,16:51,19:09,147
LGA,OMA,18:25,20:34,205
OMA,LGA,18:12,20:17,242
LGA,OMA,20:05,21:44,172
OMA,LGA,20:05,22:06,261
LGA,ORD,6:03,8:43,219
ORD,LGA,6:05,8:32,174
LGA,ORD,7:50,10:08,164
ORD,LGA,8:25,10:34,157
LGA,ORD,9:11,10:42,172
ORD,LGA,9:42,11:32,169
LGA,ORD,10:33,13:11,132
ORD,LGA,11:01,12:39,260
LGA,ORD,12:08,14:47,231
ORD,LGA,12:44,14:17,134
LGA,ORD,14:19,17:09,190
ORD,LGA,14:22,16:32,126
LGA,ORD,15:04,17:23,189
ORD,LGA,15:58,18:40,173
LGA,ORD,17:06,20:00,95
ORD,LGA,16:43,19:00,246
LGA,ORD,18:33,20:22,143
ORD,LGA,18:48,21:45,246
LGA,ORD,19:32,21:25,160
ORD,LGA,19:50,22:24,269
LGA,MIA,6:33,9:14,172
MIA,LGA,6:25,9:30,335
LGA,MIA,8:23,11:07,143
MIA,LGA,7:34,9:40,324
LGA,MIA,9:25,12:46,295
MIA,LGA,9:15,12:29,225
LGA,MIA,11:08,14:38,262
MIA,LGA,11:28,14:40,248
LGA,MIA,12:37,15:05,170
MIA,LGA,12:05,15:30,330
LGA,MIA,14:08,16:09,232
MIA,LGA,14:01,17:24,338
LGA,MIA,15:23,18:49,150
MIA,LGA,15:34,18:11,326
LGA,MIA,16:50,19:26,304
MIA,LGA,17:07,20:04,291
LGA,MIA,18:07,21:30,355
MIA,LGA,18:23,21:35,134
LGA,MIA,20:27,23:42,169
MIA,LGA,19:53,22:21,173
LGA,BOS,6:39,8:09,86
BOS,LGA,6:17,8:26,89
LGA,BOS,8:23,10:28,149
BOS,LGA,8:04,10:11,95
LGA,BOS,9:58,11:18,130
BOS,LGA,9:45,11:50,172
LGA,BOS,10:33,12:03,74
BOS,LGA,11:16,13:29,83
LGA,BOS,12:08,14:05,142
BOS,LGA,12:34,15:02,109
LGA,BOS,13:39,15:30,74
BOS,LGA,13:40,15:37,138
LGA,BOS,15:25,16:58,62
BOS,LGA,15:27,17:18,151
LGA,BOS,17:03,18:03,103
BOS,LGA,17:11,18:30,108
LGA,BOS,18:24,20:49,124
BOS,LGA,18:34,19:36,136
LGA,BOS,19:58,21:23,142
BOS,LGA,20:17,22:22,102
LGA,DAL,6:09,9:49,414
DAL,LGA,6:12,10:22,230
LGA,DAL,7:57,11:15,347
DAL,LGA,7:53,11:37,433
LGA,DAL,9:49,13:51,229
DAL,LGA,9:08,12:12,364
LGA,DAL,10:51,14:16,256
DAL,LGA,10:30,14:57,290
LGA,DAL,12:20,16:34,500
DAL,LGA,12:19,15:25,342
LGA,DAL,14:20,17:32,332
DAL,LGA,13:54,18:02,294
LGA,DAL,15:49,20:10,497
DAL,LGA,15:44,18:55,382
LGA,DAL,17:14,20:59,277
DAL,LGA,16:52,20:48,448
LGA,DAL,18:44,22:42,351
DAL,LGA,18:26,21:29,464
LGA,DAL,19:57,23:15,512
DAL,LGA,20:07,23:27,473
LGA,CAK,6:58,9:01,238
CAK,LGA,6:08,8:06,224
LGA,CAK,8:19,11:16,122
CAK,LGA,8:27,10:45,139
LGA,CAK,9:58,12:56,249
CAK,LGA,9:15,12:14,247
LGA,CAK,10:32,13:16,139
CAK,LGA,10:53,13:36,189
LGA,CAK,12:01,13:41,267
CAK,LGA,12:08,14:59,149
LGA,CAK,13:37,15:33,142
CAK,LGA,13:40,15:38,137
LGA,CAK,15:50,18:45,243
CAK,LGA,15:23,17:25,232
LGA,CAK,16:33,18:15,253
CAK,LGA,17:08,19:08,262
LGA,CAK,18:17,21:04,259
CAK,LGA,18:35,20:28,204
LGA,CAK,19:46,21:45,214
CAK,LGA,20:30,23:11,114