Fagdatabaser og identifisering av relevant litteratur

4.2 Søkestrategier (metodiske fremgangsmåter)

4.2.1 Fagdatabaser og identifisering av relevant litteratur

(a) p = 10, c = 10, v = 1. (b) p = 10, c = 10, v = 1.

Figura 11: Simula¸c˜oes de f1 para tamanho de popula¸c˜ao 10 e

(e) p = 30, c = 10, v = 1. (f ) p = 30, c = 10, v = 2

(g) p = 30, c = 100, v = 1. (h) p = 30, c = 100, v = 2.

Figura 12: Simula¸c˜oes de f1 para tamanho de popula¸c˜ao 30 e

(i) p = 50, c = 10, v = 1. (j) p = 50, c = 10, v = 2.

(l) p = 50, c = 100, v = 1. (m) p = 50, c = 100, v = 2.

Figura 13: Simula¸c˜oes de f1 para tamanho de popula¸c˜ao 50 e

4.2.2 Simula¸c˜oes de f

(a) p = 10, c = 10, v = 1. (b) p = 10, c = 10, v = 2.

Figura 14: Simula¸c˜oes de f2 para tamanho de popula¸c˜ao 10 e

(e) p = 30, c = 10, v = 1. (f ) p = 30, c = 10, v = 2.

(g) p = 30, c = 100, v = 1. (h) p = 30, c = 100, v = 2.

Figura 15: Simula¸c˜oes de f2 para tamanho de popula¸c˜ao 30 e

(i) p = 50, c = 10, v = 1. (j) p = 50, c = 10, v = 2.

(l) p = 50, c = 100, v = 1. (m) p = 50, c = 100, v = 2.

Figura 16: Simula¸c˜oes de f2 para tamanho de popula¸c˜ao 50 e

4.2.3 Simula¸c˜oes de f

(a) p = 10, c = 10, v = 1. (b) p = 10, c = 10, v = 2.

Figura 17: Simula¸c˜oes de f3 para tamanho de popula¸c˜ao 10 e

(e) p = 30, c = 10, v = 1. (f ) p = 30, c = 10, v = 2.

(g) p = 30, c = 100, v = 1. (h) p = 30, c = 100, v = 2.

Figura 18: Simula¸c˜oes de f3 para tamanho de popula¸c˜ao 30 e

(i) p = 50, c = 10, v = 1. (j) p = 50, c = 10, v = 2.

(l) p = 50, c = 100, v = 1. (m) p = 50, c = 100, v = 2.

Figura 19: Simula¸c˜oes de f3 para tamanho de popula¸c˜ao 50 e

4.2.4 Simula¸c˜oes de f

(a) p = 10, c = 10, v = 1. (b) p = 10, c = 10, v = 2.

Figura 20: Simula¸c˜oes de f4 para tamanho de popula¸c˜ao 10 e

(e) p = 30, c = 10, v = 1. (f ) p = 30, c = 10, v = 2.

(g) p = 30, c = 100, v = 1. (h) p = 30, c = 100, v = 2.

Figura 21: Simula¸c˜oes de f4 para tamanho de popula¸c˜ao 30 e

(i) p = 50, c = 10, v = 1. (j) p = 50, c = 10, v = 2.

(l) p = 50, c = 100, v = 1. (m) p = 50, c = 10, v = 2.

Figura 22: Simula¸c˜oes de f4 para tamanho de popula¸c˜ao 50 e

4.2.5 Simula¸c˜oes de f

(a) p = 10, c = 10, v = 1. (b) p = 10, c = 10, v = 2.

Figura 23: Simula¸c˜oes de f5 para tamanho de popula¸c˜ao 10 e

(e) p = 30, c = 10, v = 1. (f ) p = 30, c = 10, v = 2.

(g) p = 30, c = 100, v = 1. (h) p = 30, c = 100, v = 2.

Figura 24: Simula¸c˜oes de f5 para tamanho de popula¸c˜ao 30 e

(i) p = 50, c = 10, v = 1. (j) p = 50, c = 10, v = 2.

(l) p = 50, c = 100, v = 1. (m) p = 50, c = 100, v = 2.

Figura 25: Simula¸c˜oes de f5 para tamanho de popula¸c˜ao 50 e

Cap´ıtulo 5

Conclus˜oes

