Surrogates provide a cheap solution evaluation and offer significant leverage for optimizing computationally expensive problems. Usually, surrogates only approximate the original function. Recently, the perfect linear surrogates were proposed that ideally represent the original function. These surrogates do not mimic the original function. In fact, they are another (correct) representation of it and enable a wide range of possibilities, e.g., discovering the optimized function for problems where the direct transformation of the encoded solution into its evaluation is not available. However, many real-world problems can not be represented by linear models, making the aforementioned surrogates inapplicable. Therefore, we propose the Limited Monotonical Perfect Surrogate (LyMPuS), which overcomes this difficulty and enables the comparison of two solutions that differ by a single variable. Our proposition is suitable for limiting the cost of expensive local search procedures. The proposed surrogate is parameterless and can be trained on the fly without any separate surrogate-building step. It uses only the necessary fitness evaluations, and the already-paid costs are not wasted when the model is updated. Finally, it offers low-cost missing-linkage detection and low-cost linkage discovery, guaranteed to find a missing dependency in no more than $2\lceil\log_2(n)\rceil$ steps.

In optimization problems, some variable subsets may have a joint non-linear or non-monotonical influence on the function value. Therefore, knowledge of variable dependencies may be crucial for effective optimization, and many state-of-the-art optimizers leverage it to improve performance. However, some real-world problem instances may be the subject of noise of various origins. In such a case, variable dependencies relevant to optimization may be hard or impossible to tell using dependency checks sufficient for problems without noise, making highly effective operators, e.g., Partition Crossover (PX), useless. Therefore, we use Statistical Linkage Learning (SLL) to decompose problems with noise and propose a new SLL-dedicated mask construction algorithm. We prove that if the quality of the SLL-based decomposition is sufficiently high, the proposed clustering algorithm yields masks equivalent to PX masks for the noise-free instances. The experiments show that the optimizer using the proposed mechanisms remains equally effective despite the noise level and outperforms state-of-the-art optimizers for the problems with high noise.

Benchmarks are essential tools for the optimizer's development. Using them, we can check for what kind of problems a given optimizer is effective or not. Since the objective of the Evolutionary Computation field is to support the tools to solve hard, real-world problems, the benchmarks that resemble their features seem particularly valuable. Therefore, we propose a hop-based analysis of the optimization process. We apply this analysis to the NP-hard, large-scale real-world problem. Its results indicate the existence of some of the features of the well-known Leading Ones Problem. To model these features well, we propose the Leading Blocks Problem (LBP), which is more general than Leading Ones and some of the benchmarks inspired by this problem. LBP allows of the assembly of new types of hard optimization problems that are not handled well by the considered state-of-the-art Genetic Algorithm (GA). Finally, the experiments reveal what kind of mechanisms must be proposed to improve GAs' effectiveness while solving LBP and the considered real-world problem.

Many state-of-the-art Genetic Algorithms (GAs) use information about variable dependencies to construct masks for variation operators and, in turn, improve their effectiveness and efficiency. In the black-box setting, the dependency structure model is not known and must be discovered as a part of the optimization process. The precision of this model may be decisive for the effectiveness of the GAs using it. This work considers the recently identified multi-structured problems that arise when two or more problems with a different structure (i.e., different variable dependencies) are combined in a non-linear manner. Such problems are hard to solve because, usually, it is not enough to know all the dependencies to solve them effectively. To do so, one must know which dependencies are a part of which substructure, i.e., the dependencies between dependencies. Finally, an optimizer must detect which substructure is valid for the solution at hand. Statistical Linkage Learning (SLL) was proposed to decompose multi-structure problems. However, SLL may report false dependencies, which can deteriorate the search. Therefore, we propose the Conditional Direct Empirical Linkage Discovery (cDLED) technique to decompose multi-structured problems. cDLED guarantees to report only true dependencies. Using cDLED, we propose detecting which problem substructure refers to the given solution. Using these two mechanisms, we propose an optimizer that is highly competitive with other state-of-the-art GAs. We consider single-objective optimization, but our propositions can also be useful in multi- and many-objective optimization. Additionally, we propose a more general formal representation of multi-structured problems.

