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.

This paper introduces a novel optimization framework for Network Functions Virtualization (NFV) that addresses the efficient implementation of end-to-end service requests in physical networks. Our approach characterizes each server node by a reliability function reflecting its computational load, which aids in balancing workloads and mitigating congestion. By optimizing the reliability metric along the route, our approach ensures robust end-to-end service quality. We formulate the NFV deployment problem as a non-convex mixed-integer non-linear programming (MINLP) model aimed at minimizing both deployment and operational costs while maximizing resource utilization, addressing also per-node installation conflicts and inter-VNF incompatibilies. Given the NP-hard nature of the problem, we develop efficient linearization techniques and bounding schemes, using also dynamic programming, to convert the formulation into a tractable mixed-integer linear programming (MILP) model. Additionally, a cutting-plane-based heuristic with a warm-start strategy is proposed to further accelerate convergence. Experimental evaluations on real-world network topologies demonstrate that our framework offers scalable and cost-effective solutions compared to existing approaches.

This paper introduces a novel optimization framework for Network Functions Virtualization (NFV) that addresses the efficient implementation of end-to-end service requests in physical networks. Our approach characterizes each server node by a reliability function reflecting its computational load, which aids in balancing workloads and mitigating congestion. By optimizing the reliability metrics along the route, our approach ensures robust end-to-end service quality. We formulate the NFV deployment problem as a non-convex mixed-integer non-linear programming (MINLP) model aimed at minimizing both deployment and operational costs while maximizing resource utilization. Given the NP-hard nature of the problem, we develop efficient linearization techniques and bounding schemes, using also dynamic programming, to convert the formulation into a tractable mixed-integer linear programming (MILP) model. Additionally, a cutting-plane-based heuristic with a warm-start strategy is proposed to further accelerate convergence. Experimental evaluations on real-world network topologies demonstrate that our framework offers scalable and cost-effective solutions compared to existing approaches.

The Quadratic Assignment Problem (QAP) is one of the classical N P-hard tasks from operations research with a history of more than 65 years. It is often approached with heuristic algorithms and over the years, a multitude of such methods has been applied. All of them have in common that they tend to prefer better solutions over worse ones. We approach the QAP with Frequency Fitness Assignment (FFA), an algorithm module that can be plugged into arbitrary iterative heuristics and that removes this bias. One would expect that a heuristic that does not care whether a new solution is better or worse compared to the current one should not perform very well. We plug FFA into a simple randomized local search (RLS) and yield the FRLS, which surprisingly outperforms RLS on the vast majority of the instances of the well-known QAPLIB benchmark set.

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.

The classical compact double-round robin traveling tournament problem (TTP) asks us to schedule the games of n teams in a tournament such that each team plays against every other team twice, once at home and once away (doubleRoundRobin constraint). The maxStreak constraint prevents teams from having more than three consecutive home or away games. The noRepeat constraint demands that, before two teams can play against each other the second time, they must at least play one other game in between. The goal is to find a game plan observing all of these constraints and having the overall shortest travel length. We define a gamepermutation based encoding that allows for representing game plans with arbitrary numbers of constraint violations and tackle the TTP as a bi-objective problem minimizing both the number of constraint violations and the travel length by applying the well-known NSGA-II. We combine both objectives in a lexicographic prioritization scheme and also apply the randomized local search RLS to this single-objective variant of the problem. We realize that Frequency Fitness Assignment (FFA), which makes algorithms invariant under all injective transformations of the objective function value, would also make optimization algorithms invariant under all lexicographic prioritization schemes for multi-objective problems. The FRLS, i.e., the RLS with FFA plugged in, would therefore solve both possible prioritizations of our TTP variants at once. We thus also explore its performance on the TTP. We find that RLS performs surprisingly well and can find game plans without constraint violations reliably until a scale of 36 teams, whereas FRLS and NSGA-II have an advantage on small- and mid-scale problems.

