Idempotent Boolean functions form a highly structured subclass of Boolean functions that is closely related to rotation symmetry under a normal-basis representation and to invariance under a fixed linear map in a polynomial basis. These functions are attractive as candidates for cryptographic design, yet their additional algebraic constraints make the search for high nonlinearity substantially more difficult than in the unconstrained case. In this work, we investigate evolutionary methods for constructing highly nonlinear idempotent Boolean functions for dimensions n = 5 up to n = 12 using a polynomial basis representation with canonical primitive polynomials. Our results show that the problem of evolving idem-potent functions is difficult due to the disruptive nature of crossover and mutation operators. Next, we show that idempotence can be enforced by encoding the truth table on orbits, yielding a compact genome of size equal to the number of distinct squaring orbits.

Abstract In recent years, the growing interest in environmental sustainability has led to Electric Vehicle Routing Problems (EVRPs) attracting more and more attention. EVRPs involve the use of electric vehicles, which have additional constraints, such as range and recharging time, compared to conventional Vehicle Routing Problems (VRPs). The complexity and dynamic nature of solving VRPs often lead to the introduction of Routing Policies (RPs), simple heuristics that incrementally build routes. However, manually designing efficient RPs proves to be a challenging and time-consuming task. Therefore, there is a pressing need to explore the application of hyper-heuristics, in particular Genetic Programming (GP), to automatically generate new RPs. Since this method has not yet been investigated in the literature in the context of EVRPs, this study explores the applicability of GP to automatically generate new RPs for EVRP. To this end, three RP variants (serial, semiparallel, and parallel) are introduced in this study, along with a set of domain-specific terminal nodes to optimise three criteria: the number of vehicles, energy consumption, and total tardiness. The experimental analysis shows that the serial variant performs best in terms of energy consumption and number of vehicles, while the parallel variant is most effective in minimising the total tardiness. A comprehensive analysis of the proposed method is conducted to determine its convergence properties and the impact of the proposed terminal nodes on performance and to describe several generated RPs. The results show that the automatically generated RPs perform commendably compared to traditional methods such as metaheuristics and exact methods, which usually require significantly more runtime. More specifically, depending on the scenario in which they are used, the generated RPs achieve results that are about 20%-37% worse compared to the best known results for the number of vehicles in almost negligible time, in just some milliseconds.

Dynamic multi-objective (MO) scheduling problems are encountered in various real-world situations. Due to dynamic events that occur in such problems, one has to resort to using simple constructive heuristics, called dispatching rules (DRs), when tackling them. Since DRs are difficult to design manually there is a lack of existing DRs suitable for solving MO problems. Due to that reason, genetic programming has successfully been applied to evolve DRs specifically for solving MO problems. The process of evolving new DRs is computationally expensive, requiring a significant amount of time to obtain DRs of good quality. For that reason it is worth investigating inwhich ways the convergence of algorithms could be improved. One option is to use DRs previously evolved for optimising individual criteria to initialise the starting population when optimising a MO problem. The goal of this study is to investigate how such an initialisation strategy affects the performance of NSGA-II and NSGA-III when evolving DRs for MO problems. Therefore, 8 MO unrelated machines scheduling problems, containing between 2 and 5 criteria, are considered. The obtained results demonstrate that using previously evolved DRs for single objective optimisation leads to a faster convergence, and in many cases significantly better results.

Priority rules are one of the most common and popular approaches to real-time scheduling. Over the last decades, several methods have been developed to generate rules automatically. In addition, it has been shown that combining rules into ensembles is better than using a single rule in many cases. In this paper, we analyze different ways to create and use ensembles previously developed through genetic programming. In our study, we classify ensembles as either collaborative or coordinated, depending on how the rules are used. In the first case, all the rules contribute to the creation of the same solution, while in the second case, each rule works independently on its own solution, and the best of them is selected as the solution of the ensemble. We found that each method has its own strengths and weaknesses, which leads us to use them in combination. Based on this hypothesis, we developed new methods to design and combine collaborative and coordinated ensembles and evaluated these methods for the One Machine Scheduling Problem with time-varying capacity and minimization of total tardiness. The results of the experimental study provided interesting insights into the use of ensembles and showed that our proposals outperform previous methods.

