Desempeño de algoritmos heurísticos en la solución de problemas cuadráticos no convexos con restricciones de caja
DOI:
https://doi.org/10.24054/rcta.v2i34.66Palabras clave:
programación cuadrática, algoritmos heurísticos, programación paramétrica, relación doblemente no negativa, métodos de continuación, optimización globalResumen
En el trabajo se proponen varios algoritmos heurísticos para resolver el problema cuadrático no convexo con restricciones de caja y se compara su rendimiento tomando en consideración la calidad de las soluciones y el tiempo de ejecución empleado. Adicionalmente, comparamos los resultados obtenidos con los algoritmos heurísticos con los algoritmos híbridos heurísticos, que consisten, una vez hallada la mejor solución del algoritmo heurístico, realizar una exploración exhaustiva de su vecindad, para determinar un mínimo local contenido en ella. Los resultados muestran un mejor desempeño de las metaheurísticas Enjambre de Partículas (PSO) y Algoritmos Genéticos (GA) en problemas de hasta 200 variables. Por último se muestra un mejor desempeño de las metaheurísticas hibridas en comparación con las no híbridas, aunque no poseen diferencias significativas entre ellas.
Descargas
Citas
Asachi, M., & Marandi, R. (2015). Response surface modeling of lead and copper removal from oil field brine by potential sorption method. Particulate Science and Technology, 33(3), 290-300. Recuperado de ResponseSurfaceModelingofLeadandCopperRemovalfromOilFieldBrinebyPotentialSorptionMethod.pdf.
Baghel, M., Agrawal, S., & Silakari, S. (2012). Survey of metaheuristic algorithms for combinatorial optimization. International Journal of Computer Applications, 58(19). Recuperado de https://www.researchgate.net/profile/Mohamed_Mourad_Lafifi/post/What_is_the_metaheuristic_that_best_works_to_solve_permutation-based_combinatorial_optimization_problems/attachment/5a58c46e4cde266d588263f4/AS:5819 82691704832@1515766894417/download/Survey+of+Metaheuristic+Algorithms+for+Combinatorial+Optimization.pdf
Berry, K., Mielke, P., & Johnston, J. (2012). Thetwo-samplerank-sumtest:early development. Electronic Journal for History of Probability and Statistics, 8. Burer, S., & Vandenbussche, D. (2008). A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program., 2 Ser. A(113), 259-282.
Chen, J. (2010). Convex relaxations in nonconvex and applied optimization (University of Iowa). Recuperado de htps://ir.uiowa.edu/etd/654
Chen, J., & Burer, S. (2012). Globally solving nonconvex quadratic programming problems via completely positive programming. Mathematical Programming Computation, 4(1), 33-52. Recuperado de 79-283-1-PB.pdf.
Connolly, D. T. (1990). An improved annealing scheme for the QAP. European Journal of Operational Research, 46(1), 93-100.
Dehghan, A., & Shah, M. (2018). Binary Quadratic Programing for Online Tracking of Hundreds of People in Extremely Crowded Scenes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(3), 568-581. https://doi.org/10.1109/TPAMI.2017.2687462
Dorigo, M., Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy.
Feo, T. A., & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization, 6(2), 109-133.
Floudas, C. A., & Visweswaran, V. (1995). Quadratic optimization. En Handbook of global optimization (pp. 217–269). Springer. 10.1.1.55.4573.pdf.
Ghandeshtani, K. S., Mollai, N., Seyedkashi, S., & Neshati, M. M. (2010). New simulated annealing algorithm for quadratic assignment problem. 87-92. Recuperado de https://www.researchgate.net/profile/S_M_Hossein_Seyedkashi/publication/265943043_New_Simulated_Annealing_Algorithm_for_Quadratic_Assignment_Problem/links/5524ee1b0cf2b123c5175e65.pdf
Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers & operations research, 13(5), 533-549.
Hager, W. W., & Hungerford, J. T. (2015). Continuous quadratic programming formulations of optimization problems on graphs. European Journal of Operational Research, 240(2), 328-337. Recuperado de graph.pdf.
Holland, J. H. (1975). Adaptation in natural and artificial systems Ann Arbor. The University of Michigan Press, 1, 975.
Horst, R., Pardalos, P. M., & Van Thoai, N. (2000). Introduction to global optimization. Springer Science & Business Media.
Iqbal, M. K., Nadeem, A., Sherazi, F., & Khan, R. A. (2015). Optimization of process parameters for kitchen waste composting by response surface methodology. International Journal of Environmental Science and Technology, 12(5), 1759-1768.
Izmailov, A. F., & Solodov, M. V. (2016). Some new facts about sequential quadratic programming methods employing second derivatives. Optimization Methods and Software, 31(6), 1111-1131. Recuperado de izmsol15SQP-modH.pdf.
Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization (PSO). 1942-1948. Recuperado de http://www.cs.cmu.edu/~arielpro/15381f16/c_slides/781f16-26.pdf
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
Krumke, S. (1994). Eine modifizierte barriermethode fur konvexe quadratische optimierungsprobleme. Unpublished master’s thesis, University of Wurzburg, Germany. (Diplomthesis)
Kvasov, D. E., & Mukhametzhanov, M. S. (2018). Metaheuristic vs. Deterministic global optimization algorithms: The univariate case. Applied Mathematics and Computation, 318, 245-259.
Laguna, M. (2000). Global optimization and meta-heuristics. Recuperado de https://pdfs.semanticscholar.org/d88b/17e53bcca18398cb9fb9d73da680d0ec26ab.pdf
Mezura-Montes, E., & Coello, C. A. C. (2011). Constraint-handling in nature-inspired numerical optimization: Past, present and future. Swarm and Evolutionary Computation, 1(4), 173-194.
Miranda, R., Allende, S., Bouza, G., & Perez, B. (2015). Algoritmo de corte y continuación con ramificación y acotación para la solución del problema cuadrático con restricciones de caja. Revista Ciencias Matemáticas, 29, 1, 19-29.
Miranda, R. Alonso, S. A., Cañedo, B. P., & Allende, G. B. (2018). DESEMPEÑO COMPUTACIONAL DE ESTRATEGIAS HÍBRIDAS PARA LA SOLUCIÓN DE PROBLEMAS CUADRÁTICOS NO CONVEXOS CON RESTRICCIONES DE CAJA. Investigación Operacional, 39(1), 42-53.
Munapo, E., & Kumar, S. (2015). A New Heuristic for the Convex Quadratic Programming Problem. American Journal of Operations Research, 5(05), 373.
Otta, B. P. (2013). Numerical algorithms for quadratic programming for approximated predictive control. Recuperado de https://support.dce.felk.cvut.cz/mediawiki/images/6/63/Dp_2013_otta_pavel.pdf
Pedersen, M. E. H. (2010). Good parameters for particle swarm optimization. Hvass Lab., Copenhagen, Denmark, Tech. Rep. HL1001, 1551-3203.
Peltonen, T. (2015). Comparative study of population-based metaheuristic methods in global optimization. Recuperado de https://jyx.jyu.fi/bitstream/handle/123456789/46236/URN:NBN:fi:jyu-201506082229.pdf?sequence=1
Peng Hui Tan, Rasmussen, L. K., & Teng Joon Lim. (2000). Box-constrained maximum-likelihood detection in CDMA. 2000 International Zurich Seminar on Broadband Communications. Accessing, Transmission, Networking. Proceedings (Cat. No.00TH8475), 55-62. https://doi.org/10.1109/IZSBC.2000.829228
Peng Hui Tan, Rasmussen, L. K., & Lim, T. J. (2001). Constrained maximum-likelihood detection in CDMA. IEEE Transactions on Communications, 49(1), 142-153. https://doi.org/10.1109/26.898258
Schlüter, M., Egea, J. A., & Banga, J. R. (2009). Extended ant colony optimization for non-convex mixed integer nonlinear programming. Computers & Operations Research, 36(7), 2217-2229.
Vavasis, S. A. (1990). Quadratic programming is in NP. Information Processing Letters, 36(2), 73-77.
Descargas
Publicado
Versiones
- 2019-07-04 (5)
- 2019-07-04 (4)
- 2019-07-04 (3)
- 2019-08-01 (2)
- 2020-10-03 (1)
Cómo citar
Número
Sección
Licencia
Derechos de autor 2019 REVISTA COLOMBIANA DE TECNOLOGIAS DE AVANZADA
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.
