( PDF ) Descoberta e composição de serviços web semânticos através de agoritmo genético baseado em tipos abstratos de dados

Download PDF

ads:

Universidade Federal de Alagoas

Instituto de Computação

Pós-Graduação em Modelagem Computacional de Conhecimento

Descoberta e Composição de Serviços

Web Semânticos Através de Algoritmo

Genético Baseado em Tipos Abstratos de

Dados

Elvys Alves Soares

Dissertação de Mestrado

Maceió

13 de novembro de 2009

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Universidade Federal de Alagoas

Instituto de Computação

Elvys Alves Soares

Descoberta e Composição de Serviços Web Semânticos

Através de Algoritmo Genético Baseado em Tipos Abstratos

de Dados

Trabalho apresentado ao Programa de Pós-Graduação em

Modelagem Computacional de Conhecimento do Instituto

de Computação da Universidade Federal de Alagoas como

requisito parcial para obtenção do grau de Mestre em Mo-

delagem Computacional de Conhecimento.

Orientador: Prof. Dr. Evandro de Barros Costa

Co-orientador: Profa. Dra. Roberta Vilhena Vieira Lopes

Maceió

13 de novembro de 2009

ads:

À minha mãezinha, cujo amor inﬁnito e verdadeiro vence

as mais elaboradas barreiras e me faz, ﬁnalmente,

entender o que é ser sábio.

Agradecimentos

Agradeço aos meus orientadores, Prof. Evandro pela paciência e Profa. Roberta pela

conﬁança, sem os quais diﬁcilmente eu conseguiria concluir este trabalho. Ainda, não poderia

deixar de prestar meus agradecimentos aos colegas de trabalho pelas injeções frequentes de

ânimo e boa companhia, da qual certamente sentirei falta. No IF-AL, agradeço aos professores,

valiosos e esperançosos colegas de trabalho, e aos alunos, cujo interesse sem ﬁm uso como

combustível para crescer mais e mais. E ﬁnalmente à FAPEAL, pelo apoio ﬁnanceiro em parte

deste trabalho.

“Fazia cinqüenta anos. Cinqüenta anos para se estabelecerem e darem

início à Fundação Enciclopédica Número Um, tornando-a uma unidade de

trabalho sem obstáculos. Cinqüenta anos colhendo material. Cinqüenta

anos de preparação.

Estava tudo pronto. Dentro de cinco anos viria à luz a publicação do

primeiro volume do trabalho mais gigantesco até então concebido na

Galáxia. Depois, com intervalos de dez anos, regularmente, volume após

volume. Juntamente com eles apareciam suplementos, artigos especiais

sobre assuntos de interesse mais atual...”

— ISAAC ASIMOV (Os Enciclopédicos, Fundação, 1951)

Resumo

A Web Semântica é uma ampliação da web atual onde a disposição da informação viabiliza

a cooperação entre homens e, sobretudo, entre máquinas. O surgimento de padrões web que

expressam signiﬁcado compartilhado possibilitam a construção de aplicações que resolvem

problemas de integração, colaboração e automação já identiﬁcados pela comunidade cientíﬁca

e mercado consumidor de tecnologias.

A utilização de Serviços Web trouxe grandes ganhos neste sentido, e sua anotação em

termos semânticos, tornando-os Serviços Web Semânticos, viabiliza a proposta da Web Se-

mântica. Diversas tecnologias viabilizam a construção de tais elementos e sua conseqüente

utilização como blocos básicos do desenvolvimento de aplicações cujo escopo é embarcado

na web. Assim, dado o rápido crescimento da quantidade de serviços, tornam-se necessárias

abordagens que resolvam de forma efetiva, com garantias de qualidade e tempo de resposta

aceitável, a integração e posterior utilização destes.

Este trabalho propõe a modelagem de uma solução de software para o problema da Des-

coberta e Composição de Serviços Web Semânticos através do uso do Algoritmo Genético

Baseado em Tipos Abstratos de Dados. Também é proposta uma implementação utilizando

OWL, OWL-S e a OWL-S API. São apresentadas a deﬁnição formal do problema, as expec-

tativas da comunidade cientíﬁca quanto às soluções elaboradas e os resultados obtidos com

respeito à viabilidade da proposta.

Palavras-chave: Serviços Web Semânticos, Algoritmo Genético, Descoberta e Composição

Abstract

The Semantic Web is an extension of the current Web, where the availability of informa-

tion is expected to enable the cooperation between man and, above all, machines. The creation

of standards which express shared meaning enable the construction of applications to solve

integration, collaboration and automation problems which were already been identiﬁed by sci-

entiﬁc community and technology consumers.

The use of Web Services has brought several advances in this sense, and their annotation

in semantic terms, transforming them into Semantic Web Services, enables the Semantic Web

intent. Several technologies also enable the creation of such elements and their inherent use as

basic blocks of application development whose scope is embedded on Web. This way, due to

the fast growing of the number of services, some approaches to effectively solve the problem

of services integration and use become necessary.

This work proposes a modeling of a software solution to the discovery and composition

of Semantic Web Services problem through the use of a genetic algorithm based on abstract

data types. It is also proposed a tool implementation using OWL, OWL-S and OWL-S API

languages and frameworks as well as the formal problem deﬁnition along with the scientiﬁc

community expectations to the given solution.

Keywords: Semantic Web Services, Genetic Algorithm, Discovery and Composition

vii

Sumário

1 Introdução 1

1.1 Apresentação 1

1.2 Objetivos 4

1.2.1 Objetivos Gerais 4

1.2.2 Objetivos Especíﬁcos 4

1.3 Relevância do Problema 5

1.4 Estrutura da Dissertação 5

2 Descoberta e Composição de Serviços Web Semânticos 6

2.1 Introdução 6

2.2 Descrição Formal 8

2.3 Abordagens e Algoritmos de Descoberta e Composição de SWS 10

2.3.1 Abordagem Não-Informada 10

2.3.2 Abordagem Heurística (Informada) 12

2.3.3 Abordagem SMA (Sistemas Multi-Agentes) 15

2.3.4 Abordagem Evolucionária 18

2.4 Síntese do Capítulo 20

3 Modelagem de um Algoritmo Evolucionário para Descoberta e Composição de

SWS 22

3.1 Introdução 22

3.2 Tipos Básicos 24

3.2.1 Base 24

3.2.2 Gene 24

viii

SUMÁRIO ix

3.2.3 Cromossomo 24

3.2.3.1 Axioma de Formação de Cromossomos 25

3.2.4 População 26

3.3 Operadores Genéticos 26

3.3.1 Seleção 27

3.3.2 Cruzamento 28

3.3.3 Mutação 29

3.4 Ambiente 29

3.5 Algoritmo 30

4 Solução Proposta: Arquitetura, Aspectos de Implementação e Resultados 32

4.1 Introdução 32

4.2 Arquitetura e Ferramentas Utilizadas 33

4.2.1 OWL - Web Ontology Language 34

4.2.2 OWL-S - Ontology Web Language for Services 35

4.2.3 OWL-S API 37

4.2.4 Jena 37

4.3 Aspectos de Implementação e Diﬁculdades Encontradas 39

4.4 Resultados Obtidos 40

4.4.1 Descrição dos Testes 40

4.4.2 Execuções 41

5 Conclusões 45

5.1 Quanto aos Objetivos 45

5.2 Quanto à Contribuição 46

5.3 Trabalhos Futuros 46

A Algoritmo Genético Baseado em Tipos Abstratos de Dados - GAADT 48

A.1 Introdução 48

A.2 O Problema do Caixeiro Viajante 48

A.3 Tipos Básicos 48

SUMÁRIO x

A.4 Operadores Genéticos 50

A.5 Ambiente 55

A.6 Algoritmo 55

B Recuperação de Informação Através do Modelo de Espaço Vetorial 57

B.1 Informação Representada no Espaço Vetorial 57

B.2 Um Exemplo 59

B.3 Execução de Consultas 60

Lista de Figuras

1.1 Sistema de pesquisa em lojas online com o servidor utilizando diversos Servi-

ços Web 2

2.1 Representação de um SWS 7

2.2 Composição de SWS 8

2.3 Arquitetura de um Sistema Multi-Agentes para descoberta e composição de

Serviços Web Semânticos 16

2.4 O ciclo básico dos algoritmos evolucionários 18

3.1 Exemplos de cromossomos válidos formados pelo AFC. 25

3.2 Exemplo de dois conceitos e um ancestral comum em uma ontologia. 26

3.3 Exemplo de cruzamento entre dois cromossomos com um só gene onde apenas

o primeiro descendente obedeceu ao AFC. 28

3.4 Exemplo de divisão possível de cromossomo com mais de um gene. 29

4.1 Arquitetura dos Componentes de Software Utilizados na Solução Implementada 33

4.2 Exemplo de ontologia descrita em OWL. 35

4.3 Exemplo de SWS descrito em OWL-S. 38

4.4 Exemplo código para execução de um SWS utilizando a OWL-S API. Fonte:

http://www.mindswap.org/2004/owl-s/api 39

4.5 Representação gráﬁca de resultado encontrado na execução da ferramenta. 42

4.6 Representação gráﬁca de um ramo da ontologia envolvendo os conceitos Sug-

gestion e SpellingSuggestion. 43

4.7 Representação gráﬁca de uma composição encontrada com Split de serviços. 44

B.1 Representação de um documento no Modelo Vetorial 57

B.2 Construção de uma matriz termos×documentos A. 60

Lista de Algoritmos

1 Composição baseada em busca de profundidade iterativa IDDFS (Não-Informada) 11

2 Composição baseada em busca gulosa (greedy search). 13

3 Heurística de parâmetros de classiﬁcação entre duas composições candidatas. 14

xii

CAPÍTULO 1

Introdução

First principles, Clarice. Simplicity.

— HANNIBAL LECTER (The Silence of the Lambs)

Any intelligent fool can make things bigger and more complex... It takes a

touch of genius - and a lot of courage to move in the opposite direction.

— ALBERT EINSTEIN

1.1 Apresentação

A Web Semântica, tal como deﬁnida por Berners-Lee, Hendler e Lassila(1), é uma am-

pliação da web atual na qual a informação passa a ter um signiﬁcado deﬁnido, viabilizando

o trabalho cooperativo entre homens e, principalmente, entre máquinas através da inclusão de

dados e informações que seriam automaticamente manipulados por agentes inteligentes e uti-

litários. O surgimento de padrões web que expressam signiﬁcado compartilhado, tais como

os deﬁnidos e citados por Shadbolt, Berners-Lee e Hall(2), viabilizam a solução de grandes

problemas já identiﬁcados anteriormente, tais como integração, colaboração e automação.

A integração, segundo Mahmoud e Gomez(3), é um dos maiores problemas enfrentados

por departamentos de TI e equipes de desenvolvimento mundo afora. Foi este problema que

motivou a ﬁlosoﬁa da Arquitetura Orientada a Serviços (SOA). Nela, os blocos de funcio-

nalidade das aplicações estariam separados em unidades chamadas de serviços, que seriam

disponibilizados em rede e, por sua vez, se integrariam para formar aplicações inteiras. Em um

cenário ideal, todos os novos sistemas de determinado projeto ou empresa seriam compostos de

funcionalidades encapsuladas em serviços que seriam herdadas das já existentes em sistemas

legados. Assim, tal como descrito por Brehm, Gomez e Rautenstrauch(4), seria viabilizado

o sonho utópico do reuso de software atingindo a casa dos 100% e, ﬁnalmente, viabilizada a

integração tanto idealizada em sistemas ERP

, por exemplo.

Vislumbrando um cenário onde os serviços de determinada rede seriam disponibilizados

para que parceiros e clientes externos contribuíssem com o desenvolvimento de novos serviços

Enterprise Resource Planning.

1.1 APRESENTAÇÃO 2

e também com o ﬂuxo de atualização de informação, a colaboração destes no desenvolvimento

de novas soluções alcançaria níveis sem precedentes através do uso de SOA. Tal abordagem

colaborativa promoveria ganhos para ambos os lados.

Quanto à implementação de SOA, diversas tecnologias e protocolos foram utilizados ante-

riormente

mas todas tinham problemas graves quanto à extensibilidade, dependência de pla-

taforma e segurança em seus padrões de comunicação. A reação da comunidade cientíﬁca aos

problemas de integração e colaboração no desenvolvimento de aplicações veio com o surgi-

mento dos Serviços Web

, que expandiu as fronteiras da SOA e permitiu que a integração se

desse, daí por diante, na Web.

Serviços Web são componentes de software fracamente acoplados, publicados, localizados

e invocados através da Web, deﬁnição dada por Ma, Zhang e He(5). Sua popularidade tem

aumentado bastante, principalmente, pelo fato de se basearem em padrões abertos para inter-

faces e deﬁnições de protocolos (HTTP com linguagens de deﬁnição estendidas do XML), o

que permite abstrair a tecnologia utilizada para a implementação da unidade de negócio que

um serviço representa.

Um exemplo clássico deumaaplicaçãode cotações em lojas virtuais é exibidona ﬁgura 1.1.

Nela, uma aplicação cliente se comunica com o servidor e este, por sua vez, utiliza protocolos

baseados na Web para se comunicar com os Serviços Web de cada uma das lojas participantes

do sistema. O retorno é a cotação dos preços para o produto desejado.

Loja Virtual 3

Web Service

Loja Virtual 2

Web Service

Loja Virtual 1

Web Service

Servidor

Sistema

Pesquisa

Sistema Local

Aplicação Cliente

Dados da Pesquisa

Resposta

Invocação do serviço

Resposta (Cotação)

Figura 1.1 Sistema de pesquisa em lojas online com o servidor utilizando diversos Serviços Web

Tais como DCOM com RPC, CORBA com IIOP e EJB com RMI que são, respectivamente, exemplos de

tecnologias e protocolos.

Também conhecidos como Web Services, em sua terminologia oﬁcial na língua inglesa.

1.1 APRESENTAÇÃO 3

A possibilidade de disponibilizar serviços na Web, a quem estiver interessado, expandiu

o modelo de negócios onde os desenvolvedores de produtos colaboravam apenas com os seus

parceiros. Neste novo modelo de negócios, produtores independentes de serviços os disponi-

bilizariam em “páginas amarelas”

de sítios que representam catálogos de serviços na Web. E

com o crescente volume de interessados neste novo modelo de negócios, surgiram também as

necessidades de padronização com ﬁns de facilitar a busca por serviços. Tecnologias foram cri-

adas neste sentido, das quais o UDDI

, ou Universal Description, Discovery and Integration,

pode ser citado.

A prosperidade de tal abordagem ganhou uma variedade de aplicações em domínios dis-

tintos e a comunidade cientíﬁca destacou duas grandes áreas de investimento: automação na

descoberta e na composição de Serviços Web. Automação na descoberta de serviços porque,

dado o crescimento na quantidade de serviços dispostos em páginas amarelas, a ineﬁciência em

procurar manualmente por serviços que melhor cumpririam determinadas tarefas cresceu pro-

porcionalmente à multiplicação de serviços disponíveis na rede. E uma vez que a interface dos

serviços já está padronizada no sentido de que todos são basicamente expressos em termos de

entradas, saídas e uma descrição da unidade de negócio que o mesmo implementa, a integração

de dois ou mais serviços para prover um novo serviço mais completo - e assim atender a uma

necessidade momentânea e especíﬁca - é, portanto, atividade desaﬁadora e encorajada. Tal inte-

gração, também conhecida como Composição de Serviços Web, tem o propósito de prover um

serviço uniﬁcado ao usuário ﬁnal, escondendo assim a distribuição - principalmente geográﬁca

- e a heterogeneidade - quanto às tecnologias de implementação - dos serviços oferecidos pelos

provedores.

No entanto, uma vez que a descrição dos serviços é geralmente feita como texto livre em

WSDL, tal como exempliﬁcado por Christensen et al.(6), adicionar uma descrição semântica

baseada no contexto aos serviços é uma atividade que tem ganhado importância e tem con-

duzido a pesquisa no desenvolvimento da habilidade de combinar serviços semanticamente, ao

invés de fazê-lo sintaticamente. Tal desaﬁo conduz ramos de pesquisa à criação de mecanismos

para recuperação de semântica a partir das descrições sintáticas dos serviços cujas estratégias

descritas por Ma, Zhang e He(7) e Hicks, Govindaraju e Meng(8) podem ser dadas como

exemplo. Os Serviços Web que se utilizam de uma linguagem ontológica

para especiﬁcar sua

descrição são chamados Serviços Web Semânticos - ou SWS.

Como será visto nas seções posteriores deste trabalho, há diversas estratégias que objetivam

descobrir e/ou compor Serviços Web Semânticos automaticamente. E a solução do problema

utilizando uma abordagem especíﬁca, baseada em algoritmos evolucionários, é o objetivo deste

trabalho.

Exemplo em http://seekda.com/

http://uddi.xml.org

Segundo Vasconcelos et al.(9), trata-se de uma linguagem que usa uma terminologia partilhada e consensual

que torna adequada a partilha e a reutilização de informação.

1.2 OBJETIVOS 4

1.2 Objetivos

1.2.1 Objetivos Gerais

• Apresentar um estudo comparativo das abordagens existentes que se propõem a resolver

o problema da descoberta e composição automáticas de Serviços Web Semânticos.

• Apresentar uma proposta de solução (modelagem e implementação) baseada em algo-

ritmo evolucionário, para o problema dado.

1.2.2 Objetivos Especíﬁcos

• Modelar o problema da descoberta e composição automáticas de Serviços Web Semânti-

cos:

– Fornecer uma descrição formal para o problema em questão;

– Instanciar o formalismo fornecido para uma solução baseada em computação evo-

lucionária.

• Implementar, numa linguagem orientada a objetos, uma ferramenta que realize a mode-

lagem criada:

– Carregar um conjunto de serviços disponíveis em um repositório web;

– Descobrir e compor de Serviços Web Semânticos, dada uma requisição;

– Fornecer composições utilizando split de serviços, desde que possível;

– Manipular ontologias utilizadas na descrição dos SWS;

– Permitir ao usuário reﬁnar a similaridade entre sua consulta e a resposta fornecida

através do ajuste do grau de relevância do conjunto resposta encontrado;

– Gerenciar a explosão combinatorial resultante do processo de composição de servi-

ços;

– Retornar como melhor resposta a composição de SWS que tenha o menor número

de serviços envolvidos e que atenda ao critério de similaridade mínima fornecido.

• Analisar o comportamento da ferramenta mediante dados de entrada fornecidos:

– Confrontar os resultados obtidos com as expectativas esperadas em termos de qua-

lidade e desempenho da solução;

– Explicitar a contribuição dada por este trabalho à solução do problema nos termos

nos resultados encontrados;

1.3 RELEVÂNCIA DO PROBLEMA 5

1.3 Relevância do Problema

Como será visto nos capítulos e seções posteriores deste trabalho, há diversas estratégias

que objetivam descobrir e/ou compor Serviços Web Semânticos automaticamente. No entanto,

não há uma alternativa aceita amplamente pela comunidade cientíﬁca como solução ideal para

o problema, tal como amplamente discutido em eventos como o 2008 IEEE International Con-

ference on Web Services (10).

Este problema se torna relevante em aplicações do mundo real quando entendemos que

as necessidades dos usuários podem ﬁgurar entre as mais diversas, criando requisições que

