The Rank Aggregation problem has applications in several fields of science like Information Retrieval, Social Sciences, Bioinformatics, among others. In this problem, the objective is to create a consensus ranking given a set of input rankings. This paper considers a variant of this problem, in which the set of input rankings may contain ties and may be incomplete. An Adaptive Biased Random-key Genetic Algorithm (A-BRKGA) is proposed to solve this problem, and the results are compared to an integer linear programming model previously introduced in the literature. Since the fitness evaluation of the A-BRKGA is its most time-consuming component, a partial fitness evaluation was derived and used in the local search component created for this problem. The partial evaluation reduces the time complexity from quadratic to linear. In the experiments, the efficiency of the A-BRKGA with the local search was evaluated against the A-BRKGA without the local search component and the integer linear programming introduced in the literature. The experimental results show that the proposed technique achieved superior results in terms of quality when compared to the A-BRKGA without the local search component, achieved similar results in terms of quality and better results in terms of computational time when compared to the integer linear programming model.

This paper presents a new approach to solve the Point Feature Cartographic Label Placement (PFCLP) problem. The PFCLP is a relevant problem for Geographic Information Systems, where the objective is to position labels on a map avoiding overlaps to improve legibility. The first techniques proposed to solve this problem considered only the presence/absence of over-lapping, while more recent ones introduced the idea of estimating the intensity of such overlap. This work extends previous works by considering the overlap intensity through the Jaccard index. Traditional mathematical models for PFCLP were compared to the proposed strategy showing that the Jaccard index provided the best results in terms of legibility. A Clustering Search (CS) algorithm was also proposed to compare the performance of our strategy on a set of large-sized instances. The experimental results show good solutions for instances with up to 13206 points.

Aggregating ranks into a consensus is an important task applied in different fields of science. This paper deals with a specific variation that aggregate ranks into a consensus considering ties between its elements. This approach is more flexible and meaningful for modeling some circumstances where a strict order is considered too restrictive. A ranking considering ties is also known as a bucket order in literature, and the problem that considers the rank aggregation of bucket orders is defined as the Optimal Bucket Order Problem (OBOP). It is an NP-hard problem, hence several heuristics have been proposed in the literature. The current state-of-the-art results for this problem were achieved through an Evolution Strategy (ES) metaheuristic. This paper proposes the application of the adaptive Biased Random-key Genetic Algorithm (A-BRKGA) with Variable Neighborhood Descent (VND) as a local search to solve it. The A-BRKGA is a metaheuristic with on-line parameter control, in which the strategy for parameter tuning is based on deterministic rules and self-adaptive schemes. The proposed approach was compared with ES in 152 instances, improving the fitness of the best solutions in 35.52% of the instances, providing better average solutions for 70.39%, and equal results for the remaining instances.

Qualitative data clustering is a fundamental data analysis task, with applications in many areas, like medicine, sociology, and economics. An appealing way to deal with this task is via Integer Linear Programming, as it avoids inappropriate inferences by the final user. This approach has two main advantages: the data are directly used, without the need of being converted to quantitative values, and the optimal number of clusters is automatically obtained by solving the optimization problem. However, it might create large and redundant models, which can limit the size of the problems it can be applied. Recently, models that are more compact and able to avoid some redundancy have been proposed in the literature. These models consume less memory and are faster to obtain the optimal solution set. In this study, a new model is introduced and compared with the state-of-the-art alternatives using datasets from different application domains. Empirical results show that the new model outperforms its predecessors, achieving the optimal solution set with lower computational time and memory consumption.

The prize collecting travelling salesman problem (PCTSP) is a generalization of the travelling salesman problem. It can be associated to a salesman that collects a prize in each city visited and pays a penalty for each city not visited, with travel costs among the cities. The objective is to minimize the sum of the costs of the trip and penalties, including in the tour an enough number of cities that allow collecting a minimum prize. This paper approaches new heuristics to solve the PCTSP, using a hybrid evolutionary algorithm, called evolutionary clustering search (ECS) and an adaptation of this, called *CS, where the evolutionary component is substituted by the metaheuristics GRASP and VNS. The validation of the obtained solutions are through the comparison with the results found by a commercial solver that was able to solve only small size problems.

This paper describes an application of a Constructive Genetic Algorithm (CGA) to the gate matrix layout problem (GMLP). The GMLP happens in very large scale integration design and can be described as a problem of assigning a set of circuit nodes (gates) in an optimal sequence, such that the layout area is minimized, as a consequence of optimizing the number of tracks necessary to cover the gates interconnection. The CGA has a number of new features compared to a traditional genetic algorithm. These include a population of dynamic size composed of schemata and structures and the possibility of using heuristics in structure representation and in the fitness function definitions. The application of CGA to GMLP uses a 2-Opt-like heuristic to define the fitness functions and the mutation operator. Computational tests are presented using available instances taken from the literature.

Genetic algorithms (GAs) have recently been accepted as powerful approaches to solving optimization problems. It is also well-accepted that building block construction (schemata formation and conservation) has a positive influence on GA behavior. Schemata are usually indirectly evaluated through a derived structure. We introduce a new approach called the Constructive Genetic Algorithm (CGA), which allows for schemata evaluation and the provision of other new features to the GA. Problems are modeled as bi-objective optimization problems that consider the evaluation of two fitness functions. This double fitness process, called fg-fitness, evaluates schemata and structures in a common basis. Evolution is conducted considering an adaptive rejection threshold that contemplates both objectives and attributes a rank to each individual in population. The population is dynamic in size and composed of schemata and structures. Recombination preserves good schemata, and mutation is applied to structures to get population diversification. The CGA is applied to two clustering problems in graphs. Representation of schemata and structures use a binary digit alphabet and are based on assignment (greedy) heuristics that provide a clearly distinguished representation for the problems. The clustering problems studied are the classical p-median and the capacitated p-median. Good results are shown for problem instances taken from the literature.