“O ´ultimo passo da raz˜ao ´e reconhecer a existˆencia de uma infinidade de coisas que a ultrapassam.”(PASCAL)

Neste trabalho, vimos a vantagem que o algoritmo gen´etico elitista leva sobre o algo- ritmo gen´etico canˆonico, pois o primeiro converge para o conjunto das popula¸c˜oes que possui o ponto de ´otimo de uma dada fun¸c˜ao positiva e limitada superiormente, enquanto o segundo n˜ao converge. Nas simula¸c˜oes realizadas, ilustramos v´arios cen´arios poss´ıveis de cruzamento (canˆonico, modificado por vizinhan¸ca e sem esta etapa) e muta¸c˜ao (canˆonico, com simulated annealing e sem essa etapa) e realizamos simula¸c˜oes com combina¸c˜oes destas diversas possibil- idades de escolha destes operadores. Nestas simula¸c˜oes, al´em de combinarmos estes poss´ıveis operadores, tamb´em modificamos o tamanho da vizinhan¸ca no operador cruzamento que utiliza a ideia apresentada em Dorea [7] e a agenda de resfriamento na etapa de muta¸c˜ao que utiliza o simulated annealing, al´em de realizar simula¸c˜oes com tamanhos de popula¸c˜oes diferentes.

Vimos teoricamente que os algoritmos elitistas sempre encontrar˜ao o ponto de ´otimo procu- rado, entretanto podemos ver em nossas simula¸c˜oes que isso n˜ao significa que, em 1000 passos, eles encontrarar˜ao o ponto de ´otimo desejado em todas as realiza¸c˜oes, e isso serve para ilustrar o significado de comportamento assint´otico, ou seja, resultados que valem no limite.

Olhando para as simula¸c˜oes realizadas, observamos que o algoritmo 1 (SnCnMn) parece ser

o que menos vezes encontra os ponto de ´otimo. J´a os gr´aficos das simula¸c˜oes ilustram que nos experimentos realizados, os algoritmos 2 (SnCviz),3(SnMSA) e 4 (SnCvizMSA) encontram

