An Algorithm Which Schedules Your LifeGenetic algorithm for “Hello World”Genetic algorithm final stageGenetic search algorithm for TSPPython genetic algorithmTraveling Salesman Problem genetic algorithmDesign of genetic algorithm which would allow TDDFirstDuplicate FinderGenetic algorithm to guess passwordGenetic algorithm fitness function for scheduling

Do I need to use capacitors when using an L7805CV voltage regulator?

Apollo CM heat shield burnt pattern around RCS thrusters

Is Fairphone violating the GPL with its newest Fairphone 3?

Is an afterburner louder than the same jet engine without it?

Why is Gaia operating around Earth orbit? Why not send it to Neptune's orbit?

80’s or earlier short fantasy about very “sweet” neighbours

Adding "dot com" to the end of a sentence?

Why is this translation not a linear transformation?

Is there any benefit of being treated as "professor" by students and admin?

United States Towns/States Traversing by Name Puzzle

My passport's Machine Readable Zone is damaged. How do I deal with it?

is differential geometry really required to understand anything in algebraic geometry?

How does a human body spend energy on its organs?

How can an AI train itself if no one is telling it if its answer is correct or wrong?

Pattern matching expressions that have been simplified

Is there a guide/reference for character hairstyle possible in D&D Forgotten Realms universe?

In C#, is there a way to enforce behavior coupling in interface methods or is the fact that I am trying to do that a design smell?

How do I recover from a cryptocurrency scam?

Did any significant programs or environments take advantage of the Rexx which came with PCDOS 7 (aka PCDOS 2000)?

Why can I solve an impossible equation using linear algebra?

What does "two ells within the selvages" mean in the Magna Carta?

How much would we learn from observing an FTL starship fly by?

How to help a male-presenting person shop for women's clothes?

What is the difference between "more" and "less" commands?



An Algorithm Which Schedules Your Life


Genetic algorithm for “Hello World”Genetic algorithm final stageGenetic search algorithm for TSPPython genetic algorithmTraveling Salesman Problem genetic algorithmDesign of genetic algorithm which would allow TDDFirstDuplicate FinderGenetic algorithm to guess passwordGenetic algorithm fitness function for scheduling






.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;









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









share|improve this question











$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

















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









share|improve this question











$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













8













8









8


2



$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









share|improve this question











$endgroup$




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






python genetic-algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Sep 19 at 14:10









AlexV

5,8102 gold badges15 silver badges40 bronze badges




5,8102 gold badges15 silver badges40 bronze badges










asked Sep 19 at 13:20









John SalterJohn Salter

834 bronze badges




834 bronze badges














  • $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
















  • $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















$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$
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




$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




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




$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










2 Answers
2






active

oldest

votes


















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.






share|improve this answer










$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.






share|improve this answer










$endgroup$















    Your Answer






    StackExchange.ifUsing("editor", function ()
    StackExchange.using("externalEditor", function ()
    StackExchange.using("snippets", function ()
    StackExchange.snippets.init();
    );
    );
    , "code-snippets");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "196"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );














    draft saved

    draft discarded
















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f229313%2fan-algorithm-which-schedules-your-life%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown


























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    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.






    share|improve this answer










    $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















    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.






    share|improve this answer










    $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













    4















    4











    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.






    share|improve this answer










    $endgroup$



    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.







    share|improve this answer













    share|improve this answer




    share|improve this answer










    answered Sep 19 at 20:26









    RootTwoRootTwo

    2,7745 silver badges12 bronze badges




    2,7745 silver badges12 bronze badges














    • $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
















    • $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















    $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




    $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.






    share|improve this answer










    $endgroup$


















      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.






      share|improve this answer










      $endgroup$
















        6















        6











        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.






        share|improve this answer










        $endgroup$



        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.







        share|improve this answer













        share|improve this answer




        share|improve this answer










        answered Sep 19 at 13:52









        ReinderienReinderien

        12.8k22 silver badges50 bronze badges




        12.8k22 silver badges50 bronze badges































            draft saved

            draft discarded















































            Thanks for contributing an answer to Code Review Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f229313%2fan-algorithm-which-schedules-your-life%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown









            Popular posts from this blog

            Tamil (spriik) Luke uk diar | Nawigatjuun

            Align equal signs while including text over equalitiesAMS align: left aligned text/math plus multicolumn alignmentMultiple alignmentsAligning equations in multiple placesNumbering and aligning an equation with multiple columnsHow to align one equation with another multline equationUsing \ in environments inside the begintabularxNumber equations and preserving alignment of equal signsHow can I align equations to the left and to the right?Double equation alignment problem within align enviromentAligned within align: Why are they right-aligned?

            Training a classifier when some of the features are unknownWhy does Gradient Boosting regression predict negative values when there are no negative y-values in my training set?How to improve an existing (trained) classifier?What is effect when I set up some self defined predisctor variables?Why Matlab neural network classification returns decimal values on prediction dataset?Fitting and transforming text data in training, testing, and validation setsHow to quantify the performance of the classifier (multi-class SVM) using the test data?How do I control for some patients providing multiple samples in my training data?Training and Test setTraining a convolutional neural network for image denoising in MatlabShouldn't an autoencoder with #(neurons in hidden layer) = #(neurons in input layer) be “perfect”?