Desempeño de algoritmos heurísticos en la solución de problemas cuadráticos no convexos con restricciones de caja

Ridelio  Miranda Pérez; Juan Manuel  Castellanos Hernández

doi:10.24054/rcta.v2i34.66

Autores/as

Ridelio Miranda Pérez Universidad de Cienfuegos
Juan Manuel Castellanos Hernández Universidad de Cienfuegos

DOI:

https://doi.org/10.24054/rcta.v2i34.66

Palabras clave:

programación cuadrática, algoritmos heurísticos, programación paramétrica, relación doblemente no negativa, métodos de continuación, optimización global

Resumen

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

Los datos de descargas todavía no están disponibles.

Citas

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 deizmsol15SQP-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 metaheuristics. 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 nonconvex mixed integer nonlinear programming. Computers & Operations Research, 36(7), 2217-2229.

Vavasis, S. A. (1990). Quadratic programming is inNP. Information Processing Letters, 36(2), 73-77.