Search

Meta-heuristics Genetic Algorithms (GA) and Ant Colony Optimisation (ACO) have both shown success when applied to permutation problems such as the Traveling Salesman Problem (TSP). Therefore, combining the approaches could prove beneficial. This paper presents an ACO inspired mutation operator for use in a GA based on Partial-ACO. Applied to a range of TSP instances the ACO mutation operator demonstrates considerable improvements over standard GA mutation operators finding solutions within a few percent of optimal for TSP instances of nearly 4000 cities. In fact, experiments demonstrate performance close to that of local search with standard mutation operators. Moreover, when integrating local search the ACO inspired mutation operator continues to provide improved results over standard mutation and local search.

In this paper, we study the effects of a modified crowding distance method and a Polynomial mutation operator on multimodal multi-objective optimization algorithms. Our goal is to provide an in-depth analysis on these two modifications which we apply to NSGA-II: The weighted sum crowding distance and the neighborhood-based mutation operator. Furthermore, we examine the performance of the proposed weighted sum crowding distance method under different weight values to find a trend for the behaviour of the proposed algorithm. We compare the different variations of the proposed method with state-of-the-art algorithms and the baseline NSGA-II. The results show that our modifications can improve the functionality of NSGA-II on multimodal multi-objective problems.

Evolutionary algorithms, including genetic algorithm, usually appear premature convergence. In this paper, new crossover and mutation operators are introduced. This paper addresses an application of improved genetic algorithms (IGA) for solving the Vehicle Routing Problem (VRP). After the introduction of new genetic operators, diversity of population becomes abundant. The ability of global search is obviously improved in new algorithm. Simulations indicate that new genetic algorithm is competitive with other modern heuristics.

It is crucial that smart contracts are tested thoroughly due to their immutable nature. Even small bugs in smart contracts can lead to huge monetary losses. However, testing is not enough; it is also important to ensure the quality and completeness of the tests. There are already several approaches that tackle this challenge with mutation testing, but their effectiveness is questionable since they only considered small contract samples. Hence, we evaluate the quality of smart contract mutation testing at scale. We choose the most promising of the existing (smart contract specific) mutation operators, analyse their effectiveness in terms of killability and highlight severe vulnerabilities that can be injected with the mutations. Moreover, we improve the existing mutation methods by introducing a novel killing condition that is able to detect a deviation in the gas consumption, i.e., in the monetary value that is required to perform transactions.

The 2D Bin-Packing Problem (2DBPP) is an NP-Hard combinatorial optimisation problem with many real-world analogues. Fully deterministic methods such as the well-known Best Fit and First Fit heuristics, stochastic methods such as Evolutionary Algorithms (EAs), and hybrid EAs that combine the deterministic and stochastic approaches have all been applied to the problem. Combining derived human expertise with a hybrid EA offers another potential approach. In this work, the moves of humans playing a gamified version of the 2DBPP were recorded and four different Human-Derived Heuristics (HDHs) were created by learning the underlying heuristics employed by those players. Each HDH used a decision tree in place of the mutation operator in the EA. To test their effectiveness, these were compared against hybrid EAs utilising Best Fit or First Fit heuristics as well as a standard EA using a random swap mutation modified with a Next Fit heuristic if the mutation was infeasible. The HDHs were shown to outperform the standard EA and were faster to converge than – but ultimately outperformed by – the First Fit and Best Fit heuristics. This shows that humans can create competitive heuristics through gameplay and helps to understand the role that heuristics can play in stochastic search.

Progress in the development of automatic grouping (clustering) methods, based on solving the p-median and similar problems, is mainly aimed at increasing the computational efficiency of the algorithms, their applicability to larger problems, accuracy, and stability of their results. The researchers’ efforts are focused on the development of compromise heuristic algorithms that provide a fairly quick solution with minimal error. The Genetic Algorithms (GAs) with greedy agglomerative crossover procedure and other special GAs for the considered problems demonstrate the best values of the objective function (sum of squared distances) for many practically important problems. Usually, such algorithms do not use any mutation operator, which is common for other GAs.

In software engineering, mutation consists in injecting small changes in artefacts – like models, programs, or data – for purposes like (mutation) testing, test data generation, and all sorts of search-based methods. These activities normally require the definition of sets of mutation operators, which are often built ad-hoc because there is currently poor support for their development and testing.

In the field of software testing, several meta-heuristics algorithms have been successfully used for finding an optimized t-way test suite (where t refers to covering level). T-way testing strategies adopt the meta-heuristic algorithms to generate the smallest/optimal test suite. However, the existing t-way strategies’ results show that no single strategy appears to be superior in all problems. The aim of this paper to propose a new variant of Jaya algorithm for generating t-way test suite called Improved Jaya Algorithm (IJA). In fact, the performance of meta-heuristic algorithms highly depends on the intensification and diversification capabilities. IJA enhances the intensification and diversification capabilities by introducing new operators search such levy flight and mutation operator in Jaya Algorithm. Experimental results show that the IJA variant improves the results of original Jaya algorithm, also overcomes the problems of slow convergence of Jaya algorithm.

In this work, we address the hard clustering problem. We present a new clustering algorithm based on evolutionary computation searching a best partition with respect to a given quality measure. We present 32 partition transformation that are used as mutation operators. The algorithm is a \((1+1)\) evolutionary strategy that selects a random mutation on each step from a subset of preselected mutation operators. Such selection is performed with a classifier trained to predict usefulness of each mutation for a given dataset. Comparison with state-of-the-art approach for automated clustering algorithm and hyperparameter selection shows the superiority of the proposed algorithm.

The null-type is a major source of faults in Java programs, and its overuse has a severe impact on software maintenance. Unfortunately traditional mutation testing operators do not cover null-type faults by default, hence cannot be used as a preventive measure. We address this problem by designing four new mutation operators which model null-type faults explicitly. We show how these mutation operators are capable of revealing the missing tests, and we demonstrate that these mutation operators are useful in practice. For the latter, we analyze the test suites of 15 open-source projects to describe the trade-offs related to the adoption of these operators to strengthen the test suite.

Optimum-Path Forest (OPF) is a graph-based classifier that has achieved remarkable results in various applications. OPF has many advantages when compared to other supervised classifiers, since it is free of parameters, achieves zero classification errors on the training set without overfitting, handles multiple classes without modifications or extensions, and does not make assumptions about the shape and separability of the classes. Despite these advantages, it still suffers with a high computational cost required to execute its classification process, which grows proportionally to the size of the training set. In order to overcome this drawback, we propose a new approach based on genetic algorithms to prune irrelevant training samples and still preserve accuracy in OPF classification. In our proposal, named FSGAP-OPF, the standard reproduction and mutation operators are modified so as to maintain the number of pruned patterns with a fixed-size. To evaluate the performance of our method, we tested its generalization capabilities on datasets obtained from the UCI repository. On the basis of our experiments, we can say that FSGAP-OPF is a good alternative for classification tasks and can also be used in problems where the memory consuming is crucial.

Tertiary protein structure prediction is one of the most challenging problems in Structural Bioinformatics, and it is a NP-Complete problem in computational complexity theory. The complexity is related to the significant number of possible conformations a single protein can assume. Metaheuristics became useful algorithms to find feasible solutions in viable computational time since exact algorithms are not capable. However, these stochastic methods are highly-dependent from parameter tuning for finding the balance between exploitation (local search refinement) and exploration (global exploratory search) capabilities. Thus, self-adaptive techniques were created to handle the parameter definition task, since it is time-consuming. In this paper, we enhance the Self-Adaptive Differential Evolution with problem-domain knowledge provided by the angle probability list approach, comparing it with every single mutation we used to compose our set of mutation operators. Moreover, a population diversity metric is used to analyze the behavior of each one of them. The proposed method was tested with ten protein sequences with different folding patterns. Results obtained showed that the self-adaptive mechanism has a better balance between the search capabilities, providing better results in regarding root mean square deviation and potential energy than the non-adaptive single-mutation methods.

This article presents a genetic algorithm (GA) to solve the picker routing problem in multiple-block warehouses in order to minimize the traveled distance. The GA uses survival, crossover, immigration, and mutation operators, and is complemented by a local search heuristic. The genetic algorithm provides average distance savings of 13.9% when compared with s-shape strategy, and distance savings of 23.3% when compared with the GA with the aisle-by-aisle policy. We concluded that the GA performs better as the number of blocks increases, and as the percentage of picking locations to visit decreases.

For the purpose of improving the search strategy of the krill herd algorithm (KHA) , an improved robust approach is proposed to address the function optimization problems, namely, modified krill herd algorithm (MKHA) . In MKHA method, the modification of krill herd algorithm focuses on genetic operators (GOs) and it occurs in the ordering of procedures of the basic krill herd algorithm, where the crossover and mutation operators are employed after the updating process of the krill individuals position, the krill herd (KH) motion calculations, is finished. This modification is conducted because the genetic operators insignificantly exploit to enhance the global exploration search in the basic krill herd algorithm so as to speed up convergence. Several versions of benchmark functions are applied to verify the proposed method (MKHA) and it is showed that, in most cases, the proposed algorithm (MKHA) obtained better results in comparison with the basic KHA and other comparative methods.