A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents

Luis G. Osorio-Hernández; Efrén Mezura-Montes; Nareli Cruz-Cortés; Francisco Rodríguez-Henríquez

doi:10.1109/CEC.2009.4983110

A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents

Luis G. Osorio-Hernández, Efrén Mezura-Montes, Nareli Cruz-Cortés, Francisco Rodríguez-Henríquez

Centro de Investigación en Computación (CIC)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

21 Scopus citations

Abstract

In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of "hard" exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.

Original language	English
Title of host publication	2009 IEEE Congress on Evolutionary Computation, CEC 2009
Pages	1422-1429
Number of pages	8
DOIs	https://doi.org/10.1109/CEC.2009.4983110
State	Published - 2009
Event	2009 IEEE Congress on Evolutionary Computation, CEC 2009 - Trondheim, Norway Duration: 18 May 2009 → 21 May 2009

Publication series

Name	2009 IEEE Congress on Evolutionary Computation, CEC 2009

Conference

Conference	2009 IEEE Congress on Evolutionary Computation, CEC 2009
Country/Territory	Norway
City	Trondheim
Period	18/05/09 → 21/05/09

Access to Document

10.1109/CEC.2009.4983110

Cite this

Osorio-Hernández, L. G., Mezura-Montes, E., Cruz-Cortés, N., & Rodríguez-Henríquez, F. (2009). A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents. In 2009 IEEE Congress on Evolutionary Computation, CEC 2009 (pp. 1422-1429). Article 4983110 (2009 IEEE Congress on Evolutionary Computation, CEC 2009). https://doi.org/10.1109/CEC.2009.4983110

@inproceedings{062f6555ec164f82a57ccddabe6ca7e8,

title = "A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents",

abstract = "In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of {"}hard{"} exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.",

author = "Osorio-Hern{\'a}ndez, {Luis G.} and Efr{\'e}n Mezura-Montes and Nareli Cruz-Cort{\'e}s and Francisco Rodr{\'i}guez-Henr{\'i}quez",

year = "2009",

doi = "10.1109/CEC.2009.4983110",

language = "Ingl{\'e}s",

isbn = "9781424429592",

series = "2009 IEEE Congress on Evolutionary Computation, CEC 2009",

pages = "1422--1429",

booktitle = "2009 IEEE Congress on Evolutionary Computation, CEC 2009",

note = "2009 IEEE Congress on Evolutionary Computation, CEC 2009 ; Conference date: 18-05-2009 Through 21-05-2009",

}

Osorio-Hernández, LG, Mezura-Montes, E, Cruz-Cortés, N & Rodríguez-Henríquez, F 2009, A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents. in 2009 IEEE Congress on Evolutionary Computation, CEC 2009., 4983110, 2009 IEEE Congress on Evolutionary Computation, CEC 2009, pp. 1422-1429, 2009 IEEE Congress on Evolutionary Computation, CEC 2009, Trondheim, Norway, 18/05/09. https://doi.org/10.1109/CEC.2009.4983110

A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents. / Osorio-Hernández, Luis G.; Mezura-Montes, Efrén; Cruz-Cortés, Nareli et al.
2009 IEEE Congress on Evolutionary Computation, CEC 2009. 2009. p. 1422-1429 4983110 (2009 IEEE Congress on Evolutionary Computation, CEC 2009).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents

AU - Osorio-Hernández, Luis G.

AU - Mezura-Montes, Efrén

AU - Cruz-Cortés, Nareli

AU - Rodríguez-Henríquez, Francisco

PY - 2009

Y1 - 2009

N2 - In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of "hard" exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.

AB - In this paper, we present an improved Genetic Algorithm (GA) that is able to find the shortest addition chains for a given exponent e. Two new variation operators (special two-point crossover and a local-search-like mutation) are proposed as a means to improve the GA search capabilities. Furthermore, the usage of an improved repair mechanism is applied to the process of generating the initial population of the algorithm. The proposed approach is compared on a set of test problems with two state-of-the-art evolutionary heuristic-based approaches recently published. Finally, the modified GA is used to find the optimal addition chain length for a small collection of "hard" exponents. The results obtained are competitive and even better in the more difficult instances of the exponentiation problem that were considered here.

UR - http://www.scopus.com/inward/record.url?scp=70450157409&partnerID=8YFLogxK

U2 - 10.1109/CEC.2009.4983110

DO - 10.1109/CEC.2009.4983110

M3 - Contribución a la conferencia

AN - SCOPUS:70450157409

SN - 9781424429592

T3 - 2009 IEEE Congress on Evolutionary Computation, CEC 2009

SP - 1422

EP - 1429

BT - 2009 IEEE Congress on Evolutionary Computation, CEC 2009

T2 - 2009 IEEE Congress on Evolutionary Computation, CEC 2009

Y2 - 18 May 2009 through 21 May 2009

ER -

Osorio-Hernández LG, Mezura-Montes E, Cruz-Cortés N, Rodríguez-Henríquez F. A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents. In 2009 IEEE Congress on Evolutionary Computation, CEC 2009. 2009. p. 1422-1429. 4983110. (2009 IEEE Congress on Evolutionary Computation, CEC 2009). doi: 10.1109/CEC.2009.4983110

A genetic algorithm with repair and local search mechanisms able to find minimal length addition chains for small exponents

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this