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.

Statistical Linkage Learning (SLL) is a part of many state-of-the-art optimizers. The purpose of SLL is to discover variable interdepen-dencies. It has been shown that the effectiveness of SLL-using optimizers is highly dependent on the quality of SLL-based problem decomposition. Thus, understanding what kind of problems are hard or easy to decompose by SLL is important for practice. In this work, we analytically estimate the size of a population sufficient for obtaining a perfect decomposition in case of concatenations of certain unitation-based functions. The experimental study confirms the accuracy of the proposed estimate. Finally, we identify those problem types that may be considered hard for SLL-using optimizers.

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.

Solving land-use allocation problems can help us to deal with some of the most urgent global environmental issues. Since these problems are NP-hard, effective optimizers are needed to handle them. The knowledge about variable dependencies allows for proposing such tools. However, in this work, we consider a real-world multi-objective problem for which standard variable dependency discovery techniques are inapplicable. Therefore, using linkage-based variation operators is unreachable. To address this issue, we propose a definition of problem-dedicated variable dependency. On this base, we propose obtaining masks of dependent variables. Using them, we construct three novel crossover operators. The results concerning real-world test cases show that introducing our propositions into two well-known optimizers (NSGA-II, MOEA/D) dedicated to multi-objective optimization significantly improves their effectiveness.

Gray-box optimization proposes effective and efficient optimizers of general use. To this end, it leverages information about variable dependencies and the subfunction-based problem representation. These approaches were already shown effective by enabling tunnelling between local optima even if these moves require the modification of many dependent variables. Tunnelling is useful in solving the maximum satisfiability problem (MaxSat), which can be reformulated to Max3Sat. Since many real-world problems can be brought to solving the MaxSat/Max3Sat instances, it is important to solve them effectively and efficiently. Therefore, we focus on Max3Sat instances for which tunnelling fails to introduce improving moves between locally optimal high-quality solutions and the region of globally optimal solutions. We analyze the features of such instances on the ground of phase transitions. Based on these observations, we propose manipulating clause-satisfiability characteristics that allow connecting high-quality solutions distant in the solution space. We utilize multi-satisfiability characteristics in the optimizer built from typical gray-box mechanisms. The experimental study shows that the proposed optimizer can solve those Max3Sat instances that are out of the grasp of state-of-the-art gray-box optimizers. At the same time, it remains effective for instances that have already been successfully solved by gray-box.

Gray-box optimization employs Walsh decomposition to obtain non-linear variable dependencies and utilize them to propose masks of variables that have a joint non-linear influence on fitness value. These masks significantly improve the effectiveness of variation operators. In some problems, all variables are non-linearly dependent, making the aforementioned masks useless. We analyze the features of the real-world instances of such problems and show that many of their dependencies may have noise-like origins. Such noise-caused dependencies are irrelevant to the optimization process and can be ignored. To identify them, we propose extending the use of Walsh decomposition by measuring variable dependency strength that allows the construction of the weighted dynamic Variable Interaction Graph (wdVIG). wdVIGs adjust the dependency strength to mixed individuals. They allow the filtering of irrelevant dependencies and re-enable using dependency-based masks by variation operators. We verify the wdVIG potential on a large benchmark suite. For problems with noise, the wdVIG masks can improve the optimizer's effectiveness. If all dependencies are relevant for the optimization, i.e., the problem is not noised, the influence of wdVIG masks is similar to that of state-of-the-art structures of this kind.

Local optima networks (LONs) capture fitness landscape information. They are typically constructed in a black-box manner; information about the problem structure is not utilised. This also applies to the analysis of LONs: knowledge about the problem, such as interaction between variables, is not considered. We challenge this status-quo with an alternative approach: we consider how LON analysis can be improved by incorporating subfunction-based information — this can either be known a-priori or learned during search. To this end, LONs are constructed for several benchmark pseudo-boolean problems using three approaches: firstly, the standard algorithm; a second algorithm which uses deterministic grey-box crossover; and a third algorithm which selects perturbations based on learned information about variable interactions. Metrics related to subfunction changes in a LON are proposed and compared with metrics from previous literature which capture other aspects of a LON. Incorporating problem structure in LON construction and analysing it can bring enriched insight into optimisation dynamics. Such information may be crucial to understanding the difficulty of solving a given problem with state-of-the-art linkage learning optimisers. In light of the results, we suggest incorporation of problem structure as an alternative paradigm in landscape analysis for problems with known or suspected subfunction structure.

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.

Hyperspectral imaging brings important opportunities in a variety of fields due to the unprecedented amount of information it captures in numerous narrow and contiguous spectral bands. However, the high spectral and spatial dimensionality of hyperspectral images makes them challenging to transfer, store, and ultimately analyze, while only a subset of bands may be significant in specific downstream applications in Earth observation. In this article, we tackle this issue and introduce CANNIBAL---a band selection algorithm based on unsupervised clustering of inter-band dependencies captured in weighted Variable Interaction Graphs, which are a side-effect of the optimization performed by the Genetic Algorithm with Linkage Learning. We apply CANNIBAL to two downstream tasks of hyperspectral unmixing and segmentation. Our experimental study revealed that it outperforms other band selection algorithms and allows us to dramatically reduce the number of bands without negatively affecting the quality of downstream models. Finally, CANNIBAL offers a high level of flexibility, as it can be both parametric and non-parametric, depending on a use case.

