UPM Institutional Repository

Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems


Citation

Nazif, Habibeh (2010) Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems. PhD thesis, Universiti Putra Malaysia.

Abstract

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.


Download File

[img]
Preview
PDF
FS_2010_53_IR.pdf

Download (541kB)

Additional Metadata

Item Type: Thesis (PhD)
Subject: Genetic algorithms
Subject: Combinatorial optimization
Call Number: FS 2010 53
Chairman Supervisor: Dr. Lee Lai Soon, PhD
Divisions: Faculty of Science
Notes: Dr. Lee Lai Soon, PhD
Depositing User: Haridan Mohd Jais
Date Deposited: 01 Mar 2013 03:34
Last Modified: 27 May 2013 08:14
URI: http://psasir.upm.edu.my/id/eprint/21097
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item