Grupo de Optimización Combinatoria

Everardo Gutiérrez López { egutierr@cicese.mx } Estudiante de Doctorado en Ciencias de la Computación

Tesis de doctorado: Caracterización de Grafos de Búsqueda para problemas combinatorios.

Director de tesis: Dr. Carlos Alberto Brizuela Rodríguez

Descripción de la tesis: La existencia de problemas para los cuales no se conocen algoritmos eficientes, ha motivado el desarrollo de métodos alternativos con el fin de obtener soluciones aceptables en la práctica. A pesar de los resultados pesimistas desde el punto de vista teórico, el método conocido como Búsqueda Local (BL) ha sido utilizado exitósamente en la práctica. Esto ha motivado diversos estudios que buscan determinar en cuáles casos es posible obtener buenos resultados, la mayoría de los cuales tratan de caracterizar las estructuras de vecindario sobre las que trabaja la BL, concidas como Grafos de Búsqueda.

Documento de la propuesta doctoral

Inicio de Página

Tesis de Maestría: Algoritmos Genéticos para el problema de Localización de Radio Bases

Director de tesis: Dr. Carlos Alberto Brizuela Rodríguez

Descripción de la tesis: En este trabajo de tesis, se propone un algoritmo genético para tratar el problema de Localización de Radio Bases (LRB). Se propone una representación para el problema así como los operadores necesarios para esa representación. Se compara el desempeño del algoritmo propuesto con el utilizado en trabajos anteriores, utilizando dos modelos del problema. Se analiza además la calidad de la solución generada por el algoritmo propuesto, en un caso que considera las características de la tecnología CDMA (Code Division Multiple Access). Se presenta también un análisis del comportamiento del algoritmo utilizando el conceptode vecindades.
Los resultados obtenidos en este trabajo indican, por un lado, que el algoritmo propuesto es superior a los utilizados anteriormente en la literatura, y que las soluciones que genera son aceptables en un entorno CDMA. Por último, el análisis de vecindades nos muestra que las vecindades generadas sobre la representación entera mejoran a las generadas sobre la representación binaria.

Inicio de Página

Listado de publicaciones:

• Gutiérrez, E. and Brizuela, C. A. 2006. "ILS-Perturbation Based on Local Optima Structure for the QAP Problem". En: Gelbukh, A. F., Reyes García, C. A. (Eds.) 5th Mexican International Conference on Artificial Intelligence (MICAI 2006), Apizaco, México. Springer, 404-414 p.Versión preliminar


• Brizuela, C. A. and Gutiérrez, E. 2005. "Multi-objective Go With The Winners Algorithm: Preliminary Study". En: Coello Coello, C. A., Hernández Aguirre, A., Zitzler, E. (Eds.) Third International Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), Guanajuato, México. Springer, 206-220 p.Versión preliminar


• Gutiérrez, E. y Brizuela, C. A. 2005. "Introducing LS Interaction for Problems having the "Big Valley" Structure".Encuentro Mexicano de Computación (ENC'05). Taller de Optimización, Puebla. BUAP.


• Gutiérrez, E. "Search Graphs Characterization for Combinatorial Problems". Encuentro Mexicano de Computación (ENC'05). Consorcio Doctoral, Puebla. BUAP.


• González-Gurrola, L. C., Brizuela, C. A. and Gutiérrez, E. 2004 "A Genetic Algorithm for the Shortest Common Superstring Problem". En: Lemaitre, C., Reyes, C. A. and González, J. A., editores, 9th Ibero-American Conference on AI (IBERAMIA), Puebla, México.


• Brizuela, C. A. y Gutiérrez, E. 2003. "An Experimental Comparison of Two Different Encoding Schemes for the Location of Base Stations in Cellular Networks". En: Günter, R., editor, Application of Evolutionary Computing, LNCS 2611, Berlin. Springer, 176-186 p.Versión preliminar


• Gutiérrez, E. y Brizuela, C. A. 2003. "Comparación Experimental de Operadores de Cruzamiento para el Problema de Localización de Radio Bases en Redes Celulares". En: Botella, S., Hernández, A., y Coello, C., editores, Congreso Mexicano de Computación Evolutiva (COMCEV'03), Guanajuato. CIMAT, 81-93 p.

Inicio de Página

Ligas de Interés:

CiteSeer

Biblioteca digital en literatura científica enfocada principalmente en el área de ciencias de la computación.

DBLP

Información bilbiográfica de las principales revistas y proceedings de ciencias de la computación.

UCSD, CSE

Departamento de Ciencias de la Computación e Ingeniería de la Universidad de California en San Diego.

MIT ORC

Investigación de Operaciones en el Instituto Tecnológico de Massachusetts.

EvoNet

Sitio Web de EvoNet (European Network of Excellence in Evolutionary Computing).

Inicio de Página

Areas de Interés Personal: Optimización Combinatoria, Búsqueda Local, Complejidad Computacional, Computación Evolutiva.