ALGORITMOS EVOLUCIONÁRIOS COM INSPIRAÇÃO EM COMPUTAÇÃO QUÂNTICA E SUA APLICAÇÃO EM PROBLEMAS DE OTIMIZAÇÃO NUMÉRICA

ALGORITMOS EVOLUCIONÁRIOS COM INSPIRAÇÃO EM COMPUTAÇÃO QUÂNTICA E SUA APLICAÇÃO EM PROBLEMAS DE OTIMIZAÇÃO NUMÉRICA ANDRÉ V. A. DA CRUZ1, CARLOS R. HALL BARBOSA1, MARCO AURÉLIO C. PACHECO1, MARLEY VELLASCO1,2 1

ICA – Laboratório de Inteligência Computacional Aplicada, Departamento de Engenharia Elétrica Pontifícia Universidade Católica do Rio de Janeiro Rua Marquês de São Vicente, 225, Rio de Janeiro – 22453-900 – RJ - Brasil 2 Department of Computer Science, University College London Gower Street – London – UK E-mails: {andrev, marco, marley, hall}@ele.puc-rio.br

Abstract⎯ This work proposes a new kind of evolutionary algorithm inspired in the principles of quantum computing. This algorithm is an extension of a proposed model for combinatorial optimization problems which uses a binary representation for the chromosome. This extension uses probability distributions for each free variable of the problem, in order to simulate the superposition of solutions, which is intrinsic in the quantum computing methodology. A set of mathematical operations is used as implicit genetic operators over those probability distributions. The efficiency and the applicability of the algorithm are demonstrated through experimental results for the F6 function. Keywords⎯ Quantum computing, evolutionary algorithms, optimization Resumo⎯ Este trabalho propõe um novo tipo de algoritmo evolucionário inspirado nos princípios da computação quântica. Este algoritmo é uma extensão de um modelo proposto para problemas de otimização combinatorial onde se usa uma representação binária para o cromossoma. Esta extensão utiliza distribuições de probabilidade para cada uma das variáveis livres do problema, de modo a simular a superposição de possíveis soluções, o que é uma característica intrínseca da computação quântica. Um conjunto de operações matemáticas é utilizado implicitamente como operadores genéticos sobre essas distribuições de probabilidade. A eficiência e a aplicabilidade do algoritmo são demonstradas através de resultados experimentais para a otimização da função F6. Palavras-chave⎯Computação quântica, algoritmos evolucionários, otimização

1

Introdução

Muitos esforços de pesquisa na área de computação quântica têm sido feitos desde 1990, após ter sido demonstrado que computadores baseados nos princípios da mecânica quântica podem oferecer maior poder de processamento para algumas classes de problemas. Graças ao princípio da superposição, no qual uma partícula pode assumir dois estados simultaneamente, os computadores quânticos podem oferecer um alto grau de paralelismo no processamento. Sua superioridade foi demonstrada através de alguns algoritmos como o algoritmo de Shor (Shor 1994) para fatoração de números e o algoritmo de Grover (Grover, 1996) para busca em bancos de dados. O algoritmo de Shor encontra os fatores primos de um número com n dígitos em tempo polinomial enquanto que o melhor algoritmo clássico de fatoração conhecido tem uma

que, motivado pela ausência de algoritmos quânticos, se concentra em desenvolver novos algoritmos desse tipo usando técnicas de geração automática de programas (Spector et al., 1999) (como, por exemplo, programação genética) e um outro grupo que se concentra em desenvolver algoritmos evolucionários inspirados em computação quântica (Narayanan and Moore, 1996, Han and Kim, 2000, Han and Kim 2002). Neste caso, no qual se inclui este trabalho, existe apenas uma inspiração na computação quântica e os algoritmos são executados em computadores convencionais. Este trabalho é organizado da seguinte forma: a seção 2 descreve o algoritmo evolucionário com inspiração quântica. A seção 3 descreve os experimentos realizados. A seção 4 descreve os resultados e mostra uma análise dos mesmos. Finalmente, a seção 5 encerra o artigo com conclusões a respeito do trabalho.

1/ 3

complexidade de O(2 n log(n) 2 / 3 ) . Já o algoritmo de Grover busca um item em uma base de dados não

ordenada com n itens em O( n ) enquanto que o melhor algoritmo clássico tem uma complexidade de O(n) .

Pesquisas para a fusão de algoritmos evolucionários com a computação quântica têm sido feitas desde o final da década de 90. Essas pesquisas podem ser classificadas em dois grupos: o primeiro

2 Algoritmo Evolucionário com Inspiração Quântica

