Algoritmo Genético Para o Problemas das P-Medianas

[pic 1]

UNIVERSIDADE FEDERAL DE VIÇOSA

CAMPUS DE RIO PARANAÍBA

INSTITUTO DE CIÊNCIAS EXATAS E TECNOLÓGICAS

[pic 2]

JORDI HENRIQUE MARQUES DA SILVA – 3927

Algoritmo Genético para o Problemas das P-Medianas

RIO PARANAÍBA – MG

JANEIRO/2018

Resumo

Descrevo um algoritmo para o problema das P-medianas, este problema é de alta complexidade computacional, por se tratar de uma análise combinatória.

Dado um conjunto C formado de n objetos (C{C1,C2, ...Cn}) com p atributos sejam qualitativos e/ou quantitativos, deve-se selecionar a partir de c, k objetos que definem um conjunto M de  medianas, de forma a minimizar a  soma das distâncias de cada um dos (n-k) objetos restantes a sua mediana mais próxima.

Neste trabalho propõe-se como solução um algoritmo genético como meta-heurística, onde por meio de fatores de evolução e representação guiados apenas pela função objetivo do problema leva a soluções com alto nível de satisfação.

Palavras chaves: Algoritmo Genético, Medianas,Meta-Heurística.

1. Introdução

Este Artigo trata-se de um problema das P-medianas, que pode ser classificado como P-medianas capacitado, P-medianas não capacitado e P-medianas custo fixo, neste documento iremos tratar do problema não capacitado cujo seu objetivo é minimizar a soma de todos vértices até a mediana mais próxima.

A solução exata deste problema seja capacitado ou não-capacitado, pode ser atingida pelo modelo matemático inteiro.  Para quantidades n de Objetos moderada, a solução pode ocasionar consumo alto de tempo computacional, ou até mesmo a não convergência resultando apenas em uma solução admissível.

 Propõe-se como solução a aplicação de algoritmos genéticos como meta heurística (não exata), é composta dos procedimentos de criação de uma população inicial (conjunto de soluções), na qual iram passar pelos processos de seleção para a sobrevivência e cruzamento, crossover e mutação. A representação é feita por vetores de números reais que identificam as medianas.

1. REVISÃO DA LITERATURA

Nesta etapa do trabalho iremos descrever e formular o problema das P-medianas e introduzir o método de cálculo entre as distâncias dos vértices.  

2.1        Problema das P-medianas.

        Dado um conjunto C formado de n objetos (C{C1,C2, ...Cn}) com p atributos sejam qualitativos e/ou quantitativos, deve-se selecionar a partir de c, k objetos que definem um conjunto M de  medianas, de forma a minimizar a  soma das distâncias de cada um dos (n-k) objetos restantes a sua mediana mais próxima.

 [pic 3]

O problema das k -medianas e algumas de suas variantes aparecem em muitas situações do mundo real, tais como: localização de indústrias, escolas, redes, facilidades públicas, etc (veja Christofides, 1975).

2.2        Calculo da Distância.

Este trabalho teve como abordagem variáveis quantitativas na qual era recebido os valores (x,y) de cada vértice. O cálculo da distância é feito aplicando a formula de distância euclidiana:

[pic 4]

A distância entre dois objetos Ci e Cj é a raiz quadrada do somatório dos quadrados das diferenças entres os valores i e j para todas variáveis.  

1.  Estratégia  de Solução baseada em Algoritmo Genético

[pic 5]

A meta-heurística algoritmo genético, associa mecanismos de evolução e representação dos genes do indivíduo para resolução de problemas combinatórios de otimização. Os genes são a estrutura que carrega as características dos indivíduos. .A aptidão neste contexto trata-se de um contexto para qualificar o indivíduo, este termo costuma estar associado a função matemática que define o problema.

Um algoritmo genético é composto pelas seguintes etapas: avaliação da aptidão dos indivíduos, criação da população inicial, seleção para reprodução, crossover e mutação, seleção para sobrevivência, o algoritmo chega ao fim ao ter atingido um critério de parada definido.

Neste trabalho teremos a taxa de cruzamento de 70%, a taxa de mutação é de 15% e o método de seleção para sobrevivência será geracional, ou seja, todos os filhos substituem os pais.

3.1 Instâncias  

Neste método de solução, requerem como dado de entrada, o conjunto de Objeto e suas respectivas localização ou seja os vértices (x,y) ,  o número k de medianas, segue um exemplo de instâncias:

...