O que é recozimento simulado?

O recozimento simulado é uma técnica de computador que pode encontrar boas - embora não necessariamente ótimas - soluções para um problema. É assim chamado porque imita o processo metalúrgico de recozimento. Nos metais, o recozimento é o processo de purificação, aquecendo o metal e depois esfriando-o lentamente. O programa de computador "purifica" o espaço da solução até que tudo o que resta são soluções melhores ou quase melhores.

Existem dois fatores críticos que o usuário de um programa de recozimento simulado precisa especificar: a temperatura inicial ou a porcentagem de soluções piores que podem ser exploradas; e a taxa de resfriamento, que é a taxa na qual essa porcentagem é reduzida. Uma temperatura inicial baixa geralmente termina com um resultado distante do ideal. A partir de uma temperatura muito alta, a pesquisa pode demorar muito mais do que o necessário. Da mesma forma, uma taxa de resfriamento muito alta gerará resultados ruins, enquanto uma taxa de resfriamento muito baixa resultará em um programa que será executado por um período muito longo.

O estado "alta temperatura" para o programa de recozimento simulado é uma configuração que permite analisar uma ampla variedade de soluções, incluindo muitas que são piores do que as soluções já encontradas. O computador pode procurar muitas soluções que são piores que a solução atual, para evitar manter um mínimo local substancialmente pior que o melhor. Como exemplo, pode-se imaginar começando no topo de uma colina ou montanha com o objetivo de alcançar a base. Ao longo do caminho, pode haver voçorocas ou abismos. Se o computador não conseguir subir o suficiente para sair, ele ficará preso, mesmo que não esteja nem perto da base.

O nível de subida do programa é determinado pela porcentagem de piores soluções que o programa pode examinar. Com o passar do tempo, soluções progressivamente melhores são encontradas e o risco de um abismo profundo diminui, diminuindo a porcentagem de soluções piores que o computador pode explorar. Diminuir essa fração é conhecido como "resfriamento". Quando a temperatura atinge uma fração predefinida - que não precisa ser 0 -, a pesquisa termina.

O motivo para usar o recozimento simulado ou outras técnicas de pesquisa de inteligência artificial é reduzir para uma quantidade gerenciável o tempo necessário para encontrar uma solução quase ideal. Para muitos problemas, uma pesquisa exaustiva - o teste de cada solução possível entre si - pode levar meses ou anos. A alternativa mais conhecida ao recozimento simulado são algoritmos genéticos. Outros algoritmos populares de busca de inteligência artificial incluem otimização de colônias de formigas, otimização de enxame de partículas, vizinho mais próximo e classificadores bayesianos.