An Optimization Algorithm Based on Dynamic Schema with Dissimilarities and Similarities of Chromosomes

Authors: Radhwan Yousif Sedik Al-Jawadi

Abstract:

Optimization is necessary for finding appropriate solutions to a range of real-life problems. In particular, genetic (or more generally, evolutionary) algorithms have proved very useful in solving many problems for which analytical solutions are not available. In this paper, we present an optimization algorithm called Dynamic Schema with Dissimilarity and Similarity of Chromosomes (DSDSC) which is a variant of the classical genetic algorithm. This approach constructs new chromosomes from a schema and pairs of existing ones by exploring their dissimilarities and similarities. To show the effectiveness of the algorithm, it is tested and compared with the classical GA, on 15 two-dimensional optimization problems taken from literature. We have found that, in most cases, our method is better than the classical genetic algorithm.

Keywords: Genetic algorithm, similarity and dissimilarity, chromosome injection, dynamic schema.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1126041

References:

[1] K. Manda, S. C. Satapathy, and B. Poornasatyanarayana, “Population based meta-heuristic techniques for solving optimization problems : A selective survey, International Journal of Emerging Technology and Advanced Engineering IJETAE”, vol. 2, no. 11, 2012.
[2] Y. Yu and Z. H. Zhou, “A new approach to estimating the expected first hitting time of evolutionary algorithms”, Artif. Intell., vol. 172, no. 15, pp. 1809–1832, 2008.
[3] X. Han, Y. Liang, Z. Li, G. Li, X. Wu, B. Wang, G. Zhao, and C. Wu, “An Efficient Genetic Algorithm for Optimization Problems with Time-Consuming Fitness Evaluation”, Int. J. Comput. Methods, vol. 12, no. 01, p. 1350106, 2015.
[4] Michalewicz Z., “Genetic Algorithms + Data Structures = Evolution Programs (3ed).PDF.” Springer, Berlin
[5] R. Mahmod, “Maintaining diversity for genetic algorithm: a case of timetabling problem”, Jurnal Teknologi (Universiti Teknologi Malaysia) vol. 44, no. D, pp. 123–130, 2007.
[6] Deb K., “Multi-Objective Optimization Using Evolutionary Algorithms”, F. Edition, Chichester, U.K.: Wiley, 2001.
[7] A. S. Eesa, A. Mohsin, A. Brifcani, and Z. Orman, “A New Tool for Global Optimization Problems - Cuttlefish Algorithm”, International Journal of Mathematical, Computational, Natural and Physical Engineering, vol. 8, no. 9, pp. 1203–1207, 2014.
[8] A. Ritthipakdee, A. Thammano, N. Premasathian, and B. Uyyanonvara, “An Improved Firefly Algorithm for Optimization Problems”, ADCONP, Hiroshima, no. 2, pp.159-164, 2014
[9] J. Town, E. Sciences, and A. K. B. Road, “A Novel Function Optimization Approach Using Opposition Based Genetic Algorithm with Gene Excitation”, International Journal of Innovative Computing, Information and Control, vol. 7, no. 7, pp. 4263–4276, 2011.
[10] J. B. Odili, M. Nizam, and M. Kahar, “Numerical Function Optimization Solutions Using the African Buffalo Optimization Algorithm ( ABO )”, British Journal of Mathematics & Computer Science, vol. 10, no. 1, pp. 1–12, 2015.
[11] G. Mitsuo, Invited Talk: Network Models and Optimization : moGA Network Models and Optimization , Graduate School of Information, Production and Systems, WASEDA University, March, 2009.
[12] E. O. Scott and K. A. De Jong, “Understanding Simple Asynchronous Evolutionary Algorithms”, In: FOGA '15 Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, pp. 85-98.