Last week I implemented my first “useful” genetic algorithm (GA) to solve a mapping problem. Lesson learned: don’t mistake “good solution according to the algorithm” with “good solution to the problem.”

Two weeks ago, I learned that my research group will trade one large room for two smaller rooms soon. The question thus immediately arose of where to sit those people about to lose their desk.

After only ten minutes of side-ways thinking, I found what I considered a pretty good solution. It only requires to move five people out of sixteen: the four that had to move anyway because their room was substituted, and one person who had requested to move independently. This solution additionally brings two groups of friends together who were previously separated.

Then both my supervisor and I simultaneously suggested that we also check whether we could improve everyone’s work situation by shuffling more desks around, if possible by bringing together people who work together.

Last time we worked on this, we used a floor plan and little paper labels to search for solutions using a trial-and-error strategy with a lot of guesswork. This time, I took the opportunity to exercise my understanding of genetic algorithms (GAs) by implementing a GA solver to our people-to-room mapping problem.

❦❦❦

Genetic algorithms use a strategy similar to natural evolution to automatically find solutions to computing problems. The process is simple and powerful: starting with a few candidate solutions, the algorithm repeatedly generates new solutions using small random changes (mutations), and grouping random existing solutions together (cross-overs). As the number of solutions increases, it only keeps the “best” solutions found so far.

To implement a GA, a programmer needs the following prerequisites:

• a function that evaluates “how good” a new solution is
• a function that mutates an existing solution into a new solution
• optionally, a function that can “breed” two solutions together to produce two new solutions

The main general challenge of implementing GAs is to find a good data representation of solutions to the problem, for which mutation and cross-over can be computed readily.

When solving mapping problems, the common choice to represent solutions is an array where:

• each cell index corresponds to an entity to place, e.g. a person, and
• each cell value corresponds to a placement target, e.g. a room seat.

With this representation, mutation is straightforward: simply exchange the values of two cells in the array. However, cross-over is a challenge: exchanging portions of the array between two solutions can create invalid solutions. For example, given the placement [101, 101, 109] and the placement [109, 101, 101], a cross-over can produce [101, 101, 101] and [109, 101, 109]. This is invalid if the room 101 has only two seats and 109 one seat. The common solutions to this problem are either to “repair” invalid solutions (make minor changes to make them valid) or simply reject them.

For my implementation, I used the Distributed Evolution Algorithms in Python (DEAP) framework, as advised by a friend and colleague. I used the data representation above, and I chose to ignore cross-overs entirely, relying only on mutation. As an initial population, I used our current desk placement and a few additional ideas that came up while writing the code.

The main “interesting” work was in writing the evaluation function. By taking into account what I knew was important to my colleagues, I used the following criteria:

• a penalty for moving people away from the room they already occupy;
• an advantage for bringing together people working on related topics;
• an advantage for bringing friends together;
• a penalty for bringing people together who’d rather not sit in the same room;
• a penalty for bringing other people in the room of a senior staff who usually expects to sit alone.

My code was working and running within two hours of work (ping me if you want a copy). Then I ran it multiple times.

❦❦❦

The exciting part is that my program found multiple solutions I had not thought about previously, and which I knew our colleagues had not envisioned before either. These solutions were even pretty good at bringing work interests and friendships together, much better than our current placement. I was not only satisfied that the program ran without errors; I was also pleased that my program would output something both “correct” and which I could not have imagined myself.

Proud with these results, I submitted them to my supervisor and colleagues, who immediately proceeded to reject them entirely as unacceptable.

In other words, if I was running my own business, this is the moment where the client walks away saying “no good, won’t pay.” As my ears were burning red, I had the feeling I had produced an instance of the proverbial answer that is “technically correct, but completely useless.” [1]

After my colleagues pointed out what they did not like about my proposals, and re-stating what they found important, I decided to propose instead the first solution I had found initially (“after a few minutes of side-ways thinking,” cf. above) and it went much more smoothly. My first GA application had failed, and my intuition prevailed.

1st lesson learned: -1 for computer science, +1 for serendipity.

❦❦❦

In hindsight, I had made two obvious mistakes in my implementation. The first mistake was to under-estimate how people are reluctant to change in general, ie. I under-estimated the weight of the move penalty in the evaluation function. I made this mistake by mis-translating my supervisor’s suggestion to “examine all options” into a very small weight for the move penalty. The other mistake was to give the same move penalty to everyone, whereas some colleagues were much more attached to their desk position than others.

After the page was turned by my supervisor, I decided to check whether my GA code could be salvaged. So I modified the evaluation function to simply use an extra weight for the move penalty, and I ran it again. This time, the GA solver came up to a single answer: the first solution that I had envisioned initially.

It was both a little disappointment and an interesting conclusion.

I was disappointed that the GA code could not, this time, find “new” solutions that I had not envisioned. Maybe additional solutions exist; maybe the GA code could not find them because it does not support cross-breed, or because I used invalid parameters for the mutation/cross-breed probabilities. Unfortunately, I have no time left to investigate this further.

The conclusion is twofold. For one, the quality of the solutions to a genetic algorithm is only as good as the evaluation function makes them; an error in the evaluation function renders the computed solutions utterly inadequate. I can now easily see how one could waste hours, days or even years toying with GA solvers to technical problems and fail to produce any interesting or appropriate solution. Then I now also realize that I subconsciously use efficient, good criteria when solving problems, and that I am not able to formulate them consciously when trying to encode my method into a computer program.

2nd lesson learned: I must learn to better externalize my thinking process.

❦❦❦

[1] The joke goes as follows:

The pilot in a helicopter could not determine his position due to fog. He spotted a tall building, flew toward it, and circled it with a handwritten sign that says “WHERE AM I?” in large letters.

People in the tall building quickly responded to the aircraft, drew a large sign, and held it in a building window. Their sign said “YOU ARE IN A HELICOPTER.”

The pilot thanked them by smiling and waving, determined the route to the nearest airport and landed safely. When they were finally on the ground, his co-pilot asked him how he’d done it.

“I knew it had to be the University, because they gave me a technically correct but useless answer.”

(“University” in this joke can be replaced by the preferred victim community)