Graphical Genetic Algorithm

Part || : Multiple Worker Assignments

Continuing with the line of work prompted by a conversation I had with a home service company, we now consider the assignment problem for multiple workers.

Assume you are (still) 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. Here, in Part II, we will address the problem of how workers should be scheduled to jobs to minimize their travel time.

1 Get Data

Again, we will generate random data for this model. Recall that we defined (but did not really use) a few system wide parameters. We will set these to values of :

SERVICE_WIDTH = 600
SERVICE_HEIGHT = 600
NUMBER_OF_WORKERS = 8
NUMBER_OF_JOBS = 5

For the following two processes, names were randomly generated from a random combination of vowel-consonant digraphs (ex. "pa" + "ja" + "ut" -> "pajaut").

1.1 Generate Jobs

Using the random name generator and selecting random x,y locations for jobs sites, we get the following list:

jobs = [

{'site': 'j:ciweit', 'x': 405, 'y': 241},

{'site': 'j:gogo', 'x': 129, 'y': 116},

{'site': 'j:egre', 'x': 186, 'y': 134},

{'site': 'j:acoxec', 'x': 206, 'y': 558},

{'site': 'j:adoh', 'x': 487, 'y': 519}

]

1.2 Generate Workers

Similarly, the following list was generated for the set of workers:

workers = [

{'name': 'amehwu-mi', 'x': 248, 'y': 170},

{'name': 'otokde-oi', 'x': 171, 'y': 482},

{'name': 'uvuhgi', 'x': 178, 'y': 309},

{'name': 'evihob', 'x': 227, 'y': 217},

{'name': 'meaf', 'x': 472, 'y': 535},

{'name': 'oosu', 'x': 573, 'y': 572},

{'name': 'iiezyi', 'x': 285, 'y': 337},

{'name': 'piakse', 'x': 140, 'y': 127}

]

Example: Our company's service area can be represented by plotting the workers and job sites.

2. Encoding

2.1 Representation

This is the representation of the input data to be used in the solution process. Here, a solution is two dimensional and describes the assignments for each worker. This is, obviously, larger than a single worker assignment solution.

Example: A solution showing assignments to jobs for each worker. Black boxes indicate that the worker, listed to the left, is assigned to a job site, listed on the bottom.

Notice that worker "auor" has been assigned three jobs and worker "duuc" only one.

2.2 Evaluation

Because our encoding has changed our evaluation method must also change. When modeling the single worker assignment problem, we were very loose with the evaluation function. Here, because we have generated actual data, we can be more specific.

Referring to the primary objective of minimizing worker travel time, we define distance as the primary metric. Thus, minimizing distance minimizes travel time. And we can determine the total distance traveled by :

a.) calculating the distance between each worker and each job site

b.) multiplying job-worker distances by assignment solution

c.) sum all resultant values

This resultant value indicates how good a solution is.

Example : An example of the sum-product calculation used to evaluate solutions.

dij =
[ [ 2, 3, 7 ],
[ 5, 8, 5 ] ]

solution =
[ [ 1, 0, 1 ],
[ 0, 1, 0 ] ]

sumproduct of dij and solution =
( 2 * 1 + 3 * 0 + 7 * 1 ) +

( 5 * 0 + 8 * 1 + 5 * 0 ) = 17

It is important to specify that all jobs must be serviced by at least one worker. If this were not included, the minimum distance solution is to not assign any workers, a score of zero. For solutions that do not require all jobs to be serviced, we penalize it some large value.

📑 Note : This evaluation value could later be augmented by other penalties, based on assignment rules/restrictions we chose to impose. But for now, it suffices to show a solutions value.

3. Population

As was previously discussed in Part I, we now generate a collection of candidate solutions referred to as the "population". If there is an indication of what a potentially close to optimal solution might be, we could generate members based on that solution. More common place, however is to generate random members.

Example: A population of five randomly generated members is provided.

4. Genetic Algorithm

As was discussed in Part I Section 3 Population, the primary mechanics of an iteration of the algorithm are :

Parent Selection
Offspring Generation
Controlling Population Size
Updating Best Found

A mutation function will now be added to offspring generation. This mimics spontaneous real-world gene mutations that sometime result in altered body functions (or sometimes super powers)!

4.1 Mutation

In this context, a mutation will be an alteration or modification to an existing solution. This alteration must have a specified probability of occurrence, where there is a balance between frequent mutations that reduces the efficacy of the searches progress, and infrequent mutations that could result in a local optimal solution. There are many different methods that could be considered such as adding/removing a worker, or assigning all jobs to a worker. We will implement three : randomize, clear, and flip.

Example: Given a sample solution the resultant changes due to the different types of mutations will demonstrated.

4.1.1 Randomize

For a worker/job, randomly alter the assignment values for that row/column.

Example: Worker "evihob" was altered using the randomize mutation. Notice that any of the values in that worker's list can be altered to either assigned or not.

4.1.2 Clear

For any worker/job, all assignments are removed for that row/column.

Example: Worker "otokde-oi" was altered with the clear mutation. Notice that there are no longer assignments for this worker.

4.1.3 Flip

For any worker/job, all values are flipped. That is, all previous assignments are removed and all non-assignments are now assigned.

Example: Worker "oosu" was altered with the flip mutation. Notice that the previously assigned jobs are removed and all previously unassigned jobs are now assigned.

4.2 Extra Credit : Pseudo-code

The logic is listed, but is not required reading.

Combining all the components mentioned in Part I and II, our genetic algorithm would behave like:

P <-- generate_population(workers, jobs)

S <-- get_scores(P)

bestS, bestP = 9999999, [[]]

Loop for number_iterations :

Loop for number_families :

parents <-- select_parents(P)

offspring <-- make_offspring(parents)

offspringx <-- mutate(offspring, rate=.01)

newP <-- P + offspringx

newS <-- get_scores(newP)

sorted_newS, sorted_newP <-- sort(newS, newP)

S, P <-- control_size(sorted_newS, sorted_newP)

if min(S) < bestS :

bestS, bestP <-- min(S), min(P)

4.3 Run and Results

Now that we have specified all of the major components, we will run the genetic algorithm search for 1,000 iterations. This is a minute number considering that there are approximately 1.1 trillion possible solutions (where each assignment has two values, and there are eight workers that can possibly be assigned to five jobs; 2^(8*5) = 1,099,511,627,776). We can expect to not find the optimal solution.

Increasing the number of iterations would likely yield better solutions (if not optimal). However, the advantage of using a genetic algorithm is to avoid evaluating all 1 trillion solutions, but to search with some 'intelligence' derived from the process of parent selection and offspring generation.

4.3.1 Run Parameters

We will use the randomly generated data from Sections 1.1 and 1.2. After 1,000 iterations the best found solution is returned.

Example: The best found assignment solution after 1,000 iterations of the genetic algorithm.

This solution's map.

Conclusion

We have fully implemented a genetic algorithm, though it may not be very well performing. With an objective of minimizing distance, and only one constraint requiring that all jobs be serviced by at least one worker, the resultant solution assigns multiple jobs to a few workers.

In the next article, Part III, we will increase the solution space dimension by considering multiple day, multiple worker assignments. This disparity in workload will be even more pronounced if unchecked as we proceed to Part III.

Jehovah, You have wonderfully designed each of us. Please encourage the reader to live the life that you have given.

Page updated

Google Sites

Report abuse