Three-Dimensional Genetic Algorithm for the Kirkman's Schoolgirl Problem

  • Jan Merta
  • Tomas Brandejsky
Keywords: multidimensional genetic algorithms, three-dimensional genetic algorithm, multidimensional chromosome, 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.

Published
2018-06-01
How to Cite
[1]
Merta, J. and Brandejsky, T. 2018. Three-Dimensional Genetic Algorithm for the Kirkman’s Schoolgirl Problem. MENDEL. 24, 1 (Jun. 2018), 25-30. DOI:https://doi.org/10.13164/mendel.2018.1.025.
Section
Research articles