Showing 1 to 26 of 26 matching Articles
Results per page:
Export (CSV)
By
Amaya, Ivan; OrtizBayliss, José Carlos; ConantPablos, Santiago Enrique; TerashimaMarín, Hugo; Coello Coello, Carlos A.
Show all (5)
1 Citations
Solvers for different combinatorial optimization problems have evolved throughout the years. These can range from simple strategies such as basic heuristics, to advanced models such as metaheuristics and hyperheuristics. Even so, the set of benchmark instances has remained almost unaltered. Thus, any analysis of solvers has been limited to assessing their performance under those scenarios. Even if this has been fruitful, we deem necessary to provide a tool that allows for a better study of each available solver. Because of that, in this paper we present a tool for assessing the strengths and weaknesses of different solvers, by tailoring a set of instances for each of them. We propose an evolutionarybased model and test our idea on four different basic heuristics for the 1D bin packing problem. This, however, does not limit the scope of our proposal, since it can be used in other domains and for other solvers with few changes. By pursuing an indepth study of such tailored instances, more relevant knowledge about each solver can be derived.
more …
By
OrtizBayliss, José Carlos; TerashimaMarín, Hugo; ConantPablos, Santiago Enrique
Hyperheuristics are methodologies that choose from a set of heuristics and decide which one to apply given some properties of the current instance. When solving a constraint satisfaction problem, the order in which the variables are selected to be instantiated has implications in the complexity of the search. In this paper we propose a logistic regression model to generate hyperheuristics for variable ordering within constraint satisfaction problems. The first step in our approach requires to generate a training set that maps any given instance, expressed in terms of some of their features, to one suitable variable ordering heuristic. This set is used later to train the system and generate a hyperheuristic that decides which heuristic to apply given the current features of the instances at hand at different steps of the search. The results suggest that hyperheuristics generated through this methodology allow us to exploit the strengths of the heuristics to minimize the cost of the search.
more …
By
TorresNogales, Alan I.; ConantPablos, Santiago E.; TerashimaMarín, Hugo
In this paper we propose using invariant local features and a global appearance validation for assisting a robust object tracker initialized by a single example. Although local features have been used before for several object detection and tracking applications, these approaches often model an object as a collection of keypoints and descriptors, which involves constructing a set of correspondences between object and image keypoints via descriptor matching or keypoint classification. However, these algorithms cannot properly adapt to long video sequences due to their limited capacity for incremental update. We differentiate from these approaches in that we obtain keypointtoobject correspondences instead of keypointtokeypoint correspondences converting the problem into an easier binary classification problem, which allows us to use a stateoftheart algorithm to incrementally update our classifier. Our approach is embedded into the TrackingLearningDetection (TLD) framework by performing a set of changes in the detection stage. We show how measuring the density of positive local features given by a binary classifier trained online is a good signal of the object’s presence, and in combination with a global appearance validation it yields a strong object detector for assisting a tracking algorithm. In order to validate our approach we compare the tracking results against the original TLD approach on a set of 10 videos.
more …
By
OrtizBayliss, José Carlos; TerashimaMarín, Hugo; ConantPablos, Santiago Enrique
1 Citations
Hyperheuristics are methodologies used to choose from a set of heuristics and decide which one to apply given some properties of the current instance. When solving a Constraint Satisfaction Problem, the order in which the variables are selected to be instantiated has implications in the complexity of the search. We propose a neural network hyperheuristic approach for variable ordering within Constraint Satisfaction Problems. The first step in our approach requires to generate a pattern that maps any given instance, expressed in terms of constraint density and tightness, to one adequate heuristic. That pattern is later used to train various neural networks which represent hyperheuristics. The results suggest that neural networks generated through this methodology represent a feasible alternative to code hyperheuristic which exploit the strengths of the heuristics to minimise the cost of finding a solution.
more …
By
OrtizBayliss, José Carlos; TerashimaMarín, Hugo; Özcan, Ender; Parkes, Andrew J.; ConantPablos, Santiago Enrique
Show all (5)
Constraint Satisfaction Problems (CSP) represent an important topic of study because of their many applications in different areas of artificial intelligence and operational research. When solving a CSP, the order in which the variables are selected to be instantiated and the order of the corresponding values to be tried affect the complexity of the search. Hyperheuristics are flexible methods that provide generality when solving different problems and, within CSP, they can be used to determine the next variable and value to try. They select from a set of lowlevel heuristics and decide which one to apply at each decision point according to the problem state. This study explores a hyperheuristic model for variable and value ordering within CSP based on a decision matrix hyperheuristic that is constructed by going into a local improvement method that changes small portions of the matrix. The results suggest that the approach is able to combine the strengths of different lowlevel heuristics to perform well on a wide range of instances and compensate for their weaknesses on specific instances.
more …
By
ReynaAyala, Edgar; ConantPablos, Santiago E.; TerashimaMarín, Hugo
In this paper we present a novel ensemble of two similar tracking approaches, which independently present good performance for different video sequences. We propose that by combining the response of these tracking approaches, we can strengthen their detecting capability and therefore increase the tracking performance of the ensemble. The TrackingLearningDetection (TLD) and the LocalTLD are the approaches we chose for building our ensemble. Our main motivation for assembling these two approaches is that both approaches focus on particular instances of an object and also manage different object representation, for instance, the TLD works reasonably well for planar rigid objects due to the global classifier it includes, meanwhile the LocalTLD focuses on invariant local features and is able to overcome the planar assumption. Combining these approaches, we are able to take advantage of their best qualities and overcome their biggest problems. For introducing our method, we first need to review the principal components of the two chosen approaches, and then we finally introduce the ensemble. The proposed ensemble is compared against results of the independent approaches using a data set of 10 video sequences, showing, in general, a significant improvement.
more …
By
HuertaAmante, Daniel Ángel; TerashimaMarín, Hugo
3 Citations
When a Genetic Algorithm is used to tackle a constrained problem, it is necessary to set a penalty weight for each constraint type, so that, if the individual violates a given constraint it will be penalized accordingly. Traditionally, penalty weights remain static throughout the generations. This paper presents an approach to allow the adaptation of weights, where the penalty function takes feedback from the search process. Although, the idea is not new since other related approaches have been reported in the literature, the work presented here considers problems which contain several kinds of constraints. The method is successfully tested for the congress timetabling problem, a difficult problem and with many practical applications. Further analysis is presented to support the efficiency of the technique.
more …
By
TerashimaMarín, Hugo; FaríasZárate, Cláudia J.; Ross, Peter; ValenzuelaRendón, Manuel
Show all (4)
The idea behind hyperheuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such combination should outperform the single heuristics. This paper presents a GAbased method that produces general hyperheuristics that solve twodimensional cutting stock problems. The GA uses a variablelength representation, which evolves combinations of conditionaction rules producing hyperheuristics after going through a learning process which includes training and testing phases. Such hyperheuristics, when tested with a large set of benchmark problems, produce outstanding results (optimal and nearoptimal) for most of the cases. The testebed is composed of problems used in other similar studies in the literature. Some additional instances of the testbed were randomly generated.
more …
By
Martinez, Emmanuel; Brena, Ramon F.; TerashimaMarín, Hugo
Highly dynamic environments with uncertainty make inadequate long or rigid plans, because they are frequently dismissed by the arrival or new unexpected situations. In these environments, most approaches eliminate planning altogether, and evaluate just the current situation. We are interested in online planning, where execution and planning are interleaved, and short plans are continuously reevaluated. Now, the plan evaluation itself could be an important issue. We have proposed in our recent work to evaluate plans taking into account the quantity and quality of future options, not just the single best future option. In this paper we present a detailed evaluation of realtime planning performance, changing the importance given to the current situation, to the best future option, and to the set of future options respective evaluations, in the context of the simulated soccer Robocup competition. Our results show that a welltuned combination of the mentioned factors could outperform any of them alone.
more …
By
OrtizBayliss, José Carlos; TerashimaMarín, Hugo; ConantPablos, Santiago Enrique
1 Citations
Selection hyperheuristics are methods that manage the use of different heuristics and recommend one of them that is suitable for the current problem space under exploration. In this paper we describe a hyperheuristic model for constraint satisfaction that is inspired in the idea of a lifelong learning process that allows the hyperheuristic to continually improve the quality of its decisions by incorporating information from every instance it solves. The learning takes place in a transparent way because the learning process is executed in parallel in a different thread than the one that deals with the user’s requests. We tested the model on various constraint satisfaction problem instances and obtained promising results, specially when tested on unseen instances from different classes.
more …
By
Duhart, Bronson; Camarena, Fernando; OrtizBayliss, José Carlos; Amaya, Ivan; TerashimaMarín, Hugo
Show all (5)
The knapsack problem is a fundamental problem that has been extensively studied in combinatorial optimization. The reason is that such a problem has many practical applications. Several solution techniques have been proposed in the past, but their performance is usually limited by the complexity of the problem. Hence, this paper studies a novel hyperheuristic approach based on the ant colony optimization algorithm to solve the knapsack problem. The hyperheuristic is used to produce rules that decide which heuristic to apply given the current problem state of the instance being solved. We test the hyperheuristic model on sets with a variety of knapsack problem instances. Our resulting data seems promising.
more …
By
LópezCamacho, Eunice; TerashimaMarín, Hugo; Ross, Peter
2 Citations
In various approaches for combinatorial optimization, a problem instance is represented by a numerical vector that summarizes to some extent the actual solution state of such instance. Such representation intends to include the most relevant features related to the instance and the problem domain. The proper selection of these features has a direct impact on the performance of a hyperheuristic. Previous approaches for hyperheuristics have been relying on intuitive ways to determine the feature set, usually based on the domain knowledge of a particular problem. In this paper, a more general methodology for establishing an adequate problemstate representation is proposed. We chose the irregular case of the twodimensional Bin Packing Problem (2D irregular BPP) and a GAbased hyperheuristic model to test the methodology. As far as we know, this is the only hyperheuristic model applied to the 2D irregular BPP and it has been successful when solving a wide range of instances. Our developed representation shows a significant improvement in performance with respect to a more conventional representation for the 2D irregular BPP.
more …
By
HernándezCisneros, Rolando R.; TerashimaMarín, Hugo
1 Citations
Breast cancer is one of the main causes of death in women and early diagnosis is an important means to reduce the mortality rate. The presence of microcalcification clusters are primary indicators of early stages of malignant types of breast cancer and its detection is important to prevent the disease. This paper proposes a procedure for the classification of microcalcification clusters in mammograms using sequential difference of gaussian filters (DoG) and three evolutionary artificial neural networks (EANNs) compared against a feedforward artificial neural network (ANN) trained with backpropagation. We found that the use of genetic algorithms (GAs) for finding the optimal weight set for an ANN, finding an adequate initial weight set before starting a backpropagation training algorithm and designing its architecture and tuning its parameters, results mainly in improvements in overall accuracy, sensitivity and specificity of an ANN, compared with other networks trained with simple backpropagation.
more …
By
Gomez, Juan Carlos; TerashimaMarín, Hugo
5 Citations
This article presents a method based on the multiobjective evolutionary algorithm NSGAII to approximate hyperheuristics for solving irregular 2D cutting stock problems under multiple objectives. In this case, additionally to the traditional objective of minimizing the number of sheets used to fit a finite number of irregular pieces, the time required to perform the placement task is also minimized, leading to a biobjective minimization problem with a tradeoff between the number of sheets and the time required for placing all pieces. We solve this problem using multiobjective hyperheuristics (MOHHs), whose main idea consists of finding a set of simple heuristics which can be combined to find a general solution for a wide range of problems, where a single heuristic is applied depending on the current condition of the problem, instead of applying a unique single heuristic during the whole placement process. The MOHHs are approximated after going through a learning process by mean of the NSGAII, which evolves combinations of conditionaction rules producing at the end a set of Paretooptimal MOHHs. We tested the approximated MMOHHs on several sets of benchmark problems, having outstanding results for most of the cases.
more …
By
AnglesDomínguez, Manuel Iván; TerashimaMarín, Hugo
1 Citations
Problems from various domains can be modeled as dynamic constraint satisfaction problems, where the constraints, the variables or the variable domains change overtime. The aim, when solving this kind of problems, is to decrease the number of variables for which their assignment changes between consecutive problems, a concept known as distance or stability. This problem of stability has previuosly been studied, but only for variations in the constraints of a given problem. This paper describes a wider analysis on the stability problem, when modifying variables, domains, constraints and combinations of these elements for the resource allocation problem, modeled as a DCSP. Experiments and results are presented related to efficiency, distance and a new parameter called global stability for several techniques such as solution reuse, reasoning reuse and a combination of both. Additionaly, results show that the distance behavior is linear with respect to the variations.
more …
By
CuestaCañada, Alberto; Garrido, Leonardo; TerashimaMarín, Hugo
9 Citations
Convergence proofs for ant colony optimization are limited [1], only in some cases it is possible to assure that the algorithm will find an optimal solution. It is even more difficult to state how long it will take, but it has been found experimentally that the computing time increases at least exponentially with the size of the problem [2]. To overcome this, the concept of hyperheuristics could be applied. The idea behind hyperheuristics is to find some combination of simple heuristics to solve a problem instead than solving it directly. In this paper we introduce the first attempt to combine hyperheuristics with an ACO algorithm. The resulting algorithm was applied to the twodimensional bin packing problem, and encouraging results were obtained when solving classic instances taken from the literature. The performance of our approach is always equal or better than that of any of the simple heuristics studied, and comparable to the best metaheuristics known.
more …
By
RamírezRuiz, José; ValenzuelaRendón, Manuel; TerashimaMarín, Hugo
3 Citations
This paper introduces the QFCS, a new approach to fuzzy learning classifier systems. QFCS can solve the multistep reinforcement learning problem in continuous environments and with a set of continuous vector actions. Rules in the QFCS are small fuzzy systems. QFCS uses a Qlearning algorithm to learn the mapping between inputs and outputs. This paper presents results that show that QFCS can evolve rules to represent only those parts of the input and action space where the expected values are important for making decisions. Results for the QFCS are compared with those obtained by Qlearning with a high discretization to show that the new approach converges in a way similar to how Qlearning does for onedimension problems with an optimal solution, and for two dimensions QFCS learns suboptimal solutions while it is difficult for Qlearning to converge due to that high discretization.
more …
By
HernándezCisneros, Rolando R.; TerashimaMarín, Hugo; ConantPablos, Santiago E.
1 Citations
The presence of microcalcification clusters in digital mammograms is a primary indicator of early stages of malignant types of breast cancer and its detection is important to prevent the disease. This paper uses a procedure for the classification of microcalcification clusters in mammograms using sequential Difference of Gaussian filters (DoG) and feedforward Neural Networks (NN). Three methods using class separability, forward sequential search and genetic algorithms for feature selection are compared. We found that the use of Genetic Algorithms (GAs) for selecting the features from microcalcifications and microcalcification clusters that will be the inputs of a feedforward Neural Network (NN) results mainly in improvements in overall accuracy, sensitivity and specificity of the classification.
more …
By
OportoDíaz, Samuel; HernándezCisneros, Rolando; TerashimaMarín, Hugo
9 Citations
Since microcalcification clusters are primary indicators of malignant types of breast cancer, its detection is important to prevent and treat the disease. This paper proposes a method for detection of microcalcification clusters in mammograms using sequential Difference of Gaussian filters (DoG). In a first stage, fifteen DoG filters are applied sequentially to extract the potential regions, and later, these regions are classified using the following features: absolute contrast, standard deviation of the gray level of the microcalcification and a moment of contour sequence (asymmetry coefficient). Once the microcalcifications are detected, two approaches for clustering are compared. In the first one, several microcalcification clusters are detected in each mammogram. In the other, all microcalcifications are considered in a single cluster. We demonstrate that the diagnosis based on the detection of several microcalcification clusters in a mammogram is more efficient than considering a single cluster including all the microcalcifications in the image.
more …
By
TerashimaMarín, Hugo; TavernierDeloya, Juan Manuel; ValenzuelaRendón, Manuel
1 Citations
Grouping problems arise in many applications, and the aim is to partition a set U of items, into a collection of mutually disjoint subsets or groups. The objective of grouping is to optimize a cost function such as to minimize the number of groups. Problems in this category may come from many different domains such as graph coloring, bin packing, cutting stock, and scheduling. This investigation is related in particular to scheduling transportation events, modeled as a grouping problem, and with the objective to minimize the number of vehicles used and satisfying the customer demand. There is a set of events to be scheduled (items) into a set of vehicles (groups). Of course, there are constraints that forbid assigning all events to a single vehicle. Two different techniques are used in this work to tackle the problem: Grouping Genetic Algorithms and an algorithm based on the heuristic DJD widely used for solving bin packing problems. Both methods were adapted to the problem and compared to each other using a set of randomly generated problem instances designed to comply with real situations.
more …
By
TerashimaMarín, Hugo; OrtizBayliss, José C.; Ross, Peter; ValenzuelaRendón, Manuel
Show all (4)
3 Citations
The idea behind hyperheuristics is to discover some combination of straightforward heuristics to solve a wide range of problems. To be worthwhile, such combination should outperform the single heuristics. This paper presents a GAbased method that produces general hyperheuristics for the dynamic variable ordering within Constraint Satisfaction Problems. The GA uses a variablelength representation, which evolves combinations of conditionaction rules producing hyperheuristics after going through a learning process which includes training and testing phases. Such hyperheuristics, when tested with a large set of benchmark problems, produce encouraging results for most of the cases. There are instances of CSP that are harder to be solved than others, this due to the constraint and the conflict density [4]. The testebed is composed of hard problems randomly generated by an algorithm proposed by Prosser [18].
more …
By
ValenzuelaRendón, Manuel; MartínezAlfaro, Horacio; TerashimaMarín, Hugo
David Goldberg has defined a competent genetic algorithm as one which “can solve hard problems, quickly, accurately, and reliably.” Among other competent genetic algorithms that have been developed are the Bayesian optimization algorithm (BOA), the fast messy genetic algorithm (fmGA), and the linkage learning genetic algorithm (LLGA). These algorithms have been tested on problems of bounded difficulty that are additive separable formed by deceptive subproblems of order not greater than k, where k < ℓ. BOA, fmGA, LLGA, and other competent genetic algorithms are stochastic, and thus, can only be assured of attaining optimality in a probabilistic sense. In this paper, we develop a deterministic algorithm that solves to optimality all linearly decomposable problems in a polynomial number of function evaluations with respect to the maximum size of the subproblems, k. The algorithm presented does not rely on a population, does not recombine individuals or apply any other genetic operator. Furthermore, because it is deterministic, the number of function evaluations required to find the optimum can be known in advance. The algorithm presented solves both the linkage and the optimization problems by finding the disjoint sets of related variables and the optimal values of these variables at the same time. The fact that such an algorithm can be devised has important implications for the design of GAhard problems, and the development and evaluation of genetic optimization algorithms.
more …
By
ConantPablos, Santiago E.; MagañaLozano, Dulce J.; TerashimaMarín, Hugo
4 Citations
This paper introduces a hybrid algorithm that combines local search and constraint satisfaction techniques with memetic algorithms for solving Course Timetabling hard problems. These problems require assigning a set of courses to a predetermined finite number of classrooms and periods of time, complying with a complete set of hard constraints while maximizing the consistency with a set of preferences (soft constraints). The algorithm works in a threestage sequence: first, it creates an initial population of approximations to the solution by partitioning the variables that represent the courses and solving each partition as a constraintsatisfaction problem; second, it reduces the number of remaining hard and soft constraint violations applying a memetic algorithm; and finally, it obtains a complete and fully consistent solution by locally searching around the best memetic solution. The approach produces competitive results, always getting feasible solutions with a reduced number of soft constraints inconsistencies, when compared against the methods running independently.
more …
By
GómezHerrera, Fernando; RamirezValenzuela, Rodolfo A.; OrtizBayliss, José Carlos; Amaya, Ivan; TerashimaMarín, Hugo
Show all (5)
This research describes three novel heuristicbased approaches for solving the 0/1 knapsack problem. The knapsack problem, in its many variants, arises in many practical scenarios such as the selection of investment projects and budget control. As an NPhard problem, it is not always possible to compute the optimal solution by using exact methods and, for this reason, the problem is usually solved by using heuristicbased strategies. In this document, we use information of the distributions of weight and profit of the items in the knapsack instances to design and implement new heuristicbased methods that solve those instances. The solution model proposed in this work is twofold: the first part focuses on the generation of two new heuristics, while the second explores the combination of solving methods through a hyperheuristic approach. The heuristics proposed, as well as the hyperheuristic model, were tested on a heterogeneous set of knapsack problem instances and compared against four heuristics taken from the literature. One of the proposed heuristics proved to be highly competent with respect to heuristics available in the literature. By using the hyperheuristic, a solver that dynamically selects heuristics based on the problem features, we improved the results obtained by the new heuristics proposed and, achieved the best results among all the methods tested in this investigation.
more …
By
Gomez, Juan Carlos; TerashimaMarín, Hugo
5 Citations
In this article, a multiobjective evolutionary framework to build selection hyperheuristics for solving instances of the 2D bin packing problem is presented. The approach consists of a multiobjective evolutionary learning process, using specific tailored genetic operators, to produce sets of variable length rules representing hyperheuristics. Each hyperheuristic builds a solution to a given problem instance by sensing the state of the instance, and deciding which single heuristic to apply at each decision point. The hyperheuristics consider the minimization of two conflicting objectives when building a solution: the number of bins used to accommodate the pieces and the total time required to do the job. The proposed framework integrates three wellstudied multiobjective evolutionary algorithms to produce sets of Paretoapproximated hyperheuristics: the Nondominated Sorting Genetic AlgorithmII, the Strength Pareto Evolutionary Algorithm 2, and the Generalized Differential Evolution Algorithm 3. We conduct an extensive experimental analysis using a large set of 2D bin packing problem instances containing convex and nonconvex irregular pieces, under many conditions, settings and using several performance metrics. The analysis assesses the robustness and flexibility of the proposed approach, providing encouraging results when compared against a set of wellknown baseline single heuristics.
more …
By
OrtizBayliss, José Carlos; TerashimaMarín, Hugo; ConantPablos, Santiago Enrique
5 Citations
Selection hyperheuristics are a technology for optimization in which a highlevel mechanism controls lowlevel heuristics, so as to be capable of solving a wide range of problem instances efficiently. Hyperheuristics are used to generate a solution process rather than producing an immediate solution to a given problem. This process is a reusable mechanism that can be applied both to seen and unseen problem instances. In this paper, we propose a selection hyperheuristic process with the intention to rise the level of generality and solve consistently well a wide range of constraint satisfaction problems. The hyperheuristic technique is based on a messy genetic algorithm that generates highlevel heuristics formed by rules (condition
$$\rightarrow $$
heuristic). The highlevel heuristics produced are seen to be good at solving instances from certain parts of the parameterized space of problems, producing results using effort comparable to the best single heuristic per instance. This is beneficial, as the choice of best heuristic varies from instance to instance, so the highlevel heuristics are definitely preferable to selecting any one lowlevel heuristic for all instances. The results confirm the robustness of the proposed approach and how highlevel heuristics trained for some specific classes of instances can also be applied to unseen classes without significant lost of efficiency. This paper contributes to the understanding of heuristics and the way they can be used in a collaborative way to benefit from their combined strengths.
more …
