The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The Generalized Assignment Problem (GAP) consists in finding a maximum-profit assignment of tasks to agents with capacity constraints. In this paper, a path relinking heuristic is proposed for the GAP. The main feature of our path relinking is that both feasible and infeasible solutions are inserted in the reference set of elite solutions, trade-off between feasibility and infeasibility being ruled...
A new metaheuristic technique called PROBE is presented. The application of PROBE to the multiconstraint knapsack problem is described. Experimental results obtained using the resulting algorithm are compared with the results obtained by Chu and Beasley using a Genetic Algorithm.
Two heuristics for the Linear Ordering Problem are investigated in this paper. These heuristics are embedded within a Lagrangian Relaxation framework and are started with a construction phase. In this process, some Lagrangian (dual) information is used as an input to guide the construction of initial Linear Orderings. Solutions thus obtained are then submitted to local improvement in an overall procedure...
The Number Partitioning Problem (MNP) remains as one of the simplest-to-describe yet hardest-to-solve combinatorial optimization problems. In this paper we use the MNP as a surrogate for several related real-world problems, to test new heuristics ideas. To be precise, we study the use of weight-matching techniques to devise smart memetic operators. Several options are considered and evaluated for...
MCACS-BRP, a new Ant Colony Optimization (ACO) based approach to solve the Bus Routing Problem is presented. MCACS is an extension of ACO, where two hierarchically connected casts of ants optimize two different objective functions. In MCACS-BRP, ants collaborate using information about the best results obtained in the particular cast. Experiments with real data from the Municipal Public Transport...
Genetic algorithms are optimization techniques especially useful in functions whose nonlinearity makes an analytical optimization impossible. This kind of functions appear when using least squares estimators in nonlinear regression problems. Least squares optimizers in general, and the Levenberg-Marquardt method in particular, are iterative methods especially designed to solve this kind of problems,...
Nurse rostering problems consist of assigning varying tasks, represented as shift types, to hospital personnel with different skills and work regulations. The goal is to satisfy as many soft constraints and personal preferences as possible while constructing a schedule which meets the required personnel coverage of the hospital over a predefined planning period. Real-world situations are often so...
This paper describes the application of a neural network metaheuristic to a real timetabling problem, the Class/Teacher Timetabling Problem (CTTP). This problem is known to be a complex, highly constrained optimization problem, thus exhibiting limitations to be solved using classical optimization methods. For this reason, many metaheuristics have been proposed to tackle real CTTP instances. Artificial...
The single source capacitated location problem is considered. Given a set of potential locations and the plant capacities, it must be decided where and how many plants must be open and which clients must be assigned to each open plant. Genetic algorithms that use different methodologies for handling constraints are described and tested. Computational experiments on different sets of problems are presented.
Solving multiobjective engineering problems is, in general, a difficult task. In spite of the success of many approaches, elitism has emerged has an effective way of improving the performance of algorithms. In this paper, a new elitist scheme, by which it is possible to control the size of the elite population, as well as the concentration of points in the approximation to the Pareto-optimal set,...
The Heuristic Search Framework (HSF) is aJava object-oriented framework allowing to easily implement single solution algorithms such as Local Search, population-based algorithms such as Genetic Algorithms, and hybrid methods being a combination of the two. The main idea in HSF is to break down any of these heuristic algorithms into a plurality of constituent parts. Thereafter, a user can use this...
In this paper we propose an improvement to the widely used metaheuristic genetic algorithm. We suggest a change in the way parents are selected. The method is based on examining the similarity of parents selected for mating. Computational comparisons for solving the quadratic assignment problem using a hybrid genetic algorithm demonstrate the effectiveness of the method. This conclusion is examined...
We investigate several versions of a tabu scatter search heuristic to solve permutation type optimization problems. The focus lies on the design of the three main components which are comprised in every pool-oriented method. These components are the input and output procedures, which are responsible for pool maintenance and determine the transfer of elite solutions, and a solution combination method...
Decisions have to be made at every level of petroleum reservoir development. For many cases, optimal decisions are dependent on many nonlinearly correlated parameters, which makes intuitive judgement difficult. In such cases automated optimization is an option. Decisions should be based on the most relevant and accurate tools available. For the well placement problem a numerical simulator that computes...
This paper concerns the analysis of solution properties of the Graph Coloring Problem. For this purpose, we introduce a property based on the notion of representative sets which are sets of vertices that are always colored the same in a set of solutions. Experimental results on well-studied DIMACS graphs show that many of them contain such sets and give interesting information about the diversity...
This paper describes new approaches to classification/identification of biological data. It is expected that the work may be extensible to other domains such as the medical domain or fault diagnostic problems. Organisms are often classified according to the value of tests which are used for measuring some characteristic of the organism. When selecting a suitable test set it is important to choose...
In recent work coevolutionary algorithms have been used to solve minimax problems from mechanical structure optimization and scheduling domains. The applications have been quite successful, but the algorithms used require the search-space of the minimax problem to have a certain symmetric property. The present article argues that the proposed algorithms will fail to converge if the problem does not...
Problems of scheduling jobs on parallel, identical machines under an additional continuous resource are considered. Jobs are non-preemptable and independent, and all are available at the start of the process. The total amount of the continuous resource available at a time is limited, and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown...
Minimizing arc crossings for drawing acyclic digraphs is a well-known NP-complete problem for which several local-search approaches based on local transformations (switching, median, ...) have been proposed. Their adaptations have been recently included in different metaheuristics. As an attempt to better understand the dynamics of the search processes, we study the fitness landscapes associated with...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.