Meeting Schedule Optimization with Genetic Algorithm in Python

Meeting Schedule Optimization with Genetic Algorithm in Python

There are many complex real world optimization problems for which it’s not possible to obtain the exact best solution efficiently with reasonable amount of computing resources. Often the solution search space for such problems is combinatorially explosive. For such problems, heuristic optimizations are the only pragmatic option. Heuristic optimization algorithm with significantly reduced computational cost is used when a sub optimum solution is acceptable.

In this post we will go through a solution for meeting schedule optimization with Genetic Algorithm (GA) in Python. For this seemingly innocuous problem, search space may have trillions of solutions to explore. I have implemented set of heuristic optimization algorithm, including GA available in my open source Github repository avenir. The implementations are reusable and agnostic to any specific problem.

Heuristic Optimization

According to the book Clever Algorithms, Nature Inspired Programming Recipes, heuristic optimization algorithms can be categorized as follows. The book contains details of many algorithms under each of these categories.

• Stochastic Algorithms
• Evolutionary Algorithms
• Physical Algorithms
• Probabilistic Algorithms
• Swarm Algorithms
• Immune Algorithms

Stochastic algorithms use randomness to elicit non-deterministic behaviors in searching the solution space e.g Tabu Search. Physical algorithms are inspired by physical processes like metallurgy and music e.g Simulated Annealing. In Probabilistic algorithms, the solution space is searched using probabilistic model of candidate solutions e.g Bayesian Optimization.

Swarm algorithms are based on collective intelligence that emerges from the cooperation of large number of agents in an environment. Immune algorithms are inspired by the process and mechanisms of the biological immune system.

Genetic Algorithm (GA) falls under the category of Evolutionary Algorithms. Algorithms can also be classified as Solitary or Population based. In population based algorithms, a pool of candidate solution are managed and tracked. GA is a population based algorithm which mimics natural evolution and selections enabled by cross over and mutation

Evolutionary Algorithm

The genetic algorithm implementation is available is in my Github repository. Here is the Python base class for optimizer. Here is the algorithm

input:
	pool size : p
	mating size : m
	replacement size : r
	number of iteration : ic
	number of local search iteration : lic
	whether to purge pool first : pf
	whether local search enabled : ls
	
algorithm:
	create pool of candidate solutions with pool size 
	
	for i 1 to ic
		if best solution from pool better than current best solution
			best solution = best solution from pool 
		create mating candidate list selecting m best from pool
		until we have a new generation of size r
			choose a pair randomly from mating list
			create 2 offsprings from the pair with cross over and mutation
			add them to new generation 
			
		if pf
			purge r worst candidates from pool
			add new generation to pool
		else
			add new generation to pool
			purge r worst candidates from pool
		
	if ls
		current local best = best solution
		for i 1 to lic
			generate new solution mutating  best solution
			if new solution better than current local best
				current local best solution = new solution 
		if current local best solution better than  best solution
			best solution = current local best solution
			
	return best solution

All parameters of the algorithm are specified in a configuration file. Here is a sample configuration file for the meeting schedule optimization problem. The value _ in the configuration file indicates default value for a configuration which is defined in the python implementation code. The solution generated by the optimizer is defined as a list of numbers, the size of the list depending on the specific problem

Meeting Schedule Optimization

An optimization problem is specified with a cost function definition and constraints if any. The optimizer finds a solution with lowest cost subject to the constraints.

When scheduling meetings it is desirable to have large blocks of free time in between meetings. For each person, we find the median of all free blocks of time. We define cost for a person as the median subtracted from a constant to make it inversely related to the median of free blocks of time. The overall cost is defined as the weighted average of the per person cost. A weight can assigned to some people, so the optimizer is coerced to focus more on maximizing free time in between meetings for people with higher weight.

Any candidate solution that the optimizer generates has to satisfy all the constraints. Here are the constraints

• Certain meetings have to occur in a specified order
• Some people may have some hours blocked. No meeting can be scheduled for them that overlaps with blocked hours
• If 2 meetings overlap, there can not same 1or more participants common in both meetings.

