8
\$\begingroup\$

An Algorithm For Scheduling Your Time

There is a strong body of research in cognitive science which has large implications for how best to plan your day to get the most out of it. However, it isn't practical for everyone to understand it, keep on up to date on recent findings, weigh up the relative importance of different principles, then apply them to optimally plan their day. What if there was an algorithm which could do it for you?

This is my first attempt at the first peice of the puzze: how to go about algorithmically scheduling a day? The literature on scheduling mainly addresses the following variables: activity duration, activity order, what time to perform an activity relative to your circadium rhymthms. I present an attempt to integrate these types of infomation into a cost function, represent schedules mathematically, then optimise schedules according to the cost function.

(At the moment, the GA uses a contrived cost-function designed to produce a clear optimal solution against which the algorithm's outputs can be compared, no real world data is incorperated yet.)

I'm looking for big picture advice on the approach I've taken, but I'd also be very grateful for information about errors I've made in the execution of my approach. This is my first ever python project, so I'm sure there are plenty of mistakes. With that in mind, it would be extremely useful to me if anyone could identify systematic errors in my thinking.

Dependencies and global variables

from collections import Counter
import statistics as stat
import random as random
import numpy as np
import operator
import pandas as pd
import matplotlib.pyplot as plt
import pdb
numActivities = 8
popSize = 500
eliteSize = 4
mutationRate = 0.08
generations = 200
numDurationGenes = 8  # This should be equal to number of ST genes

Thus far, these have been the values with which have most reliably produced good schedules. To test it using more than eight activities, first delete all line featuring the word "custom" then run as normal. Those modules which aren't called directly are included because they are very useful for debugging or analysing populations of candidate solutions.

Representing Activities, Time, and How They Interact

quantaDuration = 5  # each block of time is equal to 5 mins long
hoursPerDayToSchedule = 12
dailyQuanta = int(60 * 24 * (hoursPerDayToSchedule / 24) / quantaDuration)

The algorithm divides a time period into 5 minute quanta, so named because they are the fundamental unit of time. However, unlike the vast majority of scheduling algorithms I've seen, this algorithm's computerational complexity scales nicely with the number of quanta so one can efficiently achieve a high granularity of time.

activitiesInteractionList = []
for i in range(0, numActivities**2):
    activitiesInteractionList.append(random.randint(1, 10))

activitiesInteractionMatrix = np.array(activitiesInteractionList).reshape(
    [numActivities, numActivities])

activitiesInteractionMatrix
array([[ 1,  4,  5,  7,  7,  5,  2,  8],
       [ 9,  8,  5,  5,  2,  7, 10,  5],
       [ 4,  4,  4,  9,  4,  2,  3,  6],
       [ 5,  8,  1,  8,  8,  8,  7, 10],
       [10,  5,  1,  8,  8,  8,  8,  2],
       [ 2,  8,  7,  2,  8,  5,  3,  7],
       [ 6,  2,  5, 10,  4,  2,  8,  7],
       [ 5,  9,  2,  9,  1,  7,  5,  5]])

This generates a numpy array consisting of random integers such that index x,y represents the cost associated with activity x preceeding activity y. This exists purely as a placeholder which can be replaced with something more complex representing real world data

timesOfDay = ["morning", "mid-day", "afternoon", "night"]

activityTimeInteractionList = []
for i in range(0, numActivities * len(timesOfDay)):
    activityTimeInteractionList.append(random.randint(1, 10) / 10)

activityTimeInteractionMatrix = np.array(
    activityTimeInteractionList).reshape(numActivities, len(timesOfDay))

activityTimeInteractionMatrix
array([[0.4, 0.3, 0.2, 0.3],
       [0.9, 0.1, 0.8, 0.7],
       [0.3, 1. , 0.2, 0.1],
       [0.1, 0.9, 0.5, 0.6],
       [1. , 0.7, 0.7, 0.3],
       [0.8, 0.2, 0.7, 0.9],
       [0.1, 0.2, 0.7, 0.8],
       [0.9, 0.4, 0.7, 0.4]])

For now, four time periods are considered, each of equal aproximately length. An array is created such that index [x,y] corresponds to the cost associated with scheduling a quanta of activity x during time period y

quantaClassificationsPrecursor = []
quantaClassifications = []
for i in range(len(timesOfDay)):
    quantaClassificationsPrecursor.append(
        (int(dailyQuanta // len(timesOfDay)) * [i]))  # this creates a compound list


for i in range(len(timesOfDay)):  # this flattens the aforementioned list
    quantaClassifications = quantaClassifications + \
        quantaClassificationsPrecursor[i]

# fixes imperfect divisions by extending last time period to cover remainder
while len(quantaClassifications) < dailyQuanta:
    quantaClassifications = quantaClassifications + [len(timesOfDay) - 1]

# using this algo, last time period can only exceed others by
# len(timesOfDay) -1 quanta

To capture the fact that it is worse to mischedule long tasks, cost is attributed on a per quanta basis. quantaClassifications is a list created such that index [x] will return the period of time (i.e. morning, mid-day, afternoon, night) that the quanta is classified as belonging to.

customActivitiesInteractionMatrix=np.zeros([8,8])

customActivitiesInteractionMatrix[0,]=np.array([0,0,5,10,15,20,25,30])
customActivitiesInteractionMatrix[1,]=np.array([0,0,0,5,10,15,20,25])
customActivitiesInteractionMatrix[2,]=np.array([5,0,0,0,5,10,15,20])
customActivitiesInteractionMatrix[3,]=np.array([10,5,0,0,0,5,10,15])
customActivitiesInteractionMatrix[4,]=np.array([15,10,5,0,0,0,5,10])
customActivitiesInteractionMatrix[5,]=np.array([20,15,10,5,0,0,0,5])
customActivitiesInteractionMatrix[6,]=np.array([25,20,15,10,5,0,0,0])
customActivitiesInteractionMatrix[7,]=np.array([30,25,15,10,5,0,0,0])
activitiesInteractionMatrix=customActivitiesInteractionMatrix
activitiesInteractionMatrix
array([[ 0.,  0.,  5., 10., 15., 20., 25., 30.],
       [ 0.,  0.,  0.,  5., 10., 15., 20., 25.],
       [ 5.,  0.,  0.,  0.,  5., 10., 15., 20.],
       [10.,  5.,  0.,  0.,  0.,  5., 10., 15.],
       [15., 10.,  5.,  0.,  0.,  0.,  5., 10.],
       [20., 15., 10.,  5.,  0.,  0.,  0.,  5.],
       [25., 20., 15., 10.,  5.,  0.,  0.,  0.],
       [30., 25., 15., 10.,  5.,  0.,  0.,  0.]])

This matrix is designed to produce an ideal session order of 0,1,2,3,4,5,6,7. I choose this order as it is easy to verfiy visually when inspecting scheudules. The same is true of the below matrix which covers the interaction between time of day and an activity. It overwrites the randomly generated version for demonstration puposes. To replace with your own custom version, alter the matrix. To use random values, delete this and every line featuring the word "custom".

customActivityTimeInteractionMatrix= np.zeros([8,len(timesOfDay)])

customActivityTimeInteractionMatrix[0,] = np.array([0,3,6,9])
customActivityTimeInteractionMatrix[1,] = np.array([0,3,6,9])
customActivityTimeInteractionMatrix[2,] = np.array([3,0,3,6])
customActivityTimeInteractionMatrix[3,] = np.array([3,0,3,6])
customActivityTimeInteractionMatrix[4,] = np.array([6,3,0,3])
customActivityTimeInteractionMatrix[5,] = np.array([6,3,0,3])
customActivityTimeInteractionMatrix[6,] = np.array([9,6,3,0])
customActivityTimeInteractionMatrix[7,] = np.array([9,6,3,0])
customActivityTimeInteractionMatrix=customActivityTimeInteractionMatrix/10
activityTimeInteractionMatrix= customActivityTimeInteractionMatrix
activityTimeInteractionMatrix
array([[0. , 0.3, 0.6, 0.9],
       [0. , 0.3, 0.6, 0.9],
       [0.3, 0. , 0.3, 0.6],
       [0.3, 0. , 0.3, 0.6],
       [0.6, 0.3, 0. , 0.3],
       [0.6, 0.3, 0. , 0.3],
       [0.9, 0.6, 0.3, 0. ],
       [0.9, 0.6, 0.3, 0. ]])

The index a, b gives the cost of scheduling a quanta of activity a during time period b.

Class and Method Overview


class Schedule:
    def __init__(self, durationGenes, startTimeGenes):
        self.durationGenes = durationGenes
        self.startTimeGenes = startTimeGenes
        self.list = ScheduleListGenerator(durationGenes=self.durationGenes,
                                          startTimeGenes=self.startTimeGenes)

For the purpose of minimising the number of variables to be optimised, I chose to represent a block of scheduled activity as a start time, a duration, and an index. The index indicates which activity is being scheduled. e.g. activity 1 will begin at Schedule.startTimeGenes[1] and last for a total of Schedule.durationGenes[1] quanta.

    def ExtractSessionInfomation(self):
        sessionOrder = []
        for i in self.list:
            if i == "-":
                pass
            else:
                sessionOrder.append(i)
                break
        sessionChangeQuanta = []
        sameCounter = 0
        changeCounter = 0
        sessionLengthsChronological = []
        for i in range(0, len(self.list)):
            if self.list[i] == "-":
                continue
            elif self.list[i - 1] == self.list[i]:
                sameCounter = sameCounter + 1
            else:
                changeCounter = changeCounter + 1
                sessionLengthsChronological.append(sameCounter + 1)
                sameCounter = 0
                sessionOrder.append(self.list[i])
                sessionChangeQuanta.append(i)

        sessionLengthsChronological.append(sameCounter + 1)
        numSessions = changeCounter + 1
        sessionLengthsChronological.pop(0)
        sessionOrder.pop(0)

        self.sessionOrder = sessionOrder
        self.sessionLengthsChronological = sessionLengthsChronological
        self.sessionChangeQuanta = sessionChangeQuanta

Many crucial methods belonging to this class depend upon knowing the order in which activities are scheduled and how long each activity is scheduled for. This method extracts and stores that infomation as attributes. One session is defined as a succession of quanta dedicated exclusively to one activity. They appear on schedules as many of the same number in an uninterupted chain.

    def CalculateOrderCosts(self):
        sessionOrderCosts = []
        for i in range(0, len(self.sessionOrder) - 1):
            sessionOrderCosts.append(
                activitiesInteractionMatrix[self.sessionOrder[i], self.sessionOrder[i + 1]])
        self.sessionOrderCosts = sessionOrderCosts
        self.SessionOrderCostTotal = sum(sessionOrderCosts)

    def CaclulateTimeOfDayCosts(self):
        timeOfDayCostsByActivity = []
        for i in range(0, len(self.list)):
            if self.list[i] == "-":
                timeOfDayCostsByActivity.append(0)
            else:
                timeOfDayCostsByActivity.append(
                    activityTimeInteractionMatrix[self.list[i], quantaClassifications[i]])
        self.timeOfDayCostsByActivity = timeOfDayCostsByActivity
        self.timeOfDayCostByActivityTotal = sum(timeOfDayCostsByActivity)

These methods exploit the properties of the matrices created above to calculate the cost associated with the timing of activities



    def CalculateSessionLengthCosts(self):
        sessionLengthsCosts = []
        for i in self.sessionLengthsChronological:
            if i < 18:
                sessionLengthsCosts.append((18 - i) * 5)
            else:
                sessionLengthsCosts.append(0)
        self.sessionLengthCosts = sessionLengthsCosts
        self.sessionLengthCostsTotal = sum(sessionLengthsCosts)

For ease of visualising the ideal solution when viewing candidates solutions proposed by the algorithm, the cost function demands that all each of the eight activities take up precisely one eighth of the schedule. This could later be adapted to consider the relative importance of tasks, and to deal with different ideal task lengths.

    def CalculateTotalCosts(self):
        self.ExtractSessionInfomation()
        self.CaclulateTimeOfDayCosts()
        self.CalculateOrderCosts()
        self.CalculateSessionLengthCosts()
        #  self.CalculateOpportunityCost()
        self.CalculateExclusionCosts()
        self.suboptimality = (
            self.SessionOrderCostTotal +
            self.timeOfDayCostByActivityTotal +
            self.sessionLengthCostsTotal +
        #    self.opportunityCost +
            self.exclusionCostsTotal)

    def FillerSoThatAboveFunctionIsntAtEndOfClassDefinition(self):
        pass  # exists to prevent silent misindentation errors


The nature of the rest of the cost calculating methods shown so far causes the algorithm to schedule as few activities per day. CalculateExclusionCosts is designed to counter that.

CalculateTotalCosts acts as a way of calling all cost related methods in a single line of code.

There is an error in the above class definition which causes the last-defined method to break. I wasn't able to find it, so I included a filler method to protect CalculateTotalCosts()

The Core of the Algorithm

def GenerateRandomStartTimeGenes():
    randomStartTimeGenes = np.zeros([numActivities], dtype=int)
    for i in range(numActivities):
        randomStartTimeGenes[i] = round(random.uniform(0, dailyQuanta), 0)
    return (randomStartTimeGenes)


def GenerateRandomDurationGenes():
    randomDurationGenes = np.zeros([numActivities], dtype=int)
    for i in range(numActivities):
        randomDurationGenes[i] = round(random.uniform(5, 40), 0)
    return randomDurationGenes


These generate random genes. They are called when creating the initial population, and every time a mutation is made.

It is this representation of time which allows for computationally efficient optimisation despite high time granularity, because it maximally reduces the number of variables to be optimised per item to be scheduled.

The arguments inside random.uniform() are chosen to reduce the number of very bad genes within the pool.

def ScheduleListGenerator(durationGenes, startTimeGenes):
    schedule = ["-"] * dailyQuanta
    for g in range(startTimeGenes.size):
        indiciesToChange = range(
            startTimeGenes[g],
            startTimeGenes[g] +
            durationGenes[g])
        for i in indiciesToChange:
            if i > dailyQuanta -1:
                break
            else:
                schedule[i] = g
    return(schedule)


This function generates schedules in the form of lists. It locates the first quanta of a session, then changes it to a number which corresponds to the number representing the activity to be scheduled. It then changes the next element downstream to the same number, and repeats this until the duration of the session matches the value given by it's corresponding duration gene.

def GenerateInitialPopulation(popSize):
    initialPopulation = []
    for i in range(popSize):
        initialPopulation.append(
            Schedule(
                durationGenes=GenerateRandomDurationGenes(),
                startTimeGenes=GenerateRandomStartTimeGenes()))
        initialPopulation[i].index = i
    return(initialPopulation)



This produces randomised genes, uses those to create a schedule object, and repeats until a population of the desired size is achieved.

def CalculatePopulationSuboptimalities(population):
    for i in population:
        i.CalculateTotalCosts()


def SortPopulation(pop):
    pop.sort(key=lambda x: x.suboptimality,
             reverse=False)  # sort population by suboptimality
    return(pop)

Once an initial population is generated, the list is sorted by it's suboptimality (the lesser the index, the lesser the suboptimality). This comes in handy for the tournament selection function shown below and makes it simple to extract the best schedule within each generation for comparison purposes (using population[0].list).


def Selection(sortedPopulation):  # uses tournament selection
    selectionResults = []
    for i in range(eliteSize):
        selectionResults.append(sortedPopulation[i])
    for i in range(eliteSize, popSize):
        # returns a list with 2 random integers
        a = random.sample(range(popSize), 2)
        if a[0] < a[1]:
            selectionResults.append(sortedPopulation[a[0]])
        else:
            selectionResults.append(sortedPopulation[a[1]])
    return(selectionResults)


As the population is already sorted by suboptimality, it's possible to implement tournament selection (randomly paired schedules "fight", only the winner, i.e. the one with the lowest suboptimalitiy, passes on their genes) by simply comparing the indices of combatants.

def Breed(selectedPopulation):
    matingPool = selectedPopulation[eliteSize:popSize]
    children = []
    breedingPartnersInOrder = random.sample(matingPool, len(matingPool))
    for i in range(
            len(matingPool)):  # for every in the mating pool, choose another at randomu
        parent1DurationGenes = matingPool[i].durationGenes
        parent1StartTimeGenes = matingPool[i].startTimeGenes
        parent2DurationGenes = breedingPartnersInOrder[i].durationGenes
        parent2StartTimeGenes = breedingPartnersInOrder[i].startTimeGenes
        childDurationGenes = np.zeros(numDurationGenes, dtype=int)
        childStartTimeGenes = np.zeros(numDurationGenes, dtype=int)
        for d in range(
                numDurationGenes):  # for every gene pair, decide at random which parents genes
            p = random.sample(range(1, 3), 1)  # to use in the next generation
            if p == 1:
                childDurationGenes[d] = parent1DurationGenes[d]
                childStartTimeGenes[d] = parent1StartTimeGenes[d]
            else:
                childDurationGenes[d] = parent2DurationGenes[d]
                childStartTimeGenes[d] = parent2StartTimeGenes[d]
        # create a new entity per set of child genes
        children.append(Schedule(childDurationGenes, childStartTimeGenes))
    return (children)



The breeding step, sometimes referred to as "crossing over", is the use of the selected parents genes to create the next generation. Every schedule within the mating pool produces one offspring by "mating" with another member of the mating pool at random. I use a random "sample" of size equal to that of the mating pool, as this generates a new list in random order representing the same population. This allows for mating to be performed randomly, which I believe is better than mating the best with the best (i.e. selective breeding) as it leads more diverse resultant populations which are better able to escape local minima.

def Mutate(population, mutationRate=mutationRate):
    numberOfGenesToMutatePerType = int(
    round(mutationRate * numDurationGenes * popSize))
    for d in range(numberOfGenesToMutatePerType):
        indexOfAnimalToMutate = random.sample(range(eliteSize, len(population)), 1)
        geneMutationIndex = random.sample(range(numDurationGenes), 1)
        population[indexOfAnimalToMutate[0]].durationGenes[geneMutationIndex[0]] = GenerateRandomDurationGenes()[
        geneMutationIndex[0]]
    for ST in range(numberOfGenesToMutatePerType):
        indexOfAnimalToMutate = random.sample(
            range(eliteSize, len(population)), 1)
        geneMutationIndex = random.sample(range(numDurationGenes), 1)
        population[indexOfAnimalToMutate[0]].startTimeGenes[geneMutationIndex[0]] = GenerateRandomStartTimeGenes()[
            geneMutationIndex[0]]
    return(population)

The mutation step exists to increase the diversity of the resultant generation. I chose to equally distribute mutations between start-time and duration genes because I couldn't see any reason not to. In hindsight, if the startTime or duration genes are already very close to perfect, but the other type were weak, it would be more useful to have an uneven distribution of mutations between gene types as that way some of the mutants would only see changes to the weak genes (leaving the near perfect genes intact). This will be verified then fixed in my next draft.

def IndexAdder(population):
    for i in range(len(population)):
        population[i].index = i
    return (population)

The index of populations are absent in children. This exists to add them. While these index attributes aren't required for the algorithm to function, it is useful to have if you want to see the before and after of a schedule while testing a function which involves rearranging the population as it allows you to query a resultant schedule for the index of its precursor.


def GeneticAlgorithm(
        initialPopulation = initialPopulation,
        popSize = popSize,
        eliteSize = eliteSize,
        mutationRate = mutationRate,
        generations = generations):

    global progress
    population = initialPopulation
    for i in range(generations):
        for p in population:
            p.CalculateTotalCosts()
        population = SortPopulation(population)
        progress.append(population[0].suboptimality)
        selectedPopulation = Selection(population)

        newGenerationPreMutation = Breed(
            selectedPopulation) + selectedPopulation[0:eliteSize]

        population = Mutate(newGenerationPreMutation)

    return(population)

This calls every step in order and iterates for the desired number of generations. With every generation it appends a list with the suboptimality of the best schedule within a population, and this list can be used to visualise how schedule quality improved with each generation.

initialPopulation = GenerateInitialPopulation(popSize)
finalGeneration = GeneticAlgorithm(initialPopulation)
for i in finalGeneration:
    i.CalculateTotalCosts()
plt.plot(progress)
plt.show()
progress = []
sortedFinalGeneration=SortPopulation(finalGeneration)
sortedFinalGeneration[0].list

This runs the genetic algorithm, and opens a window featuring a graph of schedule quality vs time, then shows you the best solution found.

from collections import Counter
import statistics as stat
import random as random
import numpy as np
import operator
import pandas as pd
import matplotlib.pyplot as plt
import pdb

numActivities = 8
popSize = 100
eliteSize = 4
mutationRate = 0.04
generations = 100
numDurationGenes = 8  # This should be equal to number of ST genes


quantaDuration = 5  # each block of time is equal to 5 mins long
hoursPerDayToSchedule = 12
dailyQuanta = int(60 * 24 * (hoursPerDayToSchedule / 24) / quantaDuration)

activitiesInteractionList = []
for i in range(0, numActivities**2):
    activitiesInteractionList.append(random.randint(1, 10))

activitiesInteractionMatrix = np.array(activitiesInteractionList).reshape(
    [numActivities, numActivities])

timesOfDay = ["morning", "mid-day", "afternoon", "night"]

activityTimeInteractionList = []
for i in range(0, numActivities * len(timesOfDay)):
    activityTimeInteractionList.append(random.randint(1, 10) / 10)

activityTimeInteractionMatrix = np.array(
    activityTimeInteractionList).reshape(numActivities, len(timesOfDay))

quantaClassificationsPrecursor = []
quantaClassifications = []
for i in range(len(timesOfDay)):
    quantaClassificationsPrecursor.append(
        (int(dailyQuanta // len(timesOfDay)) * [i]))  # this creates a compound list


for i in range(len(timesOfDay)):  # this flattens the aforementioned list
    quantaClassifications = quantaClassifications + \
        quantaClassificationsPrecursor[i]

# fixes imperfect divisions by extending last time period to cover remainder
while len(quantaClassifications) < dailyQuanta:
    quantaClassifications = quantaClassifications + [len(timesOfDay) - 1]

# using this algo, last time period can only exceed others by
# len(timesOfDay) -1 quanta

customActivitiesInteractionMatrix = np.zeros([8, 8])

customActivitiesInteractionMatrix[0, ] = np.array(
    [0, 0, 5, 10, 15, 20, 25, 30])
customActivitiesInteractionMatrix[1, ] = np.array([0, 0, 0, 5, 10, 15, 20, 25])
customActivitiesInteractionMatrix[2, ] = np.array([5, 0, 0, 0, 5, 10, 15, 20])
customActivitiesInteractionMatrix[3, ] = np.array([10, 5, 0, 0, 0, 5, 10, 15])
customActivitiesInteractionMatrix[4, ] = np.array([15, 10, 5, 0, 0, 0, 5, 10])
customActivitiesInteractionMatrix[5, ] = np.array([20, 15, 10, 5, 0, 0, 0, 5])
customActivitiesInteractionMatrix[6, ] = np.array([25, 20, 15, 10, 5, 0, 0, 0])
customActivitiesInteractionMatrix[7, ] = np.array([30, 25, 15, 10, 5, 0, 0, 0])

activitiesInteractionMatrix = customActivitiesInteractionMatrix

customActivityTimeInteractionMatrix = np.zeros([8, len(timesOfDay)])

customActivityTimeInteractionMatrix[0, ] = np.array([0, 3, 6, 9])
customActivityTimeInteractionMatrix[1, ] = np.array([0, 3, 6, 9])
customActivityTimeInteractionMatrix[2, ] = np.array([3, 0, 3, 6])
customActivityTimeInteractionMatrix[3, ] = np.array([3, 0, 3, 6])
customActivityTimeInteractionMatrix[4, ] = np.array([6, 3, 0, 3])
customActivityTimeInteractionMatrix[5, ] = np.array([6, 3, 0, 3])
customActivityTimeInteractionMatrix[6, ] = np.array([9, 6, 3, 0])
customActivityTimeInteractionMatrix[7, ] = np.array([9, 6, 3, 0])
customActivityTimeInteractionMatrix = customActivityTimeInteractionMatrix / 10
activityTimeInteractionMatrix = customActivityTimeInteractionMatrix


class Schedule:
    def __init__(self, durationGenes, startTimeGenes):
        self.durationGenes = durationGenes
        self.startTimeGenes = startTimeGenes
        self.list = ScheduleListGenerator(durationGenes=self.durationGenes,
                                          startTimeGenes=self.startTimeGenes)

    def ExtractSessionInfomation(self):
        sessionOrder = []
        for i in self.list:
            if i == "-":
                pass
            else:
                sessionOrder.append(i)
                break
        sessionChangeQuanta = []
        sameCounter = 0
        changeCounter = 0
        sessionLengthsChronological = []
        for i in range(0, len(self.list)):
            if self.list[i] == "-":
                continue
            elif self.list[i - 1] == self.list[i]:
                sameCounter = sameCounter + 1
            else:
                changeCounter = changeCounter + 1
                sessionLengthsChronological.append(sameCounter + 1)
                sameCounter = 0
                sessionOrder.append(self.list[i])
                sessionChangeQuanta.append(i)

        sessionLengthsChronological.append(sameCounter + 1)
        numSessions = changeCounter + 1
        sessionLengthsChronological.pop(0)
        sessionOrder.pop(0)

        self.sessionOrder = sessionOrder
        self.sessionLengthsChronological = sessionLengthsChronological
        self.sessionChangeQuanta = sessionChangeQuanta

    def CalculateOrderCosts(self):
        sessionOrderCosts = []
        for i in range(0, len(self.sessionOrder) - 1):
            sessionOrderCosts.append(
            activitiesInteractionMatrix[self.sessionOrder[i], 
            self.sessionOrder[i + 1]])
        self.sessionOrderCosts = sessionOrderCosts
        self.SessionOrderCostTotal = sum(sessionOrderCosts)

    def CaclulateTimeOfDayCosts(self):
        timeOfDayCostsByActivity = []
        for i in range(0, len(self.list)):
            if self.list[i] == "-":
                timeOfDayCostsByActivity.append(0)
            else:
                timeOfDayCostsByActivity.append(
                    activityTimeInteractionMatrix[self.list[i], quantaClassifications[i]])
        self.timeOfDayCostsByActivity = timeOfDayCostsByActivity
        self.timeOfDayCostByActivityTotal = sum(timeOfDayCostsByActivity)

    def CalculateSessionLengthCosts(self):
        sessionLengthsCosts = []
        for i in self.sessionLengthsChronological:
            if i < 18:
                sessionLengthsCosts.append((18 - i) * 5)
            else:
                sessionLengthsCosts.append(0)
        self.sessionLengthCosts = sessionLengthsCosts
        self.sessionLengthCostsTotal = sum(sessionLengthsCosts)

#    def CalculateOpportunityCost(self):
 #       self.opportunityCost = Counter(self.list)["-"] * 10

    def CalculateExclusionCosts(self):
        exclusionCosts = []
        for i in range(numActivities):
            if Counter(self.list)[i] < 1:
                exclusionCosts.append(100)
            else:
                continue
        self.exclusionCosts = exclusionCosts
        self.exclusionCostsTotal = sum(exclusionCosts)

    def CalculateTotalCosts(self):
        self.ExtractSessionInfomation()
        self.CaclulateTimeOfDayCosts()
        self.CalculateOrderCosts()
        self.CalculateSessionLengthCosts()
        #  self.CalculateOpportunityCost()
        self.CalculateExclusionCosts()
        self.suboptimality = (
            self.SessionOrderCostTotal +
            self.timeOfDayCostByActivityTotal +
            self.sessionLengthCostsTotal +
        #    self.opportunityCost +
            self.exclusionCostsTotal)

    def FillerSoThatAboveFunctionIsntAtEndOfClassDefinition(self):
        pass  # exists to prevent silent misindentation errors


def GenerateRandomStartTimeGenes():
    randomStartTimeGenes = np.zeros([numActivities], dtype=int)
    for i in range(numActivities):
        randomStartTimeGenes[i] = round(random.uniform(0, dailyQuanta - 4), 0)
    return (randomStartTimeGenes)


def GenerateRandomDurationGenes():
    randomDurationGenes = np.zeros([numActivities], dtype=int)
    for i in range(numActivities):
        randomDurationGenes[i] = round(random.uniform(4, 40), 0)
    return randomDurationGenes


def ScheduleListGenerator(durationGenes, startTimeGenes):
    schedule = ["-"] * dailyQuanta
    for g in range(startTimeGenes.size):
        indiciesToChange = range(
            startTimeGenes[g],
            startTimeGenes[g] +
            durationGenes[g])
        for i in indiciesToChange:
            if i > dailyQuanta - 1:
                break
            else:
                schedule[i] = g
    return(schedule)


def GenerateInitialPopulation(popSize):
    initialPopulation = []
    for i in range(popSize):
        initialPopulation.append(
            Schedule(
                durationGenes=GenerateRandomDurationGenes(),
                startTimeGenes=GenerateRandomStartTimeGenes()))
       # initialPopulation[i].index = i
    return(initialPopulation)


def CalculatePopulationSuboptimalities(population):
    for i in population:
        i.CalculateTotalCosts()


def SortPopulation(pop):
    pop.sort(key=lambda x: x.suboptimality,
             reverse=False)  # sort population by suboptimality
    return(pop)


def Selection(sortedPopulation):  # uses tournament selection
    selectionResults = []
    for i in range(eliteSize):
        selectionResults.append(sortedPopulation[i])
    for i in range(eliteSize, popSize):
        # returns a list with 2 random integers
        a = random.sample(range(popSize), 2)
        if a[0] < a[1]:
            selectionResults.append(sortedPopulation[a[0]])
        else:
            selectionResults.append(sortedPopulation[a[1]])
    return(selectionResults)


def Breed(selectedPopulation):
    matingPool = selectedPopulation[eliteSize:popSize]
    children = []
    breedingPartnersInOrder = random.sample(matingPool, len(matingPool))
    for i in range(
            len(matingPool)):  # for every in the mating pool, choose another at randomu
        parent1DurationGenes = matingPool[i].durationGenes
        parent1StartTimeGenes = matingPool[i].startTimeGenes
        parent2DurationGenes = breedingPartnersInOrder[i].durationGenes
        parent2StartTimeGenes = breedingPartnersInOrder[i].startTimeGenes
        childDurationGenes = np.zeros(numDurationGenes, dtype=int)
        childStartTimeGenes = np.zeros(numDurationGenes, dtype=int)
        for d in range(
                numDurationGenes):  # for every gene pair, decide at random which parents genes
            p = random.sample(range(1, 3), 1)  # to use in the next generation
            if p == 1:
                childDurationGenes[d] = parent1DurationGenes[d]
                childStartTimeGenes[d] = parent1StartTimeGenes[d]
            else:
                childDurationGenes[d] = parent2DurationGenes[d]
                childStartTimeGenes[d] = parent2StartTimeGenes[d]
        # create a new entity per set of child genes
        children.append(Schedule(childDurationGenes, childStartTimeGenes))
    return (children)


def Mutate(population, mutationRate=mutationRate):
    numberOfGenesToMutatePerType = int(
        round(mutationRate * numDurationGenes * popSize))
    for d in range(numberOfGenesToMutatePerType):
        indexOfAnimalToMutate = random.sample(
            range(eliteSize, len(population)), 1)

        geneMutationIndex = random.sample(range(numDurationGenes), 1)
        population[indexOfAnimalToMutate[0]].durationGenes[geneMutationIndex[0]
        ] = GenerateRandomDurationGenes()[geneMutationIndex[0]]

    for ST in range(numberOfGenesToMutatePerType):
        indexOfAnimalToMutate = random.sample(
            range(eliteSize, len(population)), 1)

        geneMutationIndex = random.sample(range(numDurationGenes), 1)

        population[indexOfAnimalToMutate[0]].startTimeGenes[geneMutationIndex[0]
        ] = GenerateRandomStartTimeGenes()[geneMutationIndex[0]]

    return(population)


#def IndexAdder(population):
 #   for i in range(len(population)):
  #      population[i].index = i
   # return (population)


initialPopulation = GenerateInitialPopulation(popSize)


progress = []


def GeneticAlgorithm(
        initialPopulation = initialPopulation,
        popSize = popSize,
        eliteSize = eliteSize,
        mutationRate = mutationRate,
        generations = generations):

    global progress
    population = initialPopulation
    for i in range(generations):
        for p in population:
            p.CalculateTotalCosts()
        population = SortPopulation(population)
        progress.append(population[0].suboptimality)
        selectedPopulation = Selection(population)

        newGenerationPreMutation = Breed(
            selectedPopulation) + selectedPopulation[0:eliteSize]

        population = Mutate(newGenerationPreMutation)

    return(population)


initialPopulation = GenerateInitialPopulation(popSize)
finalGeneration = GeneticAlgorithm(initialPopulation)
for i in finalGeneration:
    i.CalculateTotalCosts()
plt.plot(progress)
plt.show()
progress = []
sortedFinalGeneration=SortPopulation(finalGeneration)
sortedFinalGeneration[0].list
\$\endgroup\$
  • \$\begingroup\$ Welcome to CodeReview! When you say There is an error in the above class definition which causes the last-defined method to break, if you expect community input to help fix this, CR isn't the site you need; you'd be better off posting on StackOverflow. If you can live with that bug for now, and you need a review of your code, you should instead describe what it is you're looking for in a code review - are your concerns mainly about performance, or code style, etc.? \$\endgroup\$ – Reinderien Sep 19 at 13:27
  • \$\begingroup\$ Thanks you! I didn't post this for help with the bug, I will update my post to include what specifically I'd like reviewed \$\endgroup\$ – John Salter Sep 19 at 13:29
  • 3
    \$\begingroup\$ Your narrative is nice. It would make review easier if, at the end of your post, you show the code again in one blob. \$\endgroup\$ – Reinderien Sep 19 at 13:37
4
\$\begingroup\$

numpy

numpy.random has functions to generate random arrays. So, this:

activitiesInteractionList = []
for i in range(0, numActivities**2):
    activitiesInteractionList.append(random.randint(1, 10))

activitiesInteractionMatrix = np.array(activitiesInteractionList).reshape(
    [numActivities, numActivities])

becomes this:

activitiesInteractionMatrix = np.random.randint(1, 11, size=[numActivities, numActivities])

and this:

activityTimeInteractionList = []
for i in range(0, numActivities * len(timesOfDay)):
    activityTimeInteractionList.append(random.randint(1, 10) / 10)

activityTimeInteractionMatrix = np.array(
    activityTimeInteractionList).reshape(numActivities, len(timesOfDay))

becomes:

activityTimeInteractionList = np.random.random(size=[numActivities, numActivities]))
activityTimeInteractionList = activityTimeInteractionList * (1 - .1) + .1

np.array() can take a list of lists.

customActivitiesInteractionMatrix = np.array([[0,0,5,10,15,20,25,30],
                                              [0,0,0,5,10,15,20,25],
                                              [5,0,0,0,5,10,15,20],
                                              [10,5,0,0,0,5,10,15],
                                              [15,10,5,0,0,0,5,10],
                                              [20,15,10,5,0,0,0,5],
                                              [25,20,15,10,5,0,0,0],
                                              [30,25,15,10,5,0,0,0]])

If things named custom... are for testing, put them in a proper test, or at least put it in an if block so you don't need to delete them to get proper operation. You can just set TESTING to True/False to enable/disable the code:

if TESTING:
    customActivitiesInteractionMatrix = ...
    ActivitiesInteractionMatrix = customActivitiesInteractionMatrix
    etc.

list.extend

Use the extend() method to add multiple elements to the end of a list.

quantaClassifications = []
for i in range(len(timesOfDay)):
    quantaClassifications.extend(dailyQuanta // len(timesOfDay) * [i])

quantaClassifications.extend((dailyQuanta - len(quantaClassifications)) * [len(timesOfDay) - 1])

list comprehension:

Or in this case, use a list comprehension:

quantaClassifications = [i*len(timesOfDay)//dailyQuanta for i in range(dailyQuanta)]

enumerate() and zip()

When looping over a sequence, like a list, and the index and value are needed, it would be better to use for i,value in enumerate(sequence): rather than for i in range(len(sequence)):. To iterate over multiple sequences in parallel, use zip(). Use slice assignment and itertools.repeat() to eliminate an explicit loop. Like so:

def ScheduleListGenerator(durationGenes, startTimeGenes):
    schedule = ["-"] * dailyQuanta
    for g,(start,duration) in enumerate(durationGenes, startTimeGenes):
        end = min(start + duration, dailyQuanta))
        schedule[start:end] = itertools.repeat(g, end-start)

    return schedule

readability

Code should be written to be read and understood. Descriptive names help. But, lines of code that are too long or that wrap to the next line are more difficult to read than shorter lines. So there is a balance between how descriptive a name is and how long it is.

misc

return doesn't need parens. return schedule instead of return(schedule)

The default start for range() is '0', so range(99) is the same as range(0, 99).

Try to avoid magic numbers: sessionLengthsCosts.append((18 - i) * 5). Where do the 5 and 18 come from? If the code is edited somewhere else (like the size of a data structure, or the value of quantaDuration) how do you know if these numbers should change? Are they used anywhere else in the code? It would be better to make them a constant, or at least add a doc string or comment to explain them.

Short, one letter, variable names often have a customary usage or implied meaning. For example, it is common to use variables i,j,k as integer indexes, or x,y,z as floating point coordinates. When they are used for something else (e.g. for i in self.list) it can be confusing.

\$\endgroup\$
  • \$\begingroup\$ I chose this as the best answer because it lead to a greater reduction in the number of lines I was able to reduce from my program, and it addressed what I believed to be deeper flaws in the program. The other answer was also very good, it was close. \$\endgroup\$ – John Salter Sep 21 at 9:45
6
\$\begingroup\$

Formatting

Get an IDE or a linter that will give you hints about PEP8, Python's standard for code formatting. Among other things, it will suggest:

  • Capital letters for your constants, e.g. NUM_ACTIVITIES
  • lower_camel_case for your variable and function names, e.g. activity_interactions instead of activitiesInteractionList (also note that you shouldn't usually write the type of a variable in its name)
  • def CalculateOrderCosts(self): becomes calculate_order_costs(self):
  • class Schedule stays as it is

Order of operations

int(60 * 24 * (hoursPerDayToSchedule / 24) / quantaDuration)

Not sure why the cancelling 24 terms are written there; you can drop them and use integer division, dropping the parens:

60 * hours_per_day_to_schedule // quanta_duration

Vectorization

activitiesInteractionList = []
for i in range(0, numActivities**2):
    activitiesInteractionList.append(random.randint(1, 10))

This should better-leverage numpy vectorization. See for example https://docs.scipy.org/doc/numpy-1.15.1/reference/generated/numpy.random.rand.html

In-place addition

quantaClassifications = quantaClassifications + \
    quantaClassificationsPrecursor[i]

can be

quanta_classifications += quanta_classifications_precursor[i]

Also, this construct:

quantaClassifications = quantaClassifications + [len(timesOfDay) - 1]

can be

quanta_classifications.append(len(times_of_day) - 1)

Matrix assignment

customActivitiesInteractionMatrix[0, ] = np.array(
    [0, 0, 5, 10, 15, 20, 25, 30])
customActivitiesInteractionMatrix[1, ] = np.array([0, 0, 0, 5, 10, 15, 20, 25])
customActivitiesInteractionMatrix[2, ] = np.array([5, 0, 0, 0, 5, 10, 15, 20])
customActivitiesInteractionMatrix[3, ] = np.array([10, 5, 0, 0, 0, 5, 10, 15])
customActivitiesInteractionMatrix[4, ] = np.array([15, 10, 5, 0, 0, 0, 5, 10])
customActivitiesInteractionMatrix[5, ] = np.array([20, 15, 10, 5, 0, 0, 0, 5])
customActivitiesInteractionMatrix[6, ] = np.array([25, 20, 15, 10, 5, 0, 0, 0])
customActivitiesInteractionMatrix[7, ] = np.array([30, 25, 15, 10, 5, 0, 0, 0])

The right-hand side should be represented as a single two-dimensional matrix. This should then be possible with a single assignment.

Null if

        if i == "-":
            pass
        else:
            ...

should just be

if i != '-':
    ...

General

You do have some methods, but you also have a bunch of globally-scoped code, particularly for matrix setup. This should also be moved into methods. Ideally, the only thing to be found at global scope should be method and class declarations, imports, and constants.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.