Finding Boolean functions suitable for cryptographic primitives is a complex combinatorial optimization problem, since they must satisfy several properties to resist cryptanalytic attacks, and the space is very large, which grows super exponentially with the number of input variables. Recent research has focused on the study of Boolean functions that satisfy properties on restricted sets of inputs due to their importance in the development of the FLIP stream cipher. In this paper, we consider one such property, perfect balancedness, and investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy this property along with a good nonlinearity profile. We formulate the related optimization problem and define two encodings for the candidate solutions, namely the truth table and the weightwise balanced representations. Somewhat surprisingly, the results show that GA with the weightwise balanced representation outperforms GP with the classical truth table phenotype in finding highly nonlinear Weightwise Perfectly Balanced (WPB) functions. This is in stark contrast to previous findings on the evolution of balanced Boolean functions, where GP always performs best.

Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally.

Dynamic scheduling problems are important optimisation problems with many real-world applications. Since in dynamic scheduling not all information is available at the start, such problems are usually solved by dispatching rules (DRs), which create the schedule as the system executes. Recently, DRs have been successfully developed using genetic programming. However, a single DR may not efficiently solve different problem instances. Therefore, much research has focused on using DRs collaboratively by forming ensembles. In this paper, a novel ensemble collaboration method for dynamic scheduling is proposed. In this method, DRs are applied independently at each decision point to create a simulation of the schedule for all currently released jobs. Based on these simulations, it is determined which DR makes the best decision and that decision is applied. The results show that the ensembles easily outperform individual DRs for different ensemble sizes. Moreover, the results suggest that it is relatively easy to create good ensembles from a set of independently evolved DRs.

Dynamic online scheduling is a difficult problem which commonly appears in the real world. This is because the decisions have to be performed in a small amount of time using only currently available incomplete information. In such cases dispatching rules (DRs) are the most commonly used methods. Since designing them manually is a difficult task, this process has been successfully automatised by using genetic programming (GP). The quality of the evolved rules depends on the problem instances that are used during the training process. Previous studies demonstrated that careful selection of problem instances on which the solutions should be evaluated during evolution improves the performance of the generated rules. This paper examines the application of the ε-lexicase selection to the design of DRs for the unrelated machines scheduling. This selection offers a better solution diversity since the individuals are selected based on a smaller subset of instances, which leads to the creation of DRs that perform well on the selected instances. The experiments demonstrate that this type of selection can significantly improve the results for the Roulette Wheel and Elimination GP variants, while achieving the same performance as the Steady State Tournament GP. Furthermore, the ε-lexicase based algorithms have a better convergence rate, which means that the increased diversity in the population has a positive effect on the evolution process.

In the last few decades, evolutionary algorithms were successfully applied numerous times for creating Boolean functions with good cryptographic properties. Still, the applicability of such approaches was always limited as the cryptographic community knows how to construct suitable Boolean functions with deterministic algebraic constructions. Thus, evolutionary results so far helped to increase the confidence that evolutionary techniques have a role in cryptography, but at the same time, the results themselves were seldom used.

We investigate the use of Genetic Programming (GP) as a convolutional predictor for missing pixels in images. The training phase is performed by sweeping a sliding window over an image, where the pixels on the border represent the inputs of a GP tree. The output of the tree is taken as the predicted value for the central pixel. We consider two topologies for the sliding window, namely the Moore and the Von Neumann neighborhood. The best GP tree scoring the lowest prediction error over the training set is then used to predict the pixels in the test set. We experimentally assess our approach through two experiments. In the first one, we train a GP tree over a subset of 1000 complete images from the MNIST dataset. The results show that GP can learn the distribution of the pixels with respect to a simple baseline predictor, with no significant differences observed between the two neighborhoods. In the second experiment, we train a GP convolutional predictor on two degraded images, removing around 20% of their pixels. In this case, we observe that the Moore neighborhood works better, although the Von Neumann neighborhood allows for a larger training set.

