Order-based genetic algorithm in Flexsim
Attached is an example of integrating an order-based genetic algorithm (GA) into a Flexsim model to solve a scheduling problem. Because of its heavy reliance on statistics, if you don't have a license key this example won't really work. Plus you won't be able to modify the GA parameters or view the functions I wrote because I left them in the tree on purpose. This example is completely made-up.
Model:
-10 different order types must pass along a conveyor, then go through one of two machines
-the ProcessTimes global table dictates which orders can be done on which machines, 0 means no
-the SetupTimeMatrix global table is a From/To lookup for changeover times
-the system is stuborn in that the orders must leave the conveyor in the order they entered
Question:
How to sequence the 10 order types such that the overall time to process all is minimized?
With no restrictions on the order sequencing, this leaves us with over 3.6 million possibilities. Assuming a model run of 0.01s this could take 10hrs to try all. Ouch.
Parameters:
A "GA" folder within the Tools folder of the model tree holds everything. The first 4 nodes in that tree are managed by the GA, the 5 nodes after that are the parameters:
*popsize
size of the population, pool of possible solutions
*nrofgens
number of generations, how long to run the GA
*elitepairs
number of solutions to pass directly to the next generation without change (1=pass top 2 performers)
*crossovermode
0=uniform crossover
1-single crossover point
2-dual crossover points
...
*mutationprob
percent probability that a given gene will be mutated, although the way I implemented it, the result is actually less than this value
How the GA works:
When you click the "Initialize and Run GA" button, the GA randomly generates a population of order sequence solution possibilities called chromosomes. The first solution is loaded into the model then run (the master chromosome is used to translate the gene number into an itemtype for the Source, in this case 1=1, 2=2, etc.). When the Sink receives the 10th item it relays the model time (our only performance measure) back to the GA. The GA loads the next solution and re-runs the model... continuing until all solutions in the population are evaluated. Next the GA randomly mates parent chromosomes from the current population to create a new population (generation). The top performers are passed through unchanged (elitism). The new population is evaluated then used to create the next generation, and so on. Over time, new top performing solutions are found until the GA finds the best solution (hard to prove) or gets stuck on a sub peek solution.
Integrating a GA into a Flexsim model was straight forward, but that's not the hard part. Writing a good GA is difficult. A poor GA will perform no better than a random search. You will find that this one is not the best. If you initialize and run it a few times you should get a time of 77. I 'think' that is the best solution.
|
Can embedding genetic algorithm in Flexsim ?
