lista 1 Topicos especiais

Prévia do material em texto

Lista 1
 1 - O que é um modelo matemático? Como ele pode ser visto?
Um modelo matemático é uma representação simplificada de uma situação real e deve demonstrar a essência do problema, representando as grandezas envolvidas por variáveis as e as relações de existentes entre elas de expressões matemáticas.
Um modelo matemático pode ser visto como uma Caixa Preta, representando as relações que descrevem a dependência das variáveis.
 2 – Defina um comparativo de modelos, considerando suas características e exemplos.
Modelo Tipo Físico
Características: Tangível; fácil compreensão; Reprodução difícil; Manipulação difícil; Escopo uso muito baixo.
Exemplos: Modelo Aeronaves; Modelo de Residências; Modelos de Cidades.
Modelo Tipo Analógico
Características: Intangível; compreensão difícil; reprodução mais difícil; manipulação mais difícil; escopo de uso baixo.
Exemplos: Mapa de estradas; velocímetro; gráficos.
 3 – Apresente o diagrama da forma gela de modelos
 4 – Descreva 3 definições de Sistema.
“Uma agregação ou montagem de coisas de tal forma combinada pela natureza ou pelo homem que forma um todo integral ou complexo. ” [Enciclopédia Americana]
“Um grupo de coisas inter-atuantes e interdependentes que formam um todo unificado. ” [Dicionário Webster's]
“Uma combinação de componentes que agem conjuntamente para completar uma função não possível para quaisquer das partes individuais. ” [Dicionário Padrão da IEEE de Termos Elétricos e Eletrônicos]
 5 – Apresente e descreva 2 exemplos clássicos de problemas de otimização combinatória
Dois exemplos clássicos da otimização: Maximizar e Minimizar
Maximizar: O que obtemos? Maior lucro; Melhor desempenho ou potência; maior retorno; o aumento ou máximo possível de um processo.
Minimizar: O que obtemos? Menor perda; menor prejuízo; Menor Gasto; A diminuição ou o mínimo possível de um processo.
6. Apresente 3 Desafios Computacionais que a otimização combinatória apresenta.
• resolver problemas de otimização combinatória pertencentes a classe NP-hardou NP-completocom pouco esforço computacional (tempo de execução). 
• encontrar soluções ótimas, ou mesmo aproximadas, para esses tipos de problemas é um desafio nem sempre fácil de ser vencido 
• Em muitos problemas práticos não há a necessidade de encontrar uma solução “teoricamente” ótima.
 7 – O que é heurística? Qual sua limitação? Os algoritmos heurísticos são capazes de encontrar a solução ótima do problema? Qual objetivo de uma heurística?
Heurística é uma técnica que melhora a eficiência do processo de busca de soluções de um problema; As Heurísticas não são capazes de garantir a solução do problema. Os algoritmos heurísticos são algoritmos que não garantem encontrar a solução ótima de um problema, mas são capazes de retornar uma solução de qualidade em um tempo adequado para as necessidades da aplicação. O objetivo de uma heurística é tentar encontrar uma solução “boa” de maneira simples e rápida.
 8 – Cite e descreva as 5 classificações da heurística que foram comentadas em sala.
1. Métodos construtivos 
Processo iterativo que inicia com uma solução vazia e adiciona um novo elemento a cada iteração até a obtenção de uma solução. 
2. Métodos de decomposição 
Consistem em dividir o problema em subproblemas menores, de modo que as resoluções de todos os subproblemas possam compor uma solução para o problema maior. 
3. Métodos de Redução 
Identificam algumas características que presumidamente deverá possuir a solução ótima e simplifica o problema fixando-se o valor de tais variáveis.
4. Manipulação do Modelo
Modificam o modelo de tal forma que ele fique mais fácil de resolver. Ex. relaxação linear, relaxação lagrangeana. 
5. Métodos de Busca 
Categoria a qual pertencem a maioria das meta-heurísticas: inicia em uma solução (podendo ser obtida a partir de outra heurística) e caminha sobre as soluções vizinhas.
9 – Apresente o algoritmo heurístico do vizinho mais próximo. 
 10 – Descreva, com suas palavras, o algoritmo do vizinho mais próximo
Um dos primeiros algoritmos para desvendar o problema do caixeiro viajante, onde ele gera rapidamente um caminho curto, mas não o ideal. 
– Descreva: 
Espaço de soluções:
O conjunto de todas as soluções (viáveis) possíveis (satisfazendo as restrições do problema)
b) Vizinhança 
Dada uma solução x, os elementos da vizinhança N (x ) de x são aquelas soluções y que pode ser obtida aplicando uma perturbação elementar sobre x.
c) Movimento
É a transição de uma solução para outra solução vizinha
d) Espaço de busca 
O conjunto das soluções obtidas por meio de uma vizinhança.
e) ótimo local 
É uma solução tão boa ou melhor do que qualquer das soluções vizinhas
f) Ótimo global (solução ótima).
É a melhor solução dentre todos os ótimos locais.
- Como os algoritmos de busca local são construídos? Cite e descreva os 3 elementos que devem ser definidos.
Algoritmos de busca local são construídos como uma forma de exploração do espaço de busca.
• Partida: solução inicial obtida através de um método construtivo
• Iteração: melhoria sucessiva da solução corrente através de uma busca na sua vizinhança
• Parada: primeiro ótimo local encontrado, ou seja, não existe solução vizinha melhor.
– Qual a dependência dos algoritmos de busca local? Qual o papel da representação de uma solução? Quais as formas mais adotadas?
Os métodos de busca local são dependentes da forma adotada para representar as soluções, pois a vizinhança de uma solução é obtida a partir da sua representação.
Representação de uma solução: indicar quais elementos estão presentes e quais não estão.
As formas mais adotadas são:
* Vetores de Pertinência
* Combinações
* Permutações
– Descreva e exemplifique “Vetores de pertinência”.
Vetores de pertinência: Vetores onde o mapeamento de cada elemento da solução é feito para cada uma das posições (ou dimensões) do vetor. A presença de um determinado elemento na resposta é representada pelo 1 na posição correspondente. Sua ausência é representada pelo 0 (ou vice-versa)
 15 - Descreva e exemplifique a representação baseada em “Combinações”.
