Content deleted Content added
m Various citation cleanup + WP:AWB fixes . Report errors and suggestions at User talk:CitationCleanerBot |
mNo edit summary |
||
Line 19:
[[Image:SchedulingGenome1.jpg|frame|Fig. 2 A. Example Schedule genome]]
<!-- Image with unknown copyright status removed: [[Image:SchedulingGenome2.jpg|frame|Fig. 2 B. Example Schedule genome]] -->
To apply a genetic algorithm to a scheduling problem we must first represent it as a genome. One way to represent a scheduling genome is to
A specific sequence of tasks and start times (genes) represents one genome in our population. To make sure that our genome is a [[Candidate solution|feasible solution]] we must take care that it obeys our precedence constraints. We generate an initial population using random start times within the precedence constraints. With genetic algorithms we then take this initial population and cross it combining genomes with a small amount of randomness (mutation). The offspring of this combination is selected based on a [[fitness function]] that includes one or many of our constraints, such minimizing time and minimizing defects. We let this process continue either for a pre-allotted time or until we find a solution that fits our minimum criteria. Overall each successive generation will have a greater average fitness i.e. taking less time with higher quality than the proceeding generations. In scheduling problems, as with other genetic algorithm solutions, we must make sure that we do not select offspring that are infeasible, such as offspring that violate our precedence constraint. We of course may have to add further fitness values such as minimizing costs however each constraint that we add greatly increases the search space and lowers the number of solutions that are good matches.
| |||