t1 14 2

Trabalho 1
Inteligˆencia Artificial
15 de Setembro, 2014

1 Motiva¸c˜ao
As metaheur´ısticas s˜ ao bem sucedidas na pr´atica pois balanceiam dois fatores importantes (diversifica¸c˜ ao e intensifica¸ca˜o) durante a busca no conjunto solu¸c˜ao. A motiva¸c˜ao deste trabalho ´e desenvolver uma metaheur´ıstica baseada em uma hist´oria qualquer e fazer com que tenha um bom desempenho na pr´atica. A hist´oria escolhida ´e de zumbi.
Vale lembrar que a escolha n˜ ao foi norteada por nenhum crit´erio t´ecnico-cient´ıfico. Na realidade, foi feita depois de ter lido um livro sobre o assunto. Para os que n˜ao gostam tanto assim de zumbi, nem de metaheur´ıstica, considere a seguinte motiva¸c˜ao: vale nota.1
O trabalho ´e aplicar esse m´etodo ao problema de agrupamento, previamente apresentado na disciplina. O trabalho deve ser desenvolvido em Java e ser integrado no Weka.

2 Os Humanos
Os humanos vivem felizes suas vidas e procuram locais adequados para viver. Tipicamente, sempre s˜ ao encontrados em m´ınimos locais verdejantes, e al´em disso, s˜ao conhecidos por n˜ ao possu´ırem um car´ater muito aventureiro, preferindo a seguran¸ca de seus m´ınimos locais ` a se arriscar em regi˜oes incertas. Contudo, desde o aparecimento do primeiro zumbi essa hist´ oria mudou.
Desde o in´ıcio do apocalipse zumbi os humanos alteraram a forma de definirem “o qu˜ao bom o local ´e”. A f´ ormula abaixo representa como eles avaliam a qualidade de um local (embora sabe-se que alguns deles, em especial os que n˜ao estudam exatas, n˜ao conhe¸cam essa equa¸c˜ ao). f (x) =

g(x), se dist-min(x, Z) > 1N g(x) − µ|Z1 |, se dist-min(x, Z) ≤ 1N

(1)

Na equa¸c˜ ao acima f (x) ´e a qualidade total, g(x) representa a qualidade do local; Z representa a popula¸c˜ ao de zumbi, e dist-min(x,Z) a distancia at´e o zumbi mais pr´oximo
(medida a partir de x); 1N representa uma vizinhan¸ca de distancia, e µ representa o
1

Outra op¸ca
˜o apresentar um algoritmo que encontre a solu¸ca
˜o ´ otima em tempo polinomial