Writing Samples
Decision Support Systems (1999)
|
|
David Montie
Writing Samples Decision Support Systems (1999) |
Decision Support for Vehicle Dispatching Using Genetic Programming
A discussion of the article published
by I. Benyahia and J. Potvin in: IEEE Transactions on Systems, Man,
and Cybernetics; Vol 28, No. 3, May 1998.
Introduction This discussion is based upon a paper written by Benyahia and Potvin describing their use of the genetic programming technique to develop a decision support system. The courier dispatch domain was selected for this project because of the unique challenges it presents to computer programming. The courier dispatch domain is defined as any "demand-responsive transport" necessary in emergency (fire, ambulance, police), military, and courier services. Decision Support Systems are a desired tool for this domain because the career of a typical human dispatcher is only about 2 years. This role has a high turnover rate mainly because discreet, or absolutely correct, answers do not exist; yet, there is a considerable amount of pressure on the dispatcher to make sound performance decisions within a minimum time frame. As a result, human dispatchers are in a constant state of stress while operating in this high-pressure and ambiguous environment. However, these characteristics provide an ideal scenario for genetic programming: The high burn-out rate of human operators creates the demand for a Decision Support System that can help to relieve human stress while simultaneously improving the level of dispatching performance. The Courier Dispatch Domain The courier dispatch domain is complicated and dynamic. Within the dispatch domain, the human operator must constantly deal with change throughout the decision making process. For example, a courier moving from point A (pick-up) to point B (delivery) can be instantly re-routed to include another pick-up along the way. Therefore, long-term prediction and planning becomes difficult, if not impossible because the routing and scheduling are done in real time as customers request service. This makes predictive models, linear algorithms, and heuristic rule based Decision Support Systems ineffective when it comes to developing solutions for the courier dispatch domain. Logistics also fuels the need for developing a courier Decision Support System. In routine cases, good dispatching ensures that couriered information is consistently transported quickly and efficiently. However, in more severe cases, human lives rely on the quality of the emergency dispatching. To add further strain on the situation, the dispatcher's decisions are often determined by conflicting forces. For example, customers want fast delivery routes; management wants efficient delivery routes; and drivers want easy delivery routes. Therefore, a large part of the human dispatcher's decision making involves compromise -- a concept that does not easily translate to a computerized model. When taken together, the problems of dynamic context and compromise create a domain too complicated for a simple traditional programming solution. In addition, even experienced dispatch operators could not convey a set of heuristics to describe how they make decisions on the job. Therefore, an effective Decision Support System would require a programming technique that allows the software to aquire it's own optimized solution. The Genetic Programming Technique Genetic programming is a method of creating non-linear code structures via evolutionary techniques. The process takes what we know about evolution in biological systems and transfers it to develop a similar process in the development of a computer program. The evolutionary technique generates a number of competing programs at random, selects the best, and then uses these top performers to breed the next batch of competing programs. Each cycle of this competition is a generation, and with enough generations a superior program or solution will emerge. It is, of course, a slightly more complex interaction among three sub processes: Selection of the fittest, cross-over, and mutation. Selection of the fittest: This is where the randomly generated programs are evaluated for "fitness" at solving a problem set. This process is similar to natural selection where the population is evaluated: The strong get to reproduce and the weak get eaten. Only those programs that come closest to a solution -- only the strongest or fittest -- contribute their genes toward the propagation of future generations. Cross-over: The selected programs, or gene algorithms, are then ‘broken' and recombined with other successful programs. This is similar to the process of biological reproduction where a child's genes are a combination of each parent's genetic makeup. The same occurs in genetic programming: Mother and Father are selected for fitness and their genes are split and recombined in various ways to produce offspring. This process varies how the parental genetics are combined in each child; and this will result in some offspring with exaggerated genetic weakness, and some with genetic strengths. Over a number of generations, the strong become stronger and the weak become weaker. Mutation: The child acquires genes from it's mother and father, plus a unique mutation quality of its own. This is considered a background operator that adds variance to the process of genetic evolution. Mutation is necessary because if the same type of genes continue reproducing, being selected, and reproducing again, then the evolution process can fixate at a local maxima or premature solution. Therefore, mutation is introduced at each generation to maintain the population diversity and provide a genetic ‘wild card' to incorporate potentially useful genes not present in previous generations. The mutation process can also have negative effects on the population, and it is up to the process of Selection to filter out these counterproductive variations. Evolution is a string of variations on a common theme: A diverse population branches off from a successful lineage; the process of Selection acts to prune away all but the best outcomes; and only those remaining reproduce via the process of Cross-over to seed the next generation with genetic strategies best suited to the target domain.
For the courier application,
the authors adapted the programming technique to compute the utility function
for assigning new courier requests to fleet vehicles. They used nine
attributes, identified as important by human dispatchers, and four
operands as their genetic tags. They established their criteria for Selection
by accumulating 140 case history samples of recent courier dispatching activity.
Once the evolution process was underway, each solution was ranked according to
fitness (how well it performed on the 140 test cases) and basic constraints (solutions
are constrained by the promise that new orders are collected within 30 minutes and
delivered within 90 minutes of the customer's call). With these adaptations in
place, the authors were able to set the process of evolution into motion. This evolutionary technique shows how advances can be gained from mimicking what we know about biology and Nature. The technique allows us to model and learn from a computed solution; whereas with traditional techniques, we just program in a representation of our existing knowledge. Therefore, this approach is particularily well suited to problems without an existing solution. To further illustrate it's advantages, the genetic programming technique was compared to another study of the courier dispatch domain using the back propagation neural network technique. The neural network 'learned' to mimic the heuristics used by human dispatchers, whereas the genetic programming technique figured out the best solution for itself. And, when the two were compared, the genetic technique yielded a more optimized first rank (a better overall solution) than the trained neural network. Both produced better results than any simple dispatching 'rule-of-thumb' (heuristic) used by human operators. Limitations of Genetic Programming On the down side, Genetic Programming relies on computational brute force to create, test, and select programs for each generation. The technique often requires many thousands of generations to achieve an acceptable solution; and in this particular case, no significant improvement evolved after 100 generations (with population of 500 in each generation). Due to the large computational requirements, time becomes a major constraint. The largest example in this case took 5 hours to compute one full generation set (population 500) on a Sun Sparc 10 Workstation. So, if it takes hours to compute one generation, and many thousands of generations are required for significant gains, then it is easy to see why computer resources become a limiting factor in the process. However, once an acceptable algorithm was identified, it took mere seconds for it to work on the job -- the evolved program could easily rank vehicles in real time to assist the dispatcher's decision making ability. Future Directions for Genetic Programming Technological limitations aside, the power of this evolutionary computing technique is limited by the criteria used for Selection of the fittest. An evolved solution is only as good as the criteria it has been selected by because evolution itself is merely an optimization process. Evolution relies on Natural Selection for direction, and this means our definition of the Selection process -- the criteria that is used to represent the problem domain -- is going to determine the nature of the solution that will evolve. So, in the application developed by Benyahia and Potvin, the solution evolved toward an algorithm that was optimized to the set of test case data used in their fitness criteria. Although the data set was a representative sample of the courier dispatch domain, the solution did not perform as well in the real world. It comes down to a question of robustness: The solution is evolved to be the best at solving that particular set of problem data, but this does not guarantee that it will work equally well on a related, but different, data set. One recommendation is
to incorporate co-evolution into the process of Genetic Programming.
This is a method of
increasing the solution robustness by incorporating competition of another
kind: The Selection criteria is designed to co-evolve with the solution.
This co-evolution functions to embody Murphy's Law by continuously challenging
the solution algorithms with worst-case-scenarios to ensure robustness in real-world conditions.
The co-evolution technique is, in essence, a parasite that evolves toward
a goal of defeating the solution algorithms; and each parasite generation is selected
for fitness according to their ability to stump the solution algorithms.
In Benyahia and Potvin's application, the solution algorithms are selected
according to performance on the static test case data. With co-evolution, however,
the test data is replaced by a parallel evolution process that is rewarded for it's
ability to outsmart the solutions. Thus, an evolutionary war is staged whereby test
data algorithms are evolved to challenge the solutions; and the solution algorithms, in
turn, evolve to efficiently handle every possible dispatching scenario.
|