Simulated Annealing Meta-heuristic for Addition Chain Optimization



Abstract Views
290

Downloads
291

Citations

Share

##plugins.themes.bootstrap3.article.sidebar##

Submitted Dec 7, 2019
Published Dec 14, 2019
10.24018/ejece.2019.3.6.159

Abstract viewed = 290 times

Table of Contents

##plugins.themes.bootstrap3.article.main##

In this work, a simulated annealing (SA) algorithm is implemented in the Python programming language with the aim of minimizing addition chains of the "star-chain" type. The strategies for generating and mutating individuals are similar to those used by the evolutionary programming (EP) and genetic algorithms (GA) methods found in the literature [1]-[3]. The proposed variant is the acceptance mechanism that is based on the simulated annealing meta-heuristic (SA). The hypothesis is that with the proposed acceptance mechanism, diversity is obtained in the search-space through a simple strategy that allows finding better solutions compared to the deterministic method Optimized Window. The simulations were performed with exponents in the range 218-234 and were compared with the results reported in [3], where a GA is proposed to get optimal addition chains. It is concluded that the proposed algorithm is able to find chains of shorter length than those found with the Optimized Window method and with a performance similar to that of the GA proposed in [3].

Keywords: Addition chain, star-chain, simulated annealing, evolutionary programming, meta-heuristic

Downloads

Download data is not yet available.

References

  1. S. Dom?nguez-Isidro, E. Mezura-Montes, ?An evolutionary programming algorithm to find minimal addition chains,? presented at the I Congreso Internacional de Ingenier?a Electr?nica, Instrumentaci?n y Computaci?n, Minatitl?n Veracruz, M?xico; July, 2011.
     Google Scholar
  2. L.G. Osorio-Hern?ndez, E. Mezura-Montes, N. Cruz-Cort?s, and F. Rodr?guez-Henr?quez, ?A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents,? in 2009 IEEE Congr. on Evolutionary Computation, Trondheim, Norway, May, 2009, pp. 1422-1429.
     Google Scholar
  3. S. Picek, C.A.C. Coello, D. Jakobovic, and N. Mentens, ?Finding short and implementation-friendly addition chains with evolutionary algorithms,? J. of Heuristics, vol. 24, no.3, pp. 457-481, 2018.
     Google Scholar
  4. F. Herbaut, P. V?ron, ?A public key cryptosystem based upon euclidean addition chains,? in International Conf. on Sequences and their Applications: Springer, Berlin, Heidelberg; September 2010, pp. 284-297
     Google Scholar
  5. D.R. Stinson, Cryptography: theory and practice, 3d. ed. Ontario, Canada, Chapman and Hall/CRC, 2005, ch. 6, pp.260-274.
     Google Scholar
  6. N.M., Clift, ?Calculating optimal addition chains,? Computing, vol. 91, no. 3, pp. 265-284, 2011.
     Google Scholar
  7. H. DELLAC, ?Question 49,? L?Interm?diaire Math, vol. 1, no. 20, 1894.
     Google Scholar
  8. A. Scholz, ?Aufgabe 253,? in Jahresbericht der Deutschen Mathematikervereinigung, Teubner Leipzig, Berlin, 1937, vol. 47, pp. 41?42, Teil II.
     Google Scholar
  9. L.J. FOGEL, ?Artificial intelligence through a simulation of evolution,? presented at the Proc. of the 2nd Cybernetics Science Symp., 1965.
     Google Scholar
  10. D.B., FOGEL, L.J. FOGEL, J.W. ATMAR, ?Meta-evolutionary programming,? in Conference Record of the Twenty-Fifth Asilomar Conference on Signals, Systems & Computers IEEE, pp. 540-545, 1991.
     Google Scholar
  11. D.K. GEHLHAAR, et al, ?Molecular recognition of the inhibitor AG-1343 by HIV-1 protease: conformationally flexible docking by evolutionary programming,? Chemistry & biology, vol. 2, no 5, p. 317-324, 1995.
     Google Scholar
  12. S. Kirkpatrick, C.D. Gelatt, M.P.V., ?Optimization by simulated annealing,? Science, vol.220, no.4598, pp.671-680, 1983.
     Google Scholar
  13. M. Pogan?i?, Evolving minimal addition chain exponentiation, University of Zagreb-Faculty of Electrical Engineering and Computing. Zagreb, Croacia, 2014
     Google Scholar
  14. S.J. Rusell, P. Norvig, Inteligencia Artificial: un enfoque moderno, 2d. ed. Madrid, Espa?a, Pearson Education S.A., 2004, ch.4, pp. 107-151.
     Google Scholar
  15. A. Flammenkamp, Shortest addition chains [online], Available: http://wwwhome;s.uni-bielefeld.de/achim/addition_chain.html
     Google Scholar


Most read articles by the same author(s)