The user specifies a set of meetings for week providing participant list and duration for each meeting. The optimizer returns as solution day of the week, hour and minute of start of each meeting.

The optimizer works as a frame work. For a particular problem the interface to the optimizer is a Python class which has to implement 2 call back. methods isValid() and evaluate(). The first method is called to check if a candidate solutions valid. It return true if no constraint is violated. A candidate solution is the day of the week, hour and minute for all meetings. The second method returns cost for a given candidate solution. Here is the Python class for meeting schedule problem.

Here is a sample output from the optimizer. The first part shows schedule for all meetings corresponding to the best solution found. The optimizer was run for 15 meetings in a week. Since each meeting has 3 numbers for solution, each solution is a list containing 45 numbers.

optimizer started, check log file for output details...

best solution found
cost 0.538
meeting: day 5 hour 16 min 0 duration 120
meeting: day 5 hour 8 min 0 duration 120
meeting: day 5 hour 8 min 0 duration 120
meeting: day 3 hour 16 min 30 duration 120
meeting: day 4 hour 15 min 0 duration 120
meeting: day 1 hour 9 min 0 duration 60
meeting: day 1 hour 8 min 0 duration 60
meeting: day 3 hour 16 min 30 duration 90
meeting: day 5 hour 8 min 0 duration 60
meeting: day 5 hour 14 min 0 duration 120
meeting: day 1 hour 8 min 30 duration 30
meeting: day 2 hour 8 min 0 duration 60
meeting: day 2 hour 13 min 0 duration 30
meeting: day 5 hour 8 min 0 duration 60
meeting: day 4 hour 8 min 30 duration 90

