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

Mauricio Solar; Vicente Figueroa; Francisco Manriquez; Francisco Pizarro; Liuba Dombrovskaia

doi:10.36561/ING.27.14

Autores

Mauricio Solar Universidad Técnica Federico Santa María, Chile https://orcid.org/0000-0002-4433-4622
Vicente Figueroa Universidad Técnica Federico Santa María, Chile https://orcid.org/0009-0001-2391-8223
Francisco Manriquez Universidad Técnica Federico Santa María, Chile https://orcid.org/0009-0008-7045-4258
Francisco Pizarro Universidad Técnica Federico Santa María, Chile https://orcid.org/0009-0004-6317-6414
Liuba Dombrovskaia Universidad Técnica Federico Santa María, Chile https://orcid.org/0000-0001-6572-9765

DOI:

https://doi.org/10.36561/ING.27.14

Palavras-chave:

Algoritmo Genético Quântico, Computação Quântica, Algoritmo Genético Quântico Híbrido

Resumo

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.

Downloads

Não há dados estatísticos.

Referências

Lee Spector, Howard Barnum, Herbert J. Bernstein, Nikhil Swamy. “7: Quantum Computing Applications of Genetic Programming”. The MIT Press. 1999. https://doi.org/10.7551/mitpress/1110.003.0010

Mohammad Mojrian y Seyed Abolghasem Mirroshandel. “A novel extractive multi-document text summarization system using quantum-inspired genetic algorithm: MTSQIGA”. Expert Systems with Applications 171 (2021), pp. 114555. issn: 0957-4174. doi: https://doi.org/10.1016/j.eswa.2020. 114555. url: https://www.sciencedirect.com/science/article/pii/S0957417420311994.

Kuk-Hyun Han y Jong-Hwan Kim. “Genetic quantum algorithm and its application to combinatorial optimization problem”. Proc. of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512). 2 (2000), pp. 1354-1360, vol. 2. doi: 10.1109/CEC.2000.870809.

Andrea Malossini, Enrico Blanzieri y Tommaso Calarco. “Quantum Genetic Optimization”. IEEE Transactions on Evolutionary Computation 12.2 (2008), pp. 231-241. doi: 10.1109/TEVC.2007.905006.

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 Engineering (2013). doi: 10.1155/2013/730749.

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 y Sistemas 26 (2022), pp. 725-742. doi: 10.13053/CyS-26-2-4253.

Arufe L, González MA, Oddi A, Rasconi R, Varela R. “Quantum circuit compilation by genetic algorithm for quantum approximate optimization algorithm applied to MaxCut problem”. Swarm Evol Comput 69:101030. (2022) https://doi.org/10.1016/j.swevo.2022.101030

In‘es Hilali-Jaghdam et al. “Quantum and classical genetic algorithms for multilevel segmentation of medical images: A comparative study”. Computer Communications 162 (2020), pp. 83-93. doi: https://doi.org/10.1016/j.comcom.2020.08.010. url: https://www.sciencedirect.com/science/article/pii/S0140366420318892.

Lensen A, Xue B, Zhang M (2021). “Genetic programming for evolving a front of interpretable models for data visualization”. IEEE Trans Cybern 51(11):5468–5482. https://doi.org/10.1109/TCYB.2020.2970198

Zhaoyang Huang et al. “Optimal design of load frequency active disturbance rejection control via double-chains quantum genetic algorithm”. Neural Computing and Applications 33 (2021). doi: 10.1007/s00521-020-05199-6.

Durán, C., Carrasco, R., Soto, I. et al. “Quantum algorithms: applications, criteria and metrics. Complex”. Intell. Syst. 9, 6373–6392 (2023). https://doi.org/10.1007/s40747-023-01073-9

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 1237(2):22130. https://doi.org/10.1088/17426596/1237/2/022130

Xinjian Pan et al. “Self-calibration for linear structured light 3D measurement system based on quantum genetic algorithm and feature matching”. Optik 225