We consider a two-dimensional orthogonal bin packing problem (2BP) where rectangular items are to be placed into rectangular bins such that their edges are parallel to those of the bins with the aim to require as few bins as possible. Two variants of the problem are analyzed. In the 2BP|O|F, the items have a fixed orientation while in the 2BP|R|F, they can be rotated by 90 degrees. We show that on both variants, a simple randomized local search (RLS) has surprisingly good performance – if the objective function guiding the search is defined suitably. In particular, on the 2BP|O|F, the RLS performs on par with more complicated state-of-the-art metaheuristics. We furthermore investigate plugging Frequency Fitness Assignment (FFA) into the RLS, obtaining the FRLS. FFA has improved the RLS performance on several classical N P-hard optimization problems from operations research, including Max-SAT, the Job Shop Scheduling Problem, and the Traveling Salesperson Problem. This paper is the first negative result for FFA: it cannot improve algorithm performance on the 2BP variants studied. This can be explained by the fact that RLS already performs very well on the instances of the 2DPackLib benchmark set used as the basis of our experiments.

Graph Convolutional Networks (GCNs) are widely used for skeleton-based action recognition and achieved remarkable performance. Due to the locality of graph convolution, GCNs can only utilize short-range node dependencies but fail to model long-range node relationships. In addition, existing graph convolution based methods normally use a uniform skeleton topology for all frames, which limits the ability of feature learning. To address these issues, we present the Graph Convolution Network with Self-Attention (SelfGCN), which consists of a mixing features across self-attention and graph convolution (MFSG) module and a temporal-specific spatial self-attention (TSSA) module. The MFSG module models local and global relationships between joints by executing graph convolution and self-attention branches in parallel. Its bi-directional interactive learning strategy utilizes complementary clues in the channel dimensions and the spatial dimensions across both of these branches. The TSSA module uses self-attention to learn the spatial relationships between joints of each frame in a skeleton sequence. It also models the unique spatial features of the single frames. We conduct extensive experiments on three popular benchmark datasets, NTU RGB+D, NTU RGB+D120, and Northwestern-UCLA. The results of the experiment demonstrate that our method achieves or exceeds the record accuracies on all three benchmarks. Our project website is available at https://github.com/SunPengP/SelfGCN.

A fitness assignment process transforms the features (such as the objective value) of a candidate solution to a scalar fitness, which then is the basis for selection. Under frequency fitness assignment (FFA), the fitness corresponding to an objective value is its encounter frequency in selection steps and is subject to minimization. FFA creates algorithms that are not biased toward better solutions and are invariant under all injective transformations of the objective function value. We investigate the impact of FFA on the performance of two theory inspired, state-of-the-art evolutionary algorithms, the Greedy (2+1) GA and the self-adjusting$(1+(\lambda,\lambda))$GA. FFA improves their performance significantly on some problems that are hard for them. In our experiments, one FFA-based algorithm exhibited mean runtimes that appear to be polynomial on the theory-based benchmark problems in our study, including traps, jumps, and plateaus. We propose two hybrid approaches that use both direct and FFA-based optimization and find that they perform well. All FFA-based algorithms also perform better on satisfiability problems than any of the pure algorithm variants.

There is a high danger of accidents in chemical manufacturing plants. A devise that could automatically detect safety signs in the vicinity of a person could issue verbal warnings in order to reduce this risk. The most important task here is to correctly identify such signs from images. While there have been many achievements in the field of traffic sign detection, there is only very little research on detecting safety signs. In this work, we first provide an open and comprehensive benchmark dataset with 4650 images (expanded to 27900 images) of 30 chemical safety signs, each with a class label and bounding box and annotated with other image features. We then conduct a comprehensive analysis comparing the performance of the state-of-the-art deep learning models Faster R-CNN, SSD, YOLOv3-spp, and YOLOv5 on this dataset. In our study, YOLOv5 performs the best. It has the best mean average precision (98.9%), the best average recall (96.9%), and can process the highest number of images per second (71) on our hardware. It is already close to be sufficient for real-world application, but, like all investigated methods, suffers when detecting many signs at once, small signs, or signs in front of complex backgrounds. Our study closes an important gap in research and lays the foundation for solid future work in the domain of sign detection for improving worker safety.