Os algoritmos evolucionários com inspiração quântica são baseados nos conceitos de bits quânticos, ou “qubits”, e na superposição de estados da mecânica quântica (Han and Kim, 2000; Han and Kim, 2002). A superposição de estados dos bits quânticos faz com que um determinado bit possa

assumir o valor 0 e 1 simultaneamente até ser observado (medido). No momento em que uma observação é feita o estado colapsa (ou converge) para um dos possíveis estados (0 ou 1 no caso dos qubits) O estado de um bit quântico pode ser representado pela equação 1 ϕ =α 0 +β 1

(1)

onde α e β são números complexos que especificam as amplitudes de probabilidade dos estados correspondentes. |α|2 dá a probabilidade do qubit estar no estado 0 quando observado e |β|2, por sua vez, dá a probabilidade do qubit estar no estado 1 quando observado. A normalização das amplitudes garante que: 2

α +β

2

=1.

(2)

O algoritmo evolucionário com representação binária (Han and Kim, 2000; Han and Kim, 2002) funciona bem somente quando esta representação é a mais adequada para o problema específico. No entanto, em alguns casos, a representação por números reais é mais eficiente (no caso de otimização de funções, por exemplo, onde se deseja encontrar um valor máximo, ou mínimo, a partir dos ajustes das variáveis). Mas como implementar essa representação usando-se o paradigma da inspiração quântica ? Para se responder essa questão é necessário responder outras duas questões: • Como representar a superposição de estados, dado que neste tipo de problema os genes podem assumir valores em um intervalo contínuo entre os limites das variáveis ? • Como atualizar estes valores de modo a levar o algoritmo a convergir para um valor ótimo ou sub-ótimo ? Para a primeira questão a resposta é simples: ao invés de se usar as probabilidades de observação de um estado, define-se uma distribuição de probabilidades para cada variável que permita sortear facilmente valores no universo de discurso da variável. Neste trabalho, para evitar um crescimento exponencial do armazenamento de informações, e para reduzir o custo computacional, optou-se por usar um conjunto de pulsos retangulares para se representar estas distribuições. Desta forma, há duas grandes vantagens: somente é necessário armazenar o centro e a largura de cada pulso nos genes do cromossoma; e simplifica-se o cálculo das funções de distribuição cumulativa de probabilidades, que são necessárias para o sorteio dos números aleatórios.. O procedimento para inicializar o algoritmo começa então com uma definição de um valor N que indica quantos pulsos serão usados para representar a

distribuição de probabilidade para cada uma das variáveis. Estes N pulsos estarão associados a um gene do cromossoma (e portanto, um cromossoma com G genes terá G.N pulsos associados à ele). Feito isto, para cada pulso usado em cada variável do problema, define-se: • Seu centro como o ponto médio do domínio; • Altura igual ao inverso do tamanho do domínio dividido por N. Estes valores são exatamente os valores que determinam um pulso e são armazenados nos genes ao qual o pulso está associado. Ao final deste processo , a soma dos N pulsos de cada uma das variáveis terá área total igual a 1. Supondo, por exemplo, que se deseje inicializar uma variável com universo de discurso em [-50,50] e utilizar 4 pulsos retangulares para representar a distribuição de probabilidade para esta variável, cada pulso teria largura igual a 100 e altura igual a 1/100/4 = 0,0025. Com a superposição, a forma gráfica desta distribuição ficaria, após a inicialização, de acordo com a figura 1.

Figura 1 – Gráfico com a superposição de 4 pulsos retangulares, cada um com largura 100 e altura 0,0025, representando a distribuição de probabilidade para uma variável

Esta curva representa portanto a superposição de todos os estados possíveis para a variável em questão. Este conjunto de pulsos associados a cada uma das variáveis (genes) do problema forma uma superposição Qi(t) para cada uma das i variáveis do problema. Por exemplo, supondo um cromossomo com dois genes e 4 pulsos em cada gene (N=4) vai conter os valores mostrados na tabela 1. Tabela 1 – Configuração de um cromossoma com dois genes

Variável (Gene) 1 Pulso 1(Centro1,Altura1) Pulso 2(Centro2,Altura2) Pulso 3(Centro3,Altura3) Pulso 4(Centro4,Altura4) Q1(f)

Variável (Gene) 2 Pulso 1(Centro1,Altura1) Pulso 2(Centro2,Altura2) Pulso 3(Centro3,Altura3) Pulso 4(Centro4,Altura4) Q2(f)

