The capacitated vehicle routing problem (CVRP) is a well-known NP-hard combinatorial problem. Genetic algorithms (GAs) are often used for solving CVRPs. However, the computational effort required to find a feasible solution becomes problematic for very large instances. Parallel-computation technology can significantly improve the performance of CVRP solution algorithms to deal with large problem sets, especially when using GAs. In this paper, an improved genetic algorithm is designed to be entirely executed on an NVIDIA GPU, taking advantage of the special CUDA GPU architecture to solving the CVRP. By distributing array elements over the GPU grid and using GPU kernel functions, the proposed algorithm successfully provides high-quality solutions within reasonable computational times, and near-optimal solutions for smaller benchmark problems. Within this framework, we address the execution speed problem in CVRPs by developing an algorithm that is entirely running on an NVIDIA GPU, investigate how to incorporate local search algorithms with the GA, and develop comparisons between the algorithm performance on both the CPU and the GPU. The utility of improved local search algorithms in the overall performance of the GA is also reported.

The choice of a proper learning rate is paramount for good Artificial Neural Network training and performance. In the past, one had to rely on experience and trial-and-error to find an adequate learning rate. Presently, a plethora of state of the art automatic methods exist that make the search for a good learning rate easier. While these techniques are effective and have yielded good results over the years, they are general solutions. This means the optimization of learning rate for specific network topologies remains largely unexplored. This work presents AutoLR, a framework that evolves Learning Rate Schedulers for a specific Neural Network Architecture using Structured Grammatical Evolution. The system was used to evolve learning rate policies that were compared with a commonly used baseline value for learning rate. Results show that training performed using certain evolved policies is more efficient than the established baseline and suggest that this approach is a viable means of improving a neural network's performance.

Evolving diverse sets of high quality solutions has gained increasing interest in the evolutionary computation literature in recent years. With this paper, we contribute to this area of research by examining evolutionary diversity optimisation approaches for the classical Traveling Salesperson Problem (TSP). We study the impact of using different diversity measures for a given set of tours and the ability of evolutionary algorithms to obtain a diverse set of high quality solutions when adopting these measures. Our studies show that a large variety of diverse high quality tours can be achieved by using our approaches. Furthermore, we compare our approaches in terms of theoretical properties and the final set of tours obtained by the evolutionary diversity optimisation algorithm.

In the present work, we propose some new modifications of an existing constraint handling technique (CHT) for single-objective optimization problems. The base CHT is generalized multiple constraint ranking (G-MCR), which is already a modified version of the original CHT, MCR. Despite that G-MCR significantly outperformed the original MCR in the previous study, it is found that G-MCR tends to generate very few feasible individuals on a certain real-world like engineering design problem. In the present work, G-MCR is further modified to strike a better balance between feasible and infeasible individuals on each generation in an adaptive way so that the interaction between feasible and infeasible regions can be maintained, thus providing more efficient search towards constrained global optimum. Based on the investigation on 78 benchmark problems, we obtain that some of the proposed modifications produce more robust convergence performance by obtaining significant superiority on many types of problems. On real-world like engineering design problems, we also observe that the feasibility ratio generated on each generation might have an important role in improving the convergence performance.

The weight maximization problem (WMP) is the problem of finding the word of highest weight on a weighted finite state automaton (WFA). It is an essential question that emerges in many optimization problems in automata theory. Unfortunately, the general problem can be shown to be undecidable, whereas its bounded decisional version is NP-complete. Designing efficient algorithms that produce approximate solutions to the WMP in reasonable time is an appealing research direction that can lead to several new applications including formal verification of systems abstracted as WFAs. In particular, in combination with a recent procedure that translates a recurrent neural network into a weighted automaton, an algorithm for the WMP can be used to analyze and verify the network by exploiting the simpler and more compact automata model.

In this work, we propose, implement and evaluate a metaheuristic based on genetic algorithms to approximate solutions to the WMP. We experimentally evaluate its performance on examples from the literature and show its potential on different applications.

Dependency Structure Matrix Genetic Algorithm-II (DSMGA-II) is a recently proposed optimization method that builds the linkage model on the base of the Dependency Structure Matrix (DSM). This model is used during the Optimal Mixing (OM) operators, such as the Restricted Mixing (RM) and the Back Mixing (BM). DSMGA-II was shown to solve theoretical and real-world optimization problems effectively. In this paper, we show that the effectiveness of DSMGA-II and its improved version, namely Two-edge Dependency Structure Matrix Genetic Algorithm-II (DSMGA-IIe), is relatively low for NK-landscape problems. Thus, we propose the Comparative Mixing (CM) operator that extends the RM operator. The CM operator modifies the linkage information obtained from the DSM-based linkage model by comparing the receiver individual with a randomly selected member of the population. Such modification enables DSMGA-II to solve NK-landscape problems effectively and does not limit DSMGA-II performance on most problems for which it was already shown effective.

We applied a Biased Random Key Genetic Algorithm (BRKGA) to solve the Vehicle Routing Problem with Time Windows and Synchronization Constraints. Additionally, both vehicles and clients are skilled, and each client can require up to two distinct skills to be serviced. On double-skilled clients, the operations of each skill should be performed by different vehicles, either simultaneously or respecting a precedence order. Those requirements introduce nonlinearities on the problem, in the sense that a small change on a single route potentially impacts all the other routes of the solution, making it hard to define an effective local search procedure. To circumvent this difficulty, we approached the problem using a genetic algorithm that evolves the sequence in which the services are inserted into the routes. We assessed the performance of our solution method using instances from the literature of the home health care problem. The genetic algorithm outperformed the previous best-known solutions found by a fix-and-optimize matheuristic by up to 25%, using less than half of computational times reported previously. The BRKGA demonstrated to be able to perform well both in exploration and exploitation in the solution space of the problem.

Deep Neural Networks have achieved many successes when applying to visual, text, and speech information in various domains. The crucial reasons behind these successes are the multi-layer architecture and the in-model feature transformation of deep learning models. These design principles have inspired other sub-fields of machine learning including ensemble learning. In recent years, there are some deep homogenous ensemble models introduced with a large number of classifiers in each layer. These models, thus, require a costly computational classification. Moreover, the existing deep ensemble models use all classifiers including unnecessary ones which can reduce the predictive accuracy of the ensemble. In this study, we propose a multi-layer ensemble learning framework called MUlti-Layer heterogeneous Ensemble System (MULES) to solve the classification problem. The proposed system works with a small number of heterogeneous classifiers to obtain ensemble diversity, therefore being efficiency in resource usage. We also propose an Evolutionary Algorithm-based selection method to select the subset of suitable classifiers and features at each layer to enhance the predictive performance of MULES. The selection method uses NSGA-II algorithm to optimize two objectives concerning classification accuracy and ensemble diversity. Experiments on 33 datasets confirm that MULES is better than a number of well-known benchmark algorithms.

Node-Depth Based Encoding is a representation for Evolutionary Algorithms applied to problems modelled by trees, storing nodes and their respective depths in an appropriately ordered list. This representation was highlighted by the results obtained, whose mutation and recombination operators have low time complexity in relation to other representations for the same problems. This work proposes new search operators. A high locality mutation operator, having as its main differential the possibility of including any edge present in a graph and a recombination operator with the ability to generate solutions with as much heritability as possible considering the edges set in the solutions, making it possible to recombine any solutions in the population with the aim of improving search convergence. All proposed operators also allow for dealing with problems modelled by forests with many trees and complete or non-complete graphs, always generating feasible solutions. This study performed bias, locality and heritability investigations for proposed operators showing that they have adequate characteristics for dealing with high dimensionality problems. In order to evaluate the performance of proposed operators, the results of preliminary tests were obtained applying to a benchmark problem in the literature. The use of proposed operators resulted in faster convergence.

Linkage learning is frequently employed in modern evolutionary algorithms. High linkage quality may be the key to an evolutionary method's effectiveness. Similarly, the faulty linkage may be the reason for its poor performance. Many state-of-the-art evolutionary methods use a Dependency Structure Matrix (DSM) to obtain linkage. In this paper, we propose a quality measure for DSM. Based on this measure, we analyze the behavior of modern evolutionary methods. We show the dependency between the linkage and the effectiveness of the considered methods. Finally, we propose a framework that improves the quality of the linkage.

Most algorithms proposed for solving complex problems require the definition of some parameter values. The process of finding suitable parameter values is an optimization problem by itself. Understanding the global structure of search spaces of complex optimization problems remains a challenge. Moreover, understanding the relationship between parameter values and the performance of metaheuristics is a key issue on their development. Local optima networks propose a scheme to model search spaces as networks whose nodes represent local optima and edges represent transitions between them. In this work, we adapt the local optima network model to analyze and visualize the global structure of parameter configuration spaces. Our main objectives are to understand the structure of these networks and explore the difficulty of different tuning scenarios using common indicators previously proposed in local optima networks studies (e.g. number of local optima, number of global optima and presence of local and global funnels). For this, we use the well-known tuning method ParamILS to analyze configuration search spaces of a standard genetic algorithm that solves continuous optimization problems.

There exist general transforms that convert pseudo-Boolean functions into k-bounded pseudo-Boolean functions, for all k ≥ 2. In addition to these general transforms, there can also exist specialized transforms that can be applied in special cases. New results are presented examining what happens to the "bit flip" neighborhood when transforms are applied. Transforms condense variables in a particular order. We show that different variable orderings produce different results in terms of problem difficulty. We also prove new results about the embedding of the original function in the new k-bounded function. Finally, this paper also looks at how parameter optimization problems can be expressed as high precision k-bounded pseudo-Boolean functions. This paper lays a foundation for the wider application of evolutionary algorithms to k-bounded pseudo-Boolean functions.