Under frequency fitness assignment (FFA), the fitness corresponding to an objective value is its encounter frequency in fitness assignment steps and is subject to minimization. FFA renders optimization processes invariant under bijective transformations of the objective function value. On TwoMax, Jump, and Trap functions of dimension s, the classical (1 + 1)-EA with standard mutation at rate 1/s can have expected runtimes exponential in s. In our experiments, a (1 + 1)-FEA, the same algorithm but using FFA, exhibits mean runtimes that seem to scale as s2ln s. Since Jump and Trap are bijective transformations of OneMax, it behaves identical on all three. On OneMax, LeadingOnes, and Plateau problems, it seems to be slower than the (1 + 1)-EA by a factor linear in s. The (1 + 1)-FEA performs much better than the (1 + 1)-EA on W-Model and MaxSat instances. We further verify the bijection invariance by applying the Md5 checksum computation as transformation to some of the above problems and yield the same behaviors. Finally, we show that FFA can improve the performance of a memetic algorithm for job shop scheduling.

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.

Two factors that have a major impact on the performance of an optimization method are (1) formal algorithm specifications and (2) practical implementations. The impact of the latter is typically ignored, although it defines the results measured in experiments. We present an in-depth study of algorithm implementation issues and ask questions such as Does optimizing the implementation of an optimization algorithm pay off? Do bugs matter? and Is using more complicated but also more efficient data structures worth the effort? The intuitive answer to all of these questions is yes, but there is little published evidence. To bridge this gap, we use one of the most studied combinatorial optimization problems – the Traveling Salesman Problem – as a test bed and implement two state-of-the-art approaches for solving it – the Lin-Kernighan Heuristic and an Ejection Chain Method. We investigate implementation effort and performance gain, in order to provide further insights to the above questions.

The Traveling Salesman Problem (TSP) is one of the most well-known optimization problems. Ejection Chain Methods (ECM) and the Lin-Kernighan (LK) heuristic are the state-of-art local search (LS) algorithms for solving the TSP. Multi-Neighborhood Search (MNS) is known to be especially suitable for hybridization with Evolutionary Computation (EC). Hybridizing two different LS algorithms with each other (LS-LS) can combine their mutual advantages and lead to better performance. We introduce the new concept of LS-LS-X hybrids, which combines two different LS algorithms with a crossover operator. We enhance the two best LS-LS hybrids, ECM-LK and LK-MNS, with Order Based Crossover and Heuristic Crossover. We hybridize these LS-LS-X algorithms with an Evolutionary Algorithm, the most prominent EC method, and obtain highly-efficient (memetic) EC-LS-LS-X algorithms. We conduct a large-scale experimental study with many different algorithm setups on all 110 symmetric instances of the TSPLib benchmark set. We find that the LS-LS-X hybrids have significantly better performance than the original LS-LS and their component algorithms. They even outperform several memetic EC-LS-LS and EC-LS algorithm setups. The EC-LS-LS-X hybrids are the best hybrid EA-based TSP solvers by a large margin in our experiment and the wide range of algorithms available in the popular TSP Suite.

The Set Covering Problem (SCP) is NP-hard and has many applications. In this paper, we introduce a heuristic algorithm for SCPs based on weighting. In our algorithm, a local search framework is proposed to perturb the candidate solution under the best objective value found during the search, a weighting scheme and several search strategies are adopted to help escape from local optima and make the search more divergent. The effectiveness of our algorithm is evaluated on a set of instances from the OR-Library and Steiner triple systems. The experimental results show that it is very competitive, for it is able to find all the optima or best known results with very small runtimes on non-unicost instances from the OR-Library and outperforms two excellent solvers we have found in literature on the unicost instances from Steiner triple systems. Furthermore, it is conceptually simple and only needs one parameter to indicate the stopping criterion.

The synthesis of exact integer algorithms is a hard task for Genetic Programming (GP), as it exhibits epistasis and deceptiveness. Most existing studies in this domain only target few and simple problems or test a small set of different representations. In this paper, we present the (to the best of our knowledge) largest study on this domain to date. We first propose a novel benchmark suite of 20 non-trivial problems with a variety of different features. We then test two approaches to reduce the impact of the negative features: (a) a new nested form of Transactional Memory (TM) to reduce epistatic effects by allowing instructions in the program code to be permutated with less impact on the program behavior and (b) our recently published Frequency Fitness Assignment method (FFA) to reduce the chance of premature convergence on deceptive problems. In a full-factorial experiment with six different loop instructions, TM, and FFA, we find that GP is able to solve all benchmark problems, although not all of them with a high success rate. Several interesting algorithms are discovered. FFA has a tremendous positive impact while TM turns out not to be useful.