Combinações: Conjuntos contendo exatamente os elementos presentes na resposta (ou exatamente os elementos ausentes).
 16 - Descreva a representação baseada em “Permutações”.
Conjunto ordinal (contendo todos os elementos) indicando a ordem com que estes aparecem na solução. (ex.: lista de cidades visitadas para o problema do caixeiro viajante).
 17 – O que são Metaheuristicas? Como são baseados seus modelos? Quais seus objetivos?
Metaheurísticas são modelos gerais que servem como guia para construção de algoritmos heurísticos. Muitos dos modelos são baseados na natureza (físicos, biológicos, evolutivos). Uma meta-heurística representa uma classe de heurísticas. As estratégias metaheurísticas tem como objetivo superar as falhas da busca local, como por exemplo, o término prematuro em um ótimo local.
 18 – Quais as propriedades desejadas em uma Metaheuristica?
• Simplicidade
–Baseadas em princípios simples e claros
• Coerência
–A instanciação deve ser intuitiva
• Generalidade
–Capacidade de solucionar diferentes problemas
• Eficácia
–Fornece soluções ótimas ou quase ótimas
• Eficiência
–Baixo custo computacional
• Robustez
–Performance consistente sobre várias instâncias
19 – Apresente o algoritmo genético (diagrama). Cite e descreva seus termos principais.
Os termos principais são: 
●Mutação:anomalias que causam a alteração aleatória de genes, seja na sua localização, seja no seu conteúdo; 
●Seleção natural:processo que elimina os indivíduos menos adaptados (ou aptos) em relação à cada geração da população; 
●Geração:iteração do algoritmo genético; 
●Aptidão (ou fitness):indicador qualitativo de um indivíduo. O grau de aptidão de um indivíduo é obtido a partir de uma função objetivo; 
●Função objetivo:função matemática que avalia as soluções (indivíduos) em relação ao problema.
Algoritmos Genéticos20 – Apresente o algoritmo Simulated Annealing e comente qual a sua essência
A metalurgia utiliza um processo de tratamento térmico visando alterar a estrutura cristalina de metais conferindo-lhes características mecânicas e estruturais desejadas. Este processo, chamado de recozimento, consiste em aquecer continuamente metais até determinada temperatura, e, posteriormente, resfriá-los em um forno com resfriamento controlado. Diferentes velocidades de resfriamento levam a diferentes propriedades nos metais. Um resfriamento muito rápido acarreta em imperfeições nos cristais metálicos. Já um resfriamento muito lento leva à formação de cristais muito grandes. Baseado neste processo, foi criado o método heurístico chamado simulated annealing(SA), ou recozimento simulado, em português. Neste método, parte-se de uma solução viável de um problema e passa-se a aceitar soluções vizinhas.
Note que a medida que a temperaturat diminui, o valor deexp(-Δ/t) aumenta, consequentementehaverá menor chance de se gerar um número aleatório maior que este valor e, portanto, menor probabilidade de uma solução ruim ser aceita. É exatamente esta a essência do SA. Caso o valor de r seja muito pequeno, haverá um resfriamento rápido, fazendo com que o algoritmo se limite a uma busca local (Colin, 2007). Entretanto, um r muito grande (próximo de 1) faz com que o algoritmo possa gastar muitas iterações com soluções ruins. Para um problema de maximização, este algoritmo pode ser facilmente adaptado.