In complex problems, variable subsets may have a joint non-monotonical influence on function value. Therefore, variation operators in many single-objective (SO) state-of-the-art optimizers leverage such dependent variable sets to improve effectiveness and efficiency. In multi-objective optimization (MO), we optimize multiple objective functions and each may have different dependencies. Thus, choosing relevant dependencies to improve a solution is challenging in MO. To overcome this difficulty, we can transform the MO problem into a set of SO problems (that may be infinite) and discover the dependencies for each SO problem separately. However, dependency discovery is expensive, even for a single problem. Performing it for each SO problem separately seems unacceptable. Moreover, the dependencies of the scalarized problem are neither necessarily a subset nor a superset of the dependencies of all objective functions, making choosing appropriate dependencies impossible. Two variables dependent in all objective functions can be independent in their scalarization, and two variables independent in all objective functions can be dependent in their scalarization. Therefore, we propose the bi-objective non-monotonicity check (BONM). BONM is a linkage learning technique that uses only a single check to discover weight vector ranges for which a given variable pair is dependent concerning the non-monotonicity check. Limiting our proposition only to scalarization using weight vectors may deteriorate its applicability for the MO problems with concave Pareto fronts. Nevertheless, it enables using gray-box-dedicated operators in the black-box setting for MO problems. Finally, the proposed parameter-less optimizer that employs BONM significantly outperforms the competing state-of-the-art MO optimizers.

The knowledge about variable interactions is frequently employed in state-of-the-art research concerning genetic algorithms (GAs). Whether these interactions are known a priori (gray-box optimization) or are discovered by the optimizer (black-box optimization), they are used for many purposes, including proposing more effective mixing operators. Frequently, the quality of the problem structure decomposition is decisive to the optimizers’ effectiveness. However, in gray- and black-box optimization, the dependency between the variables is assumed to be symmetric. This work identifies and defines the nonsymmetrical (directional) variable dependencies. We show that these dependencies may exist (together with symmetrical) in the considered real-world problem, in which we must optimize subsequent variable groups (one after the other) in the appropriate optimization order that is not known by the optimizer. To improve GA’s effectiveness in solving the problem of such features, we propose a new linkage learning (LL) technique that can discover symmetrical and nonsymmetrical dependencies (in binary and nonbinary discrete domains) and distinguish them from each other. We show that telling these two types of dependencies from each other may significantly increase the optimizer’s effectiveness in solving real-world and theoretical problems with nonsymmetrical dependencies. Finally, we show that using the proposed LL technique does not deteriorate the effectiveness of the state-of-the-art optimizer in solving typical benchmarks containing only symmetrical dependencies.

One of the main approaches for solving Large-Scale Global Optimization (LSGO) problems is embedding a decomposition strategy into a Cooperative Co-Evolution (CC) framework. Decomposing an LSGO problem into smaller subproblems and optimizing them separately using a CC framework was shown to be effective when a considered problem is partially separable. Components in CC frameworks are usually disjoint. Thus, the existence of the perfect decomposition of such problems allows of the optimization of independent components. However, for overlapping problems, the perfect, unique decomposition does not exist due to the existence of shared variables. Despite this, each variable is usually assigned to a single component, and the assignment does not change during a whole framework run. In this paper, we propose a new CC framework that allows multiple assignments of shared variables. Allocating computational resources to each of its components is influenced by other components that share variables with it. According to experimental results, our proposed method outperforms the state-of-the-art LSGO-dedicated optimization methods, including other CC frameworks, when overlapping LSGO problems are considered.

Optimal Mixing (OM) is a mating operator employed by many state-of-the-art Genetic Algorithms (GAs). This paper identifies the sliding phenomenon defined as a serie of the so-called plateau moves. Sliding is a part of the original OM proposition. Although sliding seems to be a minor element of OM, we show that performing or avoiding it may significantly affect the effectiveness of OM-employing GAs. Therefore, we analyze the details of sliding pros and cons and propose the Autonomous Slide Deciding Algorithm (ASDA). ASDA analyzes the diversity of the population for a given subset of genes. Then, it decides, for a given mixing operation, sliding will be profitable or not. We show that using ASDA is greedily beneficial for two different state-of-the-art GAs. Additionally, we explain why ASDA deteriorates the effectiveness of the third considered OM-using GA.