resultam quase que obrigatoriamente em respostas dadas por composições de serviços. Ainda,

Meditskos e Bassiliades(11) aﬁrmam que, dada uma requisição, não se espera que haja um

serviço (ou composição) que combine em 100% (em termos de entrada e saída desejados)

com esta requisição. Assim, Klusch, Fries e Sycara(12) estabelece que, na estratégia utilizada,

devem ser retornados como resposta os casos de maior semelhança possível com a solução

procurada. Portanto, seria possível traduzir o problema em um cenário real, dado por uma

requisição de serviço que é atendida, de forma transparente ao usuário, por uma composição

cujos serviços têm a capacidade de fornecer uma solução que se assemelhe à requisição, e esta

solução, embora não seja exatamente o que o usuário procura, seja considerada satisfatória para

o mesmo.

Ambos o problema da descoberta e composição automáticas de SWS e o problema do

grau de semelhança entre um candidato encontrado (abstraindo a quantidade de serviços que

este encapsula) e uma requisição são tratados tanto pela modelagem proposta por este trabalho

quanto pela implementação realizada.

1.4 Estrutura da Dissertação

O Capítulo 2 apresenta conceitos gerais sobre descoberta e composição de SWS, traz as

deﬁnições formal e informal do problema e o “estado da arte” desta pesquisa, com abordagens

e algoritmos utilizados para descobrir e/ou compor Serviços Web Semânticos. O Capítulo 3

traz a deﬁnição do GAADT, com tipos e operadores particulares, bem como sua especiﬁcação

para o problema da descoberta e composição de SWS. Detalhes técnicos sobre a implementa-

ção realizada são apresentados e discutidos no Capítulo 4, que também traz os resultados sobre

as experimentações realizadas. As considerações ﬁnais sobre a pesquisa desenvolvida são apre-

sentadas no Capítulo 5. O Apêndice A traz o formalismo do Algoritmo Genético Baseado em

Tipos Abstratos de Dados - GAADT - e o Apêndice B traz maiores detalhes sobre a deﬁnição

e o cálculo do cosseno para a determinar a similaridade entre conceitos, utilizada na função de

avaliação do GAADT.

CAPÍTULO 2

Descoberta e Composição de Serviços Web

Semânticos

Se, a princípio, a ideia não é absurda, então não há esperança para ela.

— ALBERT EINSTEIN

Conhecer não é demonstrar nem explicar, é aceder à visão.

— ANTOINE DE SAINT-EXUPÉRY (O Pequeno Príncipe)

2.1 Introdução

Como já citado no Capítulo 1, os serviços web possibilitaram um aumento sem precedentes

nos níveis de reaproveitamento de funcionalidades, integração e colaboração entre sistemas.

Porém, a adoção de serviços web no desenvolvimento de novas aplicações expande a lista

de requisitos necessários para além da descoberta e composição de serviços - ainda que estes

últimos possam ser considerados grandes grupos de pesquisa da comunidade cientíﬁca na área.

Yu(13) deﬁne mais itens para a lista de necessidades que precisam ser atendidas na adoção de

serviços web, bem como suas motivações, que seguem:

1. Descoberta automática de Serviços Web: Encontrar o serviço desejado pode ser difícil,

especialmente quando o requerente do serviço não sabe da existência do serviço provido;

a única esperança do requerente seria a de alguém já ter provido o serviço online. No

entanto, para tornar os Serviços Web um verdadeiro sucesso, uma forma de descobrir o

serviço requerido deve ser provida; também, o mesmo deve ser descoberto automatica-

mente, com grande precisão e eﬁciência.

2. Invocação Automática do Serviço: Após o serviço requerido ter sido descoberto, o agente

de software deve ser capaz de invocar o serviço automaticamente. O benefício é óbvio:

sem atrasos causados por intervenção humana, pode-se levar um negócio a uma larga

escala com eﬁciência muito maior. Também, em muitos casos, essa invocação automática

é simplesmente uma obrigação; algumas aplicações devem rodar continuamente e sem

interrupções.

2.1 INTRODUÇÃO 7

3. Composição Automática dos Serviços Necessários: Muito frequentemente, uma necessi-

dade de negócio especíﬁca requer que vários Serviços Web trabalhem em conjunto. Por

exemplo, um replanejamento de inventário envolverá a consulta de preços em vários dis-

tribuidores - chamando os Serviços Web providos por esses distribuidores -, comparando

os preços e criando os pedidos - este é outro Serviço Web provido pelo distribuidor de

onde se decide comprar. Claramente, um agente de software deve ser capaz de encontrar

todos os serviços necessários e invocá-los na ordem correta para cumprir o objetivo do

negócio.

4. Monitoramento Automático do Processo de Execução: Claramente, se todos os serviços

precedentes são automáticos, então como saber se um serviço foi encontrado e execu-

tado com sucesso e corretamente? Deve haver um mecanismo para detectar e informar

possíveis falhas, caso elas aconteçam.

Desde o estabelecimento dos serviços web, diversos trabalhos já foram publicados com o

intuito de prover uma solução para um ou mais dos problemas listados acima - o que tornaria

a tentativa de citá-los todos uma tarefa árdua e dinâmica, visto que a produção acadêmica

relacionada tem grande escala e dinamicidade, além de resultados interessantes em termos de

qualidade e eﬁciência que têm sido apresentados com frequência cada vez maior nos últimos

eventos relacionados.

Para os ﬁns deste trabalho, é suﬁciente entender um Serviço Web Semântico como uma

estrutura dada pela Figura 2.1, que representa um SWS com cada elemento de seus conjuntos

de entradas e saídas sendo descrito através de referências a termos de uma ontologia.

SWS

Ontologia

Figura 2.1 Representação de um SWS

A anotação semântica de serviços, tal como descrita por Liu, Peng e Chen(14), elimina

o processo de extração semântica da descrição dos mesmos, bem como de seus parâmetros

de entrada e saída. Assim, elimina-se o problema de haver dois serviços idênticos em suas

funções e parâmetros, mas com descrições ligeiramente diferentes (texto descritivo utilizando

sinônimos ou até mesmo em outra língua), fato este que exigiria um esforço na construção de

um mecanismo de recuperação de informação.

2.2 DESCRIÇÃO FORMAL 8

A descoberta de SWS dá-se através da comparação entre as entradas e saídas de uma requi-

sição e as entradas e saídas dos serviços presentes no repositório onde se deseja pesquisar. Caso

haja um serviço cujas entradas e saídas combinem, então diz-se que houve um match direto, e

a requisição é atendida por um serviço unitário.

SWS Composto

Figura 2.2 Composição de SWS

A Figura 2.2 representa uma composição de Serviços Web Semânticos. Nesta, um serviço

que engloba a composição de 4 outros serviços é representado pelo conjunto de entradas do

primeiro serviço e de saídas do último. E os serviços encapsulados se ligam através da relação

de herança entre os conceitos que eles referenciam da seguinte forma: se um conceito utilizado

para deﬁnir a saída do serviço A é, ao menos, um subconceito de uma entrada do serviço B,

então os dois podem ser ligados. Um serviço B é considerado apto para a composição se todas

as suas entradas forem providas pelos serviços anteriores a ele.

Há diversas estratégias de descoberta e composição de serviços. Os detalhes destas serão

analisados nas seções posteriores deste capítulo.

2.2 Descrição Formal

Nesta seção, utilizaremos o formalismo deﬁnido em Cardoso(15) para descrever as opera-

ções e propriedades desejadas de uma composição de Serviços Web Semânticos.

De forma a discutir esta ideia propriamente, são necessários alguns pré-requisitos. Assim,

vamos inicialmente deﬁnir o conjunto de todos os conceitos semânticos M. Todos os conceitos

que existem na base de conhecimento são membros de M e podem ser representados como nós

de uma árvore, e destas, são respeitadas todas as propriedades de ordens parcial e total, como

segue:

Deﬁnição 2.1. A relação ⊆ de ordem parcial para grafos é reﬂexiva, anti-simétrica e transitiva.

Considere

grafos:

1. Reﬂexiva:

⊆

;

2. Anti-simétrica: Se

⊆

então

3. Transitiva: Se

⊆

então

2.2 DESCRIÇÃO FORMAL 9

Provas para as propriedades listadas podem ser encontradas em MENEZES(16).

Assumindo e estendendo as propriedades dos grafos citadas acima para os elementos do

conjunto M, deﬁniremos então a relação compreende:

Deﬁnição 2.2. Compreende: Dois conceitos A, B ∈ M podem se relacionar de quatro formas

diferentes. A função compreende : (M ×M) ⇒ {Verdadeiro,Falso} expressa essa relação,

como segue:

1. compreende(A, B) é verdadeiro se, e somente se, A ⊆ B (B é então uma especialização de

A);

2. compreende(B, A) é verdadeiro se, e somente se, B ⊆ A (B é então uma generalização de

A);

3. Se nem compreende(A,B) nem compreende(B,A) são verdadeiros, A e B não se relacio-

nam entre si, ou seja, A∩B = /0;

4. compreende(A, B) e compreende(B,A) é verdadeiro se, e somente se, A = B.

Assim, a função compreende é transitiva, anti-reﬂexiva e associativa e também o são a genera-

lização e a especialização.

Se um parâmetro x de um serviço é anotado com A e, no entanto, somente um valor y ano-

tado com B está disponível, se compreende(A,B) for verdadeiro (contravariância), poderemos

invocar o serviço referido assumindo x = y. Isto signiﬁca que y representa informação pelo

menos igual à dada por x. Um exemplo pode ser visualizado por um serviço que necessite de

uma instância de veículo e que pode ser executado com uma instância de carro, visto que carro

seria uma especialização de veículo.

Do ponto de vista de um algoritmo de composição, não há necessidade de distinção entre

parâmetros e os conceitos anotados. O conjunto S contém todos os serviços s conhecidos do

repositório. Cada serviço s ∈ S tem um conjunto de conceitos requeridos de entrada s.in ⊆ M

e um conjunto de conceitos de saída s.out ⊆M que será entregue como retorno. Pode-se ativar

um serviço se forem providos todos os seus parâmetros de entrada.

Similarmente, um pedido de composição R sempre consiste de um conjunto de concei-

tos de entrada R.in ⊆ M e um conjunto de saídas requeridas R.out ⊆ M. Um algoritmo

de composição descobre um conjunto de n serviços S = s

,...,sn : s

,...,s

∈ S. Assim

como mostrado na equação (2.1), o primeiro serviço (s

) de uma composição válida pode ser

executado com instâncias dos conceitos de entrada R.in. Juntamente com R.in, suas saídas

(s.out) estão disponíveis para executar os próximos serviços (s

) de S, e assim por diante.

A composição provê saídas que podem ser anotadas tanto com os conceitos exatos de R.out

quanto com outros mais especíﬁcos (covariância). Podemos, também, deﬁnir uma relação

ehObjetivo : (S×S) ⇒{Verdadeiro,Falso} para cada composição S que soluciona a requisição

R. Assim, a função ehObjetivo(S) é dada por:

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 10

ehObjetivo(S) ⇔ ∀A ∈ s

.in ∃B ∈ R.in : compreende(A,B) ∧

∀A ∈ s

.in,i ∈ {2..n}∃B ∈s

i−1

.out∪... ∪s1.out : compreende(A,B) ∧

∀A ∈R.out ∃B ∈ s

.out : compreende(A,B) (2.1)

2.3 Abordagens e Algoritmos de Descoberta e Composição de SWS

Muitas abordagens de descoberta e composição automáticas de Serviços Web foram e vêm

sendo propostas. Estas variam desde Composição baseada em Planejamento Yan e Zheng;

Sheshagiri, Desjardins e Finin; Wu et al.(17–19) a Composição baseada em Fluxo de Trabalho

(workﬂow), passando por Composição baseada em Transições (interativa) Hull e Su(20). Para

a descoberta e composição de Serviços Web Semânticos, podemos classiﬁcar as abordagens

disponíveis em quatro grandes grupos:

• Abordagem Não-Informada

• Abordagem Heurística (Informada)

• Abordagem SMA (Sistemas Multi-Agentes)

• Abordagem Evolucionária

2.3.1 Abordagem Não-Informada

Como os algoritmos de busca não-informada não se utilizam de nenhuma informação di-

ferente de predicados de objetivo, tal como deﬁnidos na seção anterior, pode-se construir um

algoritmo de composição baseado em busca de profundidade iterativa, ou iterative deepening

depth-ﬁrst search (IDDFS), que é considerada a mais geral e direta para a composição de Ser-

viços Web Semânticos de acordo com Weise et al.(21). Tal algoritmo é rápido para encontrar

soluções para pequenos repositórios de serviços e é ótimo se o problema requer uma busca

exaustiva.

Considerando que o espaço de busca que precisa ser investigado na composição de SWS

é o conjunto de todas as permutações possíveis de todos os conjuntos de serviços. Deﬁnimos,

então, a operação promissor que contém o conjunto de todos os serviços s ∈ S que produzem

um parâmetro de saída anotado com o conceito A (independentemente de suas entradas).

∀s ∈promissor(A)∃B ∈ s.out : compreende(A, B) (2.2)

O Algoritmo 1 mostra uma proposta para a composição não-informada.

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 11

Input: R a requisição de composição

Data: profundidadeMaxima, profundidade as profundidades máxima e atual de pesquisa

Data: in, out conjuntos de parâmetros

Output: S uma composição de serviços que soluciona R

begin

profundidadeMaxima ←2

repeat

S ← dfs(R.in,R.out,/0,1)

profundidadeMaxima ←profundidadeMaxima+1

until S = /0

end

dfs(in,out,composition,profundidade)

begin

foreach A ∈ out do

foreach s ∈ promissor(A) do

wanted ← out

foreach B ∈ wanted do

if ∃C ∈ s.out : compreende(B,C) then

wanted ← wanted\{B}

end

foreach D ∈ s.in do

if ∄E ∈ in : compreende(D,E) then

wanted ← wanted ∪{D}

end

comp ← s⊕composition

if wanted = /0 then

return /0

end

if profundidade < profundidadeMaxima then

comp ← dfs(in,wanted,comp,profundidade+ 1)

if comp = /0 then

return comp

end

return /0

end

Algoritmo 1: Composição baseada em busca de profundidade iterativa IDDFS (Não-

Informada)

O algoritmo 1 constrói um SWS válido por uma estratégia de encadeamento para trás

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 12

(Backward Chaining). A cada recursão, seu método interno dfs testa todos os elementos A do

conjunto wanted de parâmetros ainda desconhecidos. Ele então itera sobre o conjunto de todos

os serviços s que possam prover A. Para cada s, procurado é recomputado. Se ele se tornar

o conjunto vazio /0, uma composição válida foi encontrada e então é retornada. Se a função

dfs não for capaz de encontrar uma solução dentro da profundidade máxima estabelecida (que

denota o número máximo de serviços em uma composição), ela retora /0. O

loop

no Algoritmo 1

invoca iterativamente dfs através do incremento da profundidade limite passo a passo, até que

uma solução válida seja encontrada.

Pode-se citar, entre a literatura relacionada a esta abordagem:

• SWSDS

: O sistema de composição SWSDS Xu et al.(22) pode ser utilizado para mat-

ching sintático e semântico através da mudança de um índice de busca. O sistema usa um

algoritmo de composição muito similar ao apresentado nesta sessão, mas estendido com

a restrição de um serviço ser considerado apenas uma vez para ser parte de uma com-

posição. Isso mitiga o fraco desempenho da abordagem da busca não-informada mas

contrasta com a otimalidade garantida do resultado.

2.3.2 Abordagem Heurística (Informada)

O algoritmo mostrado na seção anterior é devagar e um grande consumidor de memória

para repositórios maiores, uma vez que ele não utiliza nenhuma informação adicional sobre

o espaço de estados. Se tal informação for utilizada, pode-se aumentar a eﬁciência de uma

busca, tal como aﬁrmado por Weise et al.; Paliwal, Adam e Bornhovd(21, 23). Resultados

experimentais sobre estratégias que consideram informações de contexto podem ser obtidos

em Pietro et al.; Ma, Zhang e He(5, 24).

Em uma busca informada, uma heurística c ajuda a decidir quais nós devem ser expandidos

a seguir. Se a heurística é boa, estes algoritmos terão uma performance melhor que estratégias

de busca não-informada, tal como aﬁrmam Russell e Norvig(25). Como um segundo método,

será deﬁnido um algoritmo de busca gulosa (greedy search) que internamente organiza a lista

de composições candidatas conhecidas atualmente em ordem decrescente de acordo com a

heurística na forma de uma função de comparação e : S

∈ R. A função comparadora e(S

)

terá valor abaixo de zero se S

parecer estar mais próximo da solução que S

e maior que zero

se S

for um melhor candidato. Assim, os melhores elementos estarão no ﬁnal da lista X do

algoritmo 2

SWSDS = SEWSIP Web Service Discovery System, SEWIP = Semantic Web Services Integration Platform.

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 13

Input: R a requisição de composição

Data: X a lista sorteada de composições para explorar

Output: S a composição solução encontrada, ou /0

begin

X ← ∪

∀A∈R.out

(promissor(A))

while X = /0 do

X ← sort(decrescente,X,e)

S ← retireUltimoElemento(X)

if ehObjetivo(S) then

return S

end

foreach A ∈ procurado(S) do

foreach s ∈ promissor(A) do

X ← acrescentarLista(X,s⊕S)

end

return /0

end

Algoritmo 2: Composição baseada em busca gulosa (greedy search).

Pode-se derivar funções de comparação que levam em conta vários fatores, aumentando

assim a eﬁciência da heurística e. Por exemplo, pode-se combinar o tamanho do conjunto

de parâmetros não-satisfeitos ∀A ∈ procurado(S) ⇒ ∃s ∈ S : As.in ∧ A /∈ conhecidos(S), os

tamanhos das composições, o número de parâmetros satisfeitos ∀B ∈eliminados(S) ⇒∃s ∈S :

B ∈s.in ∧B ∈conhecidos(S), e o número de conceitos conhecidos conhecidos(S) = R.in∪

∀s∈S

s.out como deﬁnido no Algoritmo 3.

Primeiro, o algoritmo compara o número de parâmetros requeridos. Se uma composição

não contém tais parâmetros não atendidos, é uma solução válida. Se ambos S

e S

são válidos,

a solução envolvendo a menor quantidade de serviços vence. Se somente uma delas é com-

pleta, ela também vence. Caso contrário, ambos os candidatos ainda possuem conceitos não

atendidos. Somente são comparados novamente os conceitos requeridos se ambos os serviços

tiverem o mesmo número de parâmetros atendidos. Se os números de parâmetros dos serviços

é igual, então a composição mais curta é preferida. Se até mesmo as composições envolverem

a mesma quantidade de serviços, então a decisão é baseada no número total de conceitos.

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 14

Input: S

duas composições candidatas

Output: r ∈ Z indicando se S

(r < 0) ou S

(r > 0) deve ser expandido em seguida

begin

←| procurado(S

) |

←| procurado(S

) |

if i

= 0 then

if i

= 0 then

return | s

| − | s

end

return-1

end

if i

= 0 then

return 1

end

←| eliminado(S

) |

←| eliminado(S

) |

if e

> e

then

return-1

else

if e

< e

then

return 1

end

if i

> i

then

return-1

else

if i

< i

then

return 1

end

if | S