best solution history
iter: 0000	cost: 1.688 	soln: [5, 14, 30, 4, 8, 0, 5, 15, 30, 5, 13, 0, 2, 8, 30, 2, 10, 30, 1, 15, 30, 1, 9, 0, 4, 10, 30, 1, 12, 0, 2, 8, 0, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 11, 30]
iter: 0001	cost: 1.666 	soln: [3, 15, 30, 5, 13, 0, 3, 11, 0, 1, 9, 0, 3, 14, 0, 5, 8, 30, 2, 12, 0, 5, 14, 30, 2, 10, 0, 3, 13, 30, 2, 12, 30, 4, 11, 0, 1, 9, 0, 1, 9, 30, 5, 11, 30]
iter: 0002	cost: 1.587 	soln: [5, 10, 0, 5, 14, 0, 2, 13, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 5, 12, 0, 1, 16, 30, 4, 10, 30, 1, 12, 0, 2, 8, 0, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 11, 30]
iter: 0004	cost: 1.584 	soln: [3, 15, 30, 5, 13, 0, 3, 16, 0, 4, 9, 0, 3, 14, 0, 5, 8, 30, 2, 12, 0, 5, 14, 30, 2, 10, 0, 3, 13, 30, 2, 12, 30, 4, 11, 0, 1, 9, 0, 1, 9, 30, 5, 11, 30]
iter: 0005	cost: 1.359 	soln: [5, 10, 0, 5, 14, 0, 2, 13, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 14, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 11, 30]
iter: 0008	cost: 1.250 	soln: [5, 10, 0, 5, 15, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 14, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 11, 30]
iter: 0012	cost: 1.236 	soln: [5, 10, 0, 5, 15, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 0, 5, 14, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 11, 30]
iter: 0013	cost: 1.196 	soln: [5, 10, 0, 5, 13, 0, 2, 13, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0014	cost: 1.087 	soln: [5, 10, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0018	cost: 1.060 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 0, 5, 14, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0020	cost: 1.033 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 3, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0022	cost: 0.978 	soln: [5, 16, 30, 5, 10, 0, 2, 9, 0, 3, 15, 0, 4, 15, 30, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 15, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0023	cost: 0.951 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 12, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0026	cost: 0.938 	soln: [5, 16, 30, 5, 10, 0, 2, 9, 0, 3, 15, 0, 4, 15, 30, 1, 10, 0, 1, 12, 0, 3, 9, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 15, 30, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0027	cost: 0.897 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 11, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0032	cost: 0.891 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 11, 0, 3, 9, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 1, 8, 30, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0033	cost: 0.883 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 11, 0, 3, 15, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 9, 0, 4, 8, 30]
iter: 0036	cost: 0.856 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 15, 0, 4, 15, 0, 1, 10, 0, 1, 11, 0, 3, 9, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0038	cost: 0.747 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 9, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0048	cost: 0.707 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 30, 2, 13, 0, 5, 8, 0, 4, 8, 0]
iter: 0051	cost: 0.693 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0056	cost: 0.679 	soln: [5, 16, 0, 5, 14, 0, 2, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0060	cost: 0.666 	soln: [5, 16, 0, 5, 14, 0, 5, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 0, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0062	cost: 0.652 	soln: [5, 16, 0, 5, 14, 0, 5, 9, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 0]
iter: 0065	cost: 0.625 	soln: [5, 16, 0, 5, 14, 0, 5, 8, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 11, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 0]
iter: 0069	cost: 0.606 	soln: [5, 16, 0, 5, 14, 0, 5, 8, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0076	cost: 0.592 	soln: [5, 16, 0, 5, 14, 30, 5, 8, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0079	cost: 0.579 	soln: [5, 16, 0, 5, 9, 0, 5, 8, 0, 3, 16, 30, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0081	cost: 0.565 	soln: [5, 16, 0, 5, 8, 30, 5, 8, 0, 3, 16, 0, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0100	cost: 0.552 	soln: [5, 16, 0, 5, 8, 0, 5, 8, 0, 3, 16, 30, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 1, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]
iter: 0111	cost: 0.538 	soln: [5, 16, 0, 5, 8, 0, 5, 8, 0, 3, 16, 30, 4, 15, 0, 1, 9, 0, 1, 8, 0, 3, 16, 30, 5, 8, 0, 5, 14, 0, 1, 8, 30, 2, 8, 0, 2, 13, 0, 5, 8, 0, 4, 8, 30]


best solution after local search of global best solution
cost 0.538
meeting: day 5 hour 16 min 0 duration 120
meeting: day 5 hour 8 min 0 duration 120
meeting: day 5 hour 8 min 0 duration 120
meeting: day 3 hour 16 min 30 duration 120
meeting: day 4 hour 15 min 0 duration 120
meeting: day 1 hour 9 min 0 duration 60
meeting: day 1 hour 8 min 0 duration 60
meeting: day 3 hour 16 min 30 duration 90
meeting: day 5 hour 8 min 0 duration 60
meeting: day 5 hour 14 min 0 duration 120
meeting: day 1 hour 8 min 30 duration 30
meeting: day 2 hour 8 min 0 duration 60
meeting: day 2 hour 13 min 0 duration 30
meeting: day 5 hour 8 min 0 duration 60
meeting: day 4 hour 8 min 30 duration 90

local search failed to find a better solution

total solution count 3927  invalid solution count 1900

The second part shows the solution convergence with iteration. We find that the solution converges after 110 iterations, although we performed 200 iterations, as you will find in the configuration file. This is remarkable, when contrasted with the trillions of potential solutions that needed to be searched with a brute force approach.

The last part of the output shows the result of local search. In this case, the local search did not yield a solution better than the best solution already found. As alluded to earlier, in local search we take the best solution and mutate it for certain number of times, looking for a better solution.

For more more details and intermediate output, you could look up the log file. The log file path is specified in the configuration file.

Wrapping Up

We sent through a solution for optimizing meeting schedule using Genetic Algorithm (GA) in python. For the particular example used, a brute fore approach would have required evaluation of trillions potential solutions . The number of solutions with a brute force approach is C(40, 15), assuming meetings are scheduled at hour boundaries. Instead, we found an optimum solution after around 110 iterations. Such is the extraordinary power of heuristic optimization algorithms. Here is the tutorial for running this example