Algoritmo Genético: Principais Gaps, Trade-offs e Perspectivas para Futuras Pesquisas

Autores

  • A. R. F. Pinto Departamento de Engenharia de Produção, Centro Universitário Uniara, Universidade de Araraquara
  • N. J. Martarelli Departamento de Engenharia de Produção, Escola de Engenharia de São Carlos, Universidade de São Paulo.
  • M. S. Nagano Departamento de Engenharia de Produção, Escola de Engenharia de São Carlos, Universidade de São Paulo.

DOI:

https://doi.org/10.5540/tcam.2022.023.03.00413

Palavras-chave:

Algoritmo Genético, Operadores Genéticos, Teoria dos Esquemas, Hipótese dos Blocos Construtivos.

Resumo

O Algoritmo Genético (AG) é caracterizado por ser uma meta-heurística mimetizada no processo genético de evolução natural baseada na Teoria dos Esquemas (TE) e pela Hipótese dos Blocos Construtivos (HBC). O algoritmo fundamenta-se na busca por boas soluções por meio da ação de operadores genéticos que, se configurados indevidamente, podem inviabilizar a otimização. As dificuldades em projetar designs de alta aptidão e as insuficientes provas teóricas sobre a TE e a HBC retratam o dilema fundamental do AG. Dessa forma, o objetivo deste artigo é explorar o arcabouço teórico, por meio de uma revisão tradicional da literatura, sobre os efeitos que a ação dos operadores genéticos exerce sobre a TE e a HBC. Apresentamos importantes reflexões sobre os principais gaps, trade-offs e perspectivas futuras sobre o AG.

Referências

M. Mitchell, An introduction to genetic algorithms. Cambridge: MIT, 1996.

J. H. Holland, Adaptation in natural and artificial systems. Ann Arbor, MI: University of Michigan Press, 1975.

Z. Michalewicz, Genetic algorithm + data structures = evolution programs. Springer-Verlag, 3 ed., 1996.

M. D. A. Vose, Critical examination of the schema theorem, University of Tennessee, technical report, Department of Computer Science, 1993.

T. Toffoli, _What you always wanted to know about genetic algorithms but were afraid to hear, in Perspectives on Adaptation in Natural and Artificial Systems-Essays in honor of John Holland (L. Booker, ed.), Oxford University Press, 2004.

J. Mccall, Genetic algorithms for modeling and optimization, Journal of Computational and Applied Mathematics, vol. 184, no. 1, pp. 205_222, 2005.

F. G. Lobo and C. F. Lima, _Adaptive population sizing schemes in genetic algorithms, Parameter Setting in Evolutionary Algorithms, vol. 54, pp. 185_204, 2007.

T. Y. Lim, _Structured population genetic algorithms: a literature survey, Artificial Intelligence Review, vol. 41, no. 3, pp. 385_399, 2014.

D. Whitley and A. M. Sutton, _Genetic algorithms - a survey of models and methods, Handbook of Natural Computing, vol. 1, pp. 637_671, 2012.

J. Zhang, W.-N. Chen, Z.-H. Zhan, W.-J. Yu, Y.-L. Li, N. Chen, and Q. Zhou, A survey on algorithm adaptation in evolutionary computation, Frontiers of Electrical and Electronic Engineering, vol. 7, no. 1, pp. 16_31, 2012.

R. Linden, Algoritmos genéticos: uma importante ferramenta da inteligência computacional. Rio de Janeiro: Brasport, 2 ed., 2008.

D. Whitley, A genetic algorithm tutorial, Statistics and Computing, vol. 4, no. 2, pp. 65_85, 1994.

D. E. Goldberg, Genetic algorithms in search, optimization, and machine learning. USA: Addison-Wesley Co. Massachusetts, 2 ed., 1989.

K. d. Jong, _Learning with genetic algorithms: An overview, Machine learning, vol. 3, no. 2-3, pp. 121_138, 1988.

D. White, An overview of schema theory, 2014.

