Ciencias Exactas y Ciencias de la Salud
Permanent URI for this collectionhttps://hdl.handle.net/11285/551039
Pertenecen a esta colección Tesis y Trabajos de grado de las Maestrías correspondientes a las Escuelas de Ingeniería y Ciencias así como a Medicina y Ciencias de la Salud.
Browse
Search Results
- Automated design of specialized variation operators using a generation hyper heuristic for the multi objective quadratic assignment problem(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2025-06) Morales Paredes, Adrián Isaí; Terashima Marín, Hugo; emimmayorquin; Falcón Cardona, Jesús Guillermo; School of Engineering and Sciences; Campus Monterrey; Coello Coello, Carlos ArtemioThe development of specialized, domain-specific operators has significantly enhanced the performance of evolutionary algorithms for solving optimization problems. However, creating such operators often requires substantial effort from human experts, making the process slow, resource-intensive, and heavily reliant on domain knowledge. To overcome these limitations, generation hyper-heuristics provide a framework for automating the design of variation operators by evolving combinations of heuristic components without direct expert input. In this work, a generation hyper-heuristic method based on grammatical evolution using the hypervolume indicator (HV) as part of its selection mechanism to automatically design variation operators (crossover and mutation) tailored to the multi-objective quadratic assignment problem (mQAP)—a challenging combinatorial optimization problem with many real-world applications—is proposed. The proposed method was used to generate variation operators following a grammar-defined search space. This generation was guided by six mQAP instances featuring 10, 20, and 30 variables with two and three objectives, leveraging MOEA/D as its multi-objective optimizer. During the generation process, the hyper-heuristic exhibited consistent improvements in the HV of the population throughout the evolutionary process, demonstrating its ability to evolve increasingly effective operators over time. To validate the hyper-heuristic output, the generated operators were evaluated on sixteen unseen and diverse mQAPinstances. From experimental results, the evolved operators consistently outperformed standard ones regarding median HV in all test instances. Statistical tests further indicate that these evolved operators possess strong exploration and exploitation capabilities for problems with permutation-based solution representations and behave distinctly from conventional operators. Pairwise comparisons confirmed their superiority over human-designed recombination operators such as PMX and CX in HV performance. These results highlight the potential of automated operator design in effectively solving complex combinatorial optimization problems, such as the mQAP. Beyond this specific case, the proposed framework contributes to the field of automated operator design by introducing a new methodology applicable to multi-objective combinatorial optimization scenarios.
- Tailoring metaheuristics for designing thermodynamic-optimal water based cooling devices for microelectronic thermal management applications(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2023-06) Pérez Espinosa, Guillermo; TERASHIMA MARIN, HUGO; 65879; Terashima Marín, Hugo; emipsanchez; Ortiz Bayliss, José Carlos; Aviña Cervantes, Juan Gabriel; Escuela de Ingeniería y Ciencias; Campus Monterrey; Cruz Duarte, Jorge MarioHeat sinks provide a common and straightforward alternative to dealing with the Microelectronic Thermal Management (MTM) problem due to their simplicity of fabrication, low cost, and reliability of heat dissipation. The MTM problem is highly relevant in today's electronics industry, as new electronic devices' miniaturization and enhanced performance have increased their heat power generation. So, regarding the second law of thermodynamics, an optimal heat sink design can guarantee that the microelectronic components operate without jeopardizing their life span and performance. To solve this challenging problem, Metaheuristics~(MHs) have shown to be excellent alternatives due to their reliability, flexibility, and simplicity. Nevertheless, no single MH guarantees an overall outstanding performance. Thus, the motivation for this work is to open ample room for practitioners to find the proper solver to deal with a given problem without requiring extensive knowledge of heuristic-based optimization. This work studies the feasibility of implementing a strategy for Automatic Metaheuristic Design powered by a hyper-heuristic search to minimize the entropy generation rate of microchannel heat sinks and tailor population-based and metaphor-less MHs for solving the MTM. A mathematical model based on thermodynamic modeling via the Entropy Generation Minimization (EGM) criterion was used to obtain the value of the entropy generation rate of a rectangular microchannel heat sink according to their design. Four different scenarios were considered, varying the design specifications for the heat sinks and comparing our generated MH against seven well-known heuristic-based algorithms from the literature. The one-sided Wilcoxon signed ranked test was used to perform these comparisons. Statistical evidence was found to claim that our tailored MHs manage to outperform them, in most cases, at least in the tested scenarios. Additionally, we followed a methodology to infer which operators should be considered in a curated heuristic space to design the proper MH easily. We found that using this curated search space benefits the overall process, as the HH algorithm managed to tailor high-performing MHs faster and more consistently than its counterpart. Furthermore, insights were obtained on which HH parameters are more suitable for our search, as some can enhance the tailoring process when tuned correctly. Finally, we tested some of our best designs found to see how they perform when minor fluctuations appear on some variables, just as they occur in real-life implementations. All the experimentation processes also found that the search operators of evolutionary algorithms are well suited to solve this problem, as they compose several of our tailored MHs, and that the combination of High Thermal Conductive Graphite and water achieved the lower entropy generation rate values from the four combinations tested.
- Dense video captioning of violent behavior using bi-modal transformers and unsupervised semantic information.(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2023) Cárdenas Pimentel, Israel; Terashima Marín, Hugo; emipsanchez; Conant Pablos, Santiago Enrique; Rad, Paul; School of Engineering and Sciences; Campus Estado de MéxicoThis work presents the research developed to obtain the degree of Master of Science in Computer Science. Security and safety are issues that, in recent decades, with the increasing number of crimes in cities that overwhelm public security, have been subject to improvement with the use of technology. With the evolution of technology, people access security systems such as video surveillance to ensure security and safety in all places, from home to business. Nevertheless, the data these systems collect is large and sometimes complex for the non-trained eye to interpret. Therefore, a system capable of understanding the environment, the subjects involved in it, and explaining what is happening in a video with a textual description is an improvement to video surveillance to understand and prevent crime. Technical challenges of dense video captioning are related to the correct event detection and textual description of these events by exploiting visual and audio features on a dataset with a specific domain. Some video captioning techniques have been developed, like bidirectional analysis, hierarchical reinforcement learning agent and event sequence generation. The difference between these dense video captioning models and the proposed bi-modal transformer is that it generates descriptions for events using visual and audio inputs, showing how audio facilitates the dense video captioning performance. However, the audio signal is not available in all cases for the proposed application of captioning of violent behavior present in CCTV footage. So the audio signal is replaced in the Bi-modal transformer by unsupervised semantic information, learn with a method based on the premise that complex events can be decomposed into more elementary events shared across several complex events. The dense video captioning process is relevant because it covers a tedious and challenging task for humans helping to reduce the work of detection and interpretation of the events presented on screen. For this work, implementing a dataset of a specific domain of violent behavior satisfies this problem. The contribution of this work is to implement this dense video captioning infrastructure with a dataset with these characteristics, the existent DCSASS video dataset, a collection of surveillance camera videos that contain anomalies and expected behaviors, and the merge of this dataset with the ActivityNet dataset, a collection of videos that contains human behavior. Both databases contribute to the description of these violent events presented in videos. The DCSASS dataset is processed to create from scratch new descriptions for the events in the videos from the DCSASS/ActivityNet merged dataset. These descriptions provide the features to feed the bi-modal transformer and train it to generate new model adapted environments involving violent and expected behaviors. Also, it allows results closest to the original implementation of the ActivityNet dataset when comparing the output metric scores such as METEOR, SPLICE, and CIDER. It represents an opportunity to engance the dataset and improve the trainning process of this new model.
- Hyper-heuristic Model Based on Neural Networks for Solving the Metaheuristic Composition Optimisation Problem in Continuous Domains(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2022-12) Tapia Avitia, José Manuel; Terashima Marín, Hugo; emimmayorquin; Pillay, Nelishia; Ortiz Bayliss, José Carlos; Amaya Contreras, Iván Mauricio; School of Engineering and Sciences; Campus Monterrey; Cruz Duarte, Jorge MarioMetaheuristics (MHs) have been proven to be powerful algorithms for solving highly non-linear and intricate optimisation problems over discrete, continuous, or mixed domains, with applications ranging from basic sciences to applied technologies. Nowadays, the literature is prolific with MHs based on outstanding ideas, but the researchers often recombine elements from other methods. To avoid the frenetic tendency of proposing methods more focused on metaphors than operations, a standard model has been proposed to customise population-based MHs, which uses simple heuristics or search operators extracted from well-known metaheuristics. The framework corresponding to this model can be found as Customising Optimising Metaheuristic via Hyper-heuristic Search (CUSTOMHyS), which facilitates implementing models that explore a heuristic space. Still, they are limited by the nature of the metaheuristics used in such models, as such algorithms does not consider the information gained from previous explorations to enhance the tailoring process. A field of action and improvement that has not been explored is the model implementation to take advantage of previous results and learns from them to boost the performance of the tailoring process. For that reason, we propose a hyper-heuristic model based on neural networks, which is trained with processed sequences of heuristics to identify patterns that one can use for generating modified metaheuristics. Being more specific, the task assigned to the neural network is to predict the simple heuristic from the collection or heuristic space to apply next, considering a sequence of heuristics already applied to the low-level problem. Using the neural networks, the challenge is to define how to generate metaheuristics with a high performance for tackling a family of optimisation problems. This research work propose a novel methodology that decomposes the metaheuristics into several subsequences of heuristics to train the neural network models. To prove the feasibility of the proposed model and training methodology, it is compared against generic well-known basic metaheuristics and other heuristic-based approaches, such as the unfolded MHs. The results evidence that the proposed model outperform an average of 86% of all scenarios; in particular, 91% of basic and 81% of unfolded approaches. Plus, it is worth to highlight the configurable capability of the proposed model: several experiments are carried out to explore a few control variables and show their effects in the model. It proves to be exceptionally versatile regarding the computational budget. After exploring and finding a suitable configuration, we perform an extended analysis of the training computational cost, and a study of the metaheuristics generated by the model. Moreover, we analyse the usage of previously generated metaheuristics on an unseen problem via a few strategies. The proposed model and its metaheuristics show their adaptation capabilities to unseen problems, proving to be a good alternative for real-world application problems.
- Detection of suspicious attitudes on video using neuroevolved shallow and deep neural networks models(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2021-11) Flores Munguía, Carlos; Terashima Marín, Hugo; puemcuervo/tolmquevedo; Oliva, Diego; Ortiz Bayliss, Jose Carlos; School of Engineering and Sciences; Campus MonterreyThe analysis of surveillance cameras is a critical task usually limited by the people involved in the video supervision devoted to such a task, their knowledge, and their judgment. Security guards protect other people from different events that can compromise their security, like robbery, extortion, fraud, vehicle theft, and more, converting them to an essential part of this type of protection system. If they are not paying attention, crimes may be overlooked. Nonetheless, different approaches have arisen to automate this task. The methods are mainly based on machine learning and benefit from developing neural networks that extract underlying information from input videos. However, despite how competent those networks have proved to be, developers must face the challenging task of defining the architecture and hyperparameters that allow the network to work adequately and optimize the use of computational resources. Furthermore, selecting the architecture and hyperparameters may significantly impact the neural networks’ performance if it is not carried out adequately. No matter the type of neural network used, shallow, dense, convolutional, 3D convolutional, or recurrent; hyperparameter selection must be performed using empirical knowledge thanks to the expertise of the designer, or even with the help of automated approaches like Random Search or Bayesian Optimization. However, such methods suffer from problems like not covering the solution space well, especially if the space is made up of large dimensions. Alternatively, the requirement to evaluate the models many times to get more information about the evaluation of the objective function, employing a diverse set of hyperparameters. This work proposes a model that generates, through a genetic algorithm, neural networks for behavior classification within videos. The application of genetic algorithms allows the exploration in the hyperparameters solution space in different directions simultaneously. Two types of neural networks are evolved as part of the thesis work: shallow and deep networks, the latter based on dense layers and 3D convolutions. Each sort of network takes distinct input data types: the evolution of people’s pose and videos’ sequences, respectively. Shallow neural networks are generated by NeuroEvolution of Augmented Topologies (NEAT), while CoDeepNEAT generates deep networks. NEAT uses a direct encoding, meaning that each node and connection in the network is directly represented in the chromosome. In contrast, CoDeepNEAT uses indirect encoding, making use of cooperative coevolution of blueprints and modules. This work trains networks and tests them using the Kranok-NV dataset, which exhibited better results than their competitors on various standard metrics.
- Two-fold Approach for Video Retrieval: Semantic Vectors to Guide Neural Network Training and Video Representation Approximation Via Language-Image Models(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2021-05) Portillo Quintero, Jesús Andrés; TERASHIMA MARIN, HUGO; 65879; Terashima Marín, Hugo; tolmquevedo, emipsanchez; Ortiz Bayliss, José Carlos; Han, David; Escuela de Ciencias e Ingeniería; Campus MonterreyVideo Retrieval is a challenging task concerned with recovering relevant videos from a collection to fulfill a query. Defining relevance is an unsolved problem in Information Retrieval literature since it is prone to subjective considerations. Text-based Video Retrieval systems calculate relevance by measuring the relationship between a textual query and video metadata. This is a widely used approach, but it does not consider motion and video dynamics. On the other hand, content-based methods account for visuals in the retrieval process but can only operate with visual queries. This phenomenon poses the question of whether it is possible to create a Video Retrieval system that collects video based on visual content and works with textual queries. A method to bridge the semantic gap between video and text is presented. This approach employs a Multimodal Machine Learning model capable of mapping multiple types of infor- mation among themselves. The connection between modalities occurs in a learned video-text space, where it is possible to measure similarity between them. With a trained system like this, it is possible to retrieve the most similar videos to a query by obtaining the similarity between the vector representation of a text query and a collection of videos. The work presented in this thesis is focused on a Dual Encoder architecture to funnel video and text information through independent Neural Networks. These Neural Networks take advantage of pre-trained models for each modality, called backbones. Other authors have used word-level backbones to encode text; we claim this method restricts the descriptiveness of text. One contribution from this work is the implementation of a novel sentence-level em- bedding backbone. This method generates sentence vectors representing the holistic phrasal meaning and has the added benefit of allowing to measure the semantic similarity among sen- tences. A second research contribution is to employ similarity measurements in text in order to guide the Neural Network training. A proposed Proxy Mining loss finds the contrary of sentences and their corresponding videos to ground the video-text space training. Compared to video, the image modality has been dedicated more assets and research efforts given its ease of use. The possibility of leveraging those assets to video is considered. A third scientific contribution is to extend the image and text representation called CLIP. This model is pre-trained to produce a fixed-size representation for images and text that allows for similarity measurement. By trying several aggregation methods, it was possible to collapse the temporal dimension inherent in videos, hence approximate a video-text representation. This breakthrough resulted in state-of-the-art results on the MSR-VTT and MSVD benchmarks. This document represents a thesis project for the degree of Master in Computer Science from Instituto Tecnolo ́gico y de Estudios Superiores de Monterrey.
- A decision tree learning hyper-heuristic for decision-making in simulated self-driving cars.(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2018-05) García Escalante, Marcelo Roger; Terashima Marín, Hugo; Özcan, Ender; Gutiérrez Rodríguez, Andres Eduardo; Conant Pablos, Santiago EnriqueThis document describes a feasible way of implementing hyper-heuristics into self-driving cars for decision-making. Hyper-heuristics techniques are used as an automated procedure for selecting or generating among a set of low-level heuristics when solving a particular type of problem. This project aims to contribute and bridging the gap between the fields of self-driving cars and hyper-heuristics since there is not any known approach linking them together to date. The decision-making process for self-driving cars has been a trend in recent years. Thus, there exist a variety of techniques applied to path planning at the moment, such as A*, Dijkstra, Artificial Potential Field, Probabilistic Roadmap, Ant Colony, Particle Swarm Optimization, etc. However, since there is no information of the complete environment at the beginning of the trip and also fast dynamic measurements of the surroundings are obtained while a decision plan is raised, selection or combination among various low-level heuristics such as the path planning techniques mentioned above could be helpful, or perhaps to create new heuristics and this way build another branch for decision-making of autonomous vehicles as a path planning method. Hyper-Heuristic approach with the help of Machine learning techniques harnesses the past driving experience of a self-driving car, which results in an improvement of the decision-making of the vehicle to different kind of scenarios. This thesis proposes a hyper-heuristic approach for decision-making of a self-driving car on a highway with different types of traffic and real-life constraints. The hyper-heuristics model introduced is of a generative type; thus, it creates a most suitable heuristic to drive the car on the road based on previously existing heuristic methods. Information is obtained by the vehicle through different onboard sensors such as Radar, Camera, LIDAR, Stereo-vision, GPS and IMU that combined establish a sensor fusion approach. Experimental study of the algorithms is performed in a simulation environment for self-driving cars built on a Unity platform. The generation hyper-heuristic proposed has a Decision Tree classifier as a high-level heuristic, which will be in charge of generating a new heuristic from the low-level heuristics presented. The Decision Tree classifier is defined with the optimal hyper-parameters obtained by a Grid-search method. In this work, there is also an explanation of the simulator's setup environment since it has evolved from a robotics' building-from-scratch level to a self-driving car platform modified from an open source resource. Thus, creating a framework suitable for extraction of instances and implementation of hyper-heuristic results to a self-driving car. Finally, the result of the hyper-heuristic performance is compared against a Finite state machine defined with greedy instructions based on the current state of the car, three heuristics built for the project: left heuristic, center heuristic, right heuristic, and a human driver.
- Algoritmos de balanceo de clases en problemas de clasificación binaria de conjuntos altamente desproporcionados(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-12-01) López Pineda, Arturo; Terashima Marín, Hugo; Valenzuela Rendón, Manuel; Conant Pablos, Santiago E.; División de Mecatrónica y Tecnologías de Información; Campus MonterreyEl aprendizaje automático es un tema de gran interés en la inteligencia artificial y sus aplicaciones, puesto que se trata de la generalización de comportamientos a partir de ejemplos conocidos. Este tema tiene una gran cantidad de aplicaciones como diagnósticos médicos, detección de fraudes, análisis de mercados, clasificación de secuencias, entre otros. El proceso de inducción seguido en estos problemas tiene que ver con el entrenamiento de un modelo lógico que represente un conjunto de datos conocidos. Los ejemplos históricos tienen distintos tamaños, proporciones y calidad en su integridad, dependiendo del tipo de información que se esté manejando. En particular, la rama de aprendizaje automático supervisado con el problema de clasificación de datos representa una muy frecuente línea de investigación por la gran utilidad que genera. En este contexto es que surge el problema del desbalance de clases, que implica que la información no se encuentre distribuida equitativamente entre todas las clases que la componen, por lo que se generan efectos no deseados en el proceso de clasificación. Esto significa que alguna de las clases del conjunto de datos tiene una cantidad mucho mayor al resto. Este trabajo considera el caso de conjuntos de datos que solamente tiene dos clases y una de ellas cuenta con una mayor cantidad de ejemplos que la otra, específicamente cuando están altamente desproporcionados. El interés principal es la aplicación de técnicas de balanceo de clases como método de preprocesamiento de datos en el proceso de entrenamiento, para mejorar, en la medida de lo posible, los resultados de clasificación. En este trabajo se aplica la técnica de muestreo de datos mediante la aplicación de dos enfoques: sobremuestreo y submuestreo. Para lograr este objetivo se establecen el límite máximo al cual se puede incrementar la clase minoritaria y el límite mínimo al cual se puede disminuir la clase mayoritaria. Con dichos límites se utilizan ambas técnicas de muestreo para mejorar la proporción de las clases. Para llevar a cabo el proceso de balanceo se utiliza la idea de generación de elementos artificiales basado en elementos más cercanos. La investigación demuestra que es factible aplicar algoritmos de balanceo de clases en el preprocesamiento de datos en la etapa de entrenamiento de los problemas de clasificación, generando mejores resultados sin alterar las características del proceso del método de aprendizaje utilizado, especialmente cuando se trata de algoritmos de balanceo de clases que implementan elementos sintéticos a partir de elementos cercanos, como SMOTE y NSU, para cada una de las clases, pero también se mejora significativamente al implementar métodos híbridos como HSR, que funcionan a través de todas las clases. También se deja claro que cada uno de los métodos de balanceo tiene diferentes grados de efectividad y su implementación se limita al tiempo de ejecución, complejidad de programación y características particulares de la información con la cual se trabaja. Finalmente, también se establece la efectividad de estos algoritmos a través de diversos clasificadores con diferentes enfoques y que son los principales métodos de clasificación implementados: árboles de decisión, clasificadores bayesiano y redes neuronales.
- Hipocorísticas mediante un enfoque neuro-evolutivo para el ordenamiento dinámico de variables en problemas de satisfacción de restricciones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-12-01) Fuentes Rosado, Jorge Iván; FUENTES ROSADO, JORGE IVAN; 218157; Terashima Marín, Hugo; Acevedo Mascarúa, Joaquín; Valenzuela Rendón, Manuel; Conant Pablos, Santiago E.; Tecnológico de Monterrey, Campus Monterrey; División de Graduados en Mecatrónica y Tecnologías de Información; Campus MonterreyMuchos de los problemas de las Ciencias de la Computación y de la Inteligencia Artificial (IA) pueden ser caracterizados como problemas de Satisfacción de Restricciones. Un CSP, por sus siglas en inglés, está compuesto por un conjunto de variables, un conjunto dominio de posibles valores y una serie de restricciones entre variables a ser satisfechas. Encontrar una solución para un problema de satisfacción de restricciones consiste en encontrar una asignación consistente para todo el conjunto de variables de tal manera que satisfaga todas las restricciones. Los algoritmos de solución más conocidos son Backtracking, Foward Checking y otros híbridos los cuales están basados en la teoría de algoritmos de búsqueda en árboles. La solución de estos problemas cuando son considerados difíciles por métodos tradicionales se vuelve muy lento y tedioso puesto que el espacio de búsqueda es muy grande, es por ello que se han realizado muchas investigaciones para la optimización de la forma de solucionar estos problemas. Además, existen instancias de CSPs que son particularmente difíciles de resolver, ya que requieren una elevada cantidad de verificaciones de consistencia para encontrar una solución o demostrar que no existe alguna. El ordenamiento de las variables juega un papel de suma importancia en la búsqueda de la solución. Un buen ordenamiento de variables al momento de buscar una solución representa una menor complejidad en la búsqueda. Existen dos enfoques para el ordenamiento de variables. El primer enfoque es conocido como en ordenamiento estático el cual consiste en definir el orden en la cual las variables estarían instanciadas antes de empezar a solucionar el problema. El otro enfoque es conocido como ordenamiento dinámico el cual consiste en determinar la variable a instanciar en tiempo de solución. Para esto surgieron algunas heurísticas que ayudan en este proceso, de las cuales podemos nombrar Fail First, Rho, Kappa, entre otras, pero ninguna de ellas ha demostrado ser eficiente para todas las instancias. En este enfoque la heurística elegida es aplicada en todos los niveles del árbol sin importar las modificaciones del problema. Recientemente se ha empezado a trabajar con un enfoque basado en hiperheurísticas, el cual, dada las características del estado del problema determina que heurística debe ser aplicada para elegir la variable a ser asignada, en este modelo en cada nivel del árbol la heurística aplicada puede variar respecto a la anterior. Este modelo se compone de una etapa de entrenamiento y una de prueba. La fase de entrenamiento consiste en utilizar un algoritmo genético para evolucionar una población de redes neuronales. Las redes neuronales son entrenadas por medio del algoritmo de retroprogramación del error y después evaluadas con diferentes instancias de CSPs. La red neuronal tiene como entrada el estado del problema y como salida la heurística sencilla a aplicar. La intención de utilizar diferentes instancias de CSPs durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser aplicados para resolver un gran número de instancias, mías que encontrar buenas soluciones para instancias específicas. La idea general es la siguiente, dado el estado del CSP P es utilizado para alimentar la red neuronal de la cual se obtendrá como salida la heurística sencilla a aplicar. Una vez aplicada la heurística el CSP P cambia a un CSP P', el cual es una versión actualizada del anterior. El procedimiento se repite hasta resolver el problema completamente. Al terminar el entrenamiento de la población se toma el mejor individuo y es utilizado para solucionar tanto los problemas utilizados para su entrenamiento como problemas nuevos. Lo anterior para hacer comparaciones con los resultados de la aplicación individual de las heurísticas simples. Los resultados demuestran que es factible la creación de una hiperheurística bajo este modelo de solución puesto que las hiperheurísticas generadas se comportaron como la mejor heurística sencilla aplicada y con esto mejor que el promedio que ellas. La mejor heurística simple puede ser diferente en cada instancia del problema.
- Hiperheurísticas mediante un enfoque evolutivo para el ordenamiento dinámico de variables en problemas de satisfacción de restricciones(Instituto Tecnológico y de Estudios Superiores de Monterrey, 2008-05-01) Ortiz Bayliss, José Carlos; Ortiz Bayliss, José Carlos; 212577; Terashima Marín, Hugo; Acevedo Mascarúa, Joaquín; Uresti Charre, Eduardo; Valenzuela Rendón, Manuel; ITESM-Campus Monterrey; División de Graduados en Mecatrónica y Tecnologías de InformaciónLos problemas de satisfacción de restricciones (CSPs por sus siglas en inglés) representan un tema de gran interés en el área de sistemas inteligentes y sus aplicaciones incluyen planeación, visión, distribución de recursos, etc. Un CSP está compuesto por un conjunto de variables, un dominio de valores para cada variable y un conjunto de restricciones definidas sobre los valores que pueden tomar las variables simultáneamente. Asociado a los CSPs se encuentra el problema del ordenamiento de variables y de valores. Un buen ordenamiento de variables al momento de buscar una solución representa una menor complejidad en la búsqueda. Existen una gran cantidad de heurísticas que se han diseñado para seleccionar dinámicamente la siguiente variable a instanciar, pero ninguna de ellas ha demostrado ser eficiente para todas las instancias. Además, existen instancias de CSPs que son particularmente difíciles de resolver, ya que requieren una elevada cantidad de verificaciones de consistencia para encontrar una solución o demostrar que no existe alguna. Este trabajo considera el problema del ordenamiento dinámico de variables en CSPs utilizando hiperheurísticas producidas mediante un modelo evolutivo. Este modelo se compone de una etapa de entrenamiento y una de prueba. La etapa de entrenamiento se realiza con ayuda de un algoritmo genético con cromosomas de longitud variable. Durante la etapa de entrenamiento, el AG se encarga de evolucionar una población de individuos que representan las hiperheurísticas mediante la solución de un conjunto de entrenamiento formado por diferentes instancias de CSPs difíciles. La intención de utilizar diferentes instancias de CSPs durante la etapa de entrenamiento es desarrollar procesos de solución generales que puedan ser aplicados para resolver un gran número de instancias, más que encontrar buenas soluciones para instancias específicas. Estos individuos de la población representan grupos de reglas del tipo condición-acción, en donde la condición simboliza un estado específico del problema y la acción es una heurística de ordenamiento de variables. En términos generales, el procedimiento que se lleva a cabo es el siguiente: dado un estado P del problema, encontrar la regla más cercana i y aplicar la heurística asociada a dicha regla. Al llevar a cabo esta acción, el problema se transforma en P1 . El procedimiento se repite hasta resolver el problema completamente. La función primordial del AG durante la etapa de entrenamiento es seleccionar diferentes estados del problema y asociar cada uno de ellos con alguna de las heurísticas de bajo nivel para el ordenamiento dinámico de variables. Una misma heurística puede asociarse a varios estados o a ninguno. Al finalizar la etapa de entrenamiento, el mejor individuo de la población es utilizado para resolver el conjunto de problemas de prueba, el cual está formados por diferentes instancias de CSPs de las que fueron utilizadas durante el proceso de entrenamiento. Las hiperheurísticas generadas mediante el modelo presentado en este trabajo se comparan con los resultados obtenidos mediante la aplicación por separado de las heurísticas de bajo nivel para los problemas de entrenamiento y prueba. La investigación demuestra que es posible generar hiperheurísticas con eficiencia competitiva para una gran cantidad de instancias de CSPs mediante el modelo evolutivo presentado. Los resultados también dejan en claro que no existe una heurística capaz por sí sola de resolver eficientemente todas las instancias de CSPs. Sin embargo, el modelo evolutivo fue capaz de generar una hiperheurística general competitiva, la cual logró resultados muy parecidos a los producidos por el mejor resultado de las heurísticas simples y una reducción significativa al compararse contra el número de verificaciones de consistencia requerido por el resultado promedio de las heurísticas simples.