|=| S

| then

return | S

| − | S

end

return | conhecido

| − | conhecido

end

Algoritmo 3: Heurística de parâmetros de classiﬁcação entre duas composições candi-

datas.

Pode-se citar, entre a literatura relacionada a esta abordagem:

• Zhang et al.(26): No seu sistema de composição, são utilizadas tabelas hash que ma-

peam o serviço aos seus parâmetros de entrada e saída. Com estas tabelas, ambas as

composições usando encadeamento para frente e para trás podem ser feitas utilizando

busca em largura. Um encadeamento para trás sucessivamente encontra serviços que

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 15

provém parâmetros desconhecidos até que todas as saídas requeridas sejam encontradas.

O encadeamento para frente signiﬁca que os serviços que podem ser invocados com os

parâmetros conhecidos são adicionados iterativamente à composição até que todos as saí-

das requeridas possam ser geradas. Zhang et al.(26) aﬁrma que o encadeamento para trás

funciona melhor que o encadeamento para frente.

• Chahoud(27): No seu trabalho, a autora cria um mecanismo de composição automática

de serviços web semânticos com base em estratégias de planejamento, cuja base se dá

através das buscas heurísticas tal como deﬁnido por Russell e Norvig(25). Neste, as

atividades de descobrir, compor e invocar serviços, detalhadas no início deste capítulo,

são tratadas todas ao mesmo tempo. Assim, cenários que se reconﬁguram durante a

invocação de serviços são previstos e modelados a partir de uma linguagem própria de

representação que é baseada em lógica de primeira ordem. Assim, as composições de

serviços serão resolvidas previamente, e o trabalho direcionado à busca heurística é o de

encontrar serviços, dentre os disponíveis em determinado repositório, que se adequam

aos critérios informados.

2.3.3 Abordagem SMA (Sistemas Multi-Agentes)

Um Sistema Multi Agente (SMA) consiste em um time ou organização de agentes de soft-

ware executando, em conjunto, uma tarefa que não poderia ser executada por nenhum agente

individualmente (Ferber; Fernández e Ossowski(28, 29)). A literatura abordada entende um

sistema de composição de SWS como um SMA da seguinte forma: cada serviço componente é

considerado como uma capacidade de um agente implementada num componente de software

auto-contido.

A Figura 2.3 ilustra uma proposta de arquitetura para Sistemas Multi-Agentes, tal como

deﬁnido em Kumar e Mishra(30), que tratam o problema da descoberta e composição de Ser-

viços Web Semânticos. Nesta concepção, o Agente Usuário U fornece os parâmetros de en-

trada ao sistema de composição, que então são especiﬁcados em termos de uma ontologia

Usando os parâmetros especiﬁcados na descrição da ontologia do pedido, os agentes coorde-

nadores candidatos são descobertos e então o melhor é selecionado. O agente coordenador

selecionado C agora decide, a partir da descrição da ontologia, se o requisito de entrada é

uma atividade atômica ou complexa. No caso de uma atividade complexa, ela é então decom-

posta em tarefas atômicas Tarefa

,Tarefa

,...,Tarefa

. No entanto, antes de decompor

a requisição, C pode executar uma validação sobre a requisição de entrada para veriﬁcar se

todos os parâmetros, preferências e restrições especiﬁcadas na requisição são adequadas ou

A deﬁnição de Ontologia não é clara e as fontes bibliográﬁcas variam quanto à sua formalização. Almeida

M.(31) a deﬁne como:

“Um tipo de estrutura utilizada na organização da informação ... que se organiza a partir de concei-

tos e de seus relacionamentos de forma semelhante a uma estrutura taxonômica.”

Para os ﬁns deste trabalho, é suﬁciente entender uma ontologia como uma estrutura computacional que realiza a

deﬁnição dada acima.

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 16

não. Finalmente, o agente coordenador C descobre e então seleciona os agentes dos provedo-

res de serviço correspondentes Agente

,Agente

,...,Agente

para as tarefas atômicas

Tarefa

,Tarefa

,...,Tarefa

, respectivamente. O agente coordenador C negocia com

os agentes provedores e lhes atribui tarefas, que posteriormente invocam os serviços.

Agente

Usuário

Seleção do

agente

coordenador

com base

nos requisitos

de entrada

Agente

Coordenador

Validação de

valores de

requisitos de

entrada

para sua

viabilidade

Decomposição

de requisições

complexas em

tarefas simples

Tarefa 1

Tarefa 2

Tarefa 3

Tarefa N

Seleção do

agente

provedor do

serviço

para cada

tarefa

Agente 1

Agente 2

Agente 3

Agente N

Negociação

Valores

dos

requisitos

entrada

Figura 2.3 Arquitetura de um Sistema Multi-Agentes para descoberta e composição de Serviços Web

Semânticos

Tal como deﬁnido em Kumar e Mishra(30) e disposto na Figura 2.3, um SMA de descoberta

e composição de SWS consistiria, basicamente, de três tipos de agentes:

• Agente de Requisição de Serviço (ARS);

• Agente Coordenador (AC);

• Agente Provedor de Serviço (APS).

O Agente de Requisição de Serviço(ARS) tem a responsabilidade de fazer uma requisição

ao Agente Coordenador(AC). A requisição do ARS é especiﬁcada em termos da ontologia e

então é utilizada pelo AC. Um Agente Coordenador inteligente possui as seguintes propriedades

e capacidades:

• O Agente Coordenador é um componente de software modular e auto-contido que encap-

sula serviços de coordenação cujas descrições são dadas através de referências a termos

da ontologia (descrição ontológica);

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 17

• Ele possui a capacidade de validar restrições, preferências e outros parâmetros de alto

nível da requisição de entrada dada pelo Agente de Requisição de Serviço;

• Ele tem a capacidade de decidir se a atividadede entrada é atômica ou complexa, interpretando-

a como uma tarefa que consiste de várias atividades de granularidade variável e a decom-

pondo em tarefas atômicas de acordo com suas descrições ontológicas.

• Ele pode avaliar os Agentes Provedores de Serviço usando seus parâmetros de Qualidade

de Serviço (QoS);

• Ele pode negociar com os APS assim como com o ARS para ajustar as entradas das

atividades, as preferências e restrições do ARS para obter parâmetros IOPE

comuns e

satisfazer a requisição.

Já um Agente Provedor de Serviço tem as seguintes propriedades e capacidades:

• Um Agente Provedor de Serviço (APS) é auto-contido e modular, e encapsula serviços

na forma de componentes de software com sua descrição ontológica correspondente.

• O propósito de um APS é decidido pelos serviços que ele encapsula.

• Um APS se junta a um processo de composição apenas durante o tempo em que seu

serviço é requerido.

Diversas abordagens com a forma especiﬁcada acima estão disponíveis na literatura, dentre

as quais citamos:

• SCE: O MultiagentWeb Service Composition Engine, Buhler, Greenwoode Weichhart(33),

consiste de dois componentes arquiteturais primários: JADE

e um repositório de des-

crições de serviços. Neste, as requisições de serviços e composições são representados

por agentes. Estes agentes se comunicam entre si e solucionam as requisições de forma

cooperativa.

Normalmente, abordagens baseadas em IA tais como o SCE são mais lentas que métodos

otimizados e especíﬁcos para problemas tais como o algoritmo de busca gulosa apresentado na

seção anterior.

Entradas (Inputs), Saídas (Outputs), Pré-condições e Efeitos. Representam os tipos de anotações semânticas

disponíveis na OWL-S. Mais detalhes e estratégias com base em todas as anotações disponíveis em Bener, Ozadali

e Ilhan(32)

Java Agent Development Framework, disponível em http://jade.tilab.com/

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 18

2.3.4 Abordagem Evolucionária

SegundoBäck(34), algoritmos evolucionários são algoritmos genéricos de otimização meta-

heurística baseados em população que utilizam mecanismos inspirados na biologia tais como

mutação, cruzamento, seleção natural e sobrevivência do indivíduo mais adaptado. A vanta-

gem dos algoritmos evolucionários em relação a outros métodos de otimização é que eles fazem

apenas algumas considerações sobre o cenário de adaptação e, portanto, conseguem executar

de forma satisfatória em muitas categorias de problemas.

Avaliação

População Inicial

Reprodução

Cálculo da Adaptação

Seleção

cria uma

população inicial

de indivíduos aleatórios

calcula os valores

objetivos dos

indivíduos

cria novos indivíduos

a partir dos selecionados

por mutação e cruzamento

Seleciona os indivíduos

mais adaptados

para cruzamento

usa os valores

objetivos para determinar

valores de adaptação

Figura 2.4 O ciclo básico dos algoritmos evolucionários

Todos os algoritmos evolucionários executam, a princípio, de acordo com os passos ilus-

trados abaixo:

1. Inicialmente, uma população totalmente aleatória de indivíduos é criada;

2. Todos os indivíduos são testados com relação à sua utilidade como solução;

3. Com base nessa avaliação, valores de adaptação são atribuídos aos indivíduos;

4. Um processo de seleção subsequente ﬁltra os indivíduos com baixa adaptação e permite

aos de boa adaptação participar na próxima rodada de reprodução com maior probabili-

dade;

5. Na fase de reprodução, uma descendência (prole) é criada através da variação ou combi-

nação de candidatos à solução;

6. Se a condição de parada é alcançada, a evolução então para. Caso contrário, ela continua

no passo 2.

2.3 ABORDAGENS E ALGORITMOS DE DESCOBERTA E COMPOSIÇÃO DE SWS 19

Para a reprodução de candidatos a solução, os Algoritmos Evolucionários aplicam dois

operadores diferentes:

• A mutação modiﬁca ligeiramente um indivíduo existente e

• O operador de cruzamento combina dois candidatos a solução, criando resultados com

características de ambos.

De forma a utilizar um algoritmo evolucionário para gerar composições de serviços semân-

ticos, precisamos, primeiramente, deﬁnir um genoma capaz de representar sequências de ser-

viços. Uma abordagem direta, porém eﬁciente, é utilizar strings (com comprimento variável)

de identiﬁcadores de serviços que podem ser processados por algoritmos genéticos comuns.

Então, pode-se também aplicar os operadores de criação, mutação e cruzamento.

No entanto, através da especiﬁcação de uma operação de mutação especializada, pode-se

obter uma busca mais eﬁciente. Essa nova operação ou apaga o primeiro serviço em S (através

do mutacao

) ou adiciona um serviço promissor a S (como é feito em mutacao

). Usando a

variável ajustável

como um limitador, pode-se determinar se uma busca deve preferir crescer

ou encolher os candidatos à solução.

Deﬁnição 2.3. mutacao

≡





,...,s

|S|



se | S |> 1

S caso contrário

Deﬁnição 2.4. mutacao

≡ s⊕S : A ∈procurado(S) ∧ s ∈promissor(A)

Deﬁnição 2.5. mutacao ≡



mutacao

(S) se random() >

mutacao

(S) caso contrário

Uma nova operação para construção da população aleatória inicial pode ser deﬁnida como

uma sequência de invocações de tamanho variável de mutacao

. Inicialmente, mutacao

(/0) re-

tornará uma composição consistindo de um único serviço que satisfaz pelo menos um parâme-

tro de R.out. Iterativamente aplica-se mutacao

ao seu resultado anterior um número aleatório

de vezes para gerar um indivíduo.

A função de avaliação das composições formadas na abordagem evolucionária pode ser

deﬁnida em termos da função da heurística que adiciona parâmetros de classiﬁcação para duas

composições candidatas dada na seção anterior. Assim, pode-se deﬁnir uma função de avalia-

ção que priorize:

• composições que são completas;

• composições pequenas;

• composições que solucionam muitos parâmetros não-conhecidos;

• composições que provêm muitos parâmetros.

2.4 SÍNTESE DO CAPÍTULO 20

Mais detalhes quanto a abordagens evolucionárias para a solução de composição de Servi-

ços Web Semânticos podem ser vistos em Weise et al.; Xu e Reiff-Marganiec; Claro, Albers e

Hao(21, 35, 36).

2.4 Síntese do Capítulo

Este capítulo apresentou as diversas estratégias utilizadas para resolver o problema da des-

coberta e composição de Serviços Web Semânticos. Ficou evidenciado que abordagens tais

como a busca não-informada, embora sempre encontre uma solução ótima, pode ser um pro-

blema para bases de serviços muito grandes. A exemplo de bases reais de serviços, tais como a

Semantic Moby

citada por DiBernardo, Pottinger e Wilkinson(37), que contém 2500 serviços,

aproximadamente, não seria interessante utilizar tal estratégia de composição. A busca infor-

mada seria uma alternativa mais interessante, porém requer um alto nível de especialização em

sua heurística e controle reﬁnado do espaço de estados, tais como os fornecidos pelo Algoritmo

3 para conseguir bons resultados de execução.

Ainda na busca heurística, estratégias baseadas em planejamento tais como a criada por

Chahoud(27) requerem quem um especialista aja previamente, resolvendo as composições e

criando templates que indicam ao sistema o padrão de resolução de um possível problema

informado, usando para isso tudo uma linguagem especíﬁca de representação em lógica de

primeira ordem. Tal sistema, embora traga resultados excelentes, requer grande conhecimento

acerca do domínio que está sendo tratado, e não conseguirá resolver requisições de composição

que não tenham sido previstas e modeladas anteriormente.

A abordagem de Sistemas Multi-Agentes, embora venha sendo alvo de trabalhos tais como

os citados neste capítulo, ainda se prova ineﬁciente em termos de tempo de resposta, justamente

por estar apoiada em tecnologias ainda experimentais e, por isso, ainda não preocupadas em

eﬁciência, como descreve Kumar e Mishra(30).

Uma solução interessante seria a utilização de algoritmos evolucionários para a modela-

gem do problema proposto, e consegue-se bons resultados tais como os mostrados em Kumar e

Mishra(30). Porém, como explicado na relevância do problema, tratada na Seção 1.3, é de suma

importância que uma abordagem para o problema da descoberta e composição de Serviços Web

Semânticos trate do grau de similaridade entre requisições e respostas, ou seja, responda a uma

requisição com “a melhor resposta possível”, ao invés da “resposta” simplesmente, indepen-

dentemente destas serem compostas de um ou mais serviços.

Tal problema torna a modelagem tradicional dos algoritmos evolucionários (sequência de

bits ou caracteres) de complexidade demasiada, pois o nível de abstração que essa abordagem

traz é demasiadamente baixo. Ainda, dada a descrição formal da Seção 2.2, a abordagem

desenvolvida deve prover o split de serviços, que é o cenário mostrado pela Figura 3.1, onde

as saídas combinadas de dois ou mais serviços são utilizadas como entrada em outro serviço,

Disponível em http://semanticmoby.org

2.4 SÍNTESE DO CAPÍTULO 21

num possível cenário de solução do problema. A modelagem do split de serviços em buscas

informadas ou não-informadas também seria de difícil implementação.

O Algoritmo Genético Baseado em Tipos Abstratos de Dados, ou GAADT, proposto por

Vieira(38), traz contribuições de grande importância para o desenvolvimento deste trabalho,

tais como um maior nível de abstração (devido à utilização de tipos abstratos de dados ao invés

de cadeias de caracteres) e, portanto, mais facilidade para modelar a similaridade entre serviços

(encontrados e procurados) e o split, que é cenário desejável. Assim, o próximo capítulo trará

uma proposta de modelagem de algoritmo evolucionário para o problema da descoberta e com-

posição de SWS utilizando a ﬁlosoﬁa do GAADT e maiores informações sobre ele, tais como

seu formalismo e uma aplicação formal ao problema do caixeiro viajante, são encontradas no

Apêndice A.

CAPÍTULO 3

Modelagem de um Algoritmo Evolucionário para

Descoberta e Composição de SWS

Para ganhar conhecimento, adicione coisas todos os dias.

Para ganhar sabedoria, elimine coisas todos os dias.

— LAO-TSÉ

Foi o tempo que perdeste com tua rosa que fez tua rosa tão importante.

— ANTOINE DE SAINT-EXUPÉRY (O Pequeno Príncipe)

3.1 Introdução

O modelo de Algoritmo Genético Baseado em Tipos Abstratos de Dados (GAADT), uti-

lizado neste trabalho, foi originalmente proposto por Vieira(38) e trabalha sobre um ambiente

deﬁnido como uma estrutura na qual um dos componentes é a população. Segundo este modelo,

as mudanças ambientais são vistas como o marco do início de um novo período de evolução

durante o qual os cromossomos da população atual irão sofrer a ação dos operadores genéti-

cos com o intuito de construir uma nova população formada somente por cromossomos que

satisfazem aos requisitos do ambiente atual. Após o período de evolução vem o período de es-

tagnação, durante o qual a população não evolui. O período de estagnação é ﬁnalizado quando

uma nova alteração ambiental ocorre, dando início a um novo ciclo de um período de evolução

seguido por um período de estagnação.

O resultado do problema para o ambiente atual é o cromossomo mais adaptado na popula-

ção de estagnação atingida, se esta for compatível com uma condição de parada, a qual deverá

ser deﬁnida durante o período de concepção do GAADT.

A cada período de evolução existe uma população de cromossomos extintos associada. Os

cromossomos desta população são provenientes de uma das populações já trabalhadas pelo al-

goritmo genético, os quais foram avaliados e descartados devido ao seu baixo grau de adaptação

às conﬁgurações atuais do ambiente. A presença da população de cromossomos extintos é jus-

tiﬁcada pela necessidade de evitar que seus genes possam reaparecer nas próximas populações.

3.1 INTRODUÇÃO 23

O terceiro princípio fala sobre a hereditariedade das características adaptadas ao ambiente

dos cromossomos pais que devem ser passadas para os cromossomos ﬁlhos. Sobre este ponto,

é importante ressaltar que os operadores de cruzamento encontrados na literatura só se preo-

cupam com o fato de que as características apresentadas nos cromossomos ﬁlhos estejam pre-

sentes nos cromossomos pais, sem se preocupar com quanto a referida característica contribui

para a adaptação do cromossomo-pai ao ambiente.

O operador de cruzamento apresentado no GAADT constrói novos cromossomos somente

com as características responsáveis pela adaptação dos cromossomos pais ao ambiente, as quais

serão denominadas de genes dominantes. Uma função denominada grau de adaptação do gene

é deﬁnida para informar o quanto uma dada característica pode contribuir com a adaptação do

cromossomo ao ambiente.

O quarto princípio descarta a possibilidade dos cromossomos não adaptados ao ambiente

evoluírem e até conduzirem à geração de cromossomos mais adaptados que os cromossomos

mais adaptados da população atual. Neste quesito, o GAADT propõe que os cromossomos não

adaptados antes de desaparecerem devam ser todos submetidos à ação do operador genético

de mutação, como uma forma de garantir a presença das características adaptadas ao ambiente

destes organismos nas próximas gerações.

Também faz parte da metodologia o registro da história genealógica (táxon) dos cromosso-

mos da população atual, para que uma explicação sobre o resultado encontrado para um dado

problema possa ser gerada sempre que necessário. Um exemplo de problema onde a explicação

do resultado encontrado é relevante seria construir um algoritmo genético para exibir os erros

dos exercícios de soma de dois termos (a

e b

) propostos por um sistema

tutor a uma criança. O papel do algoritmo genético seria operar os termos da soma de modo

a convergir para o resultado declarado pela criança (c

). Ao atingir a população de