(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 of Building Engineering 35 (2021), pp. 102048. issn: 2352-7102. doi:https://doi.org/10.1016/j.jobe.2020.102048. url: https://www.sciencedirect.com/science/article/pii/S2352710220336809.

Jia-Chu Lee et al. “Quantum genetic algorithm for dynamic economic dispatch with valve-point effects and including wind power system”. Int. Journal of Electrical Power Energy Systems 33 (2011), pp. 189-197. doi: 10.1016/j.ijepes.2010.08.014.

Wang B, Zhao W, Lin S, Ke J, Wu H (2022). “Integrated energy management of highway service area based on improved multiobjective quantum genetic algorithm”. Dianwang Jishu/Power Syst Technol 46(5):1742–1751. https://doi.org/10.13335/j.1000-3673.pst.2021.1610

Junhe Wan et al. “Fractional-Order PID Motion Control for AUV Using Cloud-Model-Based Quantum Genetic Algorithm”. IEEE Access 7 (2019), pp. 124828-124843. doi: 10.1109/ACCESS.2019.2937978.

Zhu X, Xiong J, Liang Q (2018). “Fault diagnosis of rotation machinery based on support vector machine optimized by quantum genetic algorithm”. IEEE Access 6:33583–33588. https://doi.org/10.1109/ACCESS.2018.2789933

Guangfeng Cheng, Chunhua Wang y Cong Xu. “A novel hyper-chaotic image encryption scheme based on quantum genetic algorithm and compressive sensing”. Multimedia Tools and Applications 79 (2020). doi: 10.1007/s11042-020-09542-w.

Susan Stepney y John A Clark. “Evolving quantum programs and protocols”. Handbook of Theoretical and Computational Nanotechnology 3 (2006), pp. 113-160.

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 Theoretical Physics 59 (2020). doi: 10.1007/s10773-020-04409-0.

Rui Li et al. “Approximate Quantum Adders with Genetic Algorithms: An IBM Quantum Experience”. Quantum Measurements and Quantum Metrology 4 (2017), pp. 1. doi: 10.48550/arXiv.1611.07851.

B. I. P. Rubinstein, .Evolving quantum circuits using genetic programming,"Proc. of the 2001 Congress on Evolutionary Computation (IEEE Cat. No.01TH8546), Seoul, Korea (South), 2001, pp. 144-151 vol. 1, doi: 10.1109/CEC.2001.934383.

Riccardo Rasconi y Angelo Oddi. “An Innovative Genetic Algorithm for the Quantum Circuit Compilation Problem”. Proc. of the AAAI Conf. on Artificial Intelligence 33 (2019), pp. 77077714. doi: 10.1609/aaai.v33i01.33017707.

Zakaria Laboudi y Salim Chikhi. “Comparison of Genetic Algorithm and Quantum Genetic Algorithm”. Int. Arab Journal of Information Technology 9, (2012).

Akira SaiToh, Robabeh Rahimi y Mikio Nakahara. “A quantum genetic algorithm with quantum crossover and mutation operations”. Quantum Information Processing 13 (2014), pp. 737. doi: 10.1007/s11128-013-0686-6.

Jirayu Supasil, Poramet Pathumsoot y Sujin Suwanna. “Simulation of implementable quantumassisted genetic algorithm”. Journal of Physics: Conference Series 1719 (2021), pp. 012102. doi:

1088/1742-6596/1719/1/012102.

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 Genetic Algorithm”. arXiv:1907.00707, 2019.

Ruben Ibarrondo, Giancarlo Gatti, Mikel Sanz. “Quantum vs classical genetic algorithms: A numerical comparison shows faster convergence”. 2022 IEEE Symposium Series on Computational Intelligence (SSCI). http://dx.doi.org/10.1109/SSCI51031.2022.10022159, 10.1109/ssci51031.2022.10022159

Yu-Fang C, Hao X, Wen-Cong H, Liang Z (2018). “An improved multi-objective quantum genetic algorithm based on cellular automaton”. In: 2018 IEEE 9th Int. Conf. on Software Engineering and Service Sciences. IEEE, Beijing, pp 342–345. https://doi.org/10.1109/ICSESS.2018.8663840

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). https://doi.org/10.1038/s41598-023-37767-w