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:	Genetic algorithms Combinatorial optimization
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

Optimised Crossover Genetic Algorithms for Combinatorial Optimisation Problems

Similar Items