Define-se como nicho natural uma parte de um habitat onde s˜ao estabelecidas algumas condi¸c˜oes especiais de um ecossistema e as esp´ecies que nele vivem disputam seus recursos. A forma com que cada esp´ecie se adequa e desenvolve, de acordo com o nicho em que vive, forma as subpopula¸c˜oes. O n´umero de indiv´ıduos em um nicho ´e determinado pela quantidade de recurso dispon´ıvel no nicho e pela efic´acia do indiv´ıduo aproveitar esses recursos (FAN; ZENG; LI, 2009; JELASITY; DOMBI, 1998). A Figura 33 ilustra o nicho de alguns carn´ıvoros.
An´alogo ao sistema natural, podem-se definir nichos e subpopula¸c˜oes para os AGs, onde parcelas da popula¸c˜ao s˜ao evolu´ıdas em condi¸c˜oes diferentes, dando maior amplitude na busca e maior diversifica¸c˜ao. A conserva¸c˜ao da diversidade gen´etica e a capacidade de manter representantes de boas solu¸c˜oes (´otimos locais) durante a busca s˜ao as principais caracter´ısticas dos AGs com t´ecnica de nicho.
Figura 33: Nicho de alguns carn´ıvoros (FELIX, 2010)
Os AGs sem nicho evolui de forma a convergir a busca para uma ´unica ´area promissora, eliminando durante o processo bons indiv´ıduos de outras regi˜oes dos espa¸co de busca. Em problemas, como ilustrado na Figura 34, pode-se querer encontrar mais de uma solu¸c˜ao e, por isso, ´e necess´ario que o algoritmo n˜ao descarte boas solu¸c˜oes das outras regi˜oes de picos. Para tal, faz-se necess´ario a introdu¸c˜ao da t´ecnica de nicho, reduzindo a tendˆencia gen´etica para uma ´unica regi˜ao e permitindo a explora¸c˜ao e manuten¸c˜ao em outras regi˜oes. Dessa forma, as t´ecnicas de nicho tentam manter a sobrevivˆencia dos indiv´ıduos que est˜ao fora do grupo elite. Para tal, cada regi˜ao de ´otimo local, como exemplo os picos da Figura 35, ´e considerada um nicho com recursos que dever˜ao ser repartidos com os indiv´ıduos que nele se encontram. Assim, quanto mais indiv´ıduos menor s˜ao os recursos, obrigando a migra¸c˜ao de alguns para outras regi˜oes ou a elimina¸c˜ao desses.
O nicho e as subpopula¸c˜oes podem ser implementadas de v´arias formas. Basicamente, calcula-se a distˆancia entre os indiv´ıduos, para identificar os vizinhos e os competidores, por exemplo com a fun¸c˜ao de partilha, e posteriormente, estabelece-se as pondera¸c˜oes, por exemplo no operador de sele¸c˜ao com a aptid˜ao aparente, para determinar os melhores de cada regi˜ao promissora do espa¸co de busca e penalizar os vizinhos pr´oximos dos melhores (MING; NAN; XU, 2009).
Figura 34: Fun¸c˜oes-teste de Spears (1994)
Figura 35: Fun¸c˜ao multimodal Griewangk (TRACER, 2009b)
Como exemplo de c´alculo da aptid˜ao aparente, a equa¸c˜ao (4.3) define a fun¸c˜ao apa- rente usada na t´ecnica de nicho de Goldberg (GOLDBERG; RICHARDSON, 1987; GOLD- BERG, 1989). A aptid˜ao aparente ´e obtida pela divis˜ao da aptid˜ao do indiv´ıduo fi pelo
grau de vizinhan¸ca total do indiv´ıduo i em rela¸c˜ao a toda a popula¸c˜ao, com npop membros
(HORN, 1997). fs,i= fi npop X j=1 s(dij) (4.3)
onde s ´e a fun¸c˜ao de partilha e dij ´e a distˆancia entre os indiv´ıduos i e j.
mente entre indiv´ıduos da mesma subpopula¸c˜ao ou de subpopula¸c˜oes vizinhas. A t´ecnica de nicho de Spears (SPEARS, 1994) usa etiquetas para identificar os indiv´ıduos de cada subpopula¸c˜ao, permitindo uma separa¸c˜ao da popula¸c˜ao e restri¸c˜oes no cruzamento (SS1 e SS2). Essa classifica¸c˜ao por etiquetas apresenta-se como uma solu¸c˜ao de baixo custo computacional.
Considerando os diferentes tipos de nicho, o trabalho Mahfoud (1995) apresenta uma classifica¸c˜ao das t´ecnicas, ilustrada na Tabela 5. Nesse, o autor classifica os algoritmos segundo as dimens˜oes tempo versus espa¸co e ambiente ´unico versus m´ultiplos ambientes.
Tabela 5: Classifica¸c˜ao das t´ecnicas de nicho
Ambiente ´unico M´ultiplos ambientes Temporal Sequential Location Overspecification
Ecological GAs Espacial Heterozygote Advantage Ecological GAs
Crowding
Restricted Competition Immune Systems Fitness Sharing
J´a o trabalho Li, Lin e Kou (2009) classifica os algoritmos de nicho como de estrat´egias impl´ıcitas ou expl´ıcitas. Como exemplo de t´ecnicas expl´ıcitas, citam-se: individual clus- tering based sharing schemes, the species conservation GAs, species conservation particle swarm optimizer, the restricted competition and mating, the sequential niching e the island model GAs and the parallel GAs. J´a como exemplo de t´ecnicas impl´ıcitas, citam-se: the crowding and preselection, the fitness sharing e crowding with nearest neighbors replace- ment.
As t´ecnicas de nicho podem ser aplicadas a v´arios tipos de problemas, entre eles: classifica¸c˜ao e aprendizado de m´aquina, otimiza¸c˜ao de fun¸c˜ao multimodal, otimiza¸c˜ao de fun¸c˜ao multiobjetivo e simula¸c˜ao de sistemas complexos e adaptativos (MAHFOUD, 1995). Dados os resultados apresentados na literatura (HORN, 1997; SARENI; KRAHENBUHL, 1998; YUAN; LI; LI, 2008b; HUANG; TIAN; FANG, 2009; MING; NAN; XU, 2009), podem-se
afirmar que as t´ecnicas de nicho s˜ao op¸c˜oes eficazes para a manuten¸c˜ao da diversidade gen´etica e para busca e permanˆencia de solu¸c˜oes de boa qualidade. Destaque para o trabalho de Li, Lin e Kou (2009) que apresenta uma compara¸c˜ao de diferentes tipos de t´ecnicas de nicho, baseadas na estrat´egia de substitui¸c˜ao da popula¸c˜ao, para as fun¸c˜oes multimodais. Entre os algoritmos testados: Nearest Neighbors Replacement Crowding (NNRC), Species Conservation Technique (SCT), Implicit Hierarchical Fair Competition (HFC-I) e o Clearing Procedure with Elitist (CPE), o NNRC demonstra a melhor perfor-
mance.
Como exemplo da aplica¸c˜ao do NNRC no steady-state AG (SSAG), a Figura 36 ilus- tra o efeito do NNRC na representa¸c˜ao do espa¸co de busca da fun¸c˜ao Schaffer, que ´e multimodal, tem v´arios ´otimos locais e tem os picos distribu´ıdos em forma de anel.
Figura 36: Efeito da aplica¸c˜ao do NNRC na fun¸c˜ao Schaffer Li, Lin e Kou (2009)