Gray-box optimization requires user-supported information about inter-variable dependencies to propose more effective optimizers for hard combinatorial problems. In Black-box optimization, such information is unavailable. Therefore, the Gray-box operators are only usable in Black-box scenarios if an optimizer can discover the inter-variable dependencies independently. Empirical Linkage Learning (ELL) techniques are guaranteed to discover only the true dependencies, which led to proposing the Dark Gray-box optimizers class. Such optimizers use ELL to construct Empirical Variable Interaction Graph (eVIG), which may miss some dependencies but contains only the true ones. eVIG allows using Gray-box operators in Black-box scenarios. ELL techniques are computationally expensive. Therefore, the recently proposed Local Search with Linkage Learning (LSwLL) is promising because it makes ELL a no-cost technique. However, LSwLL has some disadvantages. First, it can decompose only the problems of additive nature. Second, LSwLL removes ELL costs, but in some optimization scenarios, it may be expensive itself. Therefore, we propose the First Improvement Hill Climber with Linkage Learning (FIHCwLL). FIHCwLL decomposes additive and non-additive problems, and its overall costs are frequently lower than LSwLL (although ELL is not no-cost anymore). We introduce FIHCwLL into two state-of-the-art model-building optimizers, creating two new Dark Gray-box optimizers of significantly improved effectiveness.

Real-world optimization problems may have a different underlying structure. In black-box optimization, the dependencies between decision variables remain unknown. However, some techniques can discover such interactions accurately. In Large Scale Global Optimization (LSGO), problems are high-dimensional. It was shown effective to decompose LSGO problems into subproblems and optimize them separately. The effectiveness of such approaches may be highly dependent on the accuracy of problem decomposition. Many state-of-the-art decomposition strategies are derived from Differential Grouping (DG). However, if a given problem consists of non-additively separable subproblems, DG-based strategies may discover many non-existing interactions. On the other hand, monotonicity checking strategies proposed so far do not report non-existing interactions for any separable subproblems but may miss discovering many of the existing ones. Therefore, we propose Incremental Recursive Ranking Grouping (IRRG) that suffers from none of these flaws. IRRG consumes more fitness function evaluations than the recent DG-based propositions, e.g., Recursive DG 3 (RDG3). Nevertheless, the effectiveness of the considered Cooperative Co-evolution frameworks after embedding IRRG or RDG3 was similar for problems with additively separable subproblems that are suitable for RDG3. After replacing the additive separability with non-additive, embedding IRRG leads to results of significantly higher quality.

Gray-box optimization employs the knowledge about the true direct gene dependencies represented by the Variable Interaction Graph (VIG). This knowledge is utilized in many ways, e.g., for improving the fitness computation efficiency and proposing more effective operators for Genetic Algorithms (GAs). In the Black-box optimization, the underlying problem structure is not known. Therefore, linkage learning techniques were proposed to at least approximate gene relations and improve the evolutionary search. However, since these techniques are based on predictions, they were not suitable for building VIG. The proposition of Empirical Linkage Learning (ELL) has changed the situation. In ELL, the prediction that two genes are dependent is replaced by certainty. Additionally, ELL techniques are proven never to mark two independent genes as dependent. Therefore, we use ELL to build the empirical VIG and propose the fusion of ELL and the Gray-box operators. On this base, we propose two new mechanisms that detect (with certainty) the missing linkage between two groups of genes and the fact that the population is stuck. We integrate these mechanisms with a Gray-box operator (partition crossover) in the proposed Dark Gray Genetic Algorithm that is shown highly competitive to other state-of-the-art GAs.

