Three-Dimensional Genetic Algorithm for the Kirkman's Schoolgirl Problem
Abstract
This paper focuses on the possibilities of multidimensional genetic algorithms and relevant genetic operators. After the literature overview we used a three-dimensional genetic algorithm to solve a combinatorial task called Kirkman’s Schoolgirl Problem. The first results were not good, but we improved convergence of an algorithm by adding more genetic operators. We also used problem dependent mutation, where we tried to repair the incorrect solution by using the simple heuristic method. Finally, we got a solid number of correct solutions, but we know there is enough room for other improvements.
References
Bui, T. N., and Moon, B. R.: On Multi-Dimensional Encoding/Crossover. ICGA, pp. 49–56. (2002)
Jung, S., and Moon, B. R.: The Natural Crossover for the 2D Euclidean TSP. In Genetic and Evolutionary Computation Conference, pp. 1003–1010. (2000)
Langdon, W. B., and Poli, R.: Foundations of Genetic Programming. Springer (2002). ISBN 3540424512.
Kahng, A. B., and Moon, B. R: Toward More Powerful Recombinations. In International Conference on Genetic Algorithms, pp. 96-103 (1995)
Anderson, C., Jones, K., and Ryan, J.: A two-dimensional genetic algorithm for the Ising problem. Complex Systems, pp. 327-333 (1991)
Sosic, R., and Gu, J.: Efficient local search with conflict minimization: a case study of the n-queens problem. In IEEE Transactions on Knowledge and Data Engineering, vol. 6, no. 5, pp. 661-668 (1994)
Colbourn, C. J. and Dinitz, J. H.: Handbook of combinatorial designs. Second edition. Boca Raton: Taylor & Francis Group, Discrete mathematics and its applications (2007) ISBN 978-1-58488-506-1.
Seo, D. I., and Moon, B. R.: A survey on chromosomal structures and operators for exploiting topological linkages of genes. In Genetic and Evolutionary Computation Conference (2003)
J. Cohoon and D. Paris. Genetic placement. In IEEE International Conference on Computer-Aided Design, pp. 422-425 (1986)
Balázs, M.-E.: Multidimesional Crossover in Genetic Algorithms. Artificial Neural Networks and Genetic Algorithms, Springer (1998)
Ball Rouse, W. W. and, Coxeter, H. S. M.: Mathematical recreations and essays. 13th ed. Dover Publications, Dover books on mathematical and word recreations (1987) ISBN 0-486-25357-0.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