In pseudo-Boolean optimization, a variable interaction graph represents variables as vertices, and interactions between pairs of variables as edges. In black-box optimization, the variable interaction graph may be at least partially discovered by using empirical linkage learning techniques. These methods never report false variable interactions, but they are computationally expensive. The recently proposed local search with linkage learning discovers the partial variable interaction graph as a side-effect of iterated local search. However, information about the strength of the interactions is not learned by the algorithm. We propose local search with linkage learning 2, which builds a weighted variable interaction graph that stores information about the strength of the interaction between variables. The weighted variable interaction graph can provide new insights about the optimization problem and behavior of optimizers. Experiments with NK landscapes, knapsack problem, and feature selection show that local search with linkage learning 2 is able to efficiently build weighted variable interaction graphs. In particular, experiments with feature selection show that the weighted variable interaction graphs can be used for visualizing the feature interactions in machine learning. Additionally, new transformation operators that exploit the interactions between variables can be designed. We illustrate this ability by proposing a new perturbation operator for iterated local search.

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.

Next-generation genetic algorithms (GAs) should explore information from the problem structure whenever possible. Variable interactions can be inferred using linkage learning. Statistical linkage learning techniques were shown to improve GAs' effectiveness significantly in many problems, but may eventually report false linkages. On the other hand, empirical linkage learning (ELL) techniques discover only true variable dependencies. However, traditional ELL techniques are computationally expensive. We introduce the genetic algorithm with linkage learning (GAwLL), which discovers an empirical weighted variable interaction graph (VIGw) as a side-effect of the optimization performed by a GA, making it a no-cost ELL technique. Vertices of the VIGw represent decision variables and weights indicate the strength of the interaction between variables. The VIGw allows us to obtain new insights about the optimization problem and can be used to design genetic operators that efficiently explore the information about variable dependencies. Experiments with NK landscapes show that GAwLL is able to efficiently build the empirical VIGw. We also present an interesting machine learning application, where the VIGw represents a feature interaction network. By using GAwLL, the feature interaction network is built as a side-effect of evolutionary feature selection.

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.

Perturbing solutions is a key factor in iterated local search (ILS). The standard approach for perturbing a solution is to randomly change a fixed number of decision variables from the current local optimum. Finding suitable values of perturbation strength is difficult. It is desirable that consecutive local optima generated by ILS be close to each other and correlated in fitness. However, if the perturbation is too small, we can get stuck in the same local optimum. We propose a new perturbation strategy for ILS applied to pseudo-Boolean optimization problems where decision variables that interact are perturbed. These interactions are identified in a variable interaction graph (VIG), that is available in gray-box optimization. For black-box optimization, we propose a local search strategy that estimates an empirical VIG. Theoretical and experimental results show that perturbation based on the VIG is efficient in random and adjacent NK landscapes. Results also show that the proposed local search strategy was able to build empirical VIGs with more than 97% of the edges of the true VIG.

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.

In the Evolutionary Computation field, it is frequent to assume that a computation load necessary for fitness value computation is, at least, similar for all possible cases. The main objective of this paper is to show that the above assumption is frequently false. Therefore, the examples of evolutionary methods that use problem encoding which allows for significant optimization of the fitness computation process are pointed out and analyzed. The definition of Problem Encoding Allowing Cheap Fitness Computation of Mutated Individuals (PEACh) is proposed. Another objective of the paper is to start a discussion concerning the computation load measurement in the evolutionary computation field. As shown, the Fitness Function Evaluation number is not always a fair measure and may be significantly affected by the quality of method implementation.

In this paper, we define a new practical technology-driven Resource Constrained Scheduling Problem (t-RCPSP).We propose three approaches, applying constructive heuristics to tackle effectively the practical application of RCPSP.In the RCPSP formulation, the constraints are defined to design the tasks in the spaces constructed by non-and renewable resources, without violating the precedence relationships and technologies in real world problem that exists in Plastic and Rubber Processing company.The difficulty of t-RCPSP is NP-hard and we proposed three constructive specialized methods: duration based heuristics (DBH), locally optimal resource usage PEC and NEH heuristic adaptation.The paper presents results of computational experiments that show the effectiveness of the proposed approaches.

One of the main evolutionary algorithms bottlenecks is the significant effectiveness dropdown caused by increasing number of genes necessary for coding the problem solution. In this paper, we present a multi population pattern searching algorithm (MuPPetS), which is supposed to be an answer to situations where long coded individuals are a must. MuPPetS uses some of the messy GA ideas like coding and operators. The presented algorithm uses the binary coding, however the objective is to use MuPPetS against real-life problems, whatever coding schema. The main novelty in the proposed algorithm is a gene pattern idea based on retrieving, and using knowledge of gene groups which contains genes highly dependent on each other. Thanks to gene patterns the effectiveness of data exchange between population individuals improves, and the algorithm gains new, interesting, and beneficial features like a kind of “selective attention” effect.