Substitution boxes (S-boxes) are nonlinear mappings that represent one of the core parts of many cryptographic algorithms (ciphers). If S-box does not possess good properties, a cipher would be susceptible to attacks. To design suitable S-boxes, we can use heuristics as it allows significant freedom in the selection of required cryptographic properties. Unfortunately, with heuristics, one is seldom sure how good a trade-off between cryptographic properties is reached or if optimizing for one property optimizes implicitly for another property. In this paper, we consider what is to the best of our knowledge, the most detailed analysis of trade-offs among S-box cryptographic properties. More precisely, we ask questions if one property is optimized, what is the worst possible value for some other property, and what happens if all properties are optimized. Our results show that while it is possible to reach a large variety of possible solutions, optimizing for a certain property would commonly result in good values for other properties. In turn, this suggests that a single-objective approach should be a method of choice unless some precise values for multiple properties are needed.

Tasks related to Natural Language Processing (NLP) have recently been the focus of a large research endeavor by the machine learning community. The increased interest in this area is mainly due to the success of deep learning methods. Genetic Programming (GP), however, was not under the spotlight with respect to NLP tasks. Here, we propose a first proof-of-concept that combines GP with the well established NLP tool word2vec for the next word prediction task. The main idea is that, once words have been moved into a vector space, traditional GP operators can successfully work on vectors, thus producing meaningful words as the output. To assess the suitability of this approach, we perform an experimental evaluation on a set of existing newspaper headlines. Individuals resulting from this (pre-)training phase can be employed as the initial population in other NLP tasks, like sentence generation, which will be the focus of future investigations, possibly employing adversarial co-evolutionary approaches.

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.

Finding cryptographic primitives satisfying certain properties is a difficult problem. In this domain, besides the algebraic constructions, researchers often use heuristics. There exists a set of interesting problems related to the notion of differential uniformity for a function F:\mathbbF2n→ \mathbbF2m. When n=m, then the best obtainable differential uniformity equals 2, since it is necessarily positive and even, and since examples of differentially 2-uniform functions are known. Heuristics are able to reach such functions; there is then some intuition that heuristics can be used for other open problems related to differential uniformity. When , differential uniformity is bounded by 2n-m+2 from below (when m=n-2, by 6). Unfortunately, we know such functions only for dimensions equal to n=4,5. In this paper, we explore several evolutionary algorithms and problem sizes in order to find functions having differential uniformity equal to 6. Our results show that several solution encodings are able to find such functions but only in dimensions (4, 2) and (5, 3). Since differentially 6-uniform functions were known for those sizes before, our results can be used as a source of new functions in those dimensions and as an indicator that for (6, 4) such functions either do not exist or that it is extremely difficult to find them.

Boolean functions have a prominent role in many real-world applications, which makes them a very active research domain. Throughout the years, various heuristic techniques proved to be an attractive choice for the construction of Boolean functions with different properties. One of the most important properties is nonlinearity, and in particular maximally nonlinear Boolean functions are also called bent functions. In this paper, instead of considering Boolean functions, we experiment with quaternary functions. The corresponding problem is much more difficult and presents an interesting benchmark as well as realworld applications. The results we obtain show that evolutionary metaheuristics, especially genetic programming, succeed in finding quaternary functions with the desired properties. The obtained results in the quaternary domain can also be translated into the binary domain, in which case this approach compares favorably with the state-of-the-art in Boolean optimization. Our techniques are able to find quaternary bent functions for up to 8 inputs, which corresponds to obtaining Boolean bent functions of 16 inputs.

Boolean functions and their generalizations, vectorial Boolean functions, are extremely active areas of research. Their applications can be found in domains such as error correcting codes, communication, and cryptography. Accordingly, various methods of obtaining Boolean functions are explored where one group belongs to heuristic techniques and, more precisely, evolutionary algorithms. In this paper we explore how to evolve (vectorial) Boolean functions with specific properties by utilizing several different algorithms and encodings. As far as we are aware, we are the first to explore the topic of evolution of vectorial Boolean functions where the output dimension is strictly smaller than the input dimension. Our results show that evolutionary algorithms can represent a valuable option to produce vectorial Boolean functions where good results are obtained for various sizes. On the other hand, as the number of outputs grows, we can observe that evolutionary algorithms are still able to obtain high quality results but with increasing difficulty.

