[pt] A superioridade de desempenho dos algoritmos quânticos, em alguns problemas
específicos, reside no uso direto de fenômenos da mecânica quântica para
realizar operações com dados em computadores quânticos. Esta característica fez
surgir uma nova abordagem, denominada Computação com Inspiração Quântica,
cujo objetivo é criar algoritmos clássicos (executados em computadores clássicos)
que tirem proveito de princípios da mecânica quântica para melhorar seu desempenho.
Neste sentido, alguns algoritmos evolutivos com inspiração quântica tem
sido propostos e aplicados com sucesso em problemas de otimização combinatória
e numérica, apresentando desempenho superior àquele dos algoritmos evolutivos
convencionais, quanto à melhoria da qualidade das soluções e à redução do número
de avaliações necessárias para alcançá-las. Até o presente momento, no entanto,
este novo paradigma de inspiração quântica ainda não havia sido aplicado à Programação
Genética (PG), uma classe de algoritmos evolutivos que visa à síntese automática
de programas de computador. Esta tese propõe, desenvolve e testa um novo
modelo de algoritmo evolutivo com inspiração quântica, denominado Programação
Genética Linear com Inspiração Quântica (PGLIQ), para a evolução de programas
em código de máquina. A Programação Genética Linear é assim denominada
porque cada um dos seus indivíduos é representado por uma lista de instruções (estruturas
lineares), as quais são executadas sequencialmente. As contribuições deste
trabalho são o estudo e a formulação inédita do uso do paradigma da inspiração
quântica na síntese evolutiva de programas de computador. Uma das motivações
para a opção pela evolução de programas em código de máquina é que esta é a
abordagem de PG que, por oferecer a maior velocidade de execução, viabiliza experimentos
em larga escala. O modelo proposto é inspirado em sistemas quânticos
multiníveis e utiliza o qudit como unidade básica de informação quântica, o qual
representa a superposição dos estados de um sistema deste tipo. O funcionamento
do modelo se baseia em indivíduos quânticos, que representam a superposição de
todos os programas do espaço de busca, cuja observação gera indivíduos clássicos
e os programas (soluções). Nos testes são utilizados problemas de regressão simbólica
e de classificação binária para se avaliar o desempenho da PGLIQ e compará-lo
com o do modelo AIMGP (Automatic Induction of Machine Code by Genetic Programming),
considerado atualmente o modelo de PG mais eficiente na evolução de
código de máquina, conforme citado em inúmeras referências bibliográficas na área.
Os resultados mostram que a Programação Genética Linear com Inspiração Quântica
(PGLIQ) apresenta desempenho geral superior nestas classes de problemas, ao
encontrar melhores soluções (menores erros) a partir de um número menor de avaliações,
com a vantagem adicional de utilizar um número menor de parâmetros e
operadores que o modelo de referência. Nos testes comparativos, o modelo mostra
desempenho médio superior ao do modelo de referência para todos os estudos
de caso, obtendo erros de 3 a 31% menores nos problemas de regressão simbólica,
e de 36 a 39% nos problemas de classificação binária. Esta pesquisa conclui que
o paradigma da inspiração quântica pode ser uma abordagem competitiva para se
evoluir programas eficientemente, encorajando o aprimoramento e a extensão do
modelo aqui apresentado, assim como a criação de outros modelos de programação
genética com inspiração quântica. / [en] The superior performance of quantum algorithms in some specific problems
lies in the direct use of quantum mechanics phenomena to perform operations with
data on quantum computers. This feature has originated a new approach, named
Quantum-Inspired Computing, whose goal is to create classic algorithms (running
on classical computers) that take advantage of quantum mechanics principles to
improve their performance. In this sense, some quantum-inspired evolutionary algorithms
have been proposed and successfully applied in combinatorial and numerical
optimization problems, presenting a superior performance to that of conventional
evolutionary algorithms, by improving the quality of solutions and reducing
the number of evaluations needed to achieve them. To date, however, this
new paradigm of quantum inspiration had not yet been applied to Genetic Programming
(GP), a class of evolutionary algorithms that aims the automatic synthesis
of computer programs. This thesis proposes, develops and tests a novel model of
quantum-inspired evolutionary algorithm named Quantum-Inspired Linear Genetic
Programming (QILGP) for the evolution of machine code programs. Linear Genetic
Programming is so named because each of its individuals is represented by a list of
instructions (linear structures), which are sequentially executed. The contributions
of this work are the study and formulation of the novel use of quantum inspiration
paradigm on evolutionary synthesis of computer programs. One of the motivations
for choosing by the evolution of machine code programs is because this is the GP
approach that, by offering the highest speed of execution, makes feasible large-scale
experiments. The proposed model is inspired on multi-level quantum systems and
uses the qudit as the basic unit of quantum information, which represents the superposition
of states of such a system. The model’s operation is based on quantum individuals,
which represent a superposition of all programs of the search space, whose
observation leads to classical individuals and programs (solutions). The tests use
symbolic regression and binary classification problems to evaluate the performance
of QILGP and compare it with the AIMGP model (Automatic Induction of Machine
Code by Genetic Programming), which is currently considered the most efficient GP
model to evolve machine code, as cited in numerous references in this field. The results
show that Quantum-Inspired Linear Genetic Programming (QILGP) presents
superior overall performance in these classes of problems, by achieving better solutions
(smallest error) from a smaller number of evaluations, with the additional
advantage of using a smaller number of parameters and operators that the reference model. In comparative tests, the model shows average performance higher than that
of the reference model for all case studies, achieving errors 3-31% lower in the
problems of symbolic regression, and 36-39% in the binary classification problems.
This research concludes that the quantum inspiration paradigm can be a competitive
approach to efficiently evolve programs, encouraging the improvement and
extension of the model presented here, as well as the creation of other models of
quantum-inspired genetic programming.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:17544 |
| Date | 26 May 2011 |
| Creators | DOUGLAS MOTA DIAS |
| Contributors | MARCO AURELIO CAVALCANTI PACHECO, MARCO AURELIO CAVALCANTI PACHECO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0022 seconds