Some improved genetic-algorithms based heuristics for global optimization with innovative applications
Date
2010-09-07
Authors
Adewumi, Aderemi Oluyinka
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The research is a study of the efficiency and robustness of genetic algorithm to instances of both
discrete and continuous global optimization problems. We developed genetic algorithm based
heuristics to find the global minimum to problem instances considered.
In the discrete category, we considered two instances of real-world space allocation problems
that arose from an academic environment in a developing country. These are the university
timetabling problem and hostel space allocation problem. University timetabling represents a
difficult optimization problem and finding a high quality solution is a challenging task. Many
approaches, based on instances from developed countries, have been reported in the literature.
However, most developing countries are yet to appreciate the deployment of heuristics and
metaheuristics in handling the timetabling problem. We therefore worked on an instance from a
university in Nigeria to show the feasibility and efficiency of heuristic method to the timetabling
problem. We adopt a simplified bottom up approach in which timetable are build around
departments. Thus a small portion of real data was used for experimental testing purposes. As
with similar baseline studies in literature, we employ genetic algorithm to solve this instance and
show that efficient solutions that meet stated constraints can be obtained with the metaheuristics.
This thesis further focuses on an instance of university space allocation problem, namely the
hostel space allocation problem. This is a new instance of the space allocation problems that has
not been studied by metaheuristic researchers to the best of our knowledge. The problem aims at
the allocation of categories of students into available hostel space. This must be done without
violating any hard constraints but satisfying as many soft constraints as possible and ensuring
optimum space utilization. We identified some issues in the problem that helped to adapt
metaheuristic approach to solve it. The problem is multi-stage and highly constrained. We first
highlight an initial investigation based on genetic algorithm adapted to find a good solution
within the search space of the hostel space allocation problem. Some ideas are introduced to
increase the overall performance of initial results based on instance of the problem from our case
study. Computational results obtained are reported to demonstrate the effectiveness of the
solution approaches employed.
Sensitivity analysis was conducted on the genetic algorithm for the two SAPs considered to
determine the best parameter values that consistently give good solutions. We noted that the
genetic algorithms perform well specially, when repair strategies are incorporated. This thesis
pioneers the application of metaheuristics to solve the hostel space allocation problem. It
provides a baseline study of the problem based on genetic algorithms with associated test data
sets. We report the best known results for the test instances.
It is a known fact that many real-life problems are formulated as global optimization problems
with continuous variables. On the continuous global optimization category therefore, we focus
on improving the efficiency and reliability of real coded genetic algorithm for solving
unconstrained global optimization, mainly through hybridization with exploratory features.
Hybridization has widely been recognized as one of the most attractive approach to solving
unconstrained global optimization. Literatures have shown that hybridization helps component
heuristics to taking advantage of their individual strengths while avoiding their weaknesses. We
therefore derived three modified forms of real coded genetic algorithm by hybridizing the
standard real-coded genetic algorithm with pattern search and vector projection. These are
combined to form three new algorithms namely, RCGA-PS, RCGA-P, and RCGA-PS-P. The
hybridization strategy used and results obtained are reported and compared with the standard
real-coded genetic algorithm. Experimental studies show that all the modified algorithms
perform better than the original algorithm.
Description
Keywords
Unconstrained global optimization, genetic algorithms, space allocation, hostel space allocation problem, timetabling, pattern search, vector projection, heuristics, metaheuristics, hierarchical heuristics