Graphical Genetic Algorithm

Part I : Simple Assignments

This work was motivated by a talk I had with an employee of a home service company.

Assume you are the manager of several workers that must perform home visits. Your company has a coverage area of 60 miles in diameter. Your workers live as well as service homes within this area. How should workers be scheduled to job sites to minimize their travel time. Ideally, a worker would service their own neighborhood. However, that is an unlikely scenario.

Here, in Part I, we will examine a reduction of the aforementioned problem. There will be no real objective other than illustrating some of the mechanics of a genetic algorithm.

1 Get data

We will generate random data for this problem. First, we must define some parameters that will govern each problem instance.

SERVICE_WIDTH

SERVICE_HEIGHT
NUMBER_OF_WORKERS
NUMBER_OF_SITES

1.1 Generate job sites

A job site is defined as location that must be serviced, having a x,y location within the WIDTH and HEIGHT of your company's service area.

Example: {Name: "Woodlands", location: (2400, 1800)}

1.2 Generate workers

Similarly, workers also have a home at an x,y location within the WIDTH and HEIGHT of your company's service area.

Example: {name: "Jeff Jeffington", location: (4500, 120)}

For this article, lets assume we have 10 job sites and are assigning one or multiple job sites for one worker.

2. Encoding

This refers to how we represent the data and their relationships. For simplicity, we represent Jeffington's schedule as a boolean array. That is, a list of True or False values indicating the assignment of a job site to Jeffington.

Example: Two possible assignments are shown where a black box represents the assignments of Jeffington to a job site. The first sample indicates that Jeffington must visit sites 2, 4, 5, 6, and 10.

We then define a method to determine the "goodness" of a solution. Usually, appropriate metrics would specify a solutions goodness (ex. minimize distance, maximize profit, etc.).

Example: Arbitrarily specify the ideal solution is for Jeffington to work alternating days. A solution score will be the count of the number of matching assignment values to the optimal solution. It is important to point out that this method of measuring the solution's goodness is not customary as it is usually the case that the optimal solution is unknown.

3. Population

Now, a collection of population "members" can be defined representing various solutions to the assignment problem. We will specify POPULATION_SIZE=10, and start with ten randomly generated solutions, similar to the two mentioned in the previous examples.

Example: Ten randomly generated assignment solutions for Jeffington make up this population. Many have similar assignment values (at job 1, and 10). Some more closely resemble the optimal solution (member7). The assignment solution's score is shown beneath the solution label.

3.1 Parent Selection

The selection of parents is usually based on the goodness of the solution evaluation score. After being selected, the pair of parents perform crossovers to generate new offspring solutions.

Example: Assume members 5 and 6 are chosen to generate offspring, relabeled here as "parent".

3.2 Offspring Generation

For each pair of parents, some number of offspring will be produced by selecting an assignment value from a randomly selected parent. These newly generated members then join the general population (of solutions).

Example: Here are four offspring, sharing similar assignment values with their parents. Notice that both parents, and subsequently all offspring, have identical assignment values for job 2, 5, and 10.

Offspring2 has received all assignments of parent2 and an assignment to job 2 from parent1.

3.3 Population Size Control

The population size is culled/controlled by keeping/removing some number of members to return it to the starting size of ten. This can be done by ranking solutions by scores, or simply producing enough offspring to completely replace the previous generation.

Example: After generating offspring, the population now consists of 14 members. Recall, POPULATION_SIZE=10. Foregoing the usual selection based on assignment solution values, for simplicity, we randomly choose ten members to retain.

Following the population control method, the algorithm compares solutions in the population to the best found solution (so far). The cycle iterates, selecting, producing, and removing solutions for a specified number of iterations.

Conclusion

Though there are a few mechanics that were not detailed here such as mutations, penalties, and many problem-specific alternate mechanism of crossover, we have shown some of the basic mechanics of genetic algorithms. Basically, we generate a starting set of solutions, generate new solutions based on the initial set, retaining the better scoring solutions. This approach is very useful for particular problem types and can find some good solutions, if not optimal. In Part II we will examine the specific motivating assignment problem.

Abba. Thank you for the opportunities, health, and strength to take on each daily task. Bless the readers assignments.

Page updated

Google Sites

Report abuse