Otimização Combinatória

Otimização é o processo de buscar a melhor solução dentre um conjunto de soluções disponíveis para um problema.

Possui três elementos: as varáveis de decisão (parâmetros para solução do problema), função objetivo (função a ser maximizada e minimizada) e as restrições (define o espaço de soluções desejadas).

Em um sistema de produção as variáveis de decisão podem representar as quantidades produzidas de determinados objetivos; a função objetivo pode ser o interesse relacionado aos custos na produção,(maximizar os ganhos ou minimizar os custos); e as restrições podem ser as limitações operacionais do processo de produção, como quantidade de objetos a serem utilizados.

Otimização Combinatória tenta determinar valores a variáveis de decisão, de modo que uma função desenvolvida utilizando essas variáveis seja otimizada na presença de um conjunto de restrições e pesos associados as variáveis.

Um problema que pode ser modelado como um grafo, pode ser dito como um Problema de Otimização Combinatória.

Podem ser de cinco classes:

• Problemas de conexão: Árvores, Caminho e Emparelhamento. Ex: Árvore Geradora Miníma, N-Rainhas, Caminho Mínimo, e Emparelhamento Bipartido, etc.
• Problemas de Fluxo em Redes: Processo de otimização da distribuição de itens originados em um vértice e consumidos em outros vértices. Ex: Transporte, Alocação, Problema do Transbordo, etc.
• Problema do Caixeiro Viajante: Encontrar o menor custo que se inicie e termine em um vértice passando pelos demais, sem repetição.
• Problemas de Roteamento: Atender demandas localizadas nas arestas ou nos vértices de uma rede. Problema do Carteiro Chines, Roteamento de Veículos e Escala de Tripulação.
• Problemas de Cobertura e Particionamento: É quando se procura o menor conjunto de vértices/arestas tal que toda(o) aresta/vértice do grafo incida em um(a) destes(as) vértices/arestas. Ex: Localização de Facilidades, Localização de Antenas e Radares.

Um conjunto de soluções viáveis, nesse tipo de problema, é muito grande, embora finito. Impossibilitando o uso de busca bruta, que testa todos os valores de soluções possíveis. Para algumas classes é possível utilizar métodos exatos de resolução, a Programação Matemática. Para outras há a necessidade de métodos não-exatos, tais como Heurísticas (Busca Gulosa, Busca em Profundidade, Algoritmo de Dijkstra, Algoritmo de Kruskal, etc) ou Metaheurísticas (Busca Tabu, Algoritmos Genéticos ou Colônia de Formigas).

Fonte: Pires, M. G. Abordagem Neuro-Genética para Mapeamento de Problemas de Conexão em Otimização Combinatória. Tese (Doutorado) - Escola de Engenharia de São Carlos, Universidade de São Paulo. 2009.

Sistemas Híbridos Inteligentes

Segundo Osorio e Vieira (1999) Sistemas Híbridos Inteligentes, de maneira geral, são sistemas que integram dois ou mais métodos diferentes para a solução de um problema.

Neste post não irei listar minuciosamente todos os sistemas híbridos existentes (quem sabe em postagens futuras possa abranger mais o assunto) mas sim apresentar uma visão mais geral sobre os tipos de Sistemas Híbridos Inteligentes mais comuns.

Os sistemas híbridos são úteis pois permitem que uma técnica complemente a outra, cobrindo as suas deficiências, obtendo um melhor desempenho.

Em se tratando de Machine Learning, usar sistemas híbridos pode também trazer a vantagem deste poder adquirir novas informações, fazendo com que esse sistema não tenha apenas uma visão limitada pelas suas restrições.

Os Sistemas Híbridos Inteligentes procuram de certa forma "imitar" o modo como os seres humanos solucionam um problema ao usar diferentes modos de raciocínio. Isso é realizado de formas diversas, uma delas é através da combinação das diferentes técnicas, buscando trocar informações e conhecimento entre seus módulos, o que dá a característica de evolução no tempo. Outra é através da utilização de representações de conhecimento através de regras difusas, probabilísticas, regras e predicados lógicos.

Temos assim um sistema mais robusto e que aceita algumas contradições e conflitos cognitivos entre seus módulos. Mas se for bem explorado pode trazer grandes vantagens.

Existem muitos tipos de Sistemas Híbridos Inteligentes Osorio e Vieira (1999) listaram alguns deles dando ênfase aos sistemas que utilizam os paradigmas de representação do conhecimento por meio simbólico, compreensível ao ser humano (Lógica, Redes semânticas, Frames, scripts), e métodos conexionista (Redes Neurais Artificiais).

São eles:

• Sistemas Simbólico-Difusos: Integram lógica nebulosa (lógica fuzzy) e sistemas especialistas baseados em conhecimento e/ou regras.
• Sistemas Simbólico-Genéticos: Normalmente compostos por algum método de computação evolutiva, responsável pela aquisição do conhecimento, e de um módulo simbólico, responsável pela implementação de mecanismos de inferência simbólica.
• Sistemas Neuro-Genéticos: Utilizam, também, de computação evolutiva, na tentativa de contornar os problemas de escolha da arquitetura da rede neural.
• Sistemas Neuro-CBR: Integração de uma rede neural e um sistema baseado em casos permitindo fazer generalização sobre um conjunto de exemplos de um problema.
• Sistemas Neuro-Simbólicos: É considerado o método mais estudado. Combina a representação conexionista com a representação simbólica, esse tipo de Sistema Híbrido Inteligente pode ser subdividido em outras três categorias
• Sistemas Neuro-Fuzzy: A lógica nebulosa e as redes conexionistas são combinadas.
• Sistemas Neuro-IDT: Combinam a rede neural com árvores de decisão.
• Sistemas Neuro-KBS: Combinam a rede neural com sistemas baseados em conhecimento.

Fonte: Osório, F. e Vieira, R. Sistemas Híbridos Inteligentes. XIX congresso da SBC. ENIA'99 - Encontro Nacional de Inteligência Artificial. 1999