estagnação, o sistema tutor não estaria interessado nos cromossomos obtidos pelo algoritmo,

mas sim na história genealógica destes cromossomos, que poderia dizer, entre outras coisas,

que a soma a

+ b

= c

está errada porque o elemento vai-um de a

+ b

não foi considerado,

ou porque a soma a

+ b

= c

está incorreta, etc.

A Seção 3.2 deste capítulo descreve os tipos base, gene, cromossomo e população deﬁni-

dos pelo GAADT. A Seção 3.3 deﬁne os operadores genéticos que trabalham sobre os tipos

deﬁnidos na Seção 3.2. A Seção 3.4 apresenta a estrutura do ambiente trabalhado pelo GA-

ADT e a Seção 3.5 traz a deﬁnição do algoritmo propriamente dito. Todas estas seções serão

apresentadas em termos do problema da descoberta e composição automáticas de Serviços Web

Semânticos.

3.2 TIPOS BÁSICOS 24

3.2 Tipos Básicos

3.2.1 Base

O GAADT propõe que os cromossomos sejam representados por seu material genético, o

qual têm nas bases suas unidades elementares de formação. Assim, uma base B é o conjunto

de todas as unidades genéticas elementares que podem ser usadas na formação do material

genético dos cromossomos de uma população.

Os elementos de uma base se agrupam em sequências para formar as características (genes)

dos cromossomos. Mas nem toda sequência de bases representa uma característica para o

cromossomo. Portanto, deve existir uma lei de formação para indicar como as bases devem

ser agrupadas para formar uma dada característica. A lei de formação de características é

representada pelo conjunto de Axiomas de Formação de Genes (AFG).

Voltando para o problema dos Serviços Web Semânticos, e considerando nossa representa-

ção que utiliza um conjunto de termos de entradas e saídas que se referem a uma ontologia, um

SWS, então, seria uma associação entre um conjunto de termos de entradas e um conjunto de

termos de saída

. Porém, como não é objetivo deste trabalho conceber serviços, e sim utilizar

serviços pré-existentes em determinado catálogo, os conceitos de base e AFG, deﬁnidos pelo

GAADT, não se aplicam à resolução deste problema.

3.2.2 Gene

Um gene g é uma sequência formada pelos elementos da base que pertencem ao conjunto

AFG. Os genes são agrupados em conjuntos para formar os cromossomos da população e o

conjunto de genes {g

,. ..,g

} que compõe um dado cromossomo serve para identiﬁcá-lo

dentro da população. A identidade dos cromossomos será usada para impedir que várias cópias

de um cromossomo possam coexistir ou renascer na população em qualquer tempo durante o

processo de evolução da mesma na busca por um cromossomo mais adaptado. Para os ﬁns

deste trabalho, cada SWS presente no catálogo de serviços será considerado um gene.

3.2.3 Cromossomo

Para os cromossomos, de acordo com as características descritas por Vieira(38), deve haver

um relógio biológico, capaz de garantir que o cruzamento de dois cromossomos de uma mesma

espécie resulte em um cromossomo da mesma espécie. O GAADT batiza o relógio biológico

do cromossomo de Axioma de Formação de Cromossomos (AFC). E um cromossomo c é um

conjunto de genes que obedece às condições estabelecidas pelo AFC.

Na verdade, o conjunto considerado deveria ser o IOPE - como citado no Capítulo 2 - porém a API utilizada,

que será melhor detalhada no Capítulo 4 ainda não provê suporte para trabalhar com deﬁnições de pré-condições

e efeitos.

3.2 TIPOS BÁSICOS 25

3.2.3.1 Axioma de Formação de Cromossomos

Para o problema em questão, o AFC será uma função que garanta que todo cromossomo

tenha a seguinte forma:

• As entradas do primeiro gene do cromossomo têm correspondência com as entradas de

uma requisição;

• As saídas do último gene de um cromossomo têm correspondência com as saídas de uma

requisição;

• Todo cromossomo é formado por um ou mais genes. Caso haja mais de um gene, todo

gene g

deve estar ativo, ou seja, suas entradas devem ser fornecidas por alguma das

saídas de algum dos genes g

i−1

,...,g

Assim, a Figura 3.1 representa cromossomos válidos:

Cromossomo 1

Cromossomo 2

Figura 3.1 Exemplos de cromossomos válidos formados pelo AFC.

3.3 OPERADORES GENÉTICOS 26

3.2.4 População

Os cromossomos são agrupados em conjuntos para formar uma população. Esta repre-

sentação para a população irá garantir a imparcialidade na avaliação dos cromossomos que

compõem a população, já que cada cromossomo só poderá ocorrer uma vez na população.

Seja uma população P

um conjunto de cromossomos construídos conforme descrito no

AFC, o tipo população é o conjunto formado por todos os conjuntos formados por objetos do

tipo cromossomo (ou seja, P = P(P(C))). Estes são possíveis resultados para o problema em

foco segundo a interpretação adotada para os tipos C, G e B.

3.3 Operadores Genéticos

O GAADT trabalha com dois tipos de operadores genéticos: o de reprodução e o de muta-

ção. O operador genético de reprodução caracteriza-se por combinar os genes de dois cromos-

somos (cromossomos pais) para formar outros cromossomos (cromossomos ﬁlhos) enquanto o

operador genético de mutação caracteriza-se por alterar a identidade de um cromossomo para

formar um outro cromossomo (cromossomo-mutante).

O gene dos cromossomos pais para uma dada característica que fará parte dos cromossomos

ﬁlhos é aquele que melhor satisfaz as restrições do problema sobre a característica expressa

por este gene, o qual será denominado de gene-dominante. Dados dois genes g

e g

, que

expressem uma mesma característica com diferentes fenótipos, diz-se que um gene g

melhor

satisfaz as restrições do problema em relação ao gene g

se o grau de adaptação do gene g

for

superior ou igual ao grau de adaptação do gene g

Neste trabalho, o grau de adaptação de um gene é dado por uma função grau que calcula

a similaridade, usando a regra do cosseno, entre o conceito utilizado para deﬁnir uma entrada

ou uma saída de um serviço web semântico e o conceito utilizado para deﬁnir uma entrada ou

saída de uma requisição. Maiores detalhes quanto a Recuperação de Informação no Modelo

Vetorial - modelo que enxerga uma consulta e uma resposta como vetores e através de regras

como a do cosseno consegue atribuir um grau de similaridade entre os mesmos - podem ser

encontradas no Apêndice B.

Automóvel

Carro

Passeio

Carro

Sport

Figura 3.2 Exemplo de dois conceitos e um ancestral comum em uma ontologia.

A Figura 3.2 mostra a visualização de dois termos de uma ontologia e um ancestral comum

entre eles. O cálculo da similaridade entre esses dois conceitos seria dado de acordo com a

3.3 OPERADORES GENÉTICOS 27

fórmula abaixo, simpliﬁcação da equação (B.1):

cos

◦t

|| t

|| . || t

(3.1)

Assim, a similaridade entre os conceitos Carro de Passeio e Carro Sport, na ontologia

dada, seria de 0.5, ou 50%.

Sejam e uma entrada de um gene, s uma saída, n

o número de entradas, n

o número de

saídas e Sim a função Similaridade que implementa a regra descrita na equação acima, a função

adaptGene, que informa o grau de adaptação de um gene em relação à requisição é expressa

pela média dos somatórios das similaridades individuais de cada termo, como segue:

simEntrGene =

∑

i=1

Sim(e

)

(3.2)

simSaidaGene =

∑

j=1

Sim(s

)

(3.3)

adaptGene =

simEntrGene+ simSaidaGene

(3.4)

A produção de novos cromossomos durante o processo evolutivo de uma população serve

para direcionar a busca por cromossomos mais adaptados através da transmissão das caracterís-

ticas de maior grau de adaptação presentes nos cromossomos da população atual. A adaptação

de um cromossomo é dada pela função adapt, que para o problema deste trabalho, é dada pela

média entre a adaptação da entrada do primeiro gene do cromossomo e a adaptação da saída do

último gene, expressa por:

adapt =

simEntrGene(g

) + simSaidaGene(g

)

(3.5)

3.3.1 Seleção

No GAADT, a função de seleção recebe uma população P

e retorna a subpopulação de P

formada pelos cromossomos que satisfazem um requisito do problema r, descrito por uma fór-

mula em lógica de primeira ordem, o qual indica quando um dado cromossomo é considerado

apto a cruzar.

Para o problema da descoberta de composição de SWS, a função de seleção não faz distin-

ção entre os cromossomos de uma população e os considera todos aptos a cruzar. Ressalta-se,

apenas, que o Axioma de Formação de Cromossomo nem sempre vai permitir que dois cro-

mossomos selecionados para cruzamento gerem cromossomos descendentes, visto que todas

as suas restrições axiomáticas devem ser cumpridas.

3.3 OPERADORES GENÉTICOS 28

Ainda, a reprodução no caso do problema deste trabalho é assexuada, ou seja, não há

distinção entre cromossomos macho e fêmea. Tal distinção é prevista na função de fecundação

do GAADT, responsável por discernir ambas as classes de cromossomos.

3.3.2 Cruzamento

O operador deﬁnido no GAADT, e utilizado em conjunto com o AFC, garante que o cru-

zamento entre dois cromossomos vai sempre gerar um cromossomo válido. Neste trabalho, o

operador de cruzamento pode gerar até 8 cromossomos descendentes. Para melhor visualiza-

ção, considere dois cromossomos candidatos a cruzamento A e B:

1. Se ambos os cromossomos possuem apenas um gene, são gerados ﬁlhos AB e BA, tal

como mostrado na Figura 3.3;

Figura 3.3 Exemplo de cruzamento entre dois cromossomos com um só gene onde apenas o primeiro

descendente obedeceu ao AFC.

2. Se há um cromossomo com tamanho maior que 1, então veriﬁca-se a possibilidade de

divisão do cromossomo na metade de seu comprimento.

• A divisão será considerada bem-sucedida se o genes posteriores ao gene g

, pre-

sente no meio da sequência de genes e candidato a gene inicial da nova sequência,

não dependerem de algum gene g

n−1

. A Figura 3.4 representa uma divisão bem-

sucedida de um cromossomo no gene C, pois o gene D depende apenas do gene C,

que estará presente no cromossomo formado pela parte 2 do cromossomo original;

• Em divisões bem-sucedidas, as partes A

e B

são combinadas, gerando os

ﬁlhos A

, A

, B

e B

quando estes obedecerem

todos ao AFC;

• Se a divisão não for possível, então o cromossomo não será dividido e o cruzamento

será dado como no item 1.

3.4 AMBIENTE 29

Parte 1

Parte 2

Figura 3.4 Exemplo de divisão possível de cromossomo com mais de um gene.

3.3.3 Mutação

O operador genético de mutação, deﬁnido para o GAADT, é composto pelas funções de

inserção, supressão e troca, tal que os cromossomos resultantes da ação destes operadores

apresentarão parte dos genes contidos no cromossomo que lhe deu origem, como segue:

• A operação de inserção ins adiciona um conjunto de genes ao cromossomo de origem;

• A operação de supressão del remove um conjunto de genes do cromossomo de origem;

• A operação de troca troc remove um conjunto de genes do cromossomo de origem e lhe

adiciona outro conjunto de genes.

– As ações da função de inserção e supressão podem ser vistas como casos particula-

res da ação da função de troca.

O operador de mutação do GAADT garante que um indivíduo mutante é mais adaptado

que o indivíduo que o originou. Devido às relações de dependência entre genes de um cromos-

somo, particulares ao problema que este trabalho trata, considera-se probabilidade de criar uma

composição inválida de Serviços Web Semânticos maior que a probabilidade de se criar uma

composição válida através das funções de inserção, supressão e troca deﬁnidas neste operador.

Portanto, as mesmas não foram implementadas.

3.4 Ambiente

Um algoritmo genético opera sobre populações de cromossomos que evoluem de acordo

com as características de um ambiente A. Um ambiente A é uma 8-tupla

P,P(P), Rq,AFG,AGC,Tx,Σ, P

, onde:

• P é a população;

3.5 ALGORITMO 30

• P(P) é o conjunto potência de P;

• Rq é o conjunto dos requisitos do problema, ou seja, os parâmetros de entrada e saída

do serviço que se deseja encontrar de forma unitária ou através de composição e que

inﬂuenciam a genealogia da população P;

• AFG é o conjunto de axiomas de formação dos genes dos cromossomos da população P,

vazio para o problema deste trabalho;

• AFC é o conjunto de axiomas de formação dos cromossomos da população P;

• Tx é o conjunto de pares de cromossomos (x, y), onde x é um cromossomo construído a

partir do cromossomo y, pela ação da operação de cruzamento ou mutação, registrando

desta forma a genealogia dos cromossomos pertencentes às populações geradas pelo GA-

ADT durante a sua execução;

• Σ é o conjunto de operadores genealógicos que atuam sobre a população P;

• P

é uma sub-população pertencente a P(P), chamada de população inicial, que neste

caso será o conjunto de todos os cromossomos que representam, individualmente, os

Serviços Web Semânticos providos pelo catálogo.

3.5 Algoritmo

O GAADT é uma função GAADT que recebe a população P

e, depois de submetê-la à si-

mulação de um processo evolutivo, devolve uma população P

. Os cromossomos da população

são os cromossomos das populações P

,...,P

t−1

que ainda satisfazem os requisitos do

problema Rq, ou então são novos cromossomos resultantes da ação genealógica das operações

de cruzamento e mutação sobre os cromossomos da população P

t−1

que apresentam adapta-

ção maior do que a adaptação dos cromossomos que lhes deram origem. Diz-se então que a

população P

evoluiu da população P

Os cromossomos das populações P

,...,P

t−1

que não mais satisfaçam os requisitos do

problema Rq não participarão da construção da população P

, podendo ser assim entendidos

como fazendo parte da população de cromossomos “mortos”, que não ﬁgurarão entre os cro-

mossomos da população P

e das populações seguintes manipuladas pela função GAADT. Não

obstante, tais cromossomos serão recuperados pela análise da taxonomia Tx dos cromossomos

da população atual para evitar que eles apareçam novamente nas próximas iterações da função

GAADT. Esta restrição atende ao entendimento do processo de evolução darwinista, que não

contempla a possibilidade de uma espécie extinta voltar a aparecer num outro momento futuro.

Antes de ser apresentada uma deﬁnição para a função GAADT, deve-se observar a neces-

sidade de se estabelecer um critério de preservação sobre a população atual P

, para orientar o

corte dos cromossomos que não devem ﬁgurar nas populações P

t+1

t+2

,.... Na deﬁnição da

3.5 ALGORITMO 31

função GAADT, este ponto de corte será representado por um predicado unário p

corte

perten-

cente ao conjunto de requisitos do problema Rq, que atua sobre os cromossomos de P

Para o problema da descoberta e composição de SWS, o ponto de corte será ﬁxado no

tamanho máximo da população, que está estabelecido em duas vezes o tamanho da popula-

ção inicial. Assim, até que se atinga o tamanho máximo da população, serão descartados os

indivíduos compostos de mais de um gene e que possuem baixo grau de adaptação. É impor-

tante salientar que os indivíduos de um gene apenas são os presentes da população individual

e não devem ser descartados, pois, apesar de não terem grau relevante de similaridade com a

requisição, podem atuar como ponte entre um serviço que atenda aos parâmetros de entrada da

requisição e um que atenda aos parâmetros de saída da mesma.

A adaptação média da população é obtida dividindo-se a soma da adaptação de todos os

cromossomos da população pelo número de cromossomos desta população e os critérios de

parada adotados pela função GAADT são: a) tempo máximo, aqui estipulado em 30s, de exe-

cução do algoritmo, b) valor da adaptação dos cromossomos considerado satisfatório para o

resultado do problema em análise, aqui estipulado em 90%. Estes critérios também fazem

parte do conjunto de requisitos do problema Rq.

CAPÍTULO 4

Solução Proposta: Arquitetura, Aspectos de

Implementação e Resultados

Todos veem o que pareces, poucos percebem o que és.

— NICCOLO MAQUIAVEL (O Príncipe)

Man has qualities which can never be replaced by a robot...

They (robots) are there so that he shall have more time for the truly human

tasks - those of creation.

— KARLHEINZ STOCKHAUSEN

4.1 Introdução

Em Shadbolt, Berners-Lee e Hall(2), os autores aﬁrmaram que a Web Semântica perma-

neceria, basicamente, no plano das ideias até que padrões de representação de conhecimento

e protocolos de comunicação fossem bem estabelecidos e acordados. Eles ressaltaram que, a

exemplo do protocolo HTTP, cujo uso pioneiro pela comunidade da área da física abriu cami-

nho para o sucesso da Web, o uso crescente de ontologias pela comunidade cientíﬁca eletrônica

(“e-science”) também poderia levar a Web Semântica ao sucesso tal como hoje conhecemos

a Web. Segundo os autores, além de fatores sociais e de decisões de projeto, parte do su-

cesso da Web Semântica reside na sequência de especiﬁcações (Universal Resource Identiﬁer

- URI, HTTP, RDF, ontologias, etc.) e de registros (esquema URI, conteúdos de Internet do

tipo Multipurpose Internet Mail Extensions - MIME ou extensões multi-função para mensa-

gens de Internet), os quais fornecem meios para que construções como uma ontologia derivem

signiﬁcado de um identiﬁcador URI.

Atualmente já há diversas tecnologias consolidadas e recomendadas por instituições tais

como o W3C

a exemplo do WSDL, OWL e OWL-S, que provêm suporte para a construção

http://www.w3.org/ - Segunda sua própria descrição, a entidade se deﬁne como um fórum para informação,

comércio, comunicação e entendimento coletivo que desenvolve tecnologias interoperáveis (especiﬁcações, linhas

gerais, sofware e ferramentas) na condução da Web ao seu potencial pleno.

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 33

das chamadas Aplicações Semânticas - termo que caracteriza aplicações que tratam de conteúdo

semântico, tal como descrito por Santos e Carvalho(39).

A Seção 4.2 deste capítulo trata das principais tecnologias utilizadas na implementação da

ferramenta proposta, são elas: OWL, OWL-S, OWL-S API e Jena. A Seção 4.3 traz detalhes

quanto à implementação e a Seção 4.4 traz os experimentos e resultados obtidos.

4.2 Arquitetura e Ferramentas Utilizadas

Abaixo segue uma ﬁgura descrevendo a arquitetura e as tecnologias, bem como ferramen-

tas, utilizadas na solução implementada:

Ontologia (RDF (S) / OWL / XML Schema)

Jena

Protégé

OWL-S API

SWSSWS SWSSWS SWS SWS

GAADT

Tipos

Operadores

Figura 4.1 Arquitetura dos Componentes de Software Utilizados na Solução Implementada

1. Protégé

: Ferramenta para manipulação de ontologias descritas em RDF(S), OWL e

XML Schemas. É utilizada diretamente na composição das ontologias e regras de infe-

rência associadas.

2. Ontologia: Estrutura hierárquica utilizada para armazenar os conceitos referidos pelos

SWS.

3. Jena: Framework desenvolvido pelo HP Labs Semantic Web Research Group

para a

http://protege.stanford.edu

http://www.hpl.hp.com/semweb

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 34

construção de aplicações semânticas. Capaz de interpretar as ontologias referenciadas

