Matrix-Chain Multiplication Problem using Genetic Algorithm
Main Article Content
Abstract
Tree encoding has been studied for the genetic algorithm on artificial intelligence such as sequence induction, automatic programming, machine learning, and pattern recognition [5]. This paper also presents the tree encoding for the genetic algorithm in solving the matrix-chain multiplication, which is in the form A1 A2 A3 … AN where Ai is a matrix. Tress are generated as the way the matrices are fully parenthesized. Then crossover and mutation are applied. The fitness value is calculated and stored at the root of the tree.
Keywords: tree encoding, matrix-chain multiplication, genetic algorithm
Corresponding author: E-mail: soonthar@cs.ucf.edu
Article Details
Copyright Transfer Statement
The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.
The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.
Here is the link for download: Copyright transfer form.pdf
References
[2] Chin, F.Y. 1978 An O(n) algorithm for determining a Near-Optimal Computation Order of Matrix Chain Products. Communications of the ACM, 21(7).
[3] Cormen, T.H., Leiserson, C.E., Rivest, R.L. 1989 Introduction to Algorithms. MIT Press. McGraw-Hill.
[4] Hu, T.C., and Shing, M.T. 1982 Computation of Matrix Chain Products Part I. SIAM J. computing, 11(2).
[5] Koza, J.R. 1989 Hierarchical Genetic Algorithms Operating on Populations of Computer Programs. International Joint Conference on Artificial Intelligence.