In this article, we propose the Fitness Level based Adaptive Operator Selection (FLAOS). In FLAOS, the discovered objective values are divided into intervals, the fitness levels. A probability distribution corresponding to a fitness level describes the selection probabilities of a set of operators. An evolutionary algorithm with FLAOS is suggested to solve one-dimensional cutting stock problems (CSPs) with contiguity. These problems are bi-objective and the goals are to minimize the trim loss and to minimize the number of partially finished items. Experimental studies have been carried out to test the effectiveness of the FLAOS. The solutions found by FLAOS are better than or comparable to those solutions found by previous methods.

Metaheuristic optimization procedures such as evolutionary algorithms are usually driven by an objective function that rates the quality of a candidate solution. However, it is not clear in practice whether an objective function adequately rewards intermediate solutions on the path to the global optimum and it may exhibit deceptiveness, epistasis, neutrality, ruggedness, and a lack of causality. In this paper, we introduce the frequency fitness H, subject to minimization, which rates how often solutions with the same objective value have been discovered so far. The ideas behind this method are that good solutions are difficult to find and that if an algorithm gets stuck at a local optimum, the frequency of the objective values of the surrounding solutions will increase over time, which will eventually allow it to leave that region again. We substitute a frequency fitness assignment process (FFA) for the objective function into several different optimization algorithms. We conduct a comprehensive set of experiments: the synthesis of algorithms with genetic programming (GP), the solution of MAX-3SAT problems with genetic algorithms, classification with Memetic Genetic Programming, and numerical optimization with a$(1+1)$Evolution Strategy, to verify the utility of FFA. Given that they have no access to the original objective function at all, it is surprising that for some problems (e.g., the algorithm synthesis task) the FFA-based algorithm variants perform significantly better. However, this cannot be guaranteed for all tested problems. Thus, we also analyze scenarios where algorithms using FFA do not perform better or perform even worse than with the original objective functions.

The defect-tolerant logic mapping (DTLM), which has been proved to be an NP-complete combinatorial search problem, is a key step for logic implementation in emerging crossbar-based nano-architectures. However, no practically satisfactory solution has been suggested for the DTLM until now. In this paper, the problem of DTLM is first modeled as a combinatorial optimization problem through the introduction of maximum-bipartite-matching. Then, a new memetic algorithm with fitness approximation (MA/FA) is proposed to solve the optimization problem efficiently. In MA/FA, a new greedy reassignment local search operator, capable of utilizing the domain knowledge and information from problem instances, is designed to help the algorithm find optimal logic mapping with consumption of relatively lower computational resources. A fitness approximation method is adopted to reduce the time consumption of fitness evaluation dramatically. In addition, a hybrid fitness evaluation strategy that combines the exact and approximated fitness evaluation methods is presented to balance the accuracy and time efficiency of fitness evaluation. The effectiveness and efficiency of the proposed methods are testified and evaluated on a large set of benchmark instances of various scales, and the advantage of MA/FA on keeping good balance between effectiveness and efficiency is also observed.

XCS - the extended Classifier System - combines an evolutionary algorithm with reinforcement learning to evolve a population of condition-action rules (classifiers). Typically, population-based approaches are slow and increasing the problem size (in terms of the number of features/samples) poses a real threat to the suitability of XCS for real-world applications. Thus, reducing the execution time without losing accuracy is highly desirable. Profiling of the execution of off-the-shelf XCS implementations suggests that the rule matching process is the most computational demanding step. A solution to this is parallelization, i.e., using parallel processing techniques to speed up the matching process (and thus the entire XCS learning process). There are many ways to achieve that, using Graphic Processing Units (GPUs) is one option. Originally, GPUs were designed to conduct a sequence of graphics operations in a massively parallel fashion. Today, GPUs can be used for all sorts of general purpose calculations that are normally handled by the CPU. In this paper, we propose a hybrid rule matching process using both CPU and GPU simultaneously for a maximum performance gain. Our experimental results indicate that this approach does speed up the XCS learning process, and that the GPU is the dominant powerful computing resource in the model.

