7.2 P ERFORMANCE ; L IMITATIONS AND POSSIBILITIES
7.2.2 Execution performance in practical contexts
A tarefa da classificac¸˜ao da densidade (Density classification task, DCT), ´e uma tarefa
cl´assica em ACs. A DCT consiste em encontrar um AC bin´ario (Σ= 2) que, ap´os ser iterado por at´eT iterac¸˜oes em qualquer CI, encontre uma configurac¸˜ao homogˆenea onde todas as c´elulas
se encontrem no estado 1, caso a CI possua mais 1s do que 0s (a quantidade de 1s sobre 0s, a densidade de 1s em um reticulado, ´e chamada deρ), ou uma configurac¸˜ao uniforme de 0s caso contr´ario. Usualmente, esse teste ´e feito em um reticulado unidimensional, de tamanhoL ´ımpar
(normalmenteL= 149), e ACs bin´arios com r = 3, totalizando 2128diferentes regras poss´ıveis, um espac¸o muito grande para efetuar uma busca exaustiva.
Apesar de ser uma tarefa simples para sistemas centralizados, essa tarefa se torna extrema- mente complexa em sistemas descentralizados como ACs, pois o AC deve ser capaz de tomar uma decis˜ao local que reflita uma condic¸˜ao global da qual ele n˜ao sabe o estado [OLIVEIRA; OLIVEIRA; BORTOT, 2006]; foi provado em [LAND; BELEW, 1995] que n˜ao existe um ´unico AC capaz de executar a DCT com sucesso para todas as CIs.
Devido `a enorme quantidade de regras poss´ıveis para executar a DCT (2128 poss´ıveis re- gras para ACs bin´arios der= 3) e a grande complexidade de se encontrar uma boa regra que
execute a DCT com uma alta taxa de acertos, essa ´e uma tarefa comumente utilizada para estudar a utilizac¸˜ao de AGs para encontrar, de forma autom´atica, boas regras que sejam ca- pazes de executar a DCT com uma boa margem de sucesso [CRUTCHFIELD; MITCHELL; DAS, 2002]. A melhor regra atualmente, ´e reportada em [WOLZ; OLIVEIRA, 2008] e possui efic´acia de 88.985% para 500.000 CIs comρ escolhido de forma aleat´orio em uma distribuic¸˜ao binomial; escolherρ a partir de uma distribuic¸˜ao binomial torna as CIs muito mais complexas para serem avaliada pelo AC. Um exemplo de sua iterac¸˜ao ´e ilustrada na Figura 3.8 para uma CI de teste comL= 149 eρ= 55.7947%. A mesma CI (ilustrada na Figura 3.7) ´e utilizada nas demais ilustrac¸˜oes das iterac¸˜oes dos ACs encontrados pelos diferentes AGs implementados. O AC encontrado em [WOLZ; OLIVEIRA, 2008] foi capaz de encontrar a classificac¸˜ao correta (ρT = 100%) ap´os aproximadamente 100 iterac¸˜oes.
Outra forma de se encontrar regras para a DCT, ´e a sua criac¸˜ao manual. Das regras cri- adas manualmente, a regra GKL (nomeada pelos nomes de seus autores, Gacs, Kurdyumov e Levin) proposta em [GACS; KURDYUMOV; LEVIN, 1978], ´e considerada a melhor regra criada manualmente para a DCT. Aparentemente, essa regra possui uma estrat´egia capaz de minimizar o erro conforme se aumenta a quantidade m´axima de iterac¸˜oes (T ) [MITCHELL;
CRUTCHFIELD; HRABER, 1994]. Em [MITCHELL; CRUTCHFIELD; HRABER, 1994] foi estudado o motivo que um AG simples, n˜ao ´e capaz de encontrar a regra GKL de forma au- tom´atica, mesmo ele sendo criado com esse objetivo.
Figura 3.7: CI utilizada para demonstrativo das regras encontradas pelos diversos AGs utiliza- dos,ρ = 55.7047%.
Figura 3.8: 100 iterac¸˜oes da melhor regra encontrada em [WOLZ; OLIVEIRA, 2008] (δ = 337607298446901146542393000444934784552) para a DCT com a CI apresentada na Figura 3.7.
18
Neste trabalho foram estudados 3 AGs para encontrar boas regras para a DCT, os algo- ritmos definidos em [MITCHELL; CRUTCHFIELD; HRABER, 1994] (que ser´a chamado de MCH), uma simples modificac¸˜ao do mesmo em [OLIVEIRA; OLIVEIRA; OMAR, 2001] (que ser´a chamado de OOO), e outro algoritmo definido em [CRUTCHFIELD; MITCHELL; DAS, 2002] (que ser´a chamado de CMD). Apesar de semelhantes, esses AGs apresentam pequenas diferenc¸as capazes de influenciar no resultado final.
Todos os AGs estudados partem do mesmo AG:
1. Gera-se uma populac¸˜aoP aleat´oria, onde cada indiv´ıduo i ´e um AC capazes de executar
a DCT;
2. Para cada gerac¸˜aog do AG at´e a gerac¸˜ao final G:
(a) S˜ao geradas I CIs aleat´orias, utilizando-se uma distribuic¸˜ao uniforme para o valor
ρ;
(b) Cada indiv´ıduo da populac¸˜aoPg, ´e executado para todas asI CIs por um m´aximo de T iterac¸˜oes e, a quantidade de classificac¸˜oes corretas do AC ´e a aptid˜ao (“fitness”) f
do AC. Nenhum cr´edito ´e dado a classificac¸˜oes incompletas (que n˜ao conseguiram chegar a um estado homogˆeneo de 1 ou 0);
(c) A elite E de ACs com melhor f ´e copiada sem alterac¸˜ao para a pr´oxima populac¸˜ao Pg+1;
(d) o restante da populac¸˜aoPg+1−E ´e gerada utilizando-se:
i. Cruzamento com pc probabilidade de ocorrer, com pais sempre oriundos da eliteE e;
ii. ´E efetuada mutac¸˜ao nos filhos resultantes do cruzamento, com probabilidade
pmpor bit;
3. S˜ao geradas B CIs aleat´orias, utilizando-se uma distribuic¸˜ao binomial para o valor ρ, resultando em um teste mais complexo para os ACs gerados pelo algoritmo; e
4. O indiv´ıduo dePGcom maior f ´e executado em at´e no m´aximo T vezes para todas as B
CIs, a quantidade de classificac¸˜oes corretas ´e a aptid˜ao final (F) do indiv´ıduo.
´
E importante frisar, que todos os AGs criam os indiv´ıduos da populac¸˜ao inicial (P0) uti- lizando uma distribuic¸˜ao uniforme deρ, pois foi constatado de forma emp´ırica que h´a ganho
no tempo de execuc¸˜ao do AG, al´em da qualidade das soluc¸˜oes n˜ao ser afetada por esse tipo de distribuic¸˜ao inicial [MITCHELL; CRUTCHFIELD; HRABER, 1994]. Esse fato tamb´em foi observado no presente trabalho.
Todos os AGs foram executados em um cluster possuindo 14 n´os, dentre eles 6 com 4 n´ucleos AMD Opteron de 2GHz e 8 com 2 n´ucleos AMD Opteron de 1.4 GHz. A forma de paralelismo escolhida para a execuc¸˜ao dos testes, foi utilizar OpenMPI para distribuir as threads no cluster, onde cada thread ´e respons´avel por uma execuc¸˜ao completa do AG.
3.2.1
CMD
Em [CRUTCHFIELD; MITCHELL; DAS, 2002], foram estudadas as estrat´egias dos ACs encontrados por um simples AG para a tarefa da DCT, e como essas estrat´egias se comportavam para CIs de tamanho L= 149, L = 499 e L = 999. O AG apresentado utiliza os seguintes parˆametros: P= 100, I = 100, T = 2 ∗ L, B = 104, E = 20, G = 100, pc = 100% e pm =
1.1516%.
Esse AG ´e capaz de evoluir trˆes tipos diferentes de estrat´egias para a execuc¸˜ao da DCT:
• Default: Estrat´egias do tipo default s˜ao muito boas em resolver CIs com ρ <50% ou
ρ>50%, mas s˜ao incapazes de resolver CIs para ambos os casos. Esse tipo de estrat´egia apresenta efic´acia de ≈ 50% para qualquer tamanhoL.
• Block-expanding: Esse tipo de estrat´egia consegue “expandir”a vizinhanc¸a de cada c´elula,
de forma que as c´elulas vizinhas efetuem sua expans˜ao levando em conta n˜ao apenas sua pr´opria vizinhanc¸a, mas tamb´em a vizinhanc¸a de outras c´elulas. Essa estrat´egia costuma levar a efic´acias de ≈ 60%, por´em ao aumentar o tamanhoL, esse valor diminui.
• Particle: Esse tipo de estrat´egia ´e a respons´avel por apresentar os ACs com melhor
efic´acia (acima de 70%), por´em tamb´em s˜ao as mais dif´ıceis de se encontrar. ACs que em- pregam esse tipo de estrat´egia s˜ao capazes de “transmitir” a densidade da vizinhanc¸a de cada c´elula para as c´elulas adjacentes e, dessa forma, muitas vezes efetuar corretamente a DCT. Essas estrat´egias s˜ao as que melhor mant´em a efic´acia para tamanhos maiores de
L.
20
independentes. ´E poss´ıvel perceber as 3 faixas, que caracterizam as estrat´egias apresentadas anteriormente. Das 300 execuc¸˜oes, 120 possuem performance abaixo de 60%, 175 entre 60.01% e 70%, e apenas 4 possuem performance maior que 70.01%.
As Figuras 3.10a e 3.10b, mostram respectivamente 100 iterac¸˜oes da melhor e da pior regra encontrada pelo CMD para a CI apresentada na Figura 3.7. J´a as Figuras 3.10c e 3.10d, mostram o f do melhor indiv´ıduo Pg encontrado em cada gerac¸˜aog do AG, respectivamente para a pior
e a melhor regra encontrada entre as 300 execuc¸˜oes distintas do AG.
O tempo total de execuc¸˜ao do AG para encontrar as 300 regras apresentadas foi de 8 horas e 45 minutos.
Figura 3.9: 300 execuc¸˜oes distintas do CMD. Cada ponto representa oF do melhor indiv´ıduo
335 946 353 665 655 739 599 279 694 834 806 851 712
(a) 100 iterac¸˜oes da pior regra encontrada uti- lizando o CMD.
1 622 592 825 149 487 511 997 191 488 012 273
(b) 100 iterac¸˜oes da melhor regra encontrada uti- lizando o CMD. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 335946353665655739599279694834806851712
(c) f da pior regra encontrada em cada gerac¸˜ao
do AG. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 1622592825149487511997191488012273
(d)f da melhor regra encontrada em cada gerac¸˜ao
do AG.
Figura 3.10: Detalhamento das regras do CMD.
3.2.2
MCH
Em [MITCHELL; CRUTCHFIELD; HRABER, 1994], foi estudado um dos AGs mais sim- ples poss´ıveis para encontrar boas regras para a DCT. L´a estudou-se como o AG conseguia evoluir boas regras, o motivo do AG n˜ao encontrar regras com alta performance todas as vezes, e o motivo pelo qual esse simples AG n˜ao ´e capaz de encontrar regras superiores ou equivalentes `a regra GKL, cujo desempenho ´e da ordem de 80% [MITCHELL; CRUTCHFIELD; HRABER, 1994].
O AG possui as seguintes alterac¸˜oes:
• AsI CIs s˜ao geradas utilizando-se exatamente 50% de CIs com ρ <50% e 50% com
ρ>50%;
22
de Poisson de m´edia 320 e;
• A mutac¸˜ao ´e feita em exatamentem bits de cada AC resultante do cruzamento. O valor pmpode ser inferido a partir dem.
Os parˆametros utilizados foram: P= 100, I = 100, B = 104,E= 20, G = 100, pc= 80%,
m= 2 (o equivalente a pm= 1.5625%) e L = 149. Os resultados de 300 execuc¸˜oes distintas do AG, podem ser vistos na Figura 3.11, e as 100 iterac¸˜oes da pior e da melhor regra encontradas pelo AG, podem ser vistas respectivamente, nas Figuras 3.12a e 3.12b; o f dos melhores in-
div´ıduos de cada gerac¸˜aog do AG, nas execuc¸˜oes respons´aveis por encontrar a pior e a melhor
regra s˜ao mostrados nas Figuras 3.12c e 3.12d respectivamente.
Ambas as regras conseguiram executar a DCT para a CI com sucesso, por´em a regra de pior performance se encontra na classificac¸˜ao “default”de [CRUTCHFIELD; MITCHELL; DAS,
2002], o que significa que ela consegue executar a classificac¸˜ao de forma correta, apenas para CIs com ρ >50%. A evoluc¸˜ao do f durante o AG, da melhor regra, est´a de acordo com o trabalho original, onde ´e poss´ıvel verificar as diferentes “´epocas”do AG (cada ´epoca ´e carac- terizada por um salto no f dos ACs encontrados) [MITCHELL; CRUTCHFIELD; HRABER,
Figura 3.11: 300 execuc¸˜oes distintas do MCH. Cada ponto representa aF do melhor indiv´ıduo
24
340 282 160 439 462 956 348 565 670 998 868 812 008
(a) 100 iterac¸˜oes da pior regra encontrada uti- lizando o MCH.
333 552 500 509 258 600 421 908 018 833 288 856 200
(b) 100 iterac¸˜oes da melhor regra encontrada uti- lizando o MCH. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 340282160439462956348565670998868812008
(c) f da pior regra encontrada em cada gerac¸˜ao
do AG. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 333552500509258600421908018833288856200
(d)f da melhor regra encontrada em cada gerac¸˜ao
do AG.
Figura 3.12: Detalhamento das regras do MCH.
O tempo total de execuc¸˜ao para as 300 execuc¸˜oes distintas do AG foi de 3 horas e 26 minutos. Dessas 300 execuc¸˜oes, 17 est˜ao abaixo de 60% de performance, 204 entre 60.01% e 70% e 79 regras acima de 70.01%.
´
E importante apontar que das alterac¸˜oes apresentadas, a mais significativa ´e a utilizac¸˜ao de um n´umero aleat´orio com distribuic¸˜ao de Poisson para a quantidade de iterac¸˜oes de cada AC, pois isso diminui a possibilidade de se encontrar regras com ciclo duplo, isto ´e, ACs com a caracter´ıstica de comportamento c´ıclico de per´ıodo 2 que, portanto, n˜ao convergem para um ´unico estado homogˆeneo; a prop´osito, este ´e o caso da melhor regra encontrada pelo CMD, conforme ilustrado na Figura 3.10b.
Tamb´em foi demonstrado em [MITCHELL; CRUTCHFIELD; HRABER, 1994] que re- gras com alta efic´acia possuemρ ≈50%; n˜ao estranhamente, a regra GKL possui exatamente
ρ = 50% [MITCHELL; CRUTCHFIELD; HRABER, 1994], a melhor regra encontrada nas execuc¸˜oes desse AG possuiρ= 47.6563% e a pior regra possuiρ= 60.1563%.
3.2.3
OOO
Em [OLIVEIRA; OLIVEIRA; OMAR, 2001], foram estudadas as caracter´ısticas intr´ınsecas dos ACs encontrados pelo MCH; como por exemplo o ρ de cada regra e a sensitividade `a vizinhanc¸a, dentre outros parˆametros. Em nossas execuc¸˜oes n˜ao estamos estudando esses parˆametros, apenas os resultados do AG utilizado.
Os parˆametros do AG utilizados foram: P= 100, I = 100, B = 104,E= 20, G = 100, pc=
80%, pm= 2% e L = 149. Diferentemente do AG original, a forma de mutac¸˜ao utilizada em [OLIVEIRA; OLIVEIRA; OMAR, 2001] ´e feita com probabilidadepmem cada bit, a utilizac¸˜ao de pm = 2% garante m ≈ 2. A quantidade de iterac¸˜oes de cada AC tamb´em ´e dada por um n´umero vari´avel de vezes [OLIVEIRA; OLIVEIRA; OMAR, 2001]; por´em a distribuic¸˜ao de probabilidade, utilizada para se encontrar o n´umero para definir o tempo total de iterac¸˜oes de cada AC, n˜ao ´e especificada no artigo original. Dessa forma, aqui tamb´em utiliza-se a mesma distribuic¸˜ao do MCH (distribuic¸˜ao de Poisson), com m´edia 298.
A efic´acia da melhor regra encontrada em 300 execuc¸˜oes distintas pode ser vista na Figura 3.13, e 100 iterac¸˜oes da pior e melhor regras encontradas pelo AG podem ser vistas nas Figuras 3.14a e 3.14b, respectivamente. O f das melhores regras encontrados, em cada gerac¸˜ao g nas execuc¸˜oes
respons´aveis por encontrar a pior e melhor regra do AG, s˜ao mostrados nas Figuras 3.14c e 3.14d respectivamente. O tempo total de execuc¸˜ao do AG para encontrar as 300 regras foi de 3 horas e 44 minutos; dessas 300 execuc¸˜oes, 39 possuem performance menor que 60%, 220 regras possuem entre 60.01% e 70% e 41 apresentam performance acima de 70.01%.
26
Figura 3.13: 300 execuc¸˜oes distintas do OOO. Cada ponto representa aF do melhor indiv´ıduo
277 910 614 967 827 334 053 006 880 536 310 901 760
(a) 100 iterac¸˜oes da pior regra encontrada uti- lizando o OOO.
338 516 985 978 337 537 125 333 578 344 457 831 424
(b) 100 iterac¸˜oes da melhor regra encontrada uti- lizando o OOO. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 277910614967827334053006880536310901760
(c) f da pior regra encontrada em cada gerac¸˜ao
do AG. 0 20 40 60 80 100Geração 0 20 40 60 80 100 Fitness Evolução da regra 338516985978337537125333578344457831424
(d)f da melhor regra encontrada em cada gerac¸˜ao
do AG.
Figura 3.14: Detalhamento das regras do OOO.
3.2.4
Resultados
Na Figura 3.15, temos a plotagem do resultado de 300 execuc¸˜oes distintas dos AGs. ´E poss´ıvel perceber que os melhores resultados est˜ao no OOO e MCH, esses AGs apresentam uma faixa de performance m´edia entre 65% e 70%, e poucos resultados abaixo de 50%. Por sua vez o CMD apresenta piores resultados, com uma m´edia de aproximadamente 60% e v´arios resultados entre 35% e 50%. Na Tabela 3.4 podemos ver uma contagem dos resultados para algumas faixas de performance espec´ıficas, fica claro por essa tabela que os melhores AGs realmente s˜ao OOO e MCH, uma vez que eles s˜ao extremamente parecidos fica dif´ıcil especificar qual AG ´e o melhor de todos. A Tabela 3.5 por sua vez, mostra as diferenc¸as entre os parˆametros nos AGs estudados.
28
Figura 3.15: Gr´afico comparativo com os 3 AGs em 300 execuc¸˜oes distintas, sem a utilizac¸˜ao da representac¸˜ao tern´aria. fi(%) OOO MCH CMD ≤50 33 16 60 (50, 60] 6 1 61 (60, 70] 220 204 175 (70, 80] 40 79 4 >80 1 0 0
Tabela 3.4: Contagem das regras encontradas pelos 3 AGs estudados.
AG P E pc pm m L B T
CMD 100 20 100% 1.1516% ≈2 149 104 298
MCH 100 20 80% 1.5626% 2 149 104 ≈320
OOO 100 20 80% 2% ≈2 149 104 ≈298