Some improved genetic-algorithms based heuristics for global optimization with innovative applications

Adewumi, Aderemi Oluyinka

Some improved genetic-algorithms based heuristics for global optimization with innovative applications

dc.contributor.author	Adewumi, Aderemi Oluyinka
dc.date.accessioned	2010-09-07T09:06:06Z
dc.date.available	2010-09-07T09:06:06Z
dc.date.issued	2010-09-07
dc.description.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.	en_US
dc.identifier.uri	http://hdl.handle.net/10539/8621
dc.language.iso	en	en_US
dc.subject	Unconstrained global optimization	en_US
dc.subject	genetic algorithms	en_US
dc.subject	space allocation	en_US
dc.subject	hostel space allocation problem	en_US
dc.subject	timetabling	en_US
dc.subject	pattern search	en_US
dc.subject	vector projection	en_US
dc.subject	heuristics	en_US
dc.subject	metaheuristics	en_US
dc.subject	hierarchical heuristics	en_US
dc.title	Some improved genetic-algorithms based heuristics for global optimization with innovative applications	en_US
dc.type	Thesis	en_US