Análise e Proposta de otimização dos algoritmos aplicados ao problema da árvore geradora multiobjetivo

Anexo II

Formulário para o Projeto de Pesquisa/Monografia

1-Identificação do Projeto:
Título: Análise e proposta de otimização dos algoritmos aplicados ao problema da árvore geradora multiobjetivo.
Início: Mar/2015	Duração Prevista:18 meses
Tipo de Pesquisa:
( X ) Laboratorial	( ) Estudo de caso	(   ) De campo	( ) Bibliográfica	(  ) Outro:
Palavras- Chaves:
1. Teoria dos Grafos	2. Árvore geradora multiobjetivo	3. Algoritmos de Prim e Kruskal
2-Dados sobre o local onde será executado o Projeto:
Local de Execução: Universidade Federal do Piauí
Laboratório/Sala da instituição, quando for o caso:  LIPPO
Endereço: Rua Cicero Duarte	Telefone/Ramal: (89) 3422-1093
3-Dados da Orientadora:
Nome Completo: Patrícia Medyna Lauritzen de Lucena Drumond
Endereço Profissional: Rua Cícero Duarte
E-Mail: [e-mail]	Celular: (89) 9919-1244
Currículo Lattes (data da última atualização): 13/07/2014
Maior Titulação::
(  ) Especialista	( X ) Mestre	(   ) Doutor	(   ) Pós-Doutor
4-Dados do(a)  Acadêmico (a) proponente:
Nome Completo: Lucas Benjamim de Freitas Moura
RG (número/órgão emissor): 2.618.456/SSP	Data de Nascimento: 01/04/1993
CPF: 054.988.323-11	Sexo: Masculino
Endereço: Rua Cônego João - 468	Telefone Residencial: (89) 3462-3492
E-Mail: [e-mail]	Celular: (86) 9801-5482
Nome do Curso: Bacharelado em Sistemas de Informação
Período da Graduação: 4 anos	No do Registro Acadêmico:
5 – Resumo
Os problemas clássicos de otimização servem de modelo para diversos problemas reais, por exemplo, o problema da Árvore Gerador Multiobjetivo serve para modelar projetos de redes de infraestrutura de água, energia, sinal de TV, gás, esgoto, etc. O presente trabalho tem como objetivo desenvolver um estudo sobre algoritmos de otimização usados para solucionar o problema da árvore geradora multiobjectivo e propor uma melhoria. A relevância do trabalho se dá por uma comparação detalhada entre esses algoritmos, expondo suas principais características e informando qual o mais eficiente. A pesquisa será de grande ajuda para os usuários que ainda não tem um conhecimento especifico sobre grafos e algoritmos de otimização, auxiliando na escolha de qual desses usar em seus estudos. Inicialmente, serão realizados estudos sobre problemas em grafos envolvendo algoritmos de otimização além de um estudo detalhado de cada um desses algoritmos. Após a implementação, os algoritmos serão testados e comparados.
6 – Introdução
Muitas situações do dia-a-dia podem ser descritas por um conjunto de objetos que se relacionam, rotas turísticas, mapeamento de rodovias, esquema de abastecimento de uma cidade, o simples caminho da sua casa ao trabalho, etc. Todas essas situações podem ser vistas como exemplos de grafos, sendo modeladas a partir deste conceito para busca de soluções utilizando problemas clássicos de otimização, como é o exemplo do problema da árvore geradora mínima. No entanto, existem problemas do cotidiano que necessitam otimizar mais de um critério. Observe que, num projeto de roteamento de veículos, deve-se otimizar a rota, levando-se em consideração os critérios de custo do desenvolvimento do projeto e a rota. Nem sempre, a menor rota tem o menor custo, e vice-versa. O problema da árvore geradora multiobjetivo vem despertando o interesse de pesquisadores da área de pesquisa operacional por ser classificado como um problema NP–Difícil e por apresentar inúmeras aplicações práticas na área de transportes, energia, telecomunicações, biologia molecular e agrupamento de dados (HAOUARI; CHAOUACHI, 2006). Visando auxiliar as pesquisas e projetos de usuários que terão um primeiro contato com assunto, o presente trabalho propõe um estudo sobre a teoria dos grafos e o problema da árvore geradora multiobjetivo e uma análise dos algoritmos mais utilizados para otimização deste, tendo como finalidade descobrir qual o mais eficiente e propor uma melhoria. Na implementação dos testes será necessário imaginar situações reais onde grafos dos mais variados tipos são usados e o problema da árvore multiobjetivo se aplica a eles. Os algoritmos serão aplicados aos grafos e ao final será comparado aos resultados obtidos por cada um.
7 –Objetivo Geral
O presente trabalho tem por objetivo geral realizar uma análise comparativa dos algoritmos de otimização aplicados ao problema da árvore geradora multiobjeto, apresentar o mais eficiente e propor melhorias.
8 – Objetivos Específicos
Estudar e compreender o problema da árvore geradora multiobjetivo; Estudar e compreender o conceito de algoritmos de otimização e a teoria dos grafos; Comparar a eficiência de algoritmos heurísticos (Prim e Kruskal) em grafos; Analisar os resultados obtidos e propor melhorias.
9 – Referencial Teórico
9.1 Teoria dos grafos A teoria dos grafos é um ramo da matemática que faz um estudo de objetos e suas relações dentro de determinado conjunto. Para tal são empregadas estruturas chamadas de grafos. Um grafo pode ser representado por quaisquer dois ou mais objetos que se relacionem. Outra representação para tal é em forma de diagrama, onde os pontos são os vértices e as linhas que os ligam são as arestas. Por meio de um grafo é possível representar de maneira simplificada um problema do mundo real. Matematicamente são representados por G(V,A), onde V representa o conjunto dos vértices e A é representado pelo conjunto de pares não ordenados de V, chamados de arestas. Considere um grafo G(V,A), de vértices V1 e V2. Os vértices se relacionam através das arestas e esse relacionamento é descrito pelo comportamento das mesmas. Se todos os vértices tem relação de reciprocidade, ou seja, V1 está para V2, assim como V2 está para V1, classifica-se como grafo comum (Figura 1). Já no caso de não haver reciprocidade entre os vértices, ou seja A está para B, mas B não está para A, as arestas são direcionais e o sentido é definido de acordo com relação de superioridade entre os vértices, a aresta superior aponta para o subordinado. Esse tipo de grafo é conhecido como digrafo (Figura 2). [pic 2] Figura 1 – Exemplo de Grafo Comum, (FEOFILOFF P., 2015). [pic 3] Figura 2 – Exemplo de Digrafo, (FEOFILOFF P., 2015). Se um grafo é conexo (existe um caminho possível entre quaisquer dois vértices) e acíclico (não possui ciclo) ele é uma árvore. A árvore geradora desse grafo é um subgrafo que conecta todos os vértices. Um grafo pode possuir várias árvores geradoras. Considerando que esse grafo seja valorado (existam valores para as arestas), cada árvore geradora terá um peso final, calculado pela soma dos pesos das arestas que a compõe. Uma árvore geradora mínima é aquela com menor peso em relação as outras árvores geradoras do grafo, em outras palavras é a árvore que contém o caminho de menor custo para locomover-se entre quaisquer dois pontos. Segundo Goldbarg e Luna (2002), o problema da Árvore Geradora Mínima (AGM) pode ser descrito da seguinte forma: considere uma rede não direcionada, conectada e associada a cada arco um valor (peso, tempo, etc.) não negativo, o objetivo é encontrar o caminho mais curto de tal maneira que os arcos forneçam um caminho entre todos os pares de nós. 9.2 Algoritmos de otimização Ao analisar o problema da árvore geradora multiobjetivo, estudiosos decidiram criar algoritmos de otimização para auxiliar na resolução do mesmo. Baseados na técnica gulosa (o algoritmo escolhe a melhor solução momentânea, fazendo uma escolha ótima local na esperança de que leve a uma solução ótima global), os algoritmos aplicados a esse problema tem como finalidade analisar e calcular a árvore geradora multiobjetivo de um grafo. Existem vários algoritmos dessa espécie, nesse trabalho serão analisados os mais utilizados, o de Prim e o de Kruskal. 9.2.1 Algoritmo de Prim Dado um ponto de partida, o algoritmo de Prim, através de uma estratégia gulosa, escolhe a aresta que faz parte da franja (arestas que ligam vértices marcados a não marcados) e que tem o menor custo. Em seguida é feito o mesmo procedimento, considerando que agora o subgrafo possui dois vértices marcados, então deve-se analisar a nova franja para os dois vértices. O algoritmo segue essa analogia até que todos os vértices tenham sido marcados e exista um caminho que ligue quaisquer vértices. É importante ressaltar que uma aresta que liga dois pontos marcados, não é considera parte da franja, pois fazendo uma escolha desse tipo um ciclo seria formado. O algoritmo funciona da seguinte forma: escolha um vértice V como ponto de partida do subgrafo; enquanto houver vértices não pertencentes ao subgrafo; selecione uma das aresta que pertença a franja; insira a aresta e seu vértice no subgrafo. Para ficar mais claro, imagine um grafo G(V,A), conexo e valorado, de vértices A,B,C,D,E,F. As figuras 3,4,5 e 6, descrevem o comportamento do algoritmo em G. [pic 4] Figura 3 – Grafo original Escolhendo o vértice A como ponto de partida, tem-se as arestas AB, AF e AE como possíveis caminhos a seguir. Seguindo a lógica do algoritmo guloso, a aresta escolhida é AF pois seu peso é menor, como descreve a figura: [pic 5] Figura 4 – A aresta AF é incluída no subgrafo. Continuando com a lógica do algoritmo e considerando a franja para os vértices A e F, nota-se as arestas BF, AB, AE, FE e FC, como possíveis caminhos. Pelos critérios da técnica usada, BF é a melhor escolha, então: [pic 6] Figura 5 – A aresta FB é incluída no subgrafo Mantendo os mesmos critérios de marcação de vértices, o algoritmo percorrerá o grafo da seguinte forma até encontrar a árvore geradora: [pic 7] Figura 6 – Representação de como o algoritmo vai marcando os vértices e ao final encontrando a árvore geradora multiobjetivo. 9.2.2 Algoritmo de Kruskal Seguindo a mesma técnica gulosa de Prim, o algoritmo de Kruskal se difere por relacionar vértices marcados e não marcados em florestas e subflorestas. Uma subfloresta de um grafo conexo G com custos nas arestas é qualquer floresta que seja subgrafo de G. Uma floresta geradora de G é qualquer subfloresta que tenha o mesmo conjunto de vértices que G. Uma aresta de G é externa em relação a uma subfloresta geradora F se liga duas árvores de F, ou seja, se tem uma ponta em uma árvore de F e outra ponta em outra árvore de F.  Se a é uma aresta externa então é claro que a não está em F e F + a é uma floresta (FEOFILOFF P., 2015). Em um grafo, o algoritmo procura pela aresta de menor peso e marca os vértices que a compõem, criando assim uma floresta. Se em dado momento mais de uma aresta possuir o menor valor possível, é escolhida aleatoriamente uma das duas. O comportamento é sempre o mesmo até que todas as florestas estejam ligadas, formando a árvore geradora. Como em Prim, deve-se escolher arestas evitando a criação de ciclos. O algoritmo se descreve da seguinte forma: considere uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore separada; crie um conjunto A contendo todas as arestas do grafo; enquanto A for não-vazio, faça; remova uma aresta com peso mínimo de A; se essa aresta conecta duas árvores diferentes, adicione-a à floresta, combinando duas árvores numa única árvore parcial; caso contrário, descarte a aresta . Para ficar mais claro, imagine um grafo G(V,A), conexo e valorado, de vértices A,B,C,D,E,F. As figuras 7,8,9, 10 e 11, descrevem o comportamento do algoritmo em G. [pic 8] Figura 7 – Grafo original. Seguindo a lógica do algoritmo, a aresta AB é a primeira a ser escolhida: [pic 9] Figura 8 – A aresta AB é a primeira a ser escolhida. Nessa etapa duas arestas possuem o menor valor possível, a aresta AF e a aresta CD. Como foi dito, escolhe-se aleatoriamente uma das duas. Considere que a escolhida foi a CD, então: [pic 10] Figura 9 – A aresta CD é escolhida. Após essa escolha, nota-se a formação de duas florestas no grafo. Seguindo o raciocínio, a próxima aresta a ser escolhida é a AF: [pic 11] Figura 10 – Aresta AF é escolhida. Continuando a execução do algoritmo, a aresta FE será a próxima escolhida e por fim a aresta BC, encontrando a árvore geradora multiobjetivo: [pic 12] Figura 11 – As arestas FE e BC são escolhidas, respectivamente, finalizando o algoritmo e encontrado a árvore geradora multiobjetivo.
10 – Formulação da hipótese de trabalho
O objetivo principal do projeto é compreender o funcionamento e a proposta de otimização de algoritmos usados para resolver problemas em grafos, tendo como foco o problema da árvore geradora multiobjetivo. Por fim, propor uma melhoria para tais algoritmos.
11 – Material e Métodos:
Para o estudos descrito no trabalho será necessário: Um computador com suporte à linguagem C; Linguagem C; Grafos e suas aplicações; Algoritmos de otimização aplicados ao problema em questão. De início, será feito um estudo para entender grafos e suas aplicações, tendo foco em um problema específico. Em seguida, é feita uma análise dos algoritmos e seu comportamento em relação ao problema. Por fim, os resultados de cada algoritmo são analisados e comparados e uma melhoria será proposta.
12 – Bibliografia Base
GOLDBARG, M.; GOLDBARG, E. Grafos: Conceitos, Algoritmos, Aplicações. Rio de Janeiro. HAOUARI, M.; CAOUACHI, J. S., Upper and lower bounding strategies for the generalized minimum spanning tree problem. European Journal of Operational Research, v. 171, p. 632-647, 2006. COSTA, Polyanna Possani Da, Teoria dos grafos e suas aplicações, Universidade Estadual Paulista "Júlio De Mesquita Filho" Instituto De Geociencias E Ciencias Exatas. 2011 FEOLILOFF P.; KOHAYAKAWA Y.; WAKABAYASHI Y., Uma introdução sucinta a teoria dos grafos, IME-USP, 2011. FEOFILOFF P., Algoritmos para grafos, IME-USP,2015. Disponível em: < http://www.ime.usp.br/~pf/algoritmos_para_grafos/>.
13 - Cronograma de Execução
Especificação das Fases e/ou Etapas do projeto	Ano: 2015-2016
Data de Execução
MAR	ABR	MAIO	JUN	JUL
FORMULAÇÃO DO TEMA	X
LEVANTAMENTO DE REQUISITOS	X	X
ESCRITA DO REFERENCIAL TEÓRICO	X	X	X	X
ANALISE DOS RESULTADOS			X	X
ENTREGA DA VERSÃO FINAL				X
APRESENTAÇÃO DO TRABALHO					X

...