em diversas linguagens de representação e dotado também de motores de inferência.

4. OWL-S API

: API que estende o Jena e fornece acesso à leitura, execução e gravação de

serviços atômicos e compostos descritos em OWL-S.

5. GAADT: Algoritmo Genético Baseado em Tipos Abstratos de Dados. Utilizado para

manipular e arranjar os serviços criados com a OWL-S API na busca de composições que

atendam a determinada requisição de acordo com critérios pré-estabelecidos. Seus tipos

e operadores especíﬁcos atuam nos serviços da camada anterior de forma a orquestrar os

mesmos para a descoberta e composição.

4.2.1 OWL - Web Ontology Language

Martino(40) aﬁrma que em termos computacionais, o que se espera de uma ontologia é

uma especiﬁcação explícita e formal que conceitua um modelo abstrato de algum fenômeno

do mundo em um conhecimento consensual, isto é, compartilhado por todos. Além disso, os

conceitos, as propriedades, as funções e os axiomas devem ser especiﬁcados explicitamente e

serem manipuláveis por computador. As ontologias devem ter capacidade de identiﬁcar contex-

tos de um termo, compartilhar deﬁnições e dar suporte ao reuso. Quando elas são construídas

levando-se em consideração esses aspectos, é possível ajudar as pessoas na busca, extração,

interpretação e processamento da informação.

Para McIlraith e Martin(41), na construção de ontologias é fundamental uma linguagem

com semântica bem deﬁnida e expressiva o suﬁciente para descrever inter-relacionamentos

complexos e restrições entre objetos. A recomendação dada pelo W3C à linguagem OWL

a constata como uma linguagem que atinge esses requisitos, cujo padrão é apresentado por

McGuinness, Welty e Smith(42) e que deriva de um consenso entre duas propostas, a europeia

OIL (Ontology Inference Layer) e a DAML (DARPA Agent Markup Language). A OWL é

uma linguagem para deﬁnição e instanciação de ontologias Web cuja ideia central é permitir

a representação eﬁciente de ontologias. Além disso, ela permite veriﬁcar uma ontologia para

determinar se sua lógica é consistente ou se há algum conceito falho. Uma ontologia, em OWL,

pode incluir:

• Relações de taxonomia entre classes;

• Propriedades dos tipos de dados e descrições dos atributos de elementos das classes;

• Propriedades do objeto e descrições das relações entre elementos das classes;

• Instâncias das classes e instâncias das propriedades.

A recomendação do W3C possui três versões da OWL, que depende do poder de expres-

sividade requerido. As versões menos expressivas (OWL Lite e DL) estão contidas dentro das

http://on.cs.unibas.ch/owls-api

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 35

mais expressivas (OWL DL e Full). Uma ontologia em uma linguagem menos expressiva é

aceita por uma linguagem mais expressiva, contudo a recíproca não é aceita. A adoção da lin-

guagem OWL vem aumentando a cada dia, no entanto, ainda se encontram iniciativas paralelas

tais como o formato OBO

, que tendem a desaparecer dada a quantidade limitada de ferramen-

tas capazes de manipular tais objetos e também às ferramentas de conversão, cuja missão é

converter ontologias de, e principalmente para o formato recomendado, ou seja, OWL.

A Figura 4.2 mostra o código-fonte de uma pequena ontologia descrita em OWL:

<rdfs:Class rdf:ID="MEAL-COURSE">

<rdfs:subClassOf rdf:resource="#CONSUMABLE-THING"/>

<rdfs:subClassOf>

<daml:Restriction>

<daml:onProperty rdf:resource="#FOOD"/>

<daml:minCardinality>

</daml:minCardinality>

</daml:Restriction>

</rdfs:subClassOf>

<rdfs:subClassOf>

<daml:Restriction>

<daml:onProperty rdf:resource="#FOOD"/>

<daml:toClass rdf:resource="#EDIBLE-THING"/>

</daml:Restriction>

</rdfs:subClassOf>

<rdfs:subClassOf>

<daml:Restriction>

<daml:onProperty rdf:resource="#DRINK"/>

<daml:minCardinality>

</daml:minCardinality>

</daml:Restriction>

</rdfs:subClassOf>

</rdfs:Class>

Figura 4.2 Exemplo de ontologia descrita em OWL.

4.2.2 OWL-S - Ontology Web Language for Services

OWL-S é uma ontologia para conceitos de serviços que fornecem um conjunto de constru-

ções, em linguagem de marcação, para descrever as propriedades e capacidades de um serviço

de forma não-ambígua e interpretável por computador. A versão atual da OWL-S acompa-

nha a versão recomendada pelo W3C da OWL, produzida pelo Ontology Working Group dessa

instituição.

A OWL-S permite às ontologias descrever, por um lado, os conceitos dos domínios dos

serviços (passagens aéreas, hotéis, turismo, comércio eletrônico e etc.), e por outro lado, con-

ceitos genéricos que descrevem os próprios serviços (tais como controle de ﬂuxo e controle de

dados) e como esses se relacionam com as ontologias de domínio - através das entradas, saí-

das, precondições, efeitos e etc. Estas descrições semanticamente ricas habilitam a inferência

Open Biomedical Ontologies - disponível em http://www.obofoundry.org

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 36

automática por máquinas sobre as descrições dos serviços e domínios, dando, assim, suporte à

automação da descoberta, composição e execução de serviços e reduzindo tanto a conﬁguração

manual quanto maiores esforços de programação.

A OWL-S organiza a descrição de um serviço em quatro áreas conceituais, a saber:

• Process: Descreve como um serviço executa suas tarefas. Ele inclui informação sobre as

entradas, saídas - incluindo uma especiﬁcação das condições nas quais várias saídas serão

produzidas -, pré-condições - circunstâncias que devem ser satisfeitas antes que um ser-

viço possa ser invocado - e resultados - mudanças realizadas por um serviço. O Process

Model diferencia processos compostos, simples e atômicos. Em um processo composto,

o modelo mostra como o serviço se divide em componentes de processo mais simples, e

o ﬂuxo de controle e dados entre esses componentes. Processos atômicos são essencial-

mente “caixas pretas” de funcionalidade, e processos simples são descrições abstratas de

processos que podem se relacionar com outros processos compostos ou atômicos.

• Proﬁle: Provê uma descrição geral do SWS de forma a facilitar a descoberta do serviço

quando o mesmo é publicado e compartilhado. Esta descrição pode incluir ambas as

propriedades funcionais (entradas, saídas, pré-condições e resultados) e não-funcionais

(nome do serviço, descrição textual, informações de contato, categoria do serviço e pa-

râmetros adicionais do serviço). As propriedades funcionais são derivadas do Process

Model, mas não é necessário incluir todas as propriedades funcionais do Process Model

no Proﬁle. Uma visão simpliﬁcada pode ser fornecida para a descoberta de serviços,

no pressuposto de que um consumidor de serviço olhará, eventualmente, para o Process

Model para alcançar um entendimento completo sobre como o serviço funciona.

• Grounding: Especiﬁca como um serviço é invocado através do detalhamento de como os

processos atômicos do Process Model de um serviço mapeam um protocolo real de troca

de mensagens. A OWL-S fornece tipos diferentes de groundings, no entanto, o único tipo

desenvolvido até o momento é o WSDL

grounding, que permite que qualquer Serviço

Web seja anotado como um Serviço Web Semântico usando OWL-S.

• Service: Um service simplesmente reúne todas as partes em uma unidade que pode ser

publicada e invocada. É importante compreender que as diferentes partes de um serviço

podem ser reutilizadas e conectadas de várias formas. Por exemplo, um provedor de

serviço pode conectar seu Proces Model com vários Proﬁles de forma a fornecer propa-

gandas direcionadas a diferentes comunidades de consumidores de serviço. Um prove-

dor de serviço diferente, provendo um serviço similar, pode reutilizar o mesmo Process

Model, possivelmente como parte de um processo composto maior, e conectá-lo a um

Grounding diferente. As relações entre os componentes de um Service são modeladas

utilizando propriedades tais como:

– presents: Service - Proﬁle;

O WSDL é apresentado por Christensen et al.(6)

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 37

– describedBy: Service - Process Model;

– supports: Service - Grounding.

A Figura 4.3 mostra um exemplo de serviço descrito em OWL-S.

4.2.3 OWL-S API

Trata-se de uma API Java para acesso programático à criação, leitura, escrita e execução de

serviços atômicos ou compostos descritos em OWL-S. A biblioteca fornece um motor de exe-

cução que pode executar processos atômicos (serviços atômicos) usando Groundings WSDL,

Java ou UPnP, e processos compostos (serviços compostos) que utilizam construções de con-

trole tais como Choice, Sequence, AnyOrder, Split e Split-Join. A execução de processos que

consistem de construções de controle condicionais tais como IfThenElse, RepeatUntil ou Re-

peatWhile também é suportada. Além disso, também é fornecido um monitor de execução,

responsável pela monitoria dos serviços envolvidos numa execução.

Ainda, são suportadas mais linguagens para expressar condições de controle e precondi-

ções de processo tais como SWRL

e SPARQL

. A API é projetada para ser extensível, de

forma que formalismos(lógicos), assim como seus procedimentos de avaliação, podem ser uti-

lizados. A API é distribuída em conjunto com um motor de inferência para OWL-DL chamado

Pellet

, porém esta também é uma parte extensível e pode ser substituída por outros motores de

inferência (RDFS

por exemplo).

A Figura 4.4 mostra um pequeno exemplo de leitura de um SWS deﬁnido em OWL-S.

4.2.4 Jena

Jena é um arcabouço Java para a construção de aplicações semânticas através da manipu-

lação de ontologias. Ele provê um ambiente programático para ontologias descritas em RDF,

RDFS e OWL, SPARQL e inclui um motor de inferência baseado em regras.

Jena é de código livre e surgiu no HP Labs Semantic Web Programme. Como um arca-

bouço, ele inclui:

• Uma API para manipulação de arquivos RDF;

• Leitura e escrita de ontologia descritas em RDF em diversos formatos (incluindo OWL);

• Opções de armazenamento persistente ou em memória;

• Motor de execução de consultas SPARQL.

Semantic Web Rule Language - http://www.w3.org/Submission/SWRL/

SPARQL Query Language for RDF - http://www.w3.org/TR/rdf-sparql-query/

http://clarkparsia.com/pellet

http://jena.sourceforge.net/inference

4.2 ARQUITETURA E FERRAMENTAS UTILIZADAS 38

<?xml version=’1.0’ encoding=’UTF-8’?>

<rdf:RDF

xmlns:owl = "http://www.w3.org/2002/07/owl#"

xmlns:rdfs = "http://www.w3.org/2000/01/rdf-schema#"

xmlns:rdf = "http://www.w3.org/1999/02/22-rdf-syntax-ns#"

xmlns:service = "http://www.daml.org/services/owl-s/1.1/Service.owl#"

xmlns:process = "http://www.daml.org/services/owl-s/1.1/Process.owl#"

xmlns:profile = "http://www.daml.org/services/owl-s/1.1/Profile.owl#"

xmlns:grounding = "http://www.daml.org/services/owl-s/1.1/Grounding.owl#"

xmlns:expr = "http://www.daml.org/services/owl-s/1.1/generic/Expression.owl#"

xmlns:swrl = "http://www.w3.org/2003/11/swrl#"

xml:base = "http://127.0.0.1/services/ISBNFinder.owl">

<owl:Ontology rdf:about="">

<owl:imports rdf:resource="http://127.0.0.1/ontology/Concepts.owl"/>

</owl:Ontology>

<service:Service rdf:ID="ISBNFinder">

<service:presents rdf:resource="#ISBNFinder-Profile"/>

<service:describedBy rdf:resource="#ISBNFinder-Process-Model"/>

<service:supports rdf:resource="#ISBNFinder-Grounding"/>

</service:Service>

<profile:Profile rdf:ID="ISBNFinder-Profile">

<service:isPresentedBy rdf:resource="#ISBNFinder-Service"/>

<profile:serviceName xml:lang="en">

ISBN Finder

</profile:serviceName>

<profile:textDescription xml:lang="en">

Receives a book and finds its corresponding ISBN.

</profile:textDescription>

<profile:hasInput rdf:resource="#Book"/>

<profile:hasOutput rdf:resource="#ISBN"/>

</profile:Profile>

<process:ProcessModel rdf:ID="ISBNFinder-Process-Model">

<service:describes rdf:resource="#ISBNFinder-Service"/>

<process:hasProcess rdf:resource="#ISBNFinder-Process"/>

</process:ProcessModel>

<process:AtomicProcess rdf:ID="ISBNFinder-Process">

<process:hasInput rdf:resource="#Book"/>

<process:hasOutput rdf:resource="#ISBN"/>

</process:AtomicProcess>

<process:Input rdf:ID="Book">

<process:parameterType rdf:datatype="http://www.w3.org/2001/XMLSchema#anyURI">

http://127.0.0.1/ontology/Concepts.owl#Book

</process:parameterType>

<rdfs:label>Book Information</rdfs:label>

</process:Input>

<process:Output rdf:ID="ISBN">

<process:parameterType rdf:datatype="http://www.w3.org/2001/XMLSchema#anyURI">

http://127.0.0.1/ontology/Concepts.owl#ISBN

</process:parameterType>

<rdfs:label>ISBN Information</rdfs:label>

</process:Output>

<grounding:WsdlGrounding rdf:ID="ISBNFinder-Grounding">

<service:supportedBy rdf:resource="#ISBNFinder-Service"/>

</grounding:WsdlGrounding>

</rdf:RDF>

Figura 4.3 Exemplo de SWS descrito em OWL-S.

4.3 ASPECTOS DE IMPLEMENTAÇÃO E DIFICULDADES ENCONTRADAS 39

// Cria um motor de execução

ProcessExecutionEngine exec = OWLSFactory.createExecutionEngine();

// Cria uma base de conhecimento

OWLKnowledgeBase kb = OWLFactory.createKB();

// lê a descrição de um serviço

Service aService = kb.readService("http://www.mindswap.org/2004/owl-s/1.1/Dictionary.owl");

// get the process for the server

Process aProcess = aService.getProcess();

// inicializa o mapeamento de entradas com o valor vazio

ValueMap aInputValueMap = new ValueMap();

// especifica um valor de entrada

String inValue = "hello";

// adiciona o valor ao mapeamento

aInputValueMap.setDataValue(aProcess.getInput("InputString"), inValue);

// executa o processo

ValueMap aOutputValueMap = exec.execute(aProcess, aInputValueMap);

// recebe a saída

OWLDataValue out = (OWLDataValue) aOutputValueMap.getValue(aProcess.getOutput());

Figura 4.4 Exemplo código para execução de um SWS utilizando a OWL-S API. Fonte:

http://www.mindswap.org/2004/owl-s/api

4.3 Aspectos de Implementação e Diﬁculdades Encontradas

Esta seção apresenta a construção da aplicação com a estrutura evidenciada na Figura 4.1.

O software que implementa a modelagem proposta neste trabalho foi construído em Java

ambiente Eclipse

Quanto ao conjunto de serviços, como não é objetivo deste trabalho criar Serviços Web

Semânticos e sim descobri-los e compô-los quando necessário, optou-se por utilizar um con-

junto de serviços de testes disponíveis na Web. Algumas propriedades e requisitos inerentes à

utilização dos arcabouços e tecnologias descritas na seção anterior, bem como restrições para

o desenvolvimento da aplicação, foram consideradas como segue:

• A utilização do Jena na manipulação de ontologias demanda o carregamento de todas

as ontologias utilizadas nas descrições dos SWS utilizados. Isto implica que o motor de

inferência utilizado pelo Jena, ao ser carregado, tentará inferir novas regras e ligações

entre termos das ontologias utilizadas. Se o número de ontologias foi muito grande,

este processo poderá demorar um tempo demasiadamente grande, o que causaria atraso

e lentidão não na execução da aplicação em sua versão ﬁnal (pois a ontologia já estaria

carregada em memória), mas durante sua fase de desenvolvimento e testes.

• A possibilidade de indisponibilidade de serviços em tempo de execução na Web (pro-

http://java.sun.com

www.eclipse.org

4.4 RESULTADOS OBTIDOS 40

blemas no servidor) era um risco no desenvolvimento da aplicação. Para mitigá-lo, era

necessário que o conjunto de serviços fosse utilizável a partir do próprio computador,

sem que para isso fosse necessária uma conexão externa à Web.

Dadas as características do desenvolvimento e suas restrições, optou-se por utilizar dois

conjuntos de teste, o OWL-S TC

que é um conjunto de cerca de 1200 Serviços Web Se-

mânticos de 10 domínios diferentes (médico, transportes, turismo, armamentos, biologia etc.)

descritos em OWL-S, que são entregues juntamente com suas ontologias de domínio e demais

regras de inferência SWRL; o segundo conjunto de testes foi o SWS TC

, que é um conjunto

de aproximadamente 240 serviços de domínios diferentes e entregues com o mesmo conteúdo

que o pacote anterior.

Para a execução local dos serviços, foi utilizado o servidor Web XAMPP

, que é de ins-

talação simpliﬁcada e uso imediato. Porém, por conter 34 ontologias de tamanho considerável

(algumas com mais de 500KB) que juntas somam mais de 8000 termos, o primeiro conjunto

levou mais de 1 hora (utilizando computador laptop pessoal de conﬁguração mediana) para

ser lido e interpretado, o que tornava sua utilização, dados os critérios estabelecidos acima,

impraticável. Assim, optou-se pela utilização do segundo conjunto de serviços de testes (241

serviços e ontologia com aproximadamente 600 termos), com redução considerável do tempo

de carga para pouco mais de 10 segundos, no pior caso.

Ressalta-se que a escolha se deu por razões de performance da execução dos testes apenas,

onde não se julgou que a aplicação deixaria de provar seu conceito. E, justamente por ser prova

de conceito, não foi construída com ﬁns de performance, embora se reconheçam inúmeras

oportunidades de melhoria do código produzido em termos de otimização de execução.

4.4 Resultados Obtidos

4.4.1 Descrição dos Testes

A aplicação foi projetada para receber as URI dos termos de entrada e saída desejados.

Assim, para o teste, foram idealizados quatro respostas possíveis para a execução:

1. Um match direto

, com grau de adaptação de 100% entre requisição e resposta;

2. Um match indireto, com composição de serviços necessária.

3. Um match indireto, com split de serviços presente.

Disponível em http://projects.semwebcentral.org/projects/owls-tc

disponível em http://projects.semwebcentral.org/projects/sws-tc

Disponível em http://www.apachefriends.org/pt

br/xampp.html

Considera-se match direto uma requisição que tenha sido atendida por um serviço unitário, e match indireto

uma resposta a uma requisição que envolva mais de um SWS (composição).

4.4 RESULTADOS OBTIDOS 41

Para a execução do teste 1, foram utilizados os termos que descrevem o serviço “Babylon

Dictionary”, que são “Word” para a entrada e “Deﬁnition” para a saída. O resultado da execução

se encontra a seguir:

4.4.2 Execuções

Resultado 1:

Criando base de Conhecimento... Ok.

Adicionando serviços à base de conhecimento... 241 serviços adicionados em 6.0 segundos.

Geração Inicial

Tamanho da população inicial: 215

Adaptação da população inicial: 33.48%

Execução:

Resposta Encontrada:

