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 funct...

Full description

Saved in:
Bibliographic Details
Main Author: Nazif, Habibeh
Format: Thesis
Language:English
English
Published: 2010
Subjects:
Online Access:http://psasir.upm.edu.my/id/eprint/21097/1/FS_2010_53_IR.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
id my-upm-ir.21097
record_format uketd_dc
spelling my-upm-ir.210972013-05-27T08:14:59Z Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems 2010-07 Nazif, Habibeh 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. Genetic algorithms Combinatorial optimization 2010-07 Thesis http://psasir.upm.edu.my/id/eprint/21097/ http://psasir.upm.edu.my/id/eprint/21097/1/FS_2010_53_IR.pdf application/pdf en public phd doctoral Universiti Putra Malaysia Genetic algorithms Combinatorial optimization Faculty of Science English
institution Universiti Putra Malaysia
collection PSAS Institutional Repository
language English
English
topic Genetic algorithms
Combinatorial optimization

spellingShingle Genetic algorithms
Combinatorial optimization

Nazif, Habibeh
Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
description 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.
format Thesis
qualification_name Doctor of Philosophy (PhD.)
qualification_level Doctorate
author Nazif, Habibeh
author_facet Nazif, Habibeh
author_sort Nazif, Habibeh
title Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
title_short Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
title_full Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
title_fullStr Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
title_full_unstemmed Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems
title_sort optimised crossover genetic algorithms for combinatorial optimisation problems
granting_institution Universiti Putra Malaysia
granting_department Faculty of Science
publishDate 2010
url http://psasir.upm.edu.my/id/eprint/21097/1/FS_2010_53_IR.pdf
_version_ 1747811481742737408