Hybrid Approach for Solving a Combinatorial Problem with Gene Tuning
Main Article Content
Abstract
A new hybrid approach of Genetic Algorithm (GA) with local search algorithm is proposed to solve Course Timetabling Problems (CTP). In which, GA architecture is enhanced by proposing various selection, crossover and mutation operators. Diversity in population helps to get global optimum. In order to accommodate diversity of population and to avoid local optima, grade selection and combinatorial partially matched crossover operators are proposed. To increase the convergence rate and to produce guaranteed result, various mutation strategies are proposed with gene tuning approach. To improve the quality of the solution, steepest ascent hill climbing local search algorithm has been proposed. With these, hybrid approach with enhanced GA is implemented on CTP and hence its quality is proved by getting more promising and consistent results in all operations of the possible twelve combination of GA proposed operators. Also, proved experimentally that combination of grade selection, combinatorial partially matched crossover and adaptive mutation strategy operators is performing the best among all twelve proposed combinations and a combination of operators from the literature by yielding the average relative convergence rate as 31% which is greater than all others’ convergence rate.
Â
Â
Key Words: course timetabling, grade selection, rank selection, combinatorial partially matched crossover, mutation, gene tuning, local search.
Downloads
Article Details
COPYRIGHT
Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
- The journal allows the author(s) to retain publishing rights without restrictions.
- The journal allows the author(s) to hold the copyright without restrictions.