Grau de adaptação da resposta: 100.0%

Serviços:

1: Babylon Dictionary | http://127.0.0.1/services/BabylonDictionary.owl#BabylonDictionary

Tempo total de execução: 0.0 segundos.

Segundo a modelagem dada no Capítulo 3, a população inicial é composta apenas por cro-

mossomos formados por um único gene, e estes cromossomos encapsulam, individualmente,

os serviços originalmente fornecidos pelo repositório. Como cada gene já nasce sabendo o seu

grau de adaptação em relação à requisição, não foi necessário que o algoritmo genético ope-

rasse sobre a população, uma vez que a mesma já possuía um indivíduo com grau de adaptação

maior que os 90% que fazem parte do critério de parada do mesmo.

O segundo teste também foi considerado satisfatório, pois apesar de as entradas descreve-

rem uma composição entre os serviços “Number2Words” e “Spelling Suggestor”, descritos em

termos de “Number” e “Text” como entrada e saída do primeiro serviço, e “Text” e “Spelling-

Suggestion” como entrada e saída do segundo serviço, com match pretendido(e possível) de

100%, várias respostas foram encontradas além do resultado esperado.

Resultado 2:

...

Geração: 3

Cruzamento -> Quantidade de novos indivíduos: 5

Seleção -> Quantidade de indivíduos removidos: 0

Tamanho da população: 230

Adaptação da população: 19.9%

Indivíduo mais adaptado: 70.05%

Geração: 4

Cruzamento -> Quantidade de novos indivíduos: 3

Seleção -> Quantidade de indivíduos removidos: 0

Tamanho da população: 233

Adaptação da população: 20.29%

Indivíduo mais adaptado: 100.0%

Resposta Encontrada:

Grau de adaptação da resposta: 100.0%

4.4 RESULTADOS OBTIDOS 42

Serviços:

1: Number2Words | http://127.0.0.1/services/Number2Words.owl#Number2Words

2: Spelling Suggestor | http://127.0.0.1/services/SpellingSuggestor.owl#SpellingSuggestor

Entrada: http://127.0.0.1/ontology/Concepts.owl#Text

Saída: http://127.0.0.1/ontology/Concepts.owl#Text

Serviço: 1

Tempo total de execução: 1.4 segundos.

O resultado representa exatamente o que se estava tentando encontrar, ou seja, um match

indireto com composição possuindo adaptação igual a 100%.

Resultado 3:

...

Geração: 6

Cruzamento -> Quantidade de novos indivíduos: 1

Seleção -> Quantidade de indivíduos removidos: 0

Tamanho da população: 243

Adaptação da população: 20.06%

Indivíduo mais adaptado: 70.05%

Geração: 7

Cruzamento -> Quantidade de novos indivíduos: 7

Seleção -> Quantidade de indivíduos removidos: 0

Tamanho da população: 250

Adaptação da população: 20.29%

Indivíduo mais adaptado: 96.77%

Resposta Encontrada:

Grau de adaptação da resposta: 96.77%

Serviços:

1: Number2Words | http://127.0.0.1/services/Number2Words.owl#Number2Words

2: CDYNE Spell Checker | http://127.0.0.1/services/CDYNESpellChecker.owl#CDYNESpellChecker

Entrada: http://127.0.0.1/ontology/Concepts.owl#Text

Saída: http://127.0.0.1/ontology/Concepts.owl#Text

Serviço: 1

Tempo total de execução: 3.5 segundos.

A Figura 4.5 mostra uma representação gráﬁca do resultado 3.

Number2Words

TextNumber

CDYNE

Spel

Checker

SuggestionText

Figura 4.5 Representação gráﬁca de resultado encontrado na execução da ferramenta.

De fato, o grau de adaptação do cromossomo encontrado (96,77%) é válido, pois os termos

SpellingSuggestion (informado na requisição) e Suggestion (encontrado na resposta) têm bas-

tante proximidade, assim como evidencia a Figura 4.6. Esta composição encontrada representa,

ainda, um match indireto com grau de adaptação inferior a 100%.

Resultado 4:

...

4.4 RESULTADOS OBTIDOS 43

Knowledge

Content

Idea

Suggestion

SpellingSuggestion

Figura 4.6 Representação gráﬁca de um ramo da ontologia envolvendo os conceitos Suggestion e Spel-

lingSuggestion.

Geração: 20

Cruzamento -> Quantidade de novos indivíduos: 6

Seleção -> Quantidade de indivíduos removidos: 6

Tamanho da população: 280

Adaptação da população: 27.65%

Indivíduo mais adaptado: 73.14%

Geração: 21

Cruzamento -> Quantidade de novos indivíduos: 19

Seleção -> Quantidade de indivíduos removidos: 19

Tamanho da população: 280

Adaptação da população: 28.45%

Indivíduo mais adaptado: 100.0%

Resposta Encontrada:

Grau de adaptação da resposta: 100.0%

Serviços:

1: Conference Information | http://127.0.0.1/services/ConferenceInformation.owl#

ConferenceInformation

2: Get Cheapest Hotel | http://127.0.0.1/services/GetCheapestHotel.owl#GetCheapestHotel

Entrada: http://127.0.0.1/ontology/Concepts.owl#City | Saída: http://127.0.0.1/

ontology/Concepts.owl#City | Serviço: 1

3: SightSeeing Finder | http://127.0.0.1/services/SightSeeingFinder.owl#SightSeeingFinder

Entrada: http://127.0.0.1/ontology/Concepts.owl#City | Saída: http://127.0.0.1/

ontology/Concepts.owl#City | Serviço: 1

4: Hotel Cost | http://127.0.0.1/services/HotelCost.owl#HotelCost

Entrada: http://127.0.0.1/ontology/Concepts.owl#TimeInterval | Saída: http://127.0.0.1/

ontology/Concepts.owl#TimeInterval | Serviço: 1

Entrada: http://127.0.0.1/ontology/Concepts.owl#Place | Saída: http://127.0.0.1/

ontology/Concepts.owl#Place | Serviço: 3

Tempo total de execução: 19.5 segundos.

O resultado 4 encontrado representa uma saída onde os serviços compostos se ramiﬁcam e

essas ramiﬁcações terminam por habilitar o último serviço da composição (Split). Isso signiﬁca

que o algoritmo genético foi capaz de gerar um encadeamento válido de serviços. A Figura 4.7

traz uma representação gráﬁca da resposta encontrada.

4.4 RESULTADOS OBTIDOS 44

Conference

Information

Conference

Get Cheapest

Hotel

SightSeeing

Finder

Hotel Cost

Hotel

Price

City

Time Interval

Place

Hotel

Notification

Conference

Information

Conference

Get Cheapest

Hotel

SightSeeing

Finder

Hotel Cost

Hotel

Price

City

Time Interval

Place

Hotel

Notification

City

Figura 4.7 Representação gráﬁca de uma composição encontrada com Split de serviços.

CAPÍTULO 5

Conclusões

E agora estou perdido!

Devo parar?

- Não, se paras, estás perdido.

— GOETHE (Poemas)

Even Jeovah, after Moses had got the commandments committed to stone

probably thought: “I always forget the things I really intend to say”.

— CHRISTOPHER MORLEY

Neste capítulo, são apresentadas as conclusões em relação aos objetivos gerais e espe-

cíﬁcos apresentados no Capítulo 1, às necessidades inerentes à utilização de Serviços Web,

apresentadas na introdução do Capítulo 2 e à contribuição deste trabalho.

5.1 Quanto aos Objetivos

Seguindo as orientações dos objetivos, este trabalho apresentou uma proposta de algoritmo

genético para descoberta e composição de Serviços Web Semânticos sob a ótica do Algoritmo

Genético Baseado em Tipos Abstratos de Dados, tal como deﬁnido no Capítulo 3. Ainda,

utilizou-se Java para implementar a ferramenta que realiza a modelagem.

Quanto ao comportamento da ferramenta, este foi considerado satisfatório visto que os

testes dispostos na Seção 4.4 mostraram que a mesma é capaz de executar buscas por serviços

que atendam unitariamente a uma requisição, e também de compor serviços para atender a

uma requisição quando não existe serviço unitário que o faça. Ainda, a ferramenta mostrou-se

capaz de criar composições de serviços que envolvem o conceito de split de serviços, prova

esta evidenciada também na Seção 4.4.

Por se tratar de um Algoritmo Genético, que tem por base a busca por uma solução em um

em espaço de estados não necessariamente contínuo, não se garante que a solução encontrada

será sempre ótima, tal como garantido pela busca não-informada deﬁnida na Seção 2.3. Porém

o esforço computacional para grandes bases de serviços se torna menor, uma vez que a busca

não-informada, geradora de soluções ótimas, é grande consumidora de memória.

5.2 QUANTO À CONTRIBUIÇÃO 46

As necessidades ao se utilizar serviços web apresentadas na introdução do Capítulo 2 foram

atendidas por intermédio da utilização de tecnologias já consagradas e recomendadas tais como

o OWL, OWL-S e a OWL-S API. Desaﬁos tais como a monitoração da execução são vencidos

com a criação de objetos especíﬁcos de tais arcabouços e a invocação automática são inerentes

à descoberta de um serviço unitário, ou composição, que atenda a uma dada requisição.

5.2 Quanto à Contribuição

Como contribuições deste trabalho, destacam-se a modelagem de um algoritmo genético

utilizando a orientação a objetos como abstração de fundo e a composição de serviços através

de split.

Frente aos algoritmos evolucionários tradicionais, onde os indivíduos são tratados como

sequências binárias ou cadeias de caracteres, destaca-se a facilidade da modelagem usando o

GAADT para problemas com alto grau de abstração tais como o da descoberta e composição de

SWS. Seria demasiadamente complexo e detalhista o trabalho de representar todas as relações

entre conceitos semânticos utilizados para descrever serviços, o seu grau de aproximação com

uma dada pesquisa e seu papel numa composição candidata a cada operação do algoritmo (mu-

tação, troca, cruzamento etc.). O autor considera a abstração provida pelo GAADT peça chave

para a resolução deste problema na abordagem dos algoritmos evolucionários, bem como para

a rápida implementação de melhorias de código (com relação à otimização de sua execução).

Quanto à possibilidade de compor serviços utilizando split, este não é um fato tão abor-

dado na literatura. O levantamento bibliográﬁco não menciona fortemente tais capacidades em

estratégias baseadas em sistemas multi-agentes, buscas informadas e não-informadas. Dado

o algoritmo deste trabalho, tal problema pôde ser modelado e implementado de forma mais

simpliﬁcada do que o seria numa busca em largura ou numa estratégia de encadeamento (para

frente ou para trás), visto que as possibilidades inﬁnitas de se organizar os serviços de uma base

numa estrutura de grafo levaria tais estratégias ao consumo excessivo de memória e processa-

mento.

5.3 Trabalhos Futuros

Quanto aos trabalhos futuros, podemos destacar:

• Utilização e análise de desempenho entre as diversas estratégias citadas no Capítulo Ca-

pítulo 2, a ﬁm de obter dados mais precisos quanto aos tempos de resposta (eﬁciência

das estratégias) e a qualidade das soluções encontradas;

• Testes comparativos com implementações de outras abordagens (não informada, infor-

mada e SMA) para veriﬁcar desempenho e qualidade das soluções encontradas;

5.3 TRABALHOS FUTUROS 47

• Refatoramento do código criado com ﬁns de incremento de performance, uma vez que o

objetivo da concepção do mesmo foi o de prova de conceito;

• Adequação da base de descrições de serviços à versão 1.2 da linguagem OWL-S para

inclusão de parâmetros de pré-condições e efeitos;

• Utilização de parâmetros de pré-condições e efeitos na descoberta e composição para

melhores ﬁltragem e acurácia do algoritmo em suas respostas, evitando que sejam consi-

derados dois serviços de propósitos diferentes mas que tenham os mesmos tipos de dados

de entrada e saída.

APÊNDICE A

Algoritmo Genético Baseado em Tipos Abstratos

de Dados - GAADT

A.1 Introdução

Este capítulo apresenta o GAADT em termos do problema do caixeiro viajante e demonstra

seu formalismo. Maiores detalhes poderão ser encontrados em Vieira(38).

A.2 O Problema do Caixeiro Viajante

O problema do caixeiro viajante pode ser resumido da seguinte forma: Dados um conjunto

N de cidades e uma matriz de distâncias formada pelas ligações de cada par de cidades deste

conjunto, construa a menor rota para o caixeiro percorrer as cidades de N, que parta de uma

cidade n (n ∈ N), que passe por todas as outras cidades uma única vez e que termine na cidade

n de origem.

Para um conjunto N de cardinalidade

, a rota a ser percorrida pelo caixeiro seria composta

por

+ 1 pontos de passagem. O primeiro e o último ponto de passagem seriam preenchidos

com o mesmo nome de cidade, neste caso n. Isto, por ser uma ligação comum a qualquer

roteiro, não inﬂuencia no cálculo do número de rotas possíveis. O segundo ponto de passagem

da rota pode ser preenchido com qualquer uma das cidades ainda não visitadas, correspondendo

−1 alternativas. O terceiro ponto de passagem da rota pode ser preenchido com qualquer

uma das cidades ainda não visitadas, correspondendo a

−2 alternativas. Prosseguindo com

este raciocínio, tem-se que, no momento do preenchimento do

-ésimo ponto de passagem da

rota, só existirá uma única cidade ainda não visitada para ocupá-lo. Pode-se concluir, então,

que o número de rotas analisadas para um conjunto N de cardinalidade

é (

−1)×(

−2)×

.. . ×1 = (

−1)!.

A.3 Tipos Básicos

Deﬁnição A.1. (Base) - Uma base B é o conjunto de todas as unidades genéticas elementares

que podem ser usadas na formação do material genético dos cromossomos de uma população.

A.3 TIPOS BÁSICOS 49

No caso do problema do caixeiro viajante, envolvendo quatro cidades denominadas de

CidadeA, CidadeB, CidadeC e CidadeD), o conjunto base pode ser instanciado como B =

{CidadeA,CidadeB, CidadeC,CidadeD }.

O AFG deveria estabelecer que as sequências válidas são aquelas com tamanho igual a

2, tal que a base da primeira posição desta sequência deve ser diferente da base que ocupa a

segunda posição. A semântica associada a cada sequência b

 assim descrita é que existe

um caminho da cidade b

para a cidade b

