Maio 2020 vol. 3 num. 1 - XIX Simpósio de Pesquisa Operacional & Logística da Marinha
Artigo Completo - Open Access.
BRKGA – UM PACOTE DO R PARA PROBLEMAS DE OTIMIZAÇÃO
BRKGA – UM PACOTE DO R PARA PROBLEMAS DE OTIMIZAÇÃO
Brito, José André de M. ; Fadel, Augusto ; Semaan, Gustavo S. ;
Artigo Completo:
Nos dias atuais, pesquisadores são, frequentemente, confrontados com inúmeras aplicações reais que remetem a problemas de otimização de alta complexidade. Face à complexidade desses problemas, a aplicação de métodos exatos ou de enumeração exaustiva torna-se inviável. De forma contornar essa dificuldade, pode ser considerada a aplicação de algoritmos implementados a partir de heurísticas ou metaheurísticas. Neste sentido, o presente trabalho traz a apresentação de um pacote do R que contém o algoritmo BRKGA (função), que pode ser utilizado, de forma simples, em diversos problemas de otimização. Além dos argumentos comuns de um BRKGA, para utilizar o pacote, o usuário precisa, apenas, definir a função e um decodificador para o seu problema. São apresentados alguns exemplos do uso desse pacote, considerando funções objetivo e decodificadores para vários problemas de otimização, como, por exemplo, o PCV e o problema de agrupamento.
Artigo Completo:
Nos dias atuais, pesquisadores são, frequentemente, confrontados com inúmeras aplicações reais que remetem a problemas de otimização de alta complexidade. Face à complexidade desses problemas, a aplicação de métodos exatos ou de enumeração exaustiva torna-se inviável. De forma contornar essa dificuldade, pode ser considerada a aplicação de algoritmos implementados a partir de heurísticas ou metaheurísticas. Neste sentido, o presente trabalho traz a apresentação de um pacote do R que contém o algoritmo BRKGA (função), que pode ser utilizado, de forma simples, em diversos problemas de otimização. Além dos argumentos comuns de um BRKGA, para utilizar o pacote, o usuário precisa, apenas, definir a função e um decodificador para o seu problema. São apresentados alguns exemplos do uso desse pacote, considerando funções objetivo e decodificadores para vários problemas de otimização, como, por exemplo, o PCV e o problema de agrupamento.
Palavras-chave: Otimização; Metaheurísticas; Pacote; Linguagem R; BRKGA.,
Palavras-chave: Otimização; Metaheurísticas; Pacote; Linguagem R; BRKGA.,
DOI: 10.5151/spolm2019-070
Referências bibliográficas
- [1] HANSEN, P. and JAUMARD, B. (1997). Cluster Analysis and Mathematical Programming. Mathematical Programming, 79:191-215. [2] KAUFMAN L. and ROUSSEEUW P.J. (1989). Finding Groups in Data – An Introduction to Cluster Analysis. Wiley-Interscience Publication. [3] SEMAAN, G.S. (2013). Algoritmos para o Problema de Agrupamento Automático. (Tese de Doutorado) – Instituto de Computação, Universidade Federal Fluminense, Rio de Janeiro, RJ. [4] ANGELELLI, E. and SPERANZA, M.G (2002). The Periodic Vehicle Routing Problem with Intermediate Facilities, European Journal of Operational Research, 137:233-247, Elsevier. [5] GOLDEN, L. F. B. and WASIL E. (2004). Very large-scale vehicle routing: new test problems, algorithms and results. Computers & Operations. [6] DREZNER, Z and HAMACHER. H. W. (2004). Facility location: applications and theory. New York, NY: Springer. [7] VYGEN, J. (2005). Approximation algorithms for facility location problems. Bonn, Germany: Research Institute for Discrete Mathematics. [8] BRITO, J. A. M.; SILVA, P.L.N, SEMAAN, G. S. and MACULAN, N. (2015) . Integer Programming Formulations Applied to Optimal Allocation in Stratified Sampling. Survey Methodology, 41, p. 427-442. [9] WOLSEY, L.A. and NEMHAUSER, G.L. (1999). Integer and Combinatorial Optimization, first edition, Wiley-Interscience. [10] MARTÍ, R., PARDALOS, P.M and RESENDE, M.G.C. (2018). Handbook of Heuristics. Springer. [11] GONÇALVES, J.R. and RESENDE, M.G.C (2011). Biased random-key genetic algorithms for combinatorial optimization, Journal of Heuristics, 17: 487-525. [12] APPLEGATE D. L., BIXBY, R. E., CHVÁTAL V. and Cook, W. (2006). The travelling salesman problem: a computational Study. Princeton: Princeton University Press. [13] RESENDE, M.G.C. Introdução aos Algoritmos Genéticos de Chaves Aleatórias Viciadas. Anais do XLVSBPO, p. 3680-3691, Natal/RN, 2013. [14] LINDEN, R. (2012). Algoritmos Genéticos. Editora Ciência Moderna. 3a edição. [15] SPEARS, W.M., DEJONG, K.A. (1991). On the virtues of parameterized uniform crossover. In: Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230-236. [16] RESENDE, M.G.C. (2013). Biased random-key genetic algorithms. Talk given at XLV Symposium of the Brazilian Operational Research Society (XLV SBPO) Natal, RN. [17] GAREY, M. and JOHNSON, D. S (1990). Computer and Intractibility: A guide to the Theory of NPCompleteness, Freeman, San Francisco. [18] MARTELLO, S. and TOTH, P. (1990). Knapsack Problems - Algorithms and Computer Implementations. Wiley. [19] GOLDBARG, M.C. e LUNA, H.P.L. (2000). Otimização Combinatória e Programação Linear – Modelos e Algoritmos. Editora Campus. [20] TSOULOS, L.G. (2009). Solving Constrained Optimization Problems Using a Novel Genetic Algorithm. Applied Mathematics and Computation, 208, p. 273-283. [21] YENIAY, O. and A. BEYTEPE (2005). Penalty Function Methods for Constrained Optimization with Genetic Algorithms. Mathematical and Computational Applications, 10(1), pp.45-56, [22] GLOVER, F. HERSH, G. e MILLAN, C. (1977). Selecting subsets of maximum diversity, MS/IS Report no 77-9, University of Colorado at Boulder. [23] MARTÍ, R., GALLEGO, M., DUARTE, A. and PARDO, E. g. (2013) heuristics and metaheuristics for the maximum diversity problem. Journal of Heuristics 19(4): 591-615. [24] KUBY, M. J. (1987). Programming models for facility dispersion: The p-dispersion and maximum dispersion problem. Geographical Analysis, 19(4):315-329. [25] ERKUT, E. (1990). The discrete p-dispersion problem. European Journal of Operational Research 46(1): 48–60. [26] CAMPELLO, R.E. e MACULAN, N. (1994). Algoritmos e Heurísticas – Desenvolvimento e Avaliação de Performance. Editora UFF. [27] COCHRAN, W. G. (1977). Sampling Techniques. Third Edition – Wiley. [28] LOHR, S. (2009). Survey sampling, New York: Addison and Huxley publications, 2ndEd. [29] FRIEDMAN, J. H. and MEULMAN J.J. (2004). Clustering objects on subsets of attributes. Journal Royal Statistics Society B, Part 4,66:815-849. [30] HIMMELBLAU, D. (1972). Applied Nonlinear Programming. McGraw-Hill.
Como citar:
Brito, José André de M.; Fadel, Augusto; Semaan, Gustavo S.; "BRKGA – UM PACOTE DO R PARA PROBLEMAS DE OTIMIZAÇÃO", p. 964-979 . In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha.
São Paulo: Blucher,
2020.
ISSN 2175-6295,
DOI 10.5151/spolm2019-070
últimos 30 dias | último ano | desde a publicação
downloads
visualizações
indexações