We investigate the design of Orthogonal Latin Squares (OLS) by means of Genetic Algorithms (GA) and Genetic Programming (GP). Since we focus on Latin squares generated by Cellular Automata (CA), the problem can be reduced to the search of pairs of Boolean functions that give rise to OLS when used as CA local rules. As it is already known how to design CA-based OLS with linear Boolean functions, we adopt the evolutionary approach to address the nonlinear case, experimenting with different encodings for the candidate solutions. In particular, for GA we consider single bitstring, double bitstring and quaternary string encodings, while for GP we adopt a double tree representation. We test the two metaheuristics on the spaces of local rules pairs with n = 7 and n = 8 variables, using two fitness functions. The results show that GP is always able to generate OLS, even if the optimal solutions found with the first fitness function are mostly linear. On the other hand, GA achieves a remarkably lower success rate than GP in evolving OLS, but the corresponding Boolean functions are always nonlinear.

The field of side-channel analysis has made significant progress over time. Side-channel analysis is now used in practice in design companies as well as in test laboratories, and the security of products against side-channel attacks has significantly improved. However, there are still some remaining issues to be solved for side-channel analysis to become more effective. Side-channel analysis consists of two steps, commonly referred to as identification and exploitation. The identification consists of understanding the leakage and building suitable models. The exploitation consists of using the identified leakage models to extract the secret key. In scenarios where the model is poorly known, it can be approximated in a profiling phase. There, machine learning techniques are gaining value. In this paper, we conduct extensive analysis of several machine learning techniques, showing the importance of proper parameter tuning and training. In contrast to what is perceived as common knowledge in unrestricted scenarios, we show that some machine learning techniques can significantly outperform template attacks when properly used. We therefore stress that the traditional worst case security assessment of cryptographic implementations, that mainly includes template attacks, might not be accurate enough. Besides that, we present a new measure called the Data Confusion Factor that can be used to assess how well machine learning techniques will perform on a certain dataset.

The problem of obtaining maximal nonlinearity in Boolean functions is well researched, both from the cryptographic and the evolutionary computation side. However, the results are still not conclusive enough to be able to show how good a heuristic approach is when tackling this problem. In this paper, we investigate how to obtain the maximal possible nonlinearity in balanced Boolean functions, but we also analyze how difficult is the problem itself. In order to do so, we conduct experiments with Estimation of distribution algorithms as well as the fitness landscape analysis and the deception analysis. Our results indicate that the first difficulties arise from the inappropriate fitness function and representation of solutions coupled with a huge search space. The fitness landscape analysis does not reveal any significant differences that could justify the assumed jump in problem difficulty when going from Boolean functions with 6 inputs to those with 8 inputs. Finally, we show that this problem is not order-1 deceptive.

The evolution of Boolean functions that can be used in cryptography is a topic well studied in the last decades. Previous research, however, has focused on evolving Boolean functions directly, and not on general methods that are capable of generating the desired functions. The former approach has the advantage of being able to produce a large number of functions in a relatively short time, but it directly depends on the size of the search space. In this paper, we present a method to evolve algebraic constructions for generation of bent Boolean functions. To strengthen our approach, we define three types of constructions and give experimental results for them. Our results show that this approach is able to produce a large number of constructions, which could in turn enable the construction of many more Boolean functions with a larger number of variables.

The role of Boolean functions is prominent in several areas including cryptography, sequences, and coding theory. Therefore, various methods for the construction of Boolean functions with desired properties are of direct interest. New motivations on the role of Boolean functions in cryptography with attendant new properties have emerged over the years. There are still many combinations of design criteria left unexplored and in this matter evolutionary computation can play a distinct role. This article concentrates on two scenarios for the use of Boolean functions in cryptography. The first uses Boolean functions as the source of the nonlinearity in filter and combiner generators. Although relatively well explored using evolutionary algorithms, it still presents an interesting goal in terms of the practical sizes of Boolean functions. The second scenario appeared rather recently where the objective is to find Boolean functions that have various orders of the correlation immunity and minimal Hamming weight. In both these scenarios we see that evolutionary algorithms are able to find high-quality solutions where genetic programming performs the best.

In data mining, decision tree algorithms are very popular methodologies since the algorithms have a simple inference mechanism and provide a comprehensible way to represent the model in the form of a decision tree. Over the past years, fuzzy decision tree algorithms have been proposed in order to provide a way to handle uncertainty in the data collected. Fuzzy decision tree algorithms have shown to outperform classical decision tree algorithms. This paper investigates a fuzzy decision tree algorithm applied to the classification of gene expression data. The fuzzy decision tree algorithm is compared to a classical decision tree algorithm as well as other well-known data mining algorithms commonly applied to classification tasks. Based on the five data sets analyzed, the fuzzy decision tree algorithm outperforms the classical decision tree algorithm. However, compared to other commonly used classification algorithms, both decision tree algorithms are competitive, although both do not reach the accuracy values of the best performing classifier.

