Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems

A Genetic Algorithm is successful in generating near -optimal solutions if it is able to produce o®spring during crossover that is better than the parent solutions. Most of the current methods of crossover determine o®spring by using a stochastic approach and without reference to the objective function with the result being that a potentially optimal solution could be lost through incorrect choices being made in the randomisation process. This thesis focuses on the development of a new stream of crossover within genetic algorithms, called Optimised Crossover Genetic Algorithm (OCGA) for solving combinatorial optimisation problems, which takes into account the objective function in finding the best ofspring solution among an exponentially large number of potential ofspring. Using the optimised crossover scheme, the two parents produce the two new children: the Ochild (Optimum child) and the E-child (Exploratory child). The Ochild is constructed in a way so as to have the best objective function value from the feasible set of children, while the E-child is constructed so as to maintain the diversity of the search space. In this thesis, the OCGA is applied to some combinatorial optimisation problems, specically on single machine scheduling problems and vehicle routing problems. We particularly focus on four problems: single machine family scheduling problem with maximum lateness, single machine family scheduling problem with total weighted completion time, capacitated vehicle routing problem and vehicle routing problem with time windows. These problems are motivated by the manufacturing organisations where decisions involve a trade-o® between the manufacturer's e±ciency and customers' satisfaction. Extensive computational experiments are carried out to assess the e®ectiveness of the OCGA compared to other local search methods proposed in the literature. The results shown the OCGA is competitive and capable of generating near optimal solutions.

Preview PDF FS_2010_53_IR.pdf Download (541kB)

Actions (login required)

View Item