In the field of Evolutionary Computation, the main objective is to find a high-quality solution to the considered problem. However, the other important issue is to find a solution efficiently. Therefore, evolutionary methods use various techniques to adjust to the problem and reduce the amount of resources consumed during an optimization process. One of the well-known and relatively simple techniques is storing the already evaluated genotypes and their ratings. Whenever an evolutionary method is to evaluate the fitness for a genotype that was already rated, instead of re-evaluating it, a method may use the value that was stored in the repository. Surprisingly, despite its simplicity, such a fitness caching technique was shown to cause many important phenomena. When an evolutionary method is stuck, fitness caching may cause such significant fitness function evaluation (FFE) reduction that FFE will not be a reliable resource consumption measure anymore. Moreover, fitness caching may help in detecting the drop in the number of new solutions investigated by a method. Thus, it may help in dynamic population-size management. Such a consequence is far more sophisticated than a simple FFE reduction. Therefore, in this paper, we investigate fitness caching in more detail. We analyze its influence on chosen state-of-the-art methods employed to solve well-known theoretical problems.

Problem decomposition is an important part of many state-of-the-art Evolutionary Algorithms (EAs). The quality of the decomposition may be decisive for the EA effectiveness and efficiency. Therefore, in this paper, we focus on the recent proposition of Linkage Learning based on Local Optimization (3LO). 3LO is an empirical linkage learning (ELL) technique and is proven never to report the false linkage. False linkage is one of the possible linkage defects and occurs when linkage marks two independent genes as a dependent. Although thanks to the problem decomposition quality, the use of 3LO may lead to excellent results, its main disadvantage is its high computational cost. This disadvantage makes 3LO not applicable to state-of-the-art EAs that originally employed Statistical-based Linkage Learning (SLL) and frequently update the linkage information. Therefore, we propose the Direct Linkage Empirical Discovery technique (DLED) that preserves 3LO advantages, reduces its costs, and we prove that it is precise in recognizing the direct linkage. The concept of direct linkage, which we identify in this paper, is related to the quality of the decomposition of overlapping problems. The results show that incorporating DLED in three significantly different state-of-the-art EAs may lead to promising results.

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

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

Linkage learning techniques are a crucial part of many modern evolutionary methods dedicated to solving problems in discrete domains. Linkage information quality is decisive for the effectiveness of these methods. In this article, we point on two possible linkage inaccuracy types. The missing linkage that occurs when some gene dependencies remain undiscovered, and the false linkage that takes place when linkage identifies gene dependencies that do not exist. To the best of our knowledge, all linkage learning techniques proposed so far are based on predictions, which can commit both of the mistake types. We propose a different approach. Instead of using statistical measures, or evolving the linkage, we check which genes are dependent on one another employing disturbances and the local search. We prove that the proposed technique will never report any false linkage. Thus, the proposed linkage learning based on local optimization (3LO) may miss some linkage but will never report a false one. The main objective of this article is to show the potential brought by 3LO that is fundamentally different from other linkage learning techniques. Since the main disadvantage of the proposed technique is its computational cost, it does not seem suitable for some of the already known, effective evolutionary methods. To overcome this issue, we propose an evolutionary method that employs 3LO. The extensive experimental analysis performed on a large set of hard computational problems shows that the method using 3LO is found to be competitive with other state-of-the-art methods.

In smart factories, process planning and scheduling need to be performed every time a new manufacturing order is received or a factory state change has been detected. A new plan and schedule need to be determined quickly to increase the responsiveness of the factory and enlarge its profit. Simultaneous optimisation of manufacturing process planning and scheduling leads to better results than a traditional sequential approach but is computationally more expensive and thus difficult to be applied to real-world manufacturing scenarios. In this paper, a working approach for cloud-based distributed optimisation of process planning and scheduling is presented. It executes a multi-objective genetic algorithm on multiple subpopulations (islands). The number of islands is automatically decided based on the current optimisation state. A number of test cases based on two real-world manufacturing scenarios are used to show the applicability of the proposed solution.

The usual assumption in the Evolutionary Computation field is that a cost of computing single fitness function evaluation is at last similar for all cases.Such assumption does not have to be true.In this paper we consider the recently proposed Problem Encoding Allowing Cheap Fitness Computation of Mutated Individuals (PEACh) effect that allows to significantly reduce the computation load of some of the fitness computations that occur during the evolutionary method run.To the best of our knowledge, it is the first experimental analysis that investigates the results of PEACh application to methods solving NP-hard practical problems.