Boolean functions are essential in many stream ciphers. When used in combiner generators, they need to have sufficiently high values of correlation immunity, alongside other properties. In addition, correlation immune functions with small Hamming weight reduce the cost of masking countermeasures against side-channel attacks. Various papers have examined the applicability of evolutionary algorithms for evolving cryptographic Boolean functions. However, even when authors considered correlation immunity, it was not given the highest priority. Here, we examine the effectiveness of three different EAs, namely, Genetic Algorithms, Genetic Programming (GP) and Cartesian GP for evolving correlation immune Boolean functions. Besides the properties of balancedness and correlation immunity, we consider several other relevant cryptographic properties while maintaining the optimal trade-offs among them. We show that evolving correlation immune Boolean functions is an even harder objective than maximizing nonlinearity.

Most of today's computer systems, including rapidly emerging embedded ones, rely on an operating system.Consequently, the development of embedded systems and related software often requires a deeper understanding of operating systems.This paper presents a new incrementally built operating system and a learning course formed around it.Each increment builds on the previous one and introduces new system elements, new concepts and solutions, and a new set of assignments for improving or extending operations or simply demonstrating its use.Increments and assignments are designed to extend theoretical and practical knowledge in the operating system domain, give experience with non-trivial software systems and their development tools, familiarize the learner with basic computer hardware components and demonstrate device driver construction.The audience targeted by this operating system and course materials includes advanced students with (basic) knowledge of computer architecture, programming and operating systems.In addition, materials may be used individually as part of a lifelong learning process.

Genetic algorithms are applied to numerous problems that demonstrate different properties. To efficiently solve these problems, during the years a significant number of variation operators have been and still are created. It is a problem by itself how to correctly choose between those operators, i.e. how to find the most suitable operator (or a set) for a given problem. In this paper we investigate the choice of the suitable crossover operator on the basis of fitness landscape. The fitness landscape can be described with a number of properties, so a thorough analysis needs to be done to find the most useful ones. To achieve that, we experiment with 24 noise-free problems and floating point encoding. The results indicate it is possible to either select a suitable operator or at least to reduce the number of adequate operators with fitness landscape properties.

Crossover is the most important operator in real-coded genetic algorithms. However, the choice of the best operator for a specific problem can be a difficult task. In this paper we compare 16 crossover operators on a set of 24 benchmark functions. A detailed statistical analysis is performed in an effort to find the best performing operators. The results show that there are significant differences in efficiency of different crossover operators, and that the efficiency may also depend on the distinctive properties of the fitness function. Additionally, the results point out that the combination of crossover operators yields the best results.

In the context of communication services, presence is defined as the willingness and ability of a user to communicate across a set of devices with other users, and thus an up-to-date user presence status represents an essential prerequisite for real-time communications. Smartphones are a rich source of presence-related contex information, however; this information is currently not applied by the prevailing over-the-top communication systems to implicitly change user presence status in accordance with his/her context and typical daily behavior. Smartphone battery limitations and the abundance of context data generated from built-in sensors and mobile applications are the major factors limiting the adoption of rich presence solutions in state-of-the-art communication solutions. This paper presents an approach to learning and inferring user presence status on smartphones using the available context data with a goal to enable non intrusive and energy-efficient maintenance of presence status without user intervention. We apply the Mobile Data Challenge (MDC) data set collected during the Lausanne Data Collection Campaign from October 2009 until March 2011 in our evaluations.

This paper investigates the influence of different crossover operators on the efficiency of the hybrid Taguchi genetic algorithm and aims to provide guidelines for algorithm's usage in continuous optimization. We examine the hybrid Taguchi genetic algorithm (HTGA) with 8 different crossover operators and apply it to 15 benchmark numerical optimization problems. The implementation uses binary representation which maps chromosomes to values in real domain with arbitrary precision. Different crossover operators are used with the HTGA and a detailed statistical analysis is performed to evaluate their performance. The results indicate that the HTGA obtains better results with crossover operators different than the ones commonly reported in literature.