mais vezes os pontos de ´otimo para um mesmo n´umero de passos. Vemos nas simula¸c˜oes que, `a medida que a popula¸c˜ao aumenta, os resultados parecem diferir menos, ou seja, gastam-se menos passos para encontrar os pontos de ´otimo. Ent˜ao, uma quest˜ao que se pode levantar ´e: se ao aumentarmos o tamanho da popula¸c˜ao melhoramos o desempenho dos algoritmos, por que n˜ao tomamos popula¸c˜oes grandes? A resposta ´e a seguinte: quanto maior a popula¸c˜ao, mais c´alculos o algoritmo precisa fazer em cada passo, o que aumenta muito o seu esfor¸co com- putacional e acarreta um aumento de tempo para realizar cada passo. Assim, quanto maior a popula¸c˜ao, menor a quantidade de passos necess´arios para encontrar o ponto desejado e maior o tempo que cada passo leva para ser realizado. Um problema em aberto ´e justamente esse, saber qual o tamanho de popula¸c˜ao ´otimo, ou seja, qual deve ser o tamanho da popula¸c˜ao em que o ponto de ´otimo seja encontrado em menor tempo?

A conclus˜ao que, se pode tirar ´e que embora exista um resultado que nos garanta a con- vergˆencia destes algoritmos, nem sempre ela se d´a numa quantidade finita de passos e parece que algumas abordagens (utilizando formas diferentes de fazer as etapas de sele¸c˜ao, cruzamento e muta¸c˜ao) fazem com que o algoritmo encontre o ponto procurado em menos passos.

Para trabalhos futuros, pretendemos estudar a velocidade de convergˆencia destes algoritmos e com isso poder realmente dizer se existe uma melhora entre um algoritmo e outro. Mesmo assim, o estudo da velocidade de convergˆencia se d´a em rela¸c˜ao ao n´umero de passos do algo- ritmo, que como comentado acima, o tempo de cada passo depende da quantidade de c´alculos que o algoritmo precisa realizar em cada passo.

Referˆencias

[1] Albuquerque, P.; Mazza, C. Mutation Selection Algorithm: A Large Desviation Approach - Fundations od Genetic Algorithms vol 06, p´ag. 227 - Morgan Kaufmann Publishers, Academic Press, 2001.

[2] Attenborough, Charles. Document´ario Charles Darwin e a ´Arvore da Vida, BBC, Londres, 2008.

[3] Cerf, R. The Dinamics of Mutations - Selections Algorithms with Large Populations Sizes - Ann. Inst. H.Poincar´e - Prob. Statist 32 - pp.455-508, 1996.

[4] Cerf, R. Asymptotic Convergence of Genetic Algorithms, Advanced Applied Probability, 30, pp. 521-550, 1998.

[5] Darwin, C. A Origem das Esp´ecies, Ediouro - Rio de Janeiro, 2004.

[6] Dorea, C.C.Y. J´unior et al. Multistage Markov Chain modelling of the Genetic Algorithm and Convergence results, 2010.

[7] Eiben, A. E.; Aarps, E. M. L.; Van Hee, K. M. Global Convergence of Genetic Algorithms: Markov Chaim Analysis, in Parallel Problem Solving from Nature - Springer, pp.04-12, 1991. [8] Freidlin, M. L. Wentzell, A. D. Random Perturbations of Dynamical Systems, Springer - NY, 1984.

[9] Fischer, R. A. The Genetic Theory of Natural Seletion - Dover Publications, 1958.

[10] Fran¸cois, O. Global Optimization with Explorations - Selections Algorithms and Simulated Annealing, The Annals of Applied Probability, vol.0 - number 0, pp.1-24, 2001.

[11] Goldberg, D.E. Genetic Algorithms in Search Optimization and Machine Learning- Read- ing M.A - Addison Wesley, 1989.

[12] Holland, J.H. Adaptation in Natural and Artificial Systems - Univ. Michigan Press, Ann Arbor, 1975.

[13] Iofescu, Marius. Finite Markov Process and Their Applications. 1a _{ed. Dover, 2007.}

[14] Isaacson, Dean L. Markov Chains Theory and Applications. 1a _{ed. Robert E. Krieger}

Publishing Company, INC Malabar, Fl´orida, 1985.

[15] James, Barry R. Probabilidade: Um curso intermedi´ario. 3a _{ed. Rio de Janeiro: IMPA,}

[16] Kirkpatrick, S.; Gellatt, C.D.; Vecchi, M.P. Jr. Optmization by Simulated Annealling. Science 220:671-680, 1983.

[17] Lamarck, J. B. Philosophie Zoologique, Paris, Libraire Schleicher Fr´eres, 1907. [18] Linder, R. Algoritmos Gen´eticos, 3a _{edi¸c˜ao - Ed. Ciˆencia Moderna, 2012.}

[19] Linn´ee, Karl Von. Systeme de La Nature, Bruxelas; Lemaire, 1793.

[20] Magalh˜aes, M. Nascimento. Probabilidade e Vari´aveis aleat´orias. S˜ao Paulo: Edusp, 2004. [21] Malthus, T. An Essay on the Principle of Population, Eletronic Scholarly Projeet, 1998. [22] Mendel, G. Experimentos sobre Hibrida¸c˜ao das Plantas. In: Freire-Maia, N. Gregor Mendel - Vida e Obra. T.A Queiroz, S˜ao Paulo, 1995.

[23] Nix, A.E.; Vose, M.D. Modeling Genetic Algorithms with Markov Chains, Annals of Math- ematics and Artifical Intelligence, v.5 n.1, pp 79-88, 1992.

[24] Pereira, A.G.C.; Cruz, J.A.R.; Campos, V.S.M. Modeling the Genetic Algorithm by a Non-Homogeneous Markov Chains: weak and strong ergodicity, ISSN 0040585X, 2012.

[25] Resnick, S. I. Adventures in Stochastic Process - Birkhauser, 2002:

[26] Rosa, J. C. Modelagem dos Algoritmos Gen´eticos Simples e Simulated Annelling por Cadeias de Markov, Disserta¸c˜ao de Mestrado do PPGMAE-UFRN, 2010.

[27] Rudolph, G. Convergency Analysis of Canonical Genetic Algorithms, IEE. Transactinos ou neural Networks, Special Neural Networks, Special issue on Evolutionary Compilation 5, 96 − 101, 1994.

[28] Suzuki, J. A Markov Chain Analysis on Genetic Algorithms - Large Deviation Principle Approach, Applied Probability Trust, 2010.

In document Lek og psykisk helse i barnehage. (sider 46-0)