Computação distribuída do
Algoritmo Genético Compacto
usando Web Services
Samuel Viana, nº 18778
Licenciatura em Informática – Ramo
Tecnológico
Orientador: prof. Fernando Lobo
“Road-Map”
•
•
•
•
•
Web Services
Algoritmo Genético Compacto (cGA)
cGA usando Web Services
Resultados
Conclusão e Trabalho Futuro
Web Services - Motivação
• Arquitecturas diversas
• Necessidade em integrar serviços
• Necessária linguagem comum que permita
a interoperabilidade
Web Services - Definição
• Forma de integrar e trocar e informação
entre sistemas concebidas sob plataformas
diferentes, usando um formato de texto
conhecido por XML.
Vantagens
• Acessíveis a partir de qualquer parte da Internet
• Atravessam firewall’s e proxy’s
• Independentes da plataforma
• Baseados em XML
• Interacção entre aplicações sem intervenção humana
• Diminuem complexidade e custos ligados à integração
Web Services (Arquitectura)
Suporte para Web Services
• Necessidade de um formato de transmissão de
informação que permita:
– Propagá-la facilmente
– Criar uma estrutura que facilite o acesso ao item desejado
• Vantagens da estrutura:
– Validação
– Reutilização
– Normalização
XML
• XML -> “eXtended MarkUp Language”
–
–
–
–
–
Linguagem composta por anotações (Mark-Up)
Orientada para o conteúdo
Ideal para acesso rápido
Legível para humanos
Define estrutura em árvore
HEAD
HTML
BODY
XML
• Características principais:
– Extensível
– Estruturada
– Validação
• Meta-Linguagem
• Gramática definida por DTD ou XML Schemas
Web Services
Exemplo de um documento XML
<receita>
<ingredientes>
<ingrediente>
farinha em pó
</ingrediente>
<ingrediente>
0,5 litros leite
</ingrediente>
<ingrediente>
2 ovos
</ingrediente>
</ingredientes>
</receita>
XML Schemas
<schema xmlns="http://www.w3.org/2001/XMLSchema>
<element
name="receita">
<complexType>
<sequence>
<element ref="ingredientes" maxOccurs="1" />
</sequence>
</complexType>
</element>
<element name="ingredientes">
<complexType>
<sequence>
<element ref="ingrediente" maxOccurs="unbounded" />
</sequence>
</complexType>
</element>
<element name="ingrediente" type="string" />
</schema>
WSDL
• WSDL -> “Web Services Definition Language”
• Baseado em XML
• Define interface de acesso
• Cada linguagem de programação deve transpô-lo para
código nativo
WSDL
SOAP
SOAP -> Simple Object Access Protocol
• Protocolo baseado em XML
• Define o formato das mensagens
• Qualquer protocolo da camada de aplicação, mas
geralmente usa HTTP
• Elemento Raíz é <ENVELOPE>
• Envelope divide-se em cabeçalho e corpo
SOAP
Exemplo de uma mensagem SOAP
SOAP
Mensagem SOAP (sentido request)
SOAP
Mensagem SOAP (sentido response)
Algoritmos Genéticos
•
•
•
•
•
Orientado para problemas de pesquisa e optimização
Resolvem numa escala de tempo muito inferior
Um cromossoma: composto por genes
Genes assumem valor 0 ou 1
População representa todas as soluções actualmente
disponíveis
um cromossoma de 10 bit’s representa uma potencial solução
1011100010
Algoritmos Genéticos
• Função de Fitness mede a qualidade da solução
• Indivíduos comparáveis graças ao fitness
• Selecção para cruzar os melhores indivíduos
• Nova geração terá um fitness médio mais elevado
• Deste modo, ao fim de n gerações a convergência será
atingida
Algoritmos Genéticos
• Operadores de Selecção:
– Roleta
– Torneio
Algoritmo Genético Compacto
A população é
substituída por um
vector de
probabilidades, também
conhecido por vector
população.
1
0
1
0
0
1
1
0
0
0
1
0
1
0
0
1
0
1
0
0
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
1
1
0
0
0
1
1
1
0
0
1
0
1
1
0
1,0
10 0,5
5 0,6
6 0,1
1 0,0
0
Algoritmo Genético Compacto (cGA)
1. É inicializado um vector com todas as posições a 0,5
2. São gerados s indivíduos a partir do vector, sendo s a
pressão de selecção
3. É calculado o fitness de cada indivíduo
4. É efecutado um torneio entre os s indivíduos, sendo
vencedor o indivíduo de melhor fitness
5. O vector é actualizado através da comparação bit a bit
entre vencedor e vencido.
6. Verifica-se se o vector convergiu, caso contrário, voltase ao passo 2
Exemplo do cGA
Problema One-Max (contar o
número de uns)
0
1
0.5
1
1.0
0
0.0
1
0.7
Selecção por
torneio
3
0
1
0
1
1
1
4
1
0
0.2
1
0
0.5
Exemplo do cGA
Actualização do vector população
0
1
0
1
1
1
1
1
0
1
0
0
0.5
1.0
0.0
0.7
0.2
0.5
Exemplo do cGA
Actualização do vector população
0
1
0
1
1
1
1
1
0
1
0
0
0.4
1.0
0.0
0.7
0.3
0.6
Computação Distribuída
• Aproveita-se os ciclos de CPUs desocupados
• Conectividade global da Internet permite a difusão
• O seu somatório permite ter o mesmo efeito de um
supercomputador
• O SETI@home ajudou a popularizar o modelo
cGA distribuído
• O vector é uma representação compacta
de uma população
• Única desvantagem: o comprimento do
vector
• Facilmente distribuído pela Internet
Arquitecutra Worker/Manager
• Foi proposta (Lobo,2005) uma arquitectura que
explora esta possibilidade
• Existem dois tipos de entidades: worker e
manager
• Um Manager – gera o vector população
• Múltiplos Worker s– processam o vector
Worker/Manager
manager
worker
Worker/Manager
manager
worker
Worker/Manager
manager
worker
Worker/Manager
manager
worker
worker
worker
worker
worker
Worker/Manager
manager
worker
worker
worker
worker
worker
Worker/Manager
 Vantagens:
 Custos de sincronização baixos
 Tolerância a falhas
 Escalabilidade
