Ir al contenido

Documat

Implementación Cuántica de un Algoritmo Genético

  • Solar, Mauricio [1] ; Figueroa, Vicente [1] ; Manriquez, Francisco [1] ; Pizarro, Francisco [1] ; Dombrovskaia, Liuba [1]
    1. [1] Universidad Técnica Federico Santa María

      Universidad Técnica Federico Santa María

      Valparaíso, Chile

  • Localización: Memoria Investigaciones en Ingeniería, ISSN 2301-1092, ISSN-e 2301-1106, Nº. 27, 2024, págs. 220-237
  • Idioma: español
  • DOI: 10.36561/ING.27.14
  • Títulos paralelos:
    • Implementação quântica de um algoritmo genético
    • Quantum Implementation of a Genetic Algorithm
  • Enlaces
  • Resumen
    • español

      Este trabajo proporciona una visión generalizada del estado actual de los algoritmos genéticos cuánticos (QGAs), mostrando los avances realizados en esta área de investigación los últimos 24 años. Los QGAs combinan conceptos de la computación cuántica y los algoritmos genéticos clásicos (CGAs), lo que les permite abordar problemas complejos de optimización y búsqueda de manera eficiente. Se presentan los principales hallazgos y contribuciones de estos algoritmos cuánticos destacando las tendencias y los enfoques más prometedores, así como los desafíos y limitaciones que deben superarse. Se presentan nuevos enfoques y técnicas de implementación de QGAs, incluyendo operadores genéticos cuánticos y esquemas de codificación eficientes que contribuyen a mejorar el rendimiento y la convergencia de los algoritmos. Se comparan los QGAs y otros enfoques similares, como los CGAs y los algoritmos cuánticos puros, destacando las ventajas y desventajas relativas de los QGAs en comparación a sus versiones clásicas. Se muestra también una implementación de QGA utilizando la biblioteca Qiskit. Se presentan la selección de los métodos usados para la generación de la población inicial, el cruzamiento y la mutación de las distintas poblaciones de los circuitos cuánticos simulados en los experimentos realizados, ejemplificando las ventajas significativas que estos pueden traer en comparación con los enfoques clásicos.

    • English

      This work provides a generalized view of the current state of quantum genetic algorithms (QGAs), showing the advances made in this research field over the last 24 years. QGAs combine concepts from quantum computing and classical genetic algorithms (CGAs), allowing them to address complex search and optimization problems efficiently. The main findings and contributions of these quantum algorithms are presented, highlighting the most promising trends and approaches, as well as the challenges and limitations that need to be overcome. New approaches and implementation techniques for QGAs are presented, including quantum genetic operators and efficient coding schemes that contribute to improving the performance and convergence of the algorithms. QGAs and other similar approaches, such as CGAs and pure quantum algorithms, are compared, highlighting the relative advantages and disadvantages of QGAs compared to their classical versions. An implementation of QGA using the Qiskit library is also shown. The selection of the methods used for the generation of the initial population, the crossing and the mutation of the different populations of the quantum circuits simulated in the experiments carried out are presented, exemplifying the significant advantages that these can bring in comparison with classical approaches.

    • português

      Este trabalho fornece uma visão generalizada do estado atual dos algoritmos genéticos quânticos (QGAs), mostrando os avanços feitos neste campo de pesquisa nos últimos 24 anos. Os QGAs combinam conceitos da computação quântica e algoritmos genéticos clássicos (CGAs), permitindo que eles abordem problemas complexos de busca e otimização de forma eficiente. As principais descobertas e contribuições desses algoritmos quânticos são apresentadas, destacando as tendências e abordagens mais promissoras, bem como os desafios e limitações que precisam ser superados. Novas abordagens e técnicas de implementação para QGAs são apresentadas, incluindo operadores genéticos quânticos e esquemas de codificação eficientes que contribuem para melhorar o desempenho e a convergência dos algoritmos. QGAs e outras abordagens semelhantes, como CGAs e algoritmos quânticos puros, são comparados, destacando as vantagens e desvantagens relativas dos QGAs em comparação com suas versões clássicas. Uma implementação de QGA usando a biblioteca Qiskit também é mostrada. São apresentadas a seleção dos métodos utilizados para a geração da população inicial, o cruzamento e a mutação das diferentes populações dos circuitos quânticos simulados nos experimentos realizados, exemplificando as vantagens significativas que estes podem trazer em comparação com abordagens clássicas.

  • Referencias bibliográficas
    • Lee Spector, Howard Barnum, Herbert J. Bernstein, Nikhil Swamy. “7: Quantum Computing Applications of Genetic Programming”. The MIT Press....
    • Mohammad Mojrian y Seyed Abolghasem Mirroshandel. “A novel extractive multi-document text summarization system using quantum-inspired genetic...
    • Kuk-Hyun Han y Jong-Hwan Kim. “Genetic quantum algorithm and its application to combinatorial optimization problem”. Proc. of the 2000 Congress...
    • Andrea Malossini, Enrico Blanzieri y Tommaso Calarco. “Quantum Genetic Optimization”. IEEE Transactions on Evolutionary Computation 12.2 (2008),...
    • Y. Hardy y W.-H Steeb. “Genetic Algorithms and Optimization Problems in Quantum
    • Computing”. Int. Journal of Modern Physics C -IJMPC 21 (2010), pp. 1359-1375. doi: 10.1142/S0129183110015890.
    • Huaixiao Wang et al. “The Improvement of Quantum Genetic Algorithm and Its Application on Function Optimization”. Mathematical Problems in...
    • Hatem M. H. Saad et al. “Quantum-Inspired Genetic Algorithm for Resource-
    • Constrained Project-Scheduling”. IEEE Access 9 (2021), pp. 38488-38502. doi: 10.1109/ACCESS.2021.3062790.
    • Enrique Ballinas y Oscar Montiel Ross. “Hybrid Quantum Genetic Algorithm for the 0-1 Knapsack Problem in the IBM Qiskit Simulator”. Computacion...
    • Arufe L, González MA, Oddi A, Rasconi R, Varela R. “Quantum circuit compilation by genetic algorithm for quantum approximate optimization...
    • In‘es Hilali-Jaghdam et al. “Quantum and classical genetic algorithms for multilevel segmentation of medical images: A comparative study”....
    • Lensen A, Xue B, Zhang M (2021). “Genetic programming for evolving a front of interpretable models for data visualization”. IEEE Trans Cybern...
    • Zhaoyang Huang et al. “Optimal design of load frequency active disturbance rejection control via double-chains quantum genetic algorithm”....
    • Durán, C., Carrasco, R., Soto, I. et al. “Quantum algorithms: applications, criteria and metrics. Complex”. Intell. Syst. 9, 6373–6392 (2023)....
    • Qian X, Wang S, Li C, Wang G (2019). “Multi channels data fusion algorithm on quantum genetic algorithm for sealed relays”. J Phys Conf Ser...
    • Xinjian Pan et al. “Self-calibration for linear structured light 3D measurement system based on quantum genetic algorithm and feature matching”....
    • (2021), pp. 165749. issn: 0030-4026. doi: https://doi.org/10.1016/j.ijleo.2020.165749. url: https://www.sciencedirect.com/science/article/pii/S003040262031576X.
    • Yuxing Wang y Chunyu Wei. “Design optimization of office building envelope based on quantum genetic algorithm for energy conservation”. Journal...
    • Jia-Chu Lee et al. “Quantum genetic algorithm for dynamic economic dispatch with valve-point effects and including wind power system”. Int....
    • Wang B, Zhao W, Lin S, Ke J, Wu H (2022). “Integrated energy management of highway service area based on improved multiobjective quantum genetic...
    • Junhe Wan et al. “Fractional-Order PID Motion Control for AUV Using Cloud-Model-Based Quantum Genetic Algorithm”. IEEE Access 7 (2019), pp....
    • Zhu X, Xiong J, Liang Q (2018). “Fault diagnosis of rotation machinery based on support vector machine optimized by quantum genetic algorithm”....
    • Guangfeng Cheng, Chunhua Wang y Cong Xu. “A novel hyper-chaotic image encryption scheme based on quantum genetic algorithm and compressive...
    • Susan Stepney y John A Clark. “Evolving quantum programs and protocols”. Handbook of Theoretical and Computational Nanotechnology 3 (2006),...
    • R. Lahoz-Beltra. “Quantum Genetic Algorithms for Computer Scientists”. Computers 5 (2016), pp. 24. doi: 10.3390/computers5040024.
    • Mahboobeh Houshmand et al. “An Evolutionary Approach to Optimizing Teleportation Cost in Distributed Quantum Computation”. Int. Journal of...
    • Rui Li et al. “Approximate Quantum Adders with Genetic Algorithms: An IBM Quantum Experience”. Quantum Measurements and Quantum Metrology...
    • B. I. P. Rubinstein, .Evolving quantum circuits using genetic programming,"Proc. of the 2001 Congress on Evolutionary Computation (IEEE...
    • Riccardo Rasconi y Angelo Oddi. “An Innovative Genetic Algorithm for the Quantum Circuit Compilation Problem”. Proc. of the AAAI Conf. on...
    • Zakaria Laboudi y Salim Chikhi. “Comparison of Genetic Algorithm and Quantum Genetic Algorithm”. Int. Arab Journal of Information Technology...
    • Akira SaiToh, Robabeh Rahimi y Mikio Nakahara. “A quantum genetic algorithm with quantum crossover and mutation operations”. Quantum Information...
    • Jirayu Supasil, Poramet Pathumsoot y Sujin Suwanna. “Simulation of implementable quantumassisted genetic algorithm”. Journal of Physics: Conference...
    • Bart Rylander, Terence Soule, James A. Foster, Jim Alves-Foss. “Quantum Genetic Algorithms.”
    • Proc. of the Genetic and Evolutionary Computation Conference (GECCO ’00), Las Vegas, Nevada, USA, July 8-12, 2000
    • James King, Masoud Mohseni, William Bernoudy, Alexandre Fréchette, Hossein Sadeghi, Sergei V. Isakov, Hartmut Neven, Mohammad H. Amin. “Quantum-Assisted...
    • Ruben Ibarrondo, Giancarlo Gatti, Mikel Sanz. “Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence”....
    • Yu-Fang C, Hao X, Wen-Cong H, Liang Z (2018). “An improved multi-objective quantum genetic algorithm based on cellular automaton”. In: 2018...
    • Creevey, F.M., Hill, C.D. Hollenberg, L.C.L. “GASP: a genetic algorithm for state preparation on quantum computers”. Sci Rep 13, 11956 (2023)....
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno