Frequency Fitness Assignment (FFA) offers an alternative take on metaheuristic optimization. Here, the encounter frequencies of objective values are used to make the selection decisions. This leads to a variety of interesting algorithm features, such as an invariance under all injective transformations of the objective function value and a very strong focus on exploration of the search space. In this article, for the first time, we discover a condition under which purely FFA-guided search can actually get stuck, even on a problem as simple as OneMax. To tackle this issue, we suggest hybrid approaches combining objective-guided and FFA-guided search. We propose using crossover for solution transfer between the two component algorithms of the hybrids. Our experiments show that (1) the original FFA allows us to solve problems like Trap, TwoMax, and Jump in (experimentally observed) polynomial time; (2) the suggested hybrids address FFA's shortcomings and are occasionally orders of magnitude faster; and (3) we report several new best-known solutions for the NP-hard low-autocorrelation binary sequences problem.

Horizontal Pod Auto-scalers (HPAs) are crucial for managing resource allocation in microservice architectures to handle fluctuating workloads. However, traditional HPAs fail to address resource disruptions caused by faults, cyberattacks, maintenance, and other operational challenges. These disruptions result in resource wastage, service unavailability, and HPA performance degradation. To address these challenges, we propose SecureSmart HPA, a resilient and resource-efficient HPA for microservice architectures. SecureSmart HPA monitors microservice resource demands, detects disruptions, evaluates resource wastage, and dynamically adjusts scaling decisions to enhance the resilience of auto-scaling operations. Furthermore, SecureSmart HPA enables resource sharing among microservices, optimizing scaling efficiency in resource-constrained environments. Experimental evaluation demonstrates that under disruption severities of 25%, 50%, and 75% resource wastage, SecureSmart HPA delivers robust performance, underscoring its resilience and efficiency in volatile, resource-constrained environments.

Large language models (LLMs) have demonstrated impressive capabilities in code generation, achieving high scores on benchmarks such as HumanEval and MBPP. However, these benchmarks primarily assess functional correctness and neglect broader dimensions of code quality, including security, reliability, readability, and maintainability. In this work, we systematically evaluate the ability of LLMs to generate high-quality code across multiple dimensions using the PythonSecurityEval benchmark. We introduce an iterative static analysis-driven prompting algorithm that leverages Bandit and Pylint to identify and resolve code quality issues. Our experiments with GPT-4o show substantial improvements: security issues reduced from >40% to 13%, readability violations from >80% to 11%, and reliability warnings from >50% to 11% within ten iterations. These results demonstrate that LLMs, when guided by static analysis feedback, can significantly enhance code quality beyond functional correctness.

In supporting the development of high-quality software, especially necessary in the era of LLMs, automated program repair (APR) tools aim to improve code quality by automatically addressing violations detected by static analysis profilers. Previous research tends to evaluate APR tools only for their ability to clear violations, neglecting their potential introduction of new (sometimes severe) violations, changes to code functionality and degrading of code structure. There is thus a need for research to develop and assess comprehensive evaluation frameworks for APR tools. This study addresses this research gap, and evaluates Sorald (a state-of-the-art APR tool) as a proof of concept. Sorald’s effectiveness was evaluated in repairing 3,529 SonarQube violations across 30 rules within 2,393 Java code snippets extracted from Stack Overflow. Outcomes show that while Sorald fixes specific rule violations, it introduced 2,120 new faults (32 bugs, 2088 code smells), reduced code functional correctness—as evidenced by a 24% unit test failure rate—and degraded code structure, demonstrating the utility of our framework. Findings emphasize the need for evaluation methodologies that capture the full spectrum of APR tool effects, including side effects, to ensure their safe and effective adoption.

Abstract The code base of software projects evolves essentially through inserting and removing information to and from the source code. We can measure this evolution via the elements of infor-mation—tokens, words, nodes—of the respective representation of the code. In this work, we approach the measurement of the information content of the source code of open-source projects from an information-theoretic standpoint. Our focus is on the entropy of two funda-mental representations of code: tokens and abstract syntax tree nodes, from which we derive definitions of textual and structural entropy. We proceed with an empirical assessment where we evaluate the evolution patterns of the entropy of 95 actively maintained open source pro-jects. We calculate the statistical relationships between our derived entropy metrics and classic methods of measuring code complexity and learn that entropy may capture different dimen-sions of complexity than classic metrics. Finally, we conduct entropy-based anomaly detection of unusual changes to demonstrate that our approach may effectively recognise unusual source code change events with over 60% precision, and lay the groundwork for improvements to information-theoretic measurement of source code evolution, thus paving the way for a new approach to statically gauging program complexity throughout its development.

Microservice architectures have become increasingly popular in both academia and industry, providing enhanced agility, elasticity, and maintainability in software development and deployment. To simplify scaling operations in microservice architectures, container orchestration platforms such as Kubernetes feature Horizontal Pod Auto-scalers (HPAs) designed to adjust the resources of microservices to accommodate fluctuating workloads. However, existing HPAs are not suitable for resource-constrained environments, as they make scaling decisions based on the individual resource capacities of microservices, leading to service unavailability, resource mismanagement, and financial losses. Furthermore, the inherent delay in initializing and terminating microservice pods hinders HPAs from timely responding to workload fluctuations, further exacerbating these issues. To address these concerns, we propose Smart HPA and ProSmart HPA, reactive and proactive resource-efficient horizontal pod auto-scalers respectively. Smart HPA employs a reactive scaling policy that facilitates resource exchange among microservices, optimizing auto-scaling in resource-constrained environments. For ProSmart HPA, we develop a machine-learning-driven resource-efficient scaling policy that proactively manages resource demands to address delays caused by microservice pod startup and termination, while enabling preemptive resource sharing in resource-constrained environments. Our experimental results show that Smart HPA outperforms the Kubernetes baseline HPA, while ProSmart HPA exceeds both Smart HPA and Kubernetes HPA by reducing resource overutilization, overprovisioning, and underprovisioning, and increasing resource allocation to microservice applications. • Hierarchical architecture based horizontal pod auto-scaler. • Reactive and proactive resource-efficient auto-scaling policies. • Reactive auto-scaler outperforms Kubernetes baseline auto-scaler. • Proactive auto-scaler outperforms both reactive and Kubernetes auto-scalers. • Reduction in resource overutilization, underprovisioning, and overprovisioning.

Parameter control refers to the techniques that dynamically adapt the parameter values of the evolutionary algorithm during the optimization process, such as population size, crossover rate, or operator selection. Adaptation can improve the performance and robustness of the algorithm, however, parameter control mechanisms themselves need to be designed and configured carefully. With this article, we contribute a systematic investigation of an adaptive, multi-objective algorithm that is designed for the optimisation of problems in unbounded integer decision spaces. We find that (1) adaptation outperforms the best static configurations by 39–82 %, and (2) performance of the multi-objective algorithm is often independent of the adaptation scheme's initial configuration.

Online social networks have become an integral aspect of our daily lives and play a crucial role in shaping our relationships with others. However, bugs and glitches, even minor ones, can cause anything from frustrating problems to serious data leaks that can have far-reaching impacts on millions of users.To mitigate these risks, fuzz testing, a method of testing with randomised inputs, can provide increased confidence in the correct functioning of a social network. However, implementing traditional fuzz testing methods can be prohibitively difficult or impractical for programmers outside of the social network's development team.To tackle this challenge, we present Socialz, a novel approach to social fuzz testing that (1) characterises real users of a social network, (2) diversifies their interaction using evolutionary computation across multiple, non-trivial features, and (3) collects performance data as these interactions are executed. With Socialz, we aim to put social testing tools in everybody's hands, thereby improving the reliability and security of social networks used worldwide.In our study, we came across (1) one known limitation of the current GitLab CE and (2) 6,907 errors, of which 40.16% are beyond our debugging skills.

Microservice architectures have gained prominence in both academia and industry, offering enhanced agility, reusability, and scalability. To simplify scaling operations in microservice architectures, container orchestration platforms such as Kubernetes feature Horizontal Pod Auto-scalers (HPAs) designed to adjust the resources of microservices to accommodate fluctuating workloads. However, existing HPAs are not suitable for resource-constrained environments, as they make scaling decisions based on the individual resource capacities of microservices, leading to service unavailability and performance degradation. Furthermore, HPA architectures exhibit several issues, including inefficient data processing and a lack of coordinated scaling operations. To address these concerns, we propose Smart HPA, a flexible resource-efficient horizontal pod auto-scaler. It features a hierarchical architecture that integrates both centralized and decentralized architectural styles to leverage their respective strengths while addressing their limitations. We introduce resource-efficient heuristics that empower Smart HPA to exchange resources among microservices, facilitating effective auto-scaling of microservices in resource-constrained environments. Our experimental results show that Smart HPA outperforms the Kubernetes baseline HPA by reducing resource overutilization, overprovisioning, and underprovisioning while increasing resource allocation to microservice applications.

The Traveling Salesperson Problem (TSP) is one of the most well-known N P-hard optimization tasks. A randomized local search (RLS) is not a good approach for solving TSPs, as it quickly gets stuck at local optima. FRLS, the same algorithm with Frequency Fitness Assignment plugged in, has been shown to be able to solve many more TSP instances to optimality. However, it was also assumed that its performance will decline if an instance has a large number M of different possible objective values. How can we explore these more or less obvious algorithm properties in a controlled fashion, if determining the number #L of local optima or the size BL of their joint basins of attraction as well as the feature M are N P-hard problems themselves? By creating TSP instances with a small number of cities for which we can actually know these features! We develop a deterministic construction method for creating TSP instances with rising numbers M and a sampling based approach for the other features. We determine all the instance features exactly and can clearly confirm the obvious (in the case of RLS) or previously suspected (in the case of FRLS) properties of the algorithms. Furthermore, we show that even with small-scale instances, we can make interesting new findings, such as that local optima seemingly have little impact on the performance of FRLS.

To ensure reliable object detection in autonomous systems, the detector must be able to adapt to changes in appearance caused by environmental factors such as time of day, weather, and seasons. Continually adapting the detector to incorporate these changes is a promising solution, but it can be computationally costly. Our proposed approach is to selectively adapt the detector only when necessary, using new data that does not have the same distribution as the current training data. To this end, we investigate three popular metrics for domain gap evaluation and find that there is a correlation between the domain gap and detection accuracy. Therefore, we apply the domain gap as a criterion to decide when to adapt the detector. Our experiments show that our approach has the potential to improve the efficiency of the detector’s operation in real-world scenarios, where environmental conditions change in a cyclical manner, without sacrificing the overall performance of the detector. Our code is publicly available https://github.com/dadung/DGE-CDA.

Abstract Outdated documentation is a pervasive problem in software development, preventing effective use of software, and misleading users and developers alike. We posit that one possible reason why documentation becomes out of sync so easily is that developers are unaware of when their source code modifications render the documentation obsolete. Ensuring that the documentation is always in sync with the source code takes considerable effort, especially for large codebases. To address this situation, we propose an approach that can automatically detect code element references that survive in the documentation after all source code instances have been deleted. In this work, we analysed over 3,000 GitHub projects and found that most projects contain at least one outdated code element reference at some point in their history. We submitted GitHub issues to real-world projects containing outdated references detected by our approach, some of which have already led to documentation fixes. As an initiative toward keeping documentation in software repositories up-to-date, we have made our implementation available for developers to scan their GitHub projects for outdated code element references.

No abstract available.

Countries with access to large bodies of water often aim to protect their maritime transport by employing maritime surveillance systems. However, the number of available sensors (e.g., cameras) is typically small compared to the to-be-monitored targets, and their Field of View (FOV) and range are often limited. This makes improving the situational awareness of maritime transports challenging. To this end, we propose a method that not only distributes multiple sensors but also plans paths for them to observe multiple targets, while minimizing the time needed to achieve situational awareness. In particular, we provide a formulation of this sensor allocation and path planning problem which considers the partial awareness of the targets’ state, as well as the unawareness of the targets’ trajectories. To solve the problem we present two algorithms: 1) a greedy algorithm for assigning sensors to targets, and 2) a distributed multi-agent path planning algorithm based on regret-matching learning. Because a quick convergence is a requirement for algorithms developed for high mobility environments, we employ a forgetting factor to quickly converge to correlated equilibrium solutions. Experimental results show that our combined approach achieves situational awareness more quickly than related work.

Encountering outdated documentation is not a rare occurrence for developers and users in the software engineering community. To ensure that software documentation is up-to-date, developers often have to manually check whether the documentation needs to be updated whenever changes are made to the source code. In our previous work, we proposed an approach to automatically detect outdated code element references in software repositories and found that more than a quarter of the 1000 most popular projects on GitHub contained at least one outdated reference. In this paper, we present a GitHub Actions tool that builds on our previous work’s approach that GitHub developers can configure to automatically scan for outdated code element references in their GitHub project’s documentation whenever a pull request is submitted.

Most online code snippets do not run. This means that developers looking to reuse code from online sources must manually find and fix errors. We present an approach for automatically evaluating and correcting errors in Node.js code snippets: Node Code Correction (NCC). NCC leverages the ability of the TypeScript compiler to generate errors and inform code corrections through the combination of TypeScript’s builtin codefixes, our own targeted fixes, and deletion of erroneous lines. Compared to existing approaches using linters, our findings suggest that NCC is capable of detecting a larger number of errors per snippet and more error types, and it is more efficient at fixing snippets. We find that 73.7% of the code snippets in NPM documentation have errors; with the use of NCC’s corrections, this number was reduced to 25.1%. Our evaluation confirms that the use of the TypeScript compiler to inform code corrections is a promising strategy to aid in the reuse of code snippets from online sources.

In microservice architectures, developers can face significant problems understanding the structure of the system and how the different microservices interact. This difficulty results from the distributed nature of the system, and the abundance of inter-service communication within the architecture. We want to determine if network visualisations can address these problems given their ability to convey complex topologies. However, to identify what architectural characteristics should be visualised, and how this should be done, we must first determine the needs of microservice developers. This paper identifies and presents the impact and frequency of problems faced by a cohort of microservice developers using the results of an online survey. Our findings indicate that the most frequent problems were topology related and the highest impact problems were those related to system faults and data structures. Our results support the use of network visualisations to address microservice development problems and provide context that will allow future visualisations of any type to better address these problems.

Abstract Automated program modification underlies two successful research areas — genetic improvement and program repair. Under the generate-and-validate strategy, automated program modification transforms a program, then validates the result against a test suite. Much work has focused on the search space of application of single fine-grained operators — copy, delete, replace, and swap at both line and statement granularity. This work explores the limits of this strategy. We scale up existing findings an order of magnitude from small corpora to 10 real-world Java programs comprising up to 500k LoC. We decisively show that the grammar-specificity of statement granular edits pays off: its pass rate triples that of line edits and uses 10% less computational resources. We confirm previous findings that delete is the most effective operator for creating test-suite equivalent program variants. We go farther than prior work by exploring the limits of delete ’s effectiveness by exhaustively applying it. We show this strategy is too costly in practice to be used to search for improved software variants. We further find that pass rates drop from 12–34% for single statement edits to 2–6% for 5-edit sequences, which implies that further progress will need human-inspired operators that target specific faults or improvements. A program is amenable to automated modification to the extent to which automatically editing it is likely to produce test-suite passing variants. We are the first to systematically search for a code measure that correlates with a program’s amenability to automated modification. We found no strong correlations, leaving the question open.

Most software domains rely on compilers to translate high-level code to multiple different machine languages, with performance not too much worse than what developers would have the patience to write directly in assembly language. However, cryptography has been an exception, where many performance-critical routines have been written directly in assembly (sometimes through metaprogramming layers). Some past work has shown how to do formal verification of that assembly, and other work has shown how to generate C code automatically along with formal proof, but with consequent performance penalties vs. the best- known assembly. We present CryptOpt, the first compilation pipeline that specializes high-level cryptographic functional programs into assembly code significantly faster than what GCC or Clang produce, with mechanized proof (in Coq) whose final theorem statement mentions little beyond the input functional program and the operational semantics of x86-64 assembly. On the optimization side, we apply randomized search through the space of assembly programs, with repeated automatic benchmarking on target CPUs. On the formal-verification side, we connect to the Fiat Cryptography framework (which translates functional programs into C-like IR code) and extend it with a new formally verified program-equivalence checker, incorporating a modest subset of known features of SMT solvers and symbolic-execution engines. The overall prototype is quite practical, e.g. producing new fastest-known implementations of finite-field arithmetic for both Curve25519 (part of the TLS standard) and the Bitcoin elliptic curve secp256k1 for the Intel 12𝑡ℎ and 13𝑡ℎ generations.

Cloud and edge computing have been widely adopted in many application scenarios. With the increasing demand of fast iteration and complexity of business logic, it is challenging to achieve rapid development and continuous delivery in such highly distributed cloud and edge computing environment. At present, the microservice-based architecture has been the dominant deployment style, and a microservice system has to evolve agilely to offer stable Quality of Service (QoS) in the situation where user requirement changes frequently. A lot of research have been conducted to optimally re-deploy microservices to adapt to changing requirements. Nevertheless, complex dependencies between microservices and the existence of multiple instances of one single microservice in a microservice system together have not been fully considered in existing work. This article defines SPPMS, the Service Placement Problem in Microservice Systems that featurecomplex dependenciesandmultiple instances, as a Fractional Polynomial Problem (FPP). Considering the high computation complexity of FPP, it is then transformed into a Quadratic Sum-of-Ratios Fractional Problem (QSRFP) which is further solved by the our proposed greedy-based algorithms. Experiments demonstrate that our models and algorithms outperform existing approaches in both qualities of the generated solutions and computation speed.

The ACM Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS) focuses on the measurement and performance evaluation of computer systems and operates in close collaboration with the ACM Special Interest Group SIGMETRICS. All ...

Code reuse is an important part of software development. The adoption of code reuse practices is especially common among Node.js developers. The Node.js package manager, NPM, indexes over 1 Million packages and developers often seek out packages to solve programming tasks. Due to the vast number of packages, selecting the right package is difficult and time consuming. With the goal of improving productivity of developers that heavily reuse code through third-party packages, we presentNode Code Query(NCQ), a Read-Eval-Print-Loop environment that allows developers to 1) search for NPM packages using natural language queries, 2) search for code snippets related to those packages, 3) automatically correct errors in these code snippets, 4) quickly setup new environments for testing those snippets, and 5) transition between search and editing modes. In two user studies with a total of 20 participants, we find that participants begin programming faster and conclude tasks faster with NCQ than with baseline approaches, and that they like, among other features, the search for code snippets and packages. Our results suggest that NCQ makes Node.js developers more efficient in reusing code.

Side-channel attacks are a major threat to the security of cryptographic implementations, particularly for small devices that are under the physical control of the adversary. While several strategies for protecting against side-channel attacks exist, these often fail in practice due to unintended interactions between values deep within the CPU. To detect and protect from side-channel attacks, several automated tools have recently been proposed; one of their common limitations is that they only support first-order leakage.

The optimisation of software energy consumption is of growing importance across all scales of modern computing, i.e., from embedded systems to data-centres. Practitioners in the field of Search-Based Software Engineering and Genetic Improvement of Software acknowledge that optimising software energy consumption is difficult due to noisy and expensive fitness evaluations. However, it is apparent from results to date that more progress needs to be made in rigorously validating optimisation results. This problem is pressing because modern computing platforms have highly complex and variable behaviour with respect to energy consumption. To compare solutions fairly we propose in this paper a new validation approach called R3-validation which exercises software variants in a rotated-round-robin order. Using a case study, we present an in-depth analysis of the impacts of changing system states on software energy usage, and we show how R3-validation mitigates these. We compare it with current validation approaches across multiple devices and operating systems, and we show that it aligns best with actual platform behaviour.

Wave energy is a fast-developing and promising renewable energy resource. The primary goal of this research is to maximise the total harnessed power of a large wave farm consisting of fully-submerged three-tether wave energy converters (WECs). Energy maximisation for large farms is a challenging search problem due to the costly calculations of the hydrodynamic interactions between WECs in a large wave farm and the high dimensionality of the search space. To address this problem, we propose a new hybrid multi-strategy evolutionary framework combining smart initialisation, binary population-based evolutionary algorithm, discrete local search and continuous global optimisation. For assessing the performance of the proposed hybrid method, we compare it with a wide variety of state-of-the-art optimisation approaches, including six continuous evolutionary algorithms, four discrete search techniques and three hybrid optimisation methods. The results show that the proposed method performs considerably better in terms of convergence speed and farm output.

A commonly used strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. Building on the recent success of BET-AND-RUN approaches for restarted local search solvers, we introduce a more generic version that makes use of performance prediction. It is our goal to obtain the best possible results within a given time budget t using a given black-box optimization algorithm. If no prior knowledge about problem features and algorithm behavior is available, the question about how to use the time budget most efficiently arises. We first start k ≥ 1 independent runs of the algorithm during an initialization budget t1 < t, pause these runs, then apply a decision maker D to choose 1 ≤ m < k runs from them (consuming t2 ≥ 0 time units in doing so), and then continue these runs for the remaining t3 = t−t1−t2 time units. In previous BET-AND-RUN strategies, the decision maker D = currentBest would simply select the run with the best-so-far results at negligible time. We propose using more advanced methods to discriminate between “good” and “bad” sample runs with the goal of increasing the correlation of the chosen run with the a-posteriori best one. In over 157 million experiments, we test different approaches to predict which run may yield the best results if granted the remaining budget. We show (1) that the currentBest method is indeed a very reliable and robust baseline approach, and (2) that our approach can yield better results than the previous methods.

Smartphones are becoming essential to people's everyday lives. Due to the limited battery capacity of smartphones, researchers and developers are increasingly interested in the energy efficiency of these devices and the software applications that run on them. In the most basic setting, a developer might be interested in knowing which of two program variants might consume more energy, whether this is for use in regression testing or for use in full-scale evolutionary optimisation. To perform such comparisons (tournaments) reliably, we need a model of the number of trials needed to discern between two variants to a desired level of statistical significance. To enable this, we present a conceptual framework based on tournaments which we use to compare a range of test workloads on different combinations of phones and operating systems. Our results quantify the number of trials required to resolve different variants to different levels of fidelity on a range of platforms.

Evolutionary algorithms have successfully been applied to evolve problem instances that exhibit a significant difference in performance for a given algorithm or a pair of algorithms inter alia for the Traveling Salesperson Problem (TSP). Creating a large variety of instances is crucial for successful applications in the blooming field of algorithm selection. In this paper, we introduce new and creative mutation operators for evolving instances of the TSP. We show that adopting those operators in an evolutionary algorithm allows for the generation of benchmark sets with highly desirable properties: (1) novelty by clear visual distinction to established benchmark sets in the field, (2) visual and quantitative diversity in the space of TSP problem characteristics, and (3) significant performance differences with respect to the restart versions of heuristic state-of-the-art TSP solvers EAX and LKH. The important aspect of diversity is addressed and achieved solely by the proposed mutation operators and not enforced by explicit diversity preservation.

Genetic improvement (GI) is a young field of research on the cusp of transforming software development. GI uses search to improve existing software. Researchers have already shown that GI can improve human-written code, ranging from program repair to optimising run-time, from reducing energy-consumption to the transplantation of new functionality. Much remains to be done. The cost of re-implementing GI to investigate new approaches is hindering progress. Therefore, we present Gin, an extensible and modifiable toolbox for GI experimentation, with a novel combination of features. Instantiated in Java and targeting the Java ecosystem, Gin automatically transforms, builds, and tests Java projects. Out of the box, Gin supports automated test-generation and source code profiling. We show, through examples and a case study, how Gin facilitates experimentation and will speed innovation in GI.

Substitution Boxes (S-boxes) are nonlinear objects often used in the design of cryptographic algorithms. The design of high quality S-boxes is an interesting problem that attracts a lot of attention. Many attempts have been made in recent years to use heuristics to design S-boxes, but the results were often far from the previously known best obtained ones. Unfortunately, most of the effort went into exploring different algorithms and fitness functions while little attention has been given to the understanding why this problem is so difficult for heuristics. In this paper, we conduct a fitness landscape analysis to better understand why this problem can be difficult. Among other, we find that almost each initial starting point has its own local optimum, even though the networks are highly interconnected.

Ocean wave energy is a source of renewable energy that has gained much attention for its potential to contribute significantly to meeting the global energy demand. In this research, we investigate the problem of maximising the energy delivered by farms of wave energy converters (WEC's). We consider state-of-the-art fully submerged three-tether converters deployed in arrays. The goal of this work is to use heuristic search to optimise the power output of arrays in a size-constrained environment by configuring WEC locations and the power-take-off (PTO) settings for each WEC. Modelling the complex hydrodynamic interactions in wave farms is expensive, which constrains search to only a few thousand model evaluations. We explore a variety of heuristic approaches including cooperative and hybrid methods. The effectiveness of these approaches is assessed in two real wave scenarios (Sydney and Perth) with farms of two different scales. We find that a combination of symmetric local search with Nelder-Mead Simplex direct search combined with a back-tracking optimization strategy is able to outperform previously defined search techniques by up to 3%.

Evolutionary diversity optimization aims to compute a set of solutions that are diverse in the search space or instance feature space, and where all solutions meet a given quality criterion. With this paper, we bridge the areas of evolutionary diversity optimization and evolutionary multi-objective optimization. We show how popular indicators frequently used in the area of multi-objective optimization can be used for evolutionary diversity optimization. Our experimental investigations for evolving diverse sets of TSP instances and images according to various features show that two of the most prominent multi-objective indicators, namely the hypervolume indicator and the inverted generational distance, provide excellent results in terms of visualization and various diversity indicators.

Software repositories contain large amounts of textual data, ranging from source code comments and issue descriptions to questions, answers, and comments on Stack Overflow. To make sense of this textual data, topic modelling is frequently used as a text-mining tool for the discovery of hidden semantic structures in text bodies. Latent Dirichlet allocation (LDA) is a commonly used topic model that aims to explain the structure of a corpus by grouping texts. LDA requires multiple parameters to work well, and there are only rough and sometimes conflicting guidelines available on how these parameters should be set. In this paper, we contribute (i) a broad study of parameters to arrive at good local optima for GitHub and Stack Overflow text corpora, (ii) an a-posteriori characterisation of text corpora related to eight programming languages, and (iii) an analysis of corpus feature importance via per-corpus LDA configuration. We find that (1) popular rules of thumb for topic modelling parameter configuration are not applicable to the corpora used in our experiments, (2) corpora sampled from GitHub and Stack Overflow have different characteristics and require different configurations to achieve good model fit, and (3) we can predict good configurations for unseen corpora reliably. These findings support researchers and practitioners in efficiently determining suitable configurations for topic modelling when analysing textual data contained in software repositories.

In many evolutionary algorithms (EAs), a parameter that needs to be tuned is that of the mutation rate, which determines the probability for each decision variable to be mutated. Typically, this rate is set to 1/n for the duration of the optimization, where n is the number of decision variables. This setting has the appeal that the expected number of mutated variables per iteration is one.

Despite significant empirical and theoretically supported evidence that non-static parameter choices can be strongly beneficial in evolutionary computation, the question how to best adjust parameter values plays only a marginal role in contemporary research on discrete black-box optimization. This has led to the unsatisfactory situation in which feedback-free parameter selection rules such as the cooling schedule of Simulated Annealing are predominant in state-of-the-art heuristics, while, at the same time, we understand very well that such time-dependent selection rules can not perform as well as adjustment rules that do take into account the evolution of the optimization process. A number of adaptive and self-adaptive parameter control strategies have been proposed in the literature, but did not (yet) make their way to a broader public. A key obstacle seems to lie in their rather complex update rules.

In order to address environmental concerns and meet growing energy demand the development of green energy technology has expanded tremendously. One of the most promising types of renewable energy is ocean wave energy. While there has been strong research in the development of this technology to date there remain a number of technical hurdles to overcome. This research explores a type of wave energy converter (WEC) called a buoy. This work models a power station as an array of fully submerged three-tether buoys. The target problem of this work is to place buoys in a size-constrained environment to maximise power output. This article improves prior work by using a more detailed model and exploring the search space using a wide variety of search heuristics. We show that a hybrid method of stochastic local search combined with Nelder-Mead Simplex direct search performs better than previous search techniques.

Diversity plays a crucial role in evolutionary computation. While diversity has been mainly used to prevent the population of an evolutionary algorithm from premature convergence, the use of evolutionary algorithms to obtain a diverse set of solutions has gained increasing attention in recent years. Diversity optimization in terms of features on the underlying problem allows to obtain a better understanding of possible solutions to the problem at hand and can be used for algorithm selection when dealing with combinatorial optimization problems such as the Traveling Salesperson Problem.

This research proposes a novel indicator-based hybrid evolutionary approach that combines approximate and exact algorithms. We apply it to a new bi-criteria formulation of the travelling thief problem, which is known to the Evolutionary Computation community as a benchmark multi-component optimisation problem that interconnects two classical NP-hard problems: the travelling salesman problem and the 0-1 knapsack problem. Our approach employs the exact dynamic programming algorithm for the underlying packing while travelling problem as a subroutine within a bi-objective evolutionary algorithm. This design takes advantage of the data extracted from Pareto fronts generated by the dynamic program to achieve better solutions. Furthermore, we develop a number of novel indicators and selection mechanisms to strengthen synergy of the two algorithmic components of our approach. The results of computational experiments show that the approach is capable to outperform the state-of-the-art results for the single-objective case of the problem.

Local Optima Networks are models proposed to understand the structure and properties of combinatorial landscapes. The fitness landscape is explored as a graph whose nodes represent the local optima (or basins of attraction) and edges represent the connectivity between them. In this paper, we use this representation to study a combinatorial optimisation problem, with two interdepend components, named the Travelling Thief Problem (TTP). The objective is to understand the search space structure of the TTP using basic local search heuristics and to distinguish the most impactful problem features. We create a large set of enumerable TTP instances and generate a Local Optima Network for each instance using two hill climbing variants. Two problem features are investigated, namely the knapsack capacity and profit-weight correlation. Our insights can be useful not only to design landscape-aware local search heuristics, but also to better understand what makes the TTP challenging for specific heuristics.

Energy demands of applications on mobile platforms are increasing. As a result, there has been a growing interest in optimising their energy efficiency. As mobile platforms are fast-changing, diverse and complex, the optimisation of energy use is a non-trivial task.

This paper introduces Data-Driven Search-based Software Engineering (DSE), which combines insights from Mining Software Repositories (MSR) and Search-based Software Engineering (SBSE). While MSR formulates software engineering problems as data mining problems, SBSE reformulate Software Engineering (SE) problems as optimization problems and use meta-heuristic algorithms to solve them. Both MSR and SBSE share the common goal of providing insights to improve software engineering. The algorithms used in these two areas also have intrinsic relationships. We, therefore, argue that combining these two fields is useful for situations (a) which require learning from a large data source or (b) when optimizers need to know the lay of the land to find better solutions, faster.

A common strategy for improving optimization algorithms is to restart the algorithm when it is believed to be trapped in an inferior part of the search space. However, while specific restart strategies have been developed for specific problems (and specific algorithms), restarts are typically not regarded as a general tool to speed up an optimization algorithm. In fact, many optimization algorithms do not employ restarts at all. Recently, "bet-and-run" was introduced in the context of mixed-integer programming, where first a number of short runs with randomized initial conditions is made, and then the most promising run of these is continued. In this article, we consider two classical NP-complete combinatorial optimization problems, traveling salesperson and minimum vertex cover, and study the effectiveness of different bet-and-run strategies. In particular, our restart strategies do not take any problem knowledge into account, nor are tailored to the optimization algorithm. Therefore, they can be used off-the-shelf. We observe that state-of-the-art solvers for these problems can benefit significantly from restarts on standard benchmark instances.

Multi-objective evolutionary algorithms (MOEAs) based on the concept of Pareto-dominance have been successfully applied to many real-world optimisation problems. Recently, research interest has shifted towards indicator-based methods to guide the search process towards a good set of trade-off solutions. One commonly used approach of this nature is the indicator-based evolutionary algorithm (IBEA). In this study, we highlight the solution distribution issues within IBEA and propose a modification of the original approach by embedding an additional Pareto-dominance based component for selection. The improved performance of the proposed modified IBEA (mIBEA) is empirically demonstrated on the well-known DTLZ set of benchmark functions. Our results show that mIBEA achieves comparable or better hypervolume indicator values and epsilon approximation values in the vast majority of our cases (13 out of 14 under the same default settings) on DTLZ1-7. The modification also results in an over 8-fold speed-up for larger populations.

For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks-which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.

Bet-and-run initialisation strategies have been experimentally shown to be beneficial on classical NP-complete problems such as the travelling salesperson problem and minimum vertex cover. We analyse the performance of a bet-and-run restart strategy, where k independent islands run in parallel for t1 iterations, after which the optimisation process continues on only the best-performing island. We define a family of pseudo-Boolean functions, consisting of a plateau and a slope, as an abstraction of real fitness landscapes with promising and deceptive regions. The plateau shows a high fitness, but does not allow for further progression, whereas the slope has a low fitness initially, but does lead to the global optimum. We show that bet-and-run strategies with non-trivial k and t1 are necessary to find the global optimum efficiently. We show that the choice of t1 is linked to properties of the function. Finally, we provide a fixed budget analysis to guide selection of the bet-and-run parameters to maximise expected fitness after t = k · t1 + t2 fitness evaluations.

Geographical constraints are essential when planning the locations for wind turbines. In real-world scenarios, especially in densely populated countries, the designated area where turbines can be placed is not an empty map on which the turbines can be placed arbitrarily. Even in rural areas, streets, buildings, and rivers have to be considered. In this paper, we model two constrained turbine placement scenarios and use evolutionary algorithms to find optimized turbine locations. To evaluate the locations, we combine a proven wind model with real-world data of a wind prediction model from a meteorological service. Geographical data from a free map service is used to define constrained areas in the scenarios based on administrative rules. For the evolutionary optimization process, we consider five ways to handle penalties. Starting with a simple specification that can only achieve two different values, we end up in a definition that considers distances relative of the required minimum distances to all geographical objects for each turbine. We combine the penalty definitions with three types of penalty functions. In the experimental section, we compare the various configurations and show a detailed analysis of the results.

The traveling thief problem (TTP) is fast gaining attention for being a challenging combinatorial optimization problem. A number of algorithms have been proposed for solving this problem in the recent past. Despite being a challenging problem, it is often argued if TTP is realistic enough because of its formulation, which only allows a single thief to travel across hundreds or thousands of cities to collect (steal) items. In addition, the thief is required to visit all cities, regardless of whether an item is stolen there or not. In this paper we discuss the shortcomings of the current formulation and present a relaxed version of the problem which allows multiple thieves to travel across different cities with the aim of maximizing the group's collective profit. A number of fast heuristics for solving the newly proposed multiple traveling thieves problem (MTTP) are also proposed and evaluated.

Renewable forms of energy are becoming increasingly important to consider, as the global energy demand continues to grow. Wave energy is one of these widely available forms, but it is largely unexploited. A common design for a wave energy converter is called a point absorber or buoy. The buoy typically floats on the surface or just below the surface of the water, and captures energy from the movement of the waves. It can use the motion of the waves to drive a pump to generate electricity and to create potable water. Since a single buoy can only capture a limited amount of energy, large-scale wave energy production necessitates the deployment of buoys in large numbers called arrays. However, the efficiency of arrays of buoys is affected by highly complex intra-buoy interactions. The contributions of this article are two-fold. First, we present an approximation of the buoy interactions model that results in a 350-fold computational speed-up to enable the use inside of iterative optimisation algorithms, Second, we study arrays of fully submerged three-tether buoys, with and without shared mooring points.

This study addresses the recently introduced Traveling Thief Problem (TTP) which combines the classical Traveling Salesman Problem (TSP) with the 0-1 Knapsack Problem (KP). The problem consists of a set of cities, each containing a set of available items with weights and profits. It involves searching for a permutation of the cities to visit and a decision on items to pick. A selected item contributes its profit to the overall profit at the price of higher transportation cost incurred by its weight. The objective is to maximize the resulting profit. We propose a number of problem-specific packing strategies run on top of TSP solutions derived by the Chained Lin-Kernighan heuristic. The investigations provided on the set of benchmark instances prove their rapidity and efficiency when compared with an approximate mixed integer programming based approach and state-of-the-art heuristic solutions from the literature.

Wind turbine placement, i.e., the geographical planning of wind turbine locations, is an important first step to an efficient integration of wind energy. The turbine placement problem becomes a difficult optimization problem due to varying wind distributions at different locations and due to the mutual interference in the wind field known as wake effect. Artificial and environmental geological constraints make the optimization problem even more difficult to solve. In our paper, we focus on the evolutionary turbine placement based on an enhanced wake effect model fed with real-world wind distributions. We model geo-constraints with real-world data from OpenStreetMap. Besides the realistic modeling of wakes and geo-constraints, the focus of the paper is on the comparison of various evolutionary optimization approaches. We propose four variants of evolution strategies with turbine-oriented mutation operators and compare to state-of-the-art optimizers like the CMA-ES in a detailed experimental analysis on three benchmark scenarios.

In genetic programming, the size of a solution is typically not specified in advance, and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: individuals grow without providing additional benefit to the quality of solutions, and the additional elements can block the optimization process. Consequently, problems that are relatively easy to optimize cannot be handled by variable-length evolutionary algorithms. In this article, we analyze different single- and multiobjective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures. We complement the theoretical results with comprehensive experiments to indicate the tightness of existing bounds, and to indicate bounds where theoretical results are missing.

In genetic programming, the size of a solution is typically not specified in advance and solutions of larger size may have a larger benefit. The flexibility often comes at the cost of the so-called bloat problem: individuals grow without providing additional benefit to the quality of solutions, and the additional elements can block the optimisation process. Consequently, problems that are relatively easy to optimise can not be handled by variable-length evolutionary algorithms. In this article, we present several new bounds for different single- and multi-objective algorithms on the sorting problem, a problem that typically lacks independent and additive fitness structures.

The correctness of program verification systems is of great importance, as they are used to formally prove that safety- and security-critical programs follow their specification. One of the contributing factors to the correctness of the whole verification system is the correctness of the background axiomatization, which captures the semantics of the target program language. We present a framework for the maximization of the proportion of the axiomatization that is used (“covered”) during testing of the verification tool. The diverse set of test cases found not only increases the trust in the verification system, but it can also be used to reduce the time needed for regression testing.

Real-world optimization problems often consist of several NP-hard optimization problems that interact with each other. The goal of this paper is to provide a benchmark suite that promotes a research of the interaction between problems and their mutual influence. We establish a comprehensive benchmark suite for the traveling thief problem (TTP) which combines the traveling salesman problem and the knapsack problem. Our benchmark suite builds on common benchmarks for the two sub-problems which grant a basis to examine the potential hardness imposed by combining the two classical problems. Furthermore, we present some simple heuristics for TTP and their results on our benchmark suite.

The Pareto front of a multi-objective optimization problem is typically very large and can only be approximated. Approximation-Guided Evolution (AGE) is a recently presented evolutionary multi-objective optimization algorithm that aims at minimizing iteratively the approximation factor, which measures how well the current population approximates the Pareto front. It outperforms state-of-the-art algorithms for problems with many objectives. However, AGE's performance is not competitive on problems with very few objectives. We study the reason for this behavior and observe that AGE selects parents uniformly at random, which has a detrimental effect on its performance. We then investigate different algorithm-specific selection strategies for AGE. The main difficulty here is finding a computationally efficient selection scheme which does not harm AGEs linear runtime in the number of objectives. We present several improved selections schemes that are computationally efficient and substantially improve AGE on low-dimensional objective spaces, but have no negative effect in high-dimensional objective spaces.

Understanding the behaviour of well-known algorithms for classical NP-hard optimisation problems is still a difficult task. With this paper, we contribute to this research direction and carry out a feature based comparison of local search and the well-known Christofides approximation algorithm for the Traveling Salesperson Problem. We use an evolutionary algorithm approach to construct easy and hard instances for the Christofides algorithm, where we measure hardness in terms of approximation ratio. Our results point out important features and lead to hard and easy instances for this famous algorithm. Furthermore, our cross-comparison gives new insights on the complementary benefits of the different approaches.

We consolidate the existing computational complexity analysis of genetic programming (GP) by bringing together sound theoretical proofs and empirical analysis. In particular, we address computational complexity issues arising when coupling algorithms using variable length representation, such as GP itself, with different bloat-control techniques. In order to accomplish this, we first introduce several novel upper bounds for two single- and multi-objective GP algorithms on the generalised Weighted ORDER and MAJORITY problems. To obtain these, we employ well-established computational complexity analysis techniques such as fitness-based partitions, and for the first time, additive and multiplicative drift.

Approximation-Guided Evolution (AGE) [4] is a recently presented multi-objective algorithm that outperforms state-of-the-art multi-multi-objective algorithms in terms of approximation quality. This holds for problems with many objectives, but AGE's performance is not competitive on problems with few objectives. Furthermore, AGE is storing all non-dominated points seen so far in an archive, which can have very detrimental effects on its runtime. In this article, we present the fast approximation-guided evolutionary algorithm called AGE-II. It approximates the archive in order to control its size and its influence on the runtime. This allows for trading-off approximation and runtime, and it enables a faster approximation process. Our experiments show that AGE-II performs very well for multi-objective problems having few as well as many objectives. It scales well with the number of objectives and enables practitioners to add objectives to their problems at small additional computational cost.

The single-objective yield optimisation of wind turbine placements on a given area of land is already a challenging optimization problem. In this article, we tackle the multi-objective variant of this problem: we are taking into account the wake effects that are produced by the different turbines on the wind farm, while optimising the energy yield, the necessary area, and the cable length needed to connect all turbines.

The design of a wind farm involves several complex optimization problems. We consider the multi-objective optimization problem of maximizing the energy output under the consideration of wake effects and minimizing the cost of the turbines and land area used for the wind farm. We present an efficient particle swarm optimization algorithm that computes a set of trade-off solutions for the given task. Our algorithm can be easily integrated into the layout process for developing wind farms and gives designers new insights into the trade-off between energy output and land area.

Archives have been widely used in evolutionary multi-objective optimization in order to store the optimal points found so far during the optimization process. Usually the size of an archive is bounded which means that the number of points it can store is limited. This implies that knowledge about the set of non-dominated solutions that has been obtained during the optimization process gets lost. Working with unbounded archives allows to keep this knowledge which can be useful for the progress of an evolutionary multi-objective algorithm. In this paper, we propose an adaptive data structure for dealing with unbounded archives. This data structure allows to traverse the archive efficiently and can also be used for sampling solutions from the archive which can be used for reproduction.

Multi-objective optimization problems arise frequently in applications but can often only be solved approximately by heuristic approaches. Evolutionary algorithms have been widely used to tackle multi-objective problems. These algorithms use different measures to ensure diversity in the objective space but are not guided by a formal notion of approximation. We present a new framework of an evolutionary algorithm for multi-objective optimization that allows to work with a formal notion of approximation. Our experimental results show that our approach outperforms state-of-the-art evolutionary algorithms in terms of the quality of the approximation that is obtained in particular for problems with many objectives.

We examine the problem of partitioning a square into convex polygons which are as circular as possible. Circular means that the polygon's aspect ratio is supposed to be near 1. The aspect ration of a convex polygon denotes the ratio of the diameters of the smallest circumscribing circle to the largest inscribed disk. This problem has been solved for the equilateral triangle as well as for regular k-gon with k > 4. In the case of a square, the optimal solution is still an open problem. We are planning to find a solution which is ldquogood enoughrdquo with the help of evolutionary algorithms.