J. W. Hallam, O. Akman, and F. Akman, Genetic algorithms with shrinking population size, Computational Statistics, vol. 25, no. 4, pp. 691_705, 2010.

M. Mitchell, J. H. Holland, and S. Forrest, _When will a genetic algorithm outperform hill climbing? In Advances in Neural Information Processing Systems (M. Kaufmann, ed.), (San Mateo, CA), pp. 51_58, 1994.

A. Nobakhti, On natural based optimization, Cognitive Computation, vol. 2, pp. 97_119, 2010.

G. M, T. M, T. A, and A. E, Selection intensity in cellular evolutionary algorithms for regular lattices, IEEE Transactions on Evolutionary Computation, vol. 9, no. 5, pp. 489_505, 2005

E. Alba and J. M. Troya, _Improving flexibility and efficiency by adding parallelism to genetic algorithms, Statistics and Computing, vol. 12, no. 2, pp. 91_114, 2002.

M. Li and J. Kou, _The schema illusory and deceptive problems of genetic algorithms, Science in China Series: Information Sciences, vol. 44, no. 5, pp. 342_350, 2001.

G. E. Liepins and M. D. Vose, Representational issues in genetic optimization, Journal of Experimental and Theoretical Artificial Intelligence, vol. 2, pp. 101_115, 1990.

N. J. Radcliffe, Forma analysis and random respectful recombination, in Proceedings of fourth International Conference on Genetic Algorithms (R. K. Belew and L. B. Booker, eds.), pp. 222_229, San Mateo, CA: Morgan Kaufmann, 1991.

N. J. Radcliffe, Equivalence class analysis of genetic algorithms, Complex Systems, vol. 5, pp. 183_205, 1991.

M. D. Vose, A closer look at mutation in genetic algorithms, Annals of Mathematics and Artificial Intelligence, vol. 10, pp. 423_434, 1994.

D. B. Fogel and A. Ghozeil, Schema processing under proportional selection in the presence of random effects, IEEE Transactions on Evolutionary Computation, vol. 1, no. 4, pp. 290_293, 1997.

D. B. Fogel and A. Ghozeil, The schema theorem and the misallocation of trials in the presence of stochastic effects, in Proceedings of the 7th Annual Conference on Evolutionary Programming (D. W. V. W. Porto, N. Saravanan and A. . E. . Eiben, eds.), (Berlin), pp. 313_321, Springer, 1998.

S. W. Chung and R. A. Perez, _The schema theorem considered insufficient, in Proceedings of the Sixth IEEE International Conference on Tools with Artificial Intelligence, (New Orleans), pp. 748_751, 1994.

M. D. Vose, Modeling simple genetic algorithms, Evolutionary Computation, vol. 3, pp. 453_472, 1995.

C. R. Stephens and H. Waelbroeck, _Effective degrees of freedom in genetic algorithms and the block hypothesis, in Proceedings of 7th International Conference on Genetic Algorithms, (San Francisco, CA), pp. 34_40, Morgan Kaufmann, 1997.

M. D. Vose and A. H. Wright, _Form invariance and implicit parallelism, Evolutionary Computation, vol. 9, pp. 355_370, 2001.

C. R. Stephens and H. Waelbroeck, _Schemata evolution and building blocks, Evolutionary Computation, vol. 7, pp. 109_124, 1999.

D. Whitley, _An executable model of a simple genetic algorithm, in Foundations of Genetic Algorithms 2 (L. D. Whitley, ed.), pp. 45_62, San Mateo, CA: Morgan Kaufmann, 1993.

R. Pawar, J. S. Saini, M. Gopal, and A. P. Mittal, Towards generalized expression for schemata count. Applied Soft Computing, 2011.

N. J. Radcli_e, _Forma analysis and random respectful recombination, in Proceedings of the 4th International Conference on Genetic Algorithms, 1991.

D. E. Goldberg, The design of innovation: Lessons from and for competent genetic algorithms, vol. 7. Springer Science and Business Media, 2002.