. AFG = {(∀g ∈ AFG • #g = 2), (∀g = b

 ∈

AFG • (b

= b

)}

Deﬁnição A.2. (Gene) - Um gene g é uma sequência formada pelos elementos da base que

pertence ao conjunto AFG.

Os genes são agrupados em conjuntos para formar os cromossomos da população e as ca-

racterísticas apresentadas pelos cromossomos de uma população servem também para classiﬁcá-

los em grupos taxonômicos (espécies e famílias) em função do grau de similaridade das carac-

terísticas compartilhadas pelos mesmos. Este fato conduziu alguns pesquisadores a concluir

erroneamente que todos os cromossomos com alto grau de similaridade genética (e morfoló-

gica) pertenceriam ao mesmo grupo taxonômico. O contra exemplo mais forte a esta conclusão

é o alto grau de similaridade existente entre o homem e o chimpanzé, os quais não pertencem

ao mesmo grupo taxonômico.

Após muitas tentativas, mal sucedidas, de diferenciar estas espécies pela característica in-

teligência atribuída ao homem, King e Wilson concluíram que a principal diferença entre o

homem e o chimpanzé não está em suas características genéticas e morfológicas, mas sim no

seu desenvolvimento embrionário. Segundo King e Wilson, existe um relógio biológico que

ativa o início e ﬁm da formação de uma característica em cada uma destas espécies em tempos

embrionários diferentes. Tal relógio biológico deve também garantir que o cruzamento de dois

cromossomos de uma mesma espécie resulte em um cromossomo da mesma espécie.

Neste trabalho, o relógio biológico do cromossomo será representado pelo conjunto de

Axiomas de Formação de Cromossomos (AFC), o qual deverá ser deﬁnido para cada situação

de acordo com a semântica adotada para o cromossomo.

Por exemplo, um cromossomo para o problema do caixeiro viajante é qualquer conjunto

de genes, tal que para todo elemento b do tipo base o número de ocorrências de b como cidade

de partida e o número de ocorrências de b como cidade de chegada são ambos iguais a 1.

AFC = ∀c ∈ AFC∀b ∈ B •(#g ∈c |∃a ∈ B • g = b,a = #g ∈ c |∃a ∈ B • g = a,b= 1)

Deﬁnição A.3. (Cromossomo) - Um cromossomo c é um conjunto de genes que obedece às

condições estabelecidas pelo AFC.

Deﬁnição A.4. (População) - Uma população P

é um conjunto de cromossomos construídos

conforme des-crito na Deﬁnição A.3

O tipo população é o conjunto formado por todos os conjuntos formados por objetos do

tipo cromossomo (ou seja, P = P(P(C))), que são possíveis resultados para o problema em

A.4 OPERADORES GENÉTICOS 50

foco segundo a interpretação adotada para os tipos C, G e B. Deve-se ressaltar que a geração da

população vazia pelo algoritmo indica que a interpretação adotada para o problema está errada.

A.4 Operadores Genéticos

O GAADT trabalha com dois tipos de operadores genéticos: o de reprodução e o de muta-

ção. O operador genético de reprodução caracteriza-se por combinar os genes de dois cromos-

somos (cromossomos-pai) para formar outros cromossomos (cromossomos-ﬁlho), enquanto

que o operador genético de mutação caracteriza-se por alterar a identidade de um cromossomo

para formar um outro cromossomo (cromossomo-mutante).

O gene dos cromossomos-pai para uma dada característica que fará parte dos cromossomos-

ﬁlho é aquele que melhor satisfaz as restrições do problema sobre a característica expressa por

este gene, o qual será denominado de gene-dominante. Este gene não apresenta o mesmo ní-

vel epistemológico do gene dominante proposto por Mendel em seu trabalho com ervilhas, já

que existe uma grande diferença entre dizer que um gene g

satisfaz melhor as restrições do

problema do que um gene g

e dizer que o fator hereditário de um gene g

é superior ao fator

hereditário de um gene g

O grau de adaptação de um gene é dado por uma função grau e será considerada a exis-

tência de um gene g

que será usado para representar um gene que não expressa qualquer

característica, de forma que a sua presença ou ausência não altera a identidade do cromossomo,

o qual satisfaz as restrições impostas pelo conjunto de axiomas de formação de genes. Seu grau

de adaptação é menor que o grau de adaptação de qualquer outro elemento do tipo gene. Tal

gene será denominado de gene-inócuo.

Deﬁnição A.5. (Grau) - O grau de adaptação de um gene é uma função grau do seguinte tipo:

grau : G → K tal que, a cada gene g, g ∈ G, é associado um único número k, k ∈ K (K é um

corpo ordenado

), chamado de grau(g) e que reﬂete, segundo a interpretação adotada para o

problema, uma estratiﬁcação comparativa entre a adaptação dos genes.

O gene inócuo será uma constante do sistema, cujo valor deverá ser deﬁnido no mo-

mento da instanciação do algoritmo a um dado problema. Para o problema do caixeiro vi-

ajante, será preciso redeﬁnir o tipo base e o AFG, para que o gene inócuo possa ser de-

ﬁnido. O tipo base é acrescido do elemento que irá formar a sequência do gene inócuo,

B = {CidadeA,CidadeB,CidadeC,CidadeD,CidadeInocua}.

O conjunto de axiomas de formação de gene irá conter mais um predicado, para informar

a composição do gene inócuo, que neste caso é a sequência CidadeInocua,CidadeInocua.

Para o problema do caixeiro viajante, a função grau deverá fornecer uma medida sobre

a distância entra as cidades consideradas, de modo que a soma destas medidas informem a

Corpo ordenado - é uma estrutura algébrica, com duas operações, sem divisores próprios de zero e munido de

uma ordem. Ex: R, ≤, +, ×, 0, 1.

A.4 OPERADORES GENÉTICOS 51

menor distância a ser percorrida pelo caixeiro. A distância entre as cidades CidadeA, CidadeB,

CidadeC e CidadeD está contida na Tabela A.1. Assim a função grau(g = b

) =

d(b

)

para todo gene diferente do gene inócuo, e grau(g

) é zero.

CidadeA CidadeB CidadeC CidadeD

CidadeA 0 3 7 5

CidadeB 3 0 2 1

CidadeC 7 2 0 4

CidadeD 5 1 4 0

Tabela A.1 Distância entre as cidades

grau(g) =











se g = g

se g = {CidadeA,CidadeB}.

se g = {CidadeA,CidadeC}.

se g = {CidadeA,CidadeD}.

se g = {CidadeB,CidadeC}.

se g = {CidadeB,CidadeD}.

se g = {CidadeC,CidadeD}.

Lema A.1. ∀g : G |g = g

• (grau(g),grau(g

)) ∈ maiorQ

Por uma questão de nomenclatura, será também exibida a relação de equivalência cromos-

sômica, denotada por ≡

, deﬁnida da seguinte maneira: ≡

: C ↔ C, tal que c

≡

, se e

somente se, c

−{g

}=c

−{g

O gene dominante é identiﬁcado pela função domi que recebe um par de genes, um de cada

um dos cromossomos-pai, e retorna o gene de maior grau de adaptação se os genes fornecidos

expressarem uma mesma característica. Caso os genes fornecidos não expressem uma mesma

característica, então a função domi retornará g

Dados dois genes, diz-se que eles expressam uma mesma característica se existe um atri-

buto relevante para o problema em foco que seja satisfeito pelos genes fornecidos. No caso

do problema do caixeiro viajante, o conjunto atributoRelevante exige que as cidades que com-

põem um dos genes analisados sejam as mesmas que compõem o outro gene, como ilustra a

deﬁnição axiomática abaixo:

∀g

∈ G(rang

= rang

⇔ (∃G

∈ atributoRelevante({g

} ⊆ G

)))

A relação mesma é especiﬁcada pela seguinte deﬁnição axiomática:

∀g

∈ G((g

) ∈ mesma ⇔ (∃G

∈ atributoRelevante({g

} ⊆ G

)))

Lema A.2. ∀g ∈G •(g, g) ∈ mesma

Lema A.3. ∀g

∈ G | (g

) ∈ mesma • (g

) ∈ mesma

A.4 OPERADORES GENÉTICOS 52

Lema A.4. ∀g

∈ G | (g

) ∈ mesma ∧ (g

)

∈ mesma • (g

) ∈ mesma

Deﬁnição A.6. (Dominante) - O gene dominante é uma função domi do seguinte tipo:

domi : G×G → G

domi(g

) =







se (g

) /∈ mesma,

se (g

) ∈ mesma∧grau(g

) ≥ grau(g

se (g

) ∈ mesma∧grau(g

) < grau(g







A especiﬁcação da função domi é feita através de uma deﬁnição axiomática, na qual cada

rótulo representa o predicado que descreve cada uma das alternativas do sistema que deﬁne esta

função.

domi(g

) =











se ((g

) ∈ mesma) ∧ (grau(g

) = grau(g

)),

se ((g

) ∈ mesma) ∧ (grau(g

)grau(g

)),

se ((g

) ∈ mesma) ∧ (grau(g

)grau(g

)),

se ((g

) /∈ mesma).

Lema A.5. ∀g ∈G((g, g) ∈ mesma ⇔ domi(g,g) = g)

Lema A.6. ∀g

∈ G | (g

) ∈ mesma ∧ (g

) ∈ mesma

(domi(g

,domi(g

)) = domi(domi(g

),g

))

A produção de novos cromossomos durante o processo evolutivo de uma população serve

para direcionar a busca por cromossomos mais adaptados através da transmissão das caracterís-

ticas de maior grau de adaptação presentes nos cromossomos da população atual. A adaptação

de um cromossomo é dada pela função adapt.

Deﬁnição A.7. (Adaptação) - A adaptação de um cromossomo é uma função adapt do seguinte

tipo:

adapt : C → K

adapt(c) =

∑

g∈c

c,g

×grau(g)

onde Θ

c,g

é o peso com o qual o gene g contribui para a adaptação do cromossomo c.

A assinatura da função Θ é o mapeamento do par cromossomo e gene em um valor racional

positivo, a ser dado pelo problema ao qual o GAADT será aplicado. O conjunto dos números

racionais positivos é especiﬁcado pela seguinte deﬁnição abreviada Q.

Por exemplo, para o problema do caixeiro viajante, o peso de qualquer gene no cromos-

somo será igual à

, se este gene não pertencer ao cromossomo, caso contrário ele será

Θ(c,g) =



se (g /∈ c),

se (g ∈ c).



A operação de cruzamento recebe dois cromossomos-pai, aptos a cruzarem, e retorna uma

população cujos cromossomos são formados somente pelos genes dominantes dos cromosso-

mos fornecidos. Logo, para se deﬁnir esta função precisa-se antes deﬁnir uma função para

A.4 OPERADORES GENÉTICOS 53

selecionar os cromossomos aptos a cruzarem (seleção) e uma função para retornar o conjunto

de genes dominantes para todas as características existentes nos cromossomos-pai (fecunda-

ção).

A função de seleção recebe uma população P

e retorna a subpopulação de P

formada

pelos cromossomos que satisfazem um requisito do problema r, descrito por uma fórmula em

lógica de primeira ordem, o qual indica quando um dado cromossomo é considerado apto a

cruzar.

Deﬁnição A.8. (Seleção) - A seleção dos cromossomos que satisfazem um predicado r é uma

função sel do seguinte tipo:

sel : P(P) ×P(P) → P(P)

sel(P

,r) = P

∩r.

A função fecundação recebe dois cromossomos e retorna o conjunto de genes dominantes

entre todos os genes dos cromossomos fornecidos.

Deﬁnição A.9. (Fecundação) - A fecundação é uma função fec do seguinte tipo:

fec : C×C → P(G)

fec(c

) = {g | ∀g

∈ c

∀g

∈ c

(g = domi(g

))}

Lema A.7. ∀c ∈C((fec(c, c),c) ∈≡

)

Os cromossomos-pai aptos a cruzarem são representados pelo conjunto MACHOe FEMEA,

formados da seguinte forma: MACHO = sel(P

,M) e FEMEA = sel(P

,F), onde P

é uma

subpopulação da população atual formada por cromossomos adaptados ao ambiente e, M e F

são dois predicados sobre o tipo população pertencentes ao conjunto de requisitos do ambiente

Rq, escritos em uma linguagem de primeira ordem.

Note que, dependendo da especiﬁcação dos requisitos do ambiente M e F, a reprodução

gerada pode ser sexuada, assexuada ou mista. A reprodução sexuada ocorre quando M∩F = /0,

a assexuada quando M = F, e a mista quando M ∩F = /0 e M = F.

Por exemplo, para o problema do caixeiro viajante, o requisito M pode exigir que as cida-

des CidadeA e CidadeB façam parte da rota representada pelos seus cromossomos, enquanto

F exige que as cidades CidadeC e CidadeD façam parte da rota representada pelos seus cro-

mossomos. Assim, o cromossomo resultante deste cruzamento deve representar uma rota que

passa pelas cidades CidadeA, CidadeB, CidadeC, e CidadeD.

M = {c ∈C | ∃b

∈ B(∀g

= (b

) ∈ c(b

∈ {CidadeA,CidadeB}) ∨

∈ {CidadeA,CidadeB}))}

F = {c ∈C | ∃b

∈ B(∀g

= (b

) ∈ c(b

∈ {CidadeC,CidadeD}) ∨

∈ {CidadeC,CidadeD}))}

Deﬁnição A.10. (Cruzamento) - O cruzamento é uma função cruz do seguinte tipo:

cruz : MACHO×FEMEA → P

cruz(c

) = {c | c ⊆fec(c

)}

A.4 OPERADORES GENÉTICOS 54

O operador genético de mutação, deﬁnido para o GAADT, é composto pelas funções de

inserção, supressão e troca. A operação de inserção ins adiciona um conjunto de genes ao

cromossomo de origem.

Deﬁnição A.11. (Inserção) - A inserção é uma função ins do seguinte tipo:

ins : C×P(G) → C

ins(c,G

) =



c∪G

se c∪G

∈ AFC,

c caso contrário.

A operação de supressão del remove um conjunto de genes do cromossomo de origem.

Deﬁnição A.12. (Supressão) - A supressão é uma função del do seguinte tipo:

del : C×P(G) → C

del(c,G

) =



c−G

se c−G

∈ AFC,

c caso contrário.

A operação de troca troc remove um conjunto de genes do cromossomo de origem e lhe

adiciona outro conjunto de genes.

Deﬁnição A.13. (Troca) - A troca é uma função troc do seguinte tipo:

troc : C×P(G) ×P(G) → C

troc(c,G

) =











(c∪G

) −G

se c∪G

∈ AFC∧(c∪G

) −G

∈ AFC,

c∪G

se c∪G

∈ AFC∧(c∪G

) −G

/∈AFC,

c−G

se c∪G

/∈AFC∧c−G

∈ AFC,

c se c∪G

/∈AFC∧c−G

/∈AFC.

Corolário A.1. ∀c ∈ C; G

∈ P(G)(troc(c,G

) = del(ins(c,G

),G

))

Este corolário estabelece que as ações da função de inserção e supressão podem ser vistas

como casos particulares da ação da função de troca.

Deﬁnição A.14. (Mutação) - A mutação é um predicado mut ⊆ P(P), tal que:

mut(c

) = {c

|∃G

: P(G) ((#G

≤#c

div2)∧(#G

≤#c

div2)∧(troc(c

) = c

)

∧(adapt(c

),adapt(c

)) ∈ maiorQ}

A restrição (adapt(c

),adapt(c

)) ∈maiorQ garante que todo cromossomo-mutante é mais

adaptado do que o cromossomo que lhe deu origem. E a limitação do número de genes que

podem ser alterados do cromossomo no cromossomo-mutante em cinquenta por cento do ta-

manho do cromossomo fornecido deve-se ao fato de que se as mutações ocorridas em um

cromossomo de uma dada espécie forem muito grandes, então este cromossomo seria repelido

pelos cromossomos da sua espécie, por não ser considerado mais um igual a estes.

A.5 AMBIENTE 55

A.5 Ambiente

Um algoritmo genético opera sobre populações de cromossomos que evoluem de acordo

com as características de um ambiente A. Um ambiente A é uma 8-tupla

P,P(P), Rq,AFG,AGC,Tx,Σ, P

, onde:

• P é a população,

• P(P) é o conjunto potência de P,

• Rq é o conjunto dos requisitos (características expressas através de fórmulas numa lin-

guagem de primeira ordem) do problema que inﬂuenciam a genealogia da população

• AFG é o conjunto de axiomas de formação dos genes dos cromossomos da população P,

• AFC é o conjunto de axiomas de formação dos cromossomos da população P e

• Tx é o conjunto de pares de cromossomos (x, y), onde x é um cromossomo construído a

partir do cromossomo y, pela ação da operação de cruzamento ou mutação, registrando

desta forma a genealogia dos cromossomos pertencentes às populações geradas pelo GA-

ADT durante a sua execução,

• Σ é o conjunto de operadores genealógicos que atuam sobre a população P,

• P

é uma sub-população pertencente a P(P), chamada de população inicial, com no mí-

nimo um cromossomo.

O processo de evolução darwinista, segundo o qual todas as espécies desenvolveram-se a

partir de outras espécies, pela transmissão hereditária de pequenas variações, em sucessivas

gerações, resultando na sobrevivência das espécies que melhor adaptaram-se ao ambiente, é

induzido pelas alterações ambientais produzidas pela natureza. Este papel desempenhado pela

natureza, na visão de evolução darwinista, aqui será representado pelo GAADT, que é quem

submete os cromossomos de uma população à ação dos requisitos do problema Rq, resultando

assim na geração de novos cromossomos a partir daqueles já existentes.

A.6 Algoritmo

O GAADT é uma função GAADT que recebe a população P

e, depois de submetê-la à si-

mulação de um processo evolutivo, devolve uma população P

. Os cromossomos da população

são os cromossomos das populações P

,...,P

t−1

que ainda satisfazem os requisitos do

problema Rq, ou então são novos cromossomos resultantes da ação genealógica das operações

A.6 ALGORITMO 56

de cruzamento e mutação sobre os cromossomos da população P

t−1

que apresentam adapta-

ção maior do que a adaptação dos cromossomos que lhes deram origem. Diz-se então que a

população P

evoluiu da população P

Os cromossomos das populações P

,...,P

t−1

que não mais satisfaçam os requisitos do

problema Rq não participarão da construção da população P

, podendo ser assim entendidos

como fazendo parte da população de cromossomos “mortos”, que não ﬁgurarão entre os cro-

mossomos da população P

e das populações seguintes manipuladas pela função GAADT. Não

obstante, tais cromossomos serão recuperados pela análise da taxonomia Tx dos cromossomos

da população atual para evitar que eles apareçam novamente nas próximas iterações da função

GAADT. Esta restrição atende ao entendimento do processo de evolução darwinista, que não

contempla a possibilidade de uma espécie extinta voltar a aparecer num outro momento futuro.

Antes de ser apresentada uma deﬁnição para a função GAADT, deve-se observar a neces-

sidade de se estabelecer um critério de preservação sobre a população atual P

, para orientar o

corte dos cromossomos que não devem ﬁgurar nas populações P

t+1

t+2

,.... Na deﬁnição da

função GAADT, este ponto de corte será representado por um predicado unário p

corte

perten-

cente ao conjunto de requisitos do problema Rq, que atua sobre os cromossomos de P

Por exemplo, para o problema do caixeiro viajante, o ponto de corte poderia selecionar

somente os cromossomos com grau de adaptação maior ou igual ao valor da adaptação média

da população. A adaptação média da população é obtida dividindo-se a soma da adaptação de

todos os cromossomos da população pelo número de cromossomos desta população.

Os critérios de parada adotados pela função GAADT são: a) o número máximo de iterações

desejadas, b) valor da adaptação dos cromossomos considerado satisfatório para o resultado

do problema em análise. Estes critérios também fazem parte do conjunto de requisitos do

problema Rq.

Deﬁnição A.15. (GAADT) - O GAADT é uma função GAADT do seguinte tipo:

GAADT : A → A

GAADT(P

) =







otm

se P

otm

= {c | ∀c : P

(adapt(c) ≥ k)} = /0,

t+1

se t+ 2 = T,

GAADT(P

t+1

) caso contrário.

onde P

t+1

= cruz(a, b) ∪mut(c) ∪p

corte

) com e a, b,c ∈ P

, P

é a população inicial consi-

derada, k ∈K é um valor imposto pelo ambiente A, como critério de aceitação de cromossomos

em P

que satisfazem o problema e T ∈ N é um número dado como critério de satisfação do

número de iterações.

No processo acima, a primeira e a segunda opções de saída são condições de parada. A

segunda ocorrerá garantidamente, se eventualmente a primeira não ocorrer. Também deve ser

observado que para qualquer entrada P

, o processo GAADT dá uma saída bem determinada.

Isto signiﬁca que o GAADT é um algoritmo e desta forma um procedimento correto.

APÊNDICE B

Recuperação de Informação Através do Modelo de

Espaço Vetorial

B.1 Informação Representada no Espaço Vetorial

No modelo de Recuperação de Informação - RI - de espaço vetorial, um vetor é usado

para representar cada item ou documento de uma coleção. Cada componente do vetor reﬂete

um conceito, palavra-chave ou termo particular associado ao documento dado. O valor dado a

esse componente reﬂete a importância ao representar a semântica do documento. Tipicamente,

o valor é uma função da frequência com que o termo ocorre no documento ou na coleção

de documentos como um todo, tal como aﬁrmam Baeza-Yates e Ribeiro-Neto(43). Suponha

um documento descrito, para ﬁns de indexação, por três termos: T

, T

e T

. Ele pode ser

representado por um vetor nas três dimensões correspondentes. A Figura B.1 mostra o vetor

quando os termos tem pesos 0.5, 2.5 e 5, respectivamente. Neste caso, o termo T

é o termo

mais signiﬁcante no documento, com T

com importância secundária e T

com importância

ainda menor.

0.5

2.5

Figura B.1 Representação de um documento no Modelo Vetorial

Um banco de dados contendo um total de d documentos descritos por t termos é repre-

sentado como uma matriz A de termos×documentos t ×d. Os vetores d representando os d

documentos das colunas da matriz. Assim, o elemento da matriz a

é a frequência com a qual

o termo i ocorre no documento j, como em Manning, Raghavan e Schtze(44). Na linguagem

B.1 INFORMAÇÃO REPRESENTADA NO ESPAÇO VETORIAL 58

do modelo vetorial, as colunas de A são os vetores de documentos, e as linhas de A são os veto-

res de termos. O conteúdo semântico da base de dados é contido integralmente no espaço das

colunas de A, signiﬁcando que os vetores de documentos abrangem esse conteúdo. Nem todo

vetor representado no espaço das colunas de A tem uma interpretação especíﬁca em termos

de da coleção de documentos propriamente dita, ou seja, uma combinação linear de vetores

correspondendo a dois títulos de documentos pode não se traduzir diretamente em um título

de documento que tenha um signiﬁcado válido. O que é importante de uma perspectiva de RI,

no entanto, é a possibilidade de se explorar relações geométricas entre vetores de documentos

para modelar similaridades e diferenças de utilização de termos.

Há uma variedade de esquemas disponíveis para ponderar os elementos da matriz. Aos

elementos a

da matriz termo-por-documento A são frequentemente atribuídos dois fatores

= l

. Neste caso, o fator g

, também conhecido como Inverse Document Frequency

(IdF) Manning, Raghavan e Schtze(44), é um peso global que reﬂete o valor geral do termo

i como um termo indexador para a coleção inteira. Como um exemplo, considere um termo

muito comum como computador em uma coleção de artigos de computadores pessoais. Não

é importante incluir este termo na descrição de um documento justamente porque é sabido que

todos os documentos são sobre computadores (independentemente deles usarem ou não o termo

computador em suas descrições), então um valor pequeno para o peso g

é apropriado.

O fator l

, conhecido como Term Frequency (TF) Manning, Raghavan e Schtze(44), é um

peso local que reﬂete a importância do termo i dentro do próprio documento j. Há uma gama

de valores para pesos locais, que variam desde simples valores binários (0 ou 1) a funções en-

volvendo logaritmos de frequências de termos. Estas últimas tem um efeito de suavização na

qual termos de alta frequência que tem valor discriminatório limitado ganham pesos baixos.

Esquemas de pesos globais variam desde simples normalizações a avançadas abordagens ba-

seadas em estatística. Maiores detalhes sobre estratégias de pesos locais e globais podem ser

vistas em Baeza-Yates e Ribeiro-Neto(43) e Manning, Raghavan e Schtze(44).

Para coleções de texto abrangendo muitos contextos, tais como uma enciclopédia, o nú-

mero de termos é frequentemente muito maior que o número de documentos: t ≫ d. No caso

da Web, a situação é revertida. Uma matriz de termos-por-documentos utilizando o conteúdo

do maior dicionário de inglês como termos e o conteúdo de todas as páginas em inglês como

documentos deve ter um tamanho por volta de 300, 000×300, 000,000 Berry, Drmac e Jes-

sup(45). Como um documento geralmente usa apenas um pequeno subconjunto do dicionário

inteiro de termos gerado para um dado banco de dados, a maioria dos termos de uma matriz

termos-por-documentos é zero.

Em um esquema de RI vetorial, um usuário executa uma consulta no banco de dados para

encontrar documentos relevantes utilizando alguma forma de representação vetorial para estes

documentos. A consulta é um conjunto de termos, possivelmente com pesos atribuídos, repre-

sentados da mesma forma como o seria um documento. Novamente, é provável que muitos dos

termos do banco de dados não apareçam na consulta, signiﬁcando que muitos dos componen-

tes do vetor de consulta são zero. Executar uma consulta signiﬁca encontrar os documentos

mais similares à consulta na utilização e peso dos termos. No modelo vetorial, os documentos

B.2 UM EXEMPLO 59

selecionados são aqueles mais próximos geometricamente à consulta de acordo com alguma

medição.

Uma medição comum de similaridade é o cosseno do ângulo entre os vetores da consulta

e do documento. Se a matriz termos-por-documentos A tem colunas a

,j = 1,...,d, os cossenos

de d são computados de acordo com a fórmula

cos

|| a

|| q ||

∑

i=1



∑

i=1



∑

i=1

(B.1)

para j = 1,...,d onde a norma Euclidiana || x ||

é deﬁnido por || x ||

√

x =

∑

i=1

para

qualquer vetor t-dimensional real x. Devido aos vetores de consulta e documento serem tipi-

camente esparsos, os produtos internos e normas na equação (B.1) geralmente não tem alto

custo computacional. Além disso, a norma do vetor de documentos || a

necessita ser com-

putada apenas uma vez para qualquer matriz termo-por-documento. Perceba que multiplicando

tanto a

ou q por uma constante não muda o valor do cosseno. Então, podemos dimensionar os

vetores de documentos ou consultas para qualquer valor conveniente.

B.2 Um Exemplo

A Figura B.2 demonstra como uma simples coleção de cinco títulos descrita por seis termos

leva a uma matriz termos-por-documentos de tamanho 6×5, apresentada por Berry, Drmac e

Jessup(45). Devido ao conteúdo de um documento ser determinado pelas frequências relativas

dos termos e não pelo número total de vezes que um termo aparece, os elementos da matriz

neste exemplo são dimensionados de forma que a norma Euclidiana de cada coluna é 1. Ou

seja, || a

= 1 para as colunas a

,j = 1,...,5. Desta forma, utilizamos a frequência de termos

como o peso local l

e não aplicamos peso global - neste caso, g

= 1.

A escolha dos termos utilizados para descrever o banco de dados determina não somente

o seu tamanho, mas também sua utilidade. Neste exemplo, foram utilizados apenas os termos

diretamente relacionados a cozinha, signiﬁcando que o interesse particular do leitor em cozinha

francesa não resultaria na recuperação de documentos relevantes. Neste caso, adicionar os

termos francesa e italiana para descrever as nacionalidades cobertas ampliaria a representação

da semântica do banco de dados de forma útil. Por outro lado, incluir termos muito comuns

como de e para faria muito pouco para aumentar a qualidade da matriz termos×documentos.

Ao construir uma matriz termos×documentos, os termos são geralmente identiﬁcados por

suas palavras-tronco. No exemplo citado, a palavra doces conta como doce e a palavra assando

conta como o termo assar. O uso de derivações em RI remonta aos anos 60 e a derivação reduz

a necessidade de armazenamento através da redução do número mantido de palavras Berry,

Drmac e Jessup(45).

B.3 EXECUÇÃO DE CONSULTAS 60

Os T = 6 termos:

: ass(ar, ado, ando)

: receitas

: p(ão, ães)

: bolo

: sobremesa(s)

: torta

Os D = 5 documentos:

: Como assar

pães sem receitas

: A Arte Clássica das Sobremesas de Viena

: Receitas

Numéricas: A Arte da Computação Cientíﬁca

: Pães

, Sobremesas, Tortas e Bolos: Receitas de Assados em Quantidade

: Sobremesas

: O Livro das Melhores Receitas Francesas

A matriz 6 ×5 (termos×documentos) antes da normalização, onde o elemento ˆa

representa o número de vezes que o termo i aparece no título do documento j:

A =







1 0 0 1 0

1 0 1 1 1

1 0 0 1 0

0 0 0 1 0

0 1 0 1 1

0 0 0 1 0







A matriz 6×5 (termos×documentos) com colunas unitárias:

A =







0.5774 0 0 0.4082 0

0.5774 0 1.0000 0.4082 0.7071

0.5774 0 0 0.4082 0

0 0 0 0.4082 0

0 1.0000 0 0.4082 0.7071

0 0 0 0.4082 0







Figura B.2 Construção de uma matriz termos×documentos A.

B.3 Execução de Consultas

Usando a pequena coleção de títulos da Figura B.2, é possível demonstrar a execução

de uma consulta baseada nos ângulos de um espaço vetorial de dimensão 6. Suponha que

B.3 EXECUÇÃO DE CONSULTAS 61

um usuário na busca por informação sobre cozinha inicia uma busca por livros sobre as-

sando pães. A consulta correspondente, no modelo vetorial, seria escrita como o vetor q

(1)



1 0 1 0 0 0



com entradas diferentes de zero para assando e pães. A pesquisa por

documentos relevantes é conduzida através da computação dos cossenos dos ângulos

entre o

vetor de consulta q

(1)

e os vetores de documentos a

pela equação (B.1). Um documento é dado

como relevante somente se o cosseno do ângulo que ele faz com o vetor de consultas seja maior

que um valor mínimo ou ponto de corte. Uma implementação prática poderia usar um ponto

de corte como 0.9, mas no pequeno exemplo dado, foi utilizado um valor mínimo de cosseno

de 0.5.

Para a consulta q

(1)

, os únicos cossenos diferentes de zero foram cos

= 0.8165 e cos

0.5774. Dessa forma, todos os documentos sobre assar pães (o primeiro e o quarto) são retorna-

dos como relevantes. O segundo, terceiro e quinto documentos, que não contém esses tópicos,

são corretamente ignorados.

Se o usuário tivesse simplesmente pedido livros sobre assar, no entanto, os resultados

teriam sido notadamente diferentes. Neste caso, o vetor de consulta seria dado por q

(1)



1 0 0 0 0 0



, e os cossenos dos ângulos entre a consulta e os cinco vetores de

documentos seriam, respectivamente, 0.5774, 0, 0, 0.4082 e 0. Somente o primeiro documento,

um livro sobre assar pães, atingiria o ponto de corte do cosseno. O quarto documento, que é de

fato uma referência mais compreensiva sobre assados, não é retornado como relevante.

A comunidade de Recuperação de Informação desenvolveu uma variedade de abordagens

para responder a tais falhas do modelo vetorial básico. Estas técnicas tipicamente afetam como

os dados são representados na matriz termos×documentos. Vários exemplos e reﬁnamentos do

modelo vetorial podem ser encontrados em Manning, Raghavan e Schtze(44).

Referências Bibliográﬁcas

1 BERNERS-LEE; HENDLER, T.; LASSILA, J. The semantic web. Scientiﬁc American,

maio 2001.

2 SHADBOLT, N.; BERNERS-LEE, T.; HALL, W. The semantic web revisited. IEEE

Intelligent Systems, IEEE Computer Society, Los Alamitos, CA, USA, v. 21, n. 3, p. 96–101,

2006. ISSN 1541-1672.

3 MAHMOUD, T.; GOMEZ, J. M. Integration of semantic web services principles in soa

to solve eai and erp scenarios; towards semantic service oriented architecture. In: Proc. 3rd

International Conference on Information and Communication Technologies: From Theory to

Applications ICTTA 2008. [S.l.: s.n.], 2008. p. 1–6.

4 BREHM, N.; GOMEZ, J. M.; RAUTENSTRAUCH, C. An ERP solution based

on web services and peer-to-peer networks for small and medium enterprises. Inders-

cience Publishers, v. 1, p. 99–111, nov. 29 2005. ISSN 1479-313X. Disponível em:

<http://www.inderscience.com/link.php?id=8288>.

5 MA, J.; ZHANG, Y.; HE, J. Web services discovery based on latent semantic approach. In:

ICWS. IEEE Computer Society, 2008. p. 740–747. ISBN 978-0-7695-3310-0. Disponível em:

<http://dx.doi.org/10.1109/ICWS.2008.135>.

6 CHRISTENSEN, E. et al. Web services description language (WSDL) 1.1.

Http://www.w3.org/TR/wsdl. 2001.

7 MA, J.; ZHANG, Y.; HE, J. Efﬁciently ﬁnding web services using a clustering semantic

approach. In: SHENG, Q. Z. et al. (Ed.). CSSSIA. ACM, 2008. (ACM International

Conference Proceeding Series, v. 292), p. 5. ISBN 978-1-60558-107-1. Disponível em:

<http://doi.acm.org/10.1145/1361482.1361487>.

8 HICKS, J.; GOVINDARAJU, M.; MENG, W. Search algorithms for discovery of web

services. In: Proc. IEEE International Conference on Web Services ICWS 2007. [S.l.: s.n.],

2007. p. 1172–1173.

9 VASCONCELOS, J. B. de et al. A knowledge-engine architecture for a competence

management information system. In: Proceedings of 14th UKAIS Conference, Oxford. [S.l.:

s.n.], 2009.

REFERÊNCIAS BIBLIOGRÁFICAS 63

10 2008 IEEE International Conference on Web Services (ICWS 2008), September 23-26,

2008, Beijing, China. [S.l.]: IEEE Computer Society, 2008. ISBN 978-0-7695-3310-0.

11 MEDITSKOS, G.; BASSILIADES, N. Object-oriented similarity measures for semantic

web service matchmaking. In: ECOWS. IEEE Computer Society, 2007. p. 57–66. Disponível

em: <http://doi.ieeecomputersociety.org/10.1109/ECOWS.2007.17>.

12 KLUSCH, M.; FRIES, B.; SYCARA, K. P. OWLS-MX: A hybrid semantic web service

matchmaker for OWL-S services. J. Web Sem, v. 7, n. 2, p. 121–133, 2009. Disponível em:

<http://dx.doi.org/10.1016/j.websem.2008.10.001>.

13 YU, L. Introduction to the Semantic Web and Semantic Web Services. [S.l.]: Chapman &

Hall/CRC, 2007. ISBN 1584889330.

14 LIU, C.; PENG, Y.; CHEN, J. Web services description ontology-based service discovery

model. In: Proc. IEEE/WIC/ACM International Conference on Web Intelligence WI 2006.

[S.l.: s.n.], 2006. p. 633–636.

15 CARDOSO, J. Semantic Web Services: Theory, Tools and Applications. [S.l.]: IGI Global,

2007. ISBN 159904045X, 9781599040455.

16 MENEZES, P. B. Matemática Discreta para Computação e Informática. [S.l.]: Sagra

Luzzatto, 2004.

17 YAN, Y.; ZHENG, X. A planning graph based algorithm for semantic web

service composition. In: CEC/EEE. IEEE, 2008. p. 339–342. Disponível em:

<http://dx.doi.org/10.1109/CECandEEE.2008.135>.

18 SHESHAGIRI, M.; DESJARDINS, M.; FININ, T. A Planner for Composing Services

Described in DAML-S.maio 05 2003. Disponívelem: <http://citeseer.ist.psu.edu/579497.html;

http://umbc.edu/ ﬁnin/papers/icaps03.pdf>.

19 WU, D. et al. Automating DAML-S web services composition using SHOP2. In:

FENSEL, D.; SYCARA, K. P.; MYLOPOULOS, J. (Ed.). International Semantic Web

Conference. [S.l.]: Springer, 2003. (Lecture Notes in Computer Science, v. 2870), p. 195–210.

ISBN 3-540-20362-1.

20 HULL, R.; SU, J. Tools for composite web services: a short overview. SIGMOD Rec.,

ACM, New York, NY, USA, v. 34, n. 2, p. 86–95, 2005. ISSN 0163-5808.

21 WEISE, T. et al. Different approaches to semantic web service composition. In: IEEE.

Proceedings of The Third International Conference on Internet and Web Applications and

Services, ICIW 2008. Athens, Greece: IEEE Computer Society Press, 2008. Disponível em:

<http://www.it-weise.de/documents/ﬁles/WBCG2008ICIW.pdf>.

22 XU, B. et al. Swsds: Quick web service discovery and composition in sewsip. In:

CEC-EEE ’06: Proceedings of the The 8th IEEE International Conference on E-Commerce

REFERÊNCIAS BIBLIOGRÁFICAS 64

Technology and The 3rd IEEE International Conference on Enterprise Computing,

E-Commerce, and E-Services. Washington, DC, USA: IEEE Computer Society, 2006. p. 71.

ISBN 0-7695-2511-3.

23 PALIWAL, A. V.; ADAM, N. R.; BORNHOVD, C. Web service discovery: Adding

semantics through service request expansion and latent semantic indexing. In: Proc. IEEE

International Conference on Services Computing SCC 2007. [S.l.: s.n.], 2007. p. 106–113.

24 PIETRO, I. D. et al. Semantic web service selection at the process-level: The

ebay/amazon/paypal case study. In: Proc. IEEE/WIC/ACM International Conference on Web

Intelligence and Intelligent Agent Technology WI-IAT ’08. [S.l.: s.n.], 2008. v. 1, p. 605–611.

25 RUSSELL, S.; NORVIG, P. Artiﬁcial Intelligence: A Modern Approach (Second Edition).

[S.l.]: Prentice Hall, 2003.

26 ZHANG, Y. et al. Strategies for efﬁcient syntactical and semantic web services. In: . Los

Alamitos, CA, USA: IEEE Computer Society, 2006. v. 0, p. 72. ISBN 0-7695-2511-3.

27 CHAHOUD, J. J. Planejamento para Serviços Web Semânticos. Tese (Doutorado) —

Universidade de São Paulo, 2006.

28 FERBER, J. Multi-Agent Systems: An Introduction to Distributed Artiﬁcial Intelligence.

[S.l.]: Addison-Wesley Professional, 1999. Paperback. ISBN 0201360489.

29 FERNáNDEZ, A.; OSSOWSKI, S. Filters for semantic service composition in

service-oriented multiagent systems. In: AAMAS ’07: Proceedings of the 6th international

joint conference on Autonomous agents and multiagent systems. New York, NY, USA: ACM,

2007. p. 1–3. ISBN 978-81-904262-7-5.

30 KUMAR, S.; MISHRA, R. B. Multi-agent based semantic web service composition

models. INFOCOMP Journal of Computer Science, v. 7, n. 3, p. 42–51, 2008.

31 ALMEIDA M., B. M. Uma visão geral sobre ontologias: pesquisa sobre deﬁnições, tipos,

aplicações, métodos de avaliação e de construção. Ciência da Informação, v. 32, n. 3, 2004.

Disponível em: <http://revista.ibict.br/index.php/ciinf/article/view/17>.

32 BENER, A. B.; OZADALI, V.; ILHAN, E. S. Semantic matchmaker with precondition

and effect matching using swrl. Expert Syst. Appl., Pergamon Press, Inc., Tarrytown, NY,

USA, v. 36, n. 5, p. 9371–9377, 2009. ISSN 0957-4174.

33 BUHLER, P. A.; GREENWOOD, D.; WEICHHART, G. A multiagent web service

composition engine, revisited. E-Commerce Technology, IEEE International Conference on,

and Enterprise Computing, E-Commerce, and E-Services, IEEE International Conference on,

IEEE Computer Society, Los Alamitos, CA, USA, v. 0, p. 529–532, 2007.

34 BäCK, T. Evolutionary algorithms in theory and practice: evolution strategies,

evolutionary programming, genetic algorithms. Oxford University Press, Oxford, UK, 1996.

REFERÊNCIAS BIBLIOGRÁFICAS 65

35 XU, J.; REIFF-MARGANIEC, S. Towards heuristic web services composition using

immune algorithm. Web Services, IEEE International Conference on, IEEE Computer Society,

Los Alamitos, CA, USA, v. 0, p. 238–245, 2008.

36 CLARO, D. B.; ALBERS, P.; HAO, J. kao. J.k.: Selecting web services for optimal

composition. In: In Proceedings of the 2nd International Workshop on Semantic and Dynamic

Web Processes (SDWP 2005. [S.l.: s.n.], 2005. p. 32–45.

37 DIBERNARDO, M.; POTTINGER, R.; WILKINSON, M. Semi-automatic web

service composition for the life sciences using the biomoby semantic web framework.

Journal of Biomedical Informatics, v. 41, n. 5, p. 837–847, 2008. Disponível em:

<http://dx.doi.org/10.1016/j.jbi.2008.02.005>.

38 VIEIRA, R. V. Um Algoritmo Genético Baseado em Tipos Abstratos de Dados e sua

Especiﬁcação em Z. Tese (Doutorado) — Universidade Federal de Pernambuco, 2003.

39 SANTOS, F. C.; CARVALHO, C. L. de. Aplicações de Suporte àWeb Semântica. [S.l.],

2007.

40 MARTINO, B. D. Semantic web services discovery based on structural ontology

matching. Int. J. of Web and Grid Services, Inderscience Publishers, v. 5, p. 46–65, mar. 17

2009. ISSN 1741-1114. Disponível em: <http://www.inderscience.com/link.php?id=23868>.

41 MCILRAITH, S. A.; MARTIN, D. L. Bringing semantics to web servi-

ces. IEEE Intelligent Systems, v. 18, n. 1, p. 90–93, 2003. Disponível em:

<http://csdl2.computer.org/dl/mags/ex/2003/01/x1090.pdf>.

42 MCGUINNESS, D. L.; WELTY, C.; SMITH, M. K. OWL Web Ontology Language Guide.

[S.l.], fev. 2004. Http://www.w3.org/TR/2004/REC-owl-guide-20040210/.

43 BAEZA-YATES, R. A.; RIBEIRO-NETO, B. Modern Information Retrieval. Boston,

MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1999. ISBN 020139829X.

44 MANNING, C. D.; RAGHAVAN, P.; SCHTZE, H. Introduction to Information Retrieval.

New York, NY, USA: Cambridge University Press, 2008. ISBN 0521865719, 9780521865715.

45 BERRY, M. W.; DRMAC, Z.; JESSUP, E. R. Matrices, vector spaces, and information

retrieval. SIAM Rev., Society for Industrial and Applied Mathematics, Philadelphia, PA, USA,

v. 41, n. 2, p. 335–362, 1999. ISSN 0036-1445.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 