Brincando com Algoritmos de Otimização

Como parte do ferramental computacional que muitos precisamos utilizar em nossas pesquisas, tive contato com o conceito de otimização esta semana. O material foi proposto por Jacques Sauvé, no contexto de uma disciplina da pós-graduação em Ciência da Computação da UFCG. A disciplina tem foco em modelagem matemática na pesquisa científica, e depois de dar uma olhada no material dele sobre algoritmos de otimização, fui procurar utilização dos conceitos tanto em artigos como em brinquedos.

Ainda não li os trabalhos que encontrei, mas pareceram muito legais para contextualizar a utilização deste tipo de algoritmo, como é o caso de:

• Link prediction by de-anonymization: onde os autores utilizaram Simulated Annealing para "adquirir mais informações" sobre dados de uma competição de predição de links em redes sociais e assim ganharem  a mesma.
• Modularity and community structure in networks: aqui o problema da identificação de "clusters" dentro de redes é abordado a partir de algoritmos de otimização. O mais interessante é que o autor comenta que algoritmos como o Simulated Annealing já não são uma boa opção para os problemas atuais em redes sociais por conta de seus requisitos de recursos computacionais.

Além da busca de artigos na minha área de atuação, fiquei curioso para brincar com algum problema resolvido com otimização. Encontrei este post bem recente de um professor de estatística, que implementou um algoritmo (em R) para encontrar soluções para jogos de Sudoku. Como tive que ler e entender o código, acabei inclusive conseguindo ajudá-lo a encontrar um bug (ツ), mas ainda assim o algoritmo não parece solucionar bem o problema. Mas o meu objetivo principal era VER a coisa acontecendo, por isso instrumentei o código dele para plotar o resultado (em tempo de execução).

Vendo um resultado de execução do código acima (linhas horizontais na figura abaixo), o algoritmo parece não conseguir "escapar" de um ótimo local mesmo utilizando diferentes valores para a temperatura (tau). Pretendo, assim que eu tiver um tempinho, implementar uma versão com os outros dois métodos comentados no material da aula.

Precisamos lembrar que um Sudoku pode parecer quase solucionado, mas o não encaixe final pode acabar mexendo em grande parte das opções anteriores feitas na solução do jogo. Desta forma, acho que a abordagem de populações dos Algoritmos Evolucionários parece ser uma boa abordagem.

Alguém tem alguma dica?