H. Lee and T.-L. Yu, Off-line building block identification: detecting building blocks directly from fitness without genetic algorithms, in Proceedings of the 14th annual conference on Genetic and evolutionary computation, pp. 641_648, 2012.

R. Faraji and H. R. Naji, An efficient crossover architecture for hardware parallel implementation of genetic algorithm, vol. 128. Neurocomputing, 2014.

A. Shukla, H. M. Pandey, and D. Mehrotra, _Comparative review of selection techniques in genetic algorithm, in 2015 International Conference on Futuristic Trends on Computational Analysis and Knowledge Management (ABLAZE), pp. 515_519, 2015.

A. Mishra and A. Shukla, Mathematical analysis of the cumulative effect of novel ternary crossover operator and mutation on probability of survival of a schema. Theoretical Computer Science, 2016.

Z. Qiongbing and D. Lixin, A new crossover mechanism for genetic algorithms with variable-length chromosomes for path optimization problems. Expert Systems

with Applications, 2016.

C. J. Uzor, M. Gongora, S. Coupland, and B. N. Passow, Adaptive mutation compact genetic algorithm for dynamic environments, Soft Computing, 2016.

Y. Du, K. Aoki, M. Sakamoto, K. Yamamori, and H. Furutani, Asymmetric mutation model in genetic algorithm, Artificial Life and Robotics, vol. 22,

no. 1, pp. 17_23, 2017.

D. Corus and P. S. Oliveto, Standard steady state genetic algorithms can hill climb faster than mutation-only evolutionary algorithms, IEEE Transactions on Evolutionary Computation, vol. 22, no. 5, pp. 720_732, 2018.

A. Mishra and A. Shukla, _Mathematical analysis of schema survival for genetic algorithms having dual mutation, Soft Computing, vol. 22, no. 6, pp. 1763_1771, 2018.

X. S. Yang and S. Koziel, Computational optimization, modelling and simulation-a paradigm shift, in Procedia Computer Science, pp. 1297_1300, 2010.

U. Mehboob, J. Qadir, S. Ali, and A. Vasilakos, Genetic algorithms in wireless networking: techniques, applications, and issues. Soft Computing, 2016.

N. Thi, P. Quyen, and J. C. Chen, _Hybrid genetic algorithm to solve resource constrained assembly line balancing problem in footwear manufacturing, Soft Computing, 2016.

B. Nogueira, M. P., E. Tavares, R. Silva, and E. Andrade, Multiobjective optimization of multimedia embedded systems using genetic algorithms and stochastic simulation. Soft Computing, 2016.

L. Poladian, Effect of parent selection and sibling rivalry on building-block assembly, Natural Computing, vol. 9, no. 1, pp. 263_282, 2010.

R. M. Cole, _Clustering with genetic algorithms, Master's thesis, (Master of Science). Department of Computer Science, University of Western, Australia, 1998. 101f.

A. Mishra and A. Shukla, _Analysis of the effect of elite count on the behavior of genetic algorithms: A perspective, in 2017 IEEE 7th International Advance Computing Conference (IACC), pp. 835_840, 2017.

D. S. Knysh and V. M. Kureichik, Parallel genetic algorithms: a survey and problem state of the art, Journal of Computer and Systems Sciences International, vol. 49, no. 4, pp. 579_589, 2010.

J. L. Payne, M. Giacobini, and J. H. Moore, Complex and dynamic population structures: synthesis, open questions, and future directions, Soft Computing, vol. 17, no. 7, pp. 1109_1120, 2013.

Downloads

Publicado

2022-09-12

Como Citar

Pinto, A. R. F., Martarelli, N. J., & Nagano, M. S. (2022). Algoritmo Genético: Principais Gaps, Trade-offs e Perspectivas para Futuras Pesquisas. Trends in Computational and Applied Mathematics, 23(3), 413–438. https://doi.org/10.5540/tcam.2022.023.03.00413

Edição

v. 23 n. 3 (2022)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.