Aplicação
• Função de teste utilizada (10 trap’s concatenadas totalizando um
total de 30 bits)
• Problema complicado de resolver para o cGA (Harik, Goldberg, Lobo,
1999), sendo necessário um efectivo populacional enorme
o representa o número de uns
Simulação em série
• Não é usada uma rede real
• Manager e workers correm na mesma máquina
• Série tem mesmos efeitos que em paralelo
• Um manager
• P workers, que trabalham à mesma velocidade e
arrancam ao mesmo tempo
Simulação em série
• Condições da experiência
–
–
–
–
–
–
Efectivo populacional N=100 000
Indivíduos representados por cromossomas de 30 bits
Pressão de selecção 8
Selecção por torneio
Função de 10 trap’s sobre 3 bits com deceive-to-optimal ratio 0,7
Combinações de P em {1,2,4,8,16,32,64,128,256,512,1024}
com m em {8,80,800,8000,80000}.
– Cada combinação diferente foi executada 30 vezes
Simulação em série
Número de cálculos de cada worker
Simulação em série
Total de contactos por processador worker
Simulação em série
Análise dos resultados
• Valores elevados de m diminuem o número de
comunicações, enquanto valores baixos o aumentam
• Redução quase linear entre P e o total de cálculos
necessários para atingir a convergência (não se verifica
para m= 8000 e m=80000).
• Contactos reduzem-se com m
• Contactos inversamente proporcionais a P
cGA distribuído por Web Services
• Meios utilizados:
– Java 5
– Servidor de Java Server Pages Apache Tomcat
– Apache Axis
A escolha da Java
• Orientada a objectos
• Simplicidade, experiência e à vontade
• Interoperabilidade dos WS pode ser melhor explorada
por uma linguagem multi-plataforma
• Por ser imediatamente portável, as potencialidades de
uma nova plataforma são exploradas de imediato
• Suporta threads nativamente
Modificações à proposta original
• Não foi possível concretizar as ideias originais do
projecto:
– Falta de tempo
– Objectivos ambiciosos
– Falta de recursos humanos e logísticos
Modificações à proposta original
• Como alternativa:
– Substituir um processador worker individual por uma thread
O que são threads ?
• Tradicionalmente, o CPU está ocupado apenas por uma
tarefa
O que são threads ?
• Com threads, repartimos a actividade do CPU em várias
tarefas simultaneamente
•Deste modo, é como se tivéssemos vários CPUs num
Processo de Geração do Código
WSDL
wsdl2java
java
java
java
java
java
java
java
java
Funções Web Services
CreateNewPopulationVector
O cliente pede ao servidor para inicializar
um novo vector
DownloadPopulationVector
Envia um novo vector a uma thread
worker
SendPopulationVector
O worker envia as diferenças para o
servidor manager
Esquema Geral
Servidor
Cliente
Esquema Geral
Esquema Geral
Condições da experiência
• Parâmetros dos GA idênticos às da simulação
• Dois computadores da sala de projectos
– Cliente : AMD Athlon XP 2000+, 768 MB de RAM
– Servidor: Pentium III 666 MHz, 192 MB de RAM
– Hub rede 100 MB
• 128 threads simultâneas no máximo
• Máximo 5 execuções por combinação P/m por limitações
impostas pela rede da sala saturar com m=8
Resultados da execução com Web
Services
Número de cálculos de fitness
Resultados da execução com Web
Services
Número de contactos servidor/threads
Comparação de resultados
Número de cálculos de fitness
Web Services
Simulação
Comparação de resultados
Número de contactos
Web Services
Simulação
Análise dos resultados
• Quanto maior P são reduzidos globalmente:
– o número de comunicações
– cálculos de fitness
• O aumento de m:
– diminui o número de contactos
– não altera substancialmente o número de cálculos de fitness
– Para m = 80000, a relação linear perde-se a partir de P=8
Interpretação
• Aumento de P permite:
– Explorar um maior nº de indivíduos
• Aumento de m:
– diminui o número de contactos,
– Para m=80000, ocorre degradação
Interpretação (cont.)
Tt = Te + Tc
Tt
Te
Tc
Aumento
• diminui
Aumento
• diminui
Tempo total dispendido
Tempo dispendido em cálculos
«
«
«
comunicações
de P :
tanto Te como Tc
de m:
Tc
Sugestão para a Internet
Em caso de utilização real:
• O valor de m deve ser determinado de acordo com a
largura de banda
• Para valores de m muito grandes, terá que ser
considerado o efeito da degradação eventual
Conclusão
• Os resultados dos Web Services concordam totalmente
com os resultados da simulação para P <= 128
• Apesar de não ser uma implementação em série, o efeito
acaba por ser semelhante uma vez que as threads do
cliente arrancam aproximadamente ao mesmo tempo
• Os Web Services provam ser uma alternativa a sockets
na conectividade global
Trabalho futuro
• Concretizar os objectivos originais do projecto, usando a
Internet
• Verificar para P>128
• Criar clientes em diversas linguagens de programação,
• Determinar empiricamente Te e Tc
• Usar uma distribuição exponencial ao longo do tempo