A developmental, ontogenic approach to Capacitated Arc Routing Problems (CARPs) is introduced. The genotypes of this method are constructive heuristics specified as trees of mathematical functions which are evolved with Genetic Programming (GP). In a genotype-phenotype mapping, they guide a virtual vehicle which starts at the depot. The genotype is used to compute a heuristic value for each edge with unsatisfied demands. Local information such as the visiting costs from the current position, the remaining load of the vehicle, and the edge demands are available to the heuristic. The virtual vehicle then serves the edge with the lowest heuristic value and is located at its end. This process is repeated until all requirements have been satisfied. The resulting phenotypes are sets of tours which, in turn, are sequences of edges. We show that our method has three advantages: 1) The genotypes can be reused to seed the population in new GP runs. 2) The size of the genotypes is independent from the problem scale. 3) The evolved heuristics even work well in modified or dynamic scenarios and are robust in the presence of noise.

This paper presents a comparative study of two indirect solution representations, a generative and an ontogenic one, on a set of well-known 2D truss design problems. The generative representation encodes the parameters of a trusses design as a mapping from a 2D space. The ontogenic representation encodes truss design parameters as a local truss transformation iterated several times, starting from a trivial initial truss. Both representations are tested with a naive evolution strategy based optimization scheme, as well as the state of the art HyperNEAT approach. We focus both on the best objective value obtained and the computational cost to reach a given level of optimality. The study shows that the two solution representations behave very differently. For experimental settings with equal complexity, with the same optimization scheme and settings, the generative representation provides results which are far from optimal, whereas the ontogenic representation delivers near-optimal solutions. The ontogenic representation is also much less computationally expensive than a direct representation until very close to the global optimum. The study questions the scalability of the generative representations, while the results for the ontogenic representation display much better scalability.

In this paper, we evaluate the applicability of genetic programming (GP) for the evolution of distributed algorithms. We carry out a large-scale experimental study in which we tackle three well-known problems from distributed computing with six different program representations. For this purpose, we first define a simulation environment in which phenomena such as asynchronous computation at changing speed and messages taking over each other, i.e., out-of-order message delivery, occur with high probability. Second, we define extensions and adaptations of established GP approaches (such as tree-based and linear GP) in order to make them suitable for representing distributed algorithms. Third, we introduce novel rule-based GP methods designed especially with the characteristic difficulties of evolving algorithms (such as epistasis) in mind. Based on our extensive experimental study of these approaches, we conclude that GP is indeed a viable method for evolving non-trivial, deterministic, non-approximative distributed algorithms. Furthermore, one of the two rule-based approaches is shown to exhibit superior performance in most of the tasks and thus can be considered as an interesting idea also for other problem domains.

Genetic programming (GP) is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. In most cases it is a hardwired module of a design framework assisting the engineer in optimizing specific aspects in system development. In this article, we show how the utility of GP can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our GP framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools, which in turn offer code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how GP can be combined with model-driven development (MDD).

The fitness landscape of a problem is the relation between the solution candidates and their reproduction probability. In order to understand optimization problems, it is essential to also understand the features of fitness landscapes and their interaction. In this paper we introduce a model problem that allows us to investigate many characteristics of fitness landscapes. Specifically noise, affinity for overfitting, neutrality, epistasis, multi-objectivity, and ruggedness can be independently added, removed, and fine-tuned. With this model, we contribute a useful tool for assessing optimization algorithms and parameter settings.

Semantic web service composition is about finding services from a repository that are able to accomplish a specified task if executed. The task is defined in a form of a composition request which contains a set of available input parameters and a set of wanted output parameters. Instead of the parameter values, concepts from an ontology describing their semantics are passed to the composition engine. The parameters of the services in the repository the composer works on are semantically annotated in the same way as the parameters in the request. The composer then finds a sequence of services, called a composition. If the input parameters given in the request are provided, the services of this sequence can subsequently be executed and will finally produce the wanted output parameters. In this paper, three different approaches to semantic web service composition are formally defined and compared with each other: an uninformed search in form of an IDDFS algorithm, a greedy informed search based on heuristic functions, and a multi- objective genetic algorithm.

Genetic programming is known to provide good solutions for many problems like the evolution of network protocols and distributed algorithms. Then, it is most likely a hardwired module of a design framework where it assists the engineer in optimizing specific aspects in system development. In this paper we show how the utility of genetic programming can be increased remarkably by isolating it as a component and integrating it into the model-driven software development process. Our genetic programming framework produces XMI-encoded UML models that can easily be loaded into widely available modeling tools, which in turn offer code generation as well as additional analysis and test capabilities. We use the evolution of a distributed election algorithm as an example to illustrate how genetic programming can be combined with model-driven development.