A partir desta distribuição Qi(t) sorteia-se um conjunto de n pontos que formam a população P(t). É importante notar que, quando a soma dos pulsos que forma a distribuição Qi(f) tem como resultado um pulso quadrado, os genes dos indivíduos sorteados terão valores espalhados por todo o domínio da variável que eles representam. Quando essa soma assume outras formas (por exemplo uma Gaussiana), a tendência é que a maior parte dos indivíduos assuma valores próximos do ponto do domínio com maior probabilidade de acordo com essas curvas. Após o sorteio dos indivíduos que vão formar a população P(t) é necessário atualizar a distribuição de probabilidade Qi(t) de modo a obter a convergência para a solução ótima ou sub-ótima de maneira similar ao crossover convencional dos algoritmos genéticos. O método utilizado consiste em sortear um número m de indivíduos da população P(t) usando um processo de roleta idêntico ao dos algoritmos genéticos convencionais e, em seguida, redefinir o ponto central do primeiro pulso como o valor médio desses m indivíduos sorteados. Este processo é repetido para cada um dos N pulsos que definem a distribuição Qi(t). O valor m é dado por:

m=

n N

(3)

Além disso, em cada geração, a largura dos pulsos é reduzida de forma simétrica em relação a seus centros. Esta redução é feita de forma exponencial, de acordo com a equação 4.

σ = (u − l )

⎛ t ⎞ ⎜ 1− ⎟ ⎝ T⎠

número aleatório aos mesmos. Isso é feito para evitar que os pulsos fiquem prematuramente presos em mínimos (máximos) locais.

Figura 2 – Forma da superposição de 2 pulsos de distribuição de probabilidade após algumas gerações do algoritmo.

3

Experimentos

Para avaliar o desempenho do algoritmo foi utilizado o problema de otimização da função F6. Esta função é uma função difícil de otimizar devido à presença de diversos máximos locais muito próximos uns dos outros. A equação 5 define esta função. 2

⎛ sen x 2 + y 2 ⎞ − 0,5 ⎜ ⎟ (5) ⎠ F 6( x, y ) = 0,5 − ⎝ 2 1,0 + 0,001 x 2 + y 2

(

(

))

λ

−1

(4)

Onde σ é a largura do pulso, u é o limite superior do domínio da variável, l é o limite inferior, t é a geração corrente do algoritmo, T é o total de gerações e λ é um parâmetro que define a velocidade de decaimento da largura do pulso. É importante notar que, à medida que os pulsos têm suas larguras diminuídas e a posição de seus pontos centrais modificados, a soma deles deixa de ser um pulso e começa a assumir as mais diversas formas. Um exemplo de uma forma que a soma dos pulsos pode assumir é mostrado na figura 2. Neste exemplo, tem-se a soma de 2 pulsos: o primeiro no intervalo [-50,50], com altura 0,005, e o segundo no intervalo [0,50] com altura 0,01. Além do algoritmo intrinsecamente recombinar as soluções existentes (fazendo a soma dos pulsos e usando esses pulsos como distribuições de probabilidade para sorteios posteriores de novos indivíduos), um operador similar à mutação dos algoritmos genéticos convencionais foi implementado. Este operador provoca uma pequena perturbação nos centros dos pulsos somando um

O máximo global desta função fica no ponto (0,0) e o gráfico desta função ao redor deste ponto é mostrado na figura 3:

Figura 3 – Gráfico da função F6 próxima ao máximo global.

Para fins de comparação aplicou-se um algoritmo genético convencional para otimizar esta função, com a configuração mostrada na Tabela 2. Para o algoritmo evolucionário com inspiração quântica utilizou-se os parâmetros da tabela 3.

Tabela 2 – Parâmetros de configuração do algoritmo genético convencional usando representação por números reais

1

8% 0.95

80% Avaliação

Taxa de mutação Taxa de crossover Gap Tamanho da População Número de Gerações Total de Avaliações Operadores Genéticos Domínio Método de Seleção

20% 100 40

0.85 0.8

4000

0.75

Crossover aritmético, mutação uniforme e mutação creep x, y ∈ [− 100,100]

Roleta com Steady-State

Tabela 3 – Parâmetros de configuração do algoritmo com inspiração quântica

Taxa de mutação Número de Pulsos por Variável (N) Taxa de Decaimento da Largura dos Pulsos ( λ ) Número de Observações (n) Número de Gerações (T) Total de Avaliações

0.9

2% 4 1 100 40 4000

Estes valores foram obtidos após a realização sistemática de diversos experimentos, tendo sido selecionados os melhores parâmetros. Para esta experiência foram executadas 20 rodadas e a média da avaliação destas rodadas foi calculada. 4 Resultados

Os resultados obtidos através de experimentos realizados usando um domínio para as variáveis x e y entre [-100,100] são mostrados no gráfico na figura 4. Este gráfico mostra que o algoritmo evolucionário com inspiração quântica apresenta um melhor desempenho em relação ao tempo para se aproximar da melhor solução. O algoritmo com inspiração quântica se aproxima mais rapidamente das boas soluções do que o algoritmo genético convencional. Além disso, o resultado final é um pouco melhor em termos de avaliação. É também possível observar nos gráficos da figura 5 a curva de distribuição de probabilidade e quais os indivíduos sorteados a partir dessas curvas nas gerações 1, 20 e 40 respectivamente. Estes gráficos permitem visualizar o comportamento das distribuições de probabilidade, mostrando que elas convergem na direção de um ponto ótimo ou subótimo.

0

5

10

15

20 25 Geração

30

35

40

Figura 4 – Comparativo da avaliação do algoritmo genético convencional com o algoritmo com inspiração quântica. A linha cheia mostra o desempenho do algoritmo com inspiração quântica e a linha tracejada mostra o desempenho do algoritmo genético tradicional

Aumentando o domínio das variáveis x e y para [-10000,10000] o gráfico toma a forma mostrada na figura 6: Pode-se notar que, ao contrário do algoritmo genético convencional, o algoritmo com inspiração quântica não sofreu uma perda significativa de desempenho com o aumento do domínio. Isso mostra que o algoritmo pode vir a ser um método robusto para tratar problemas onde o tamanho do domínio é crítico. 5 Conclusão

O algoritmo apresentado neste artigo se mostrou bastante eficiente para resolver o problema apresentado. Além disto, o algoritmo se mostrou robusto quando o domínio que define o espaço de busca foi aumentado de forma significativa. Isto sugere a necessidade de se pesquisar mais o impacto do aumento do domínio neste tipo de algoritmo já que este resultado pode fazer com que o método tenha aplicação em problemas onde o tamanho do espaço de busca é crítico. Ainda é necessário se pesquisar mais cuidadosamente o algoritmo, variando-se o número de indivíduos da população, variando-se o número de gerações e, principalmente, fazendo-se9 novos testes de otimização com outras funções. É interessante usar um conjunto de funções variado que seja capaz de avaliar diferentes características do algoritmo (capacidade de escapar de máximos locais, regiões muito planas em torno do máximo global, etc). Também é necessário se pesquisar mais detalhadamente o impacto do aumento do número de variáveis sobre a performance do algoritmo em relação ao algoritmo genético convencional.

1 0.95 0.9 Avaliação

0.85 0.8 0.75 0.7 0.65 0.6 0.55 0.5

0

5

10

15

20 25 Geração

30

35

40

Figura 6 - Comparativo da avaliação do algoritmo genético convencional e com inspiração quântica para a função F6 com os domínios no intervalo [-10000,10000]. A linha cheia mostra o desempenho do algoritmo com inspiração quântica e a linha tracejada mostra o do algoritmo tradicional

Finalmente, pode ser interessante verificar eventuais melhorias no resultado final com a inserção de operadores genéticos de crossover e mutação nos indivíduos sorteados. 6 Bibliografia

Davies, L. (1991). Handbook of Genetic Algorithms, Van Nostrand Reinhold. Grover, L.K. (1996). A Fast Quantum Mechanical Algorithm for Database Search, In Proceedings of the 28th Annual ACM Symposum on Theory of Computing (STOC96), pp 212-219. ACM Press. Han, K.-H. and Kim, J.H. (2000). Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem. In Proceedings of the 2000 Congress on Evolutionary Computation, pp. 1354-1360. IEEE Press. Han, K.-H. and Kim, J.H. (2002). Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization. IEEE Transactions on Evolutionary Computation, vol. 6, no. 6, pp 580-593, IEEE Press. Narayanan, A. and Moore, M. (1996). Quantum inspired genetic algorithms. In Proceedings of the 1996 IEEE International Conference on Evolutionary Computation(ICEC96). IEEE Press. Shor, P. W. (1994) Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124-134. Figura 5 – Seqüência de gráficos mostrando a curva de distribuição de probabilidade para a variável X e os pontos sorteados para compor os indivíduos. Os gráficos mostram a situação nas gerações 1, 20 e 40. A amplitude do pulso na geração 1 é da ordem de 5,0x10-3, não sendo possível visualizá-lo.

Spector, L., Barnum, H., Bernstein, H. J. (1999). Finding a Better-than-Classical Quantum AND/OR Algorithm using Genetic Programming. In Proceedings of the Congress on Evolutionary Computation, vol 3, pp. 2239-2246, IEEE Press.