Open AccessArticle

Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm

Piotr Ciepliński

and

Sławomir Golak

Department of Industrial Informatics, Faculty of Materials Engineering, Silesian University of Technology, 40-019 Katowice, Poland

Author to whom correspondence should be addressed.

Appl. Sci. 2024, 14(24), 11786; https://doi.org/10.3390/app142411786

Submission received: 29 September 2024 / Revised: 3 December 2024 / Accepted: 11 December 2024 / Published: 17 December 2024

(This article belongs to the Special Issue Technologies, Algorithms and Applications for Planning, Scheduling and Optimization)

Download

Browse Figures

Versions Notes

Abstract

This paper proposes a novel crossover operator for evolutionary algorithms in task sequencing and verifies its efficacy. Unlike the conventional blind and entirely stochastic selection of sequence fragments exchanged with the second individual, the proposed operator employs a method where the probability of fragment selection is influenced by the total cost of internal connections within the exchanged fragments. At the same time, the new operator retains its stochastic nature and is not a deterministic operator, which reduces the risk of the evolutionary algorithm getting stuck in a local minimum. The idea of the proposed crossover operator was based on the main mechanism of the evolutionary algorithm that determines the success of this type of algorithm selection. To assess its effectiveness, the new operator was compared against previously employed crossover operators using a traveling salesman problem (TSP) instance in a multidimensional space in order to map the problem of symmetric sequencing tasks described with multiparameters (e.g., a symmetric variant of production tasks sequencing).

Keywords:

evolutionary algorithm; task sequencing; crossover operator; TSP

1. Introduction

The goal of the classic traveling salesman problem (TSP) is to find the optimal route that will allow you to visit all the required cities in the shortest possible time. An extension of this problem is the asymmetric traveling salesman problem, ATSP, in which the distance

d_{i, j}

from city i to j does not have to be the same as

d_{j, i}

[1]. The traditional TSP problem is considered in a two-dimensional Euclidean space, but it can also be extended to a larger number of dimensions

R^{d}

[2] and described with other distance measures (e.g., in the case of scheduling production tasks). This problem is one of the most popular problems analyzed for many years in computer science. Many very efficient algorithms have been created to effectively determine routes between cities.

One of the most popular methods for solving TSP problems is evolutionary algorithms, but there are proposals in the literature to use many other algorithms [3], such as the discrete dragonfly algorithm [4], ant colony optimization [5], bat algorithm [6], GENI-US [7], or tabu search [8,9]. Some papers propose hybrid or memetic algorithms such as a hybrid algorithm based on the best-worst ant system and particle swarm optimization [10], or a hybrid algorithm based on the ant colony optimization and simulated annealing [11] or memetic ant colony optimization with local search [12].

A very similar problem is, in basic terms, the sequencing of tasks (e.g., production tasks). The purpose of such an algorithm is to arrange tasks in such a way as to reduce the costs resulting from the need to retool machines, finalize and initiate subsequent technological processes with different parameters, etc. This cost is equivalent to the distance in the classic TSP. Despite the similarities, the task sequencing process is a more complex process than the TSP problem. In addition to the costs of switching between tasks, it is necessary to take into account specific constraints resulting from business reasons (e.g., deadlines for orders) or technological reasons. Highly optimized, sophisticated algorithms dedicated to the classic TSP problem do not provide such an opportunity. Such freedom, the ability to take into account various constraints and freely define multifaceted optimization criteria, is provided by evolutionary algorithms. Therefore, despite their possibly lower efficiency (compared with the above-mentioned dedicated algorithms), they find practical applications in industrial IT systems. This justifies the search for ways to increase their effectiveness.

The evolutionary algorithm consists of three basic operators: selection, crossover, and mutation [13]. In the case of chromosome-modifying operators (crossover and mutation), it should be emphasized that the methods of implementing these operators are entirely distinct in classical problems—where genes (binary, integer, or real) with fixed positions define solution parameters—and in sequencing problems, where the order of nodes is rearranged. Researchers are continually developing new variations in these operators for sequencing problems. Focusing on crossover operators, two classic methods, single-point crossover and two-point crossover [14,15,16], which involve creating children by cutting the parents’ chromosomes in one or two randomly selected places, are still very popular. Articles [14,17] proposed extending the commonly used crossover methods to a multipoint form, presenting methods such as N-point crossover [17] and uniform crossover [14]. The uniform crossover method was then modified by [18] to the three-parent uniform crossover version. Among the classic, general crossover operators, another noteworthy method is the arithmetic crossover [19] method, which is dedicated to encoding real numbers. Its operating principle is to define a linear combination of two parents. In addition to the above crossover methods, many methods specially dedicated to TSP problems have also been proposed. According to [20,21], the classic and most frequently used methods from this group are partially mapped crossover, PMX [22], ordered crossover, OX [23] and cycle crossover, CX [24], which apart from randomly determining intersection points and exchanging fragments of the parent sequences, they also have built-in repair algorithms. The need for their use in TSP class problems results from damage to individuals resulting from the crossover operation. The mentioned damage consists of both missing and duplicate genes (cities) in the offspring [20]. The edge recombination crossover is based on the concept of neighborhood, ERX [25], generalized N-point crossover, GNX [26], tie-break crossover, TBX [27], MOX [28], Moon Crossover, MX [29,30] proposed combining PMX and TBX operators, modification of the OX operator Non-Wrapping Order Crossover, NWOX [31], two-part chromosome crossover, TCX [32], modification of the CX Modified-Cycle Crossover Operator, CX2 [33], modifications of the classic PMX method like PMX2 [34], IMPX [35], completely mapped crossover, CMX [36]. It should be emphasized that all the crossover methods mentioned above are characterized by random selection of sequence fragments and intersection points during the crossover operation.

In addition to these random methods, the literature also presents many proposals for deterministic crossover based on distances, such as Greedy Crossover, GX and Heuristic Crossover, HX [37], which select a random starting city and then select the next gene based on the distances to neighboring cities in parents. In the paper [38], the authors proposed a modification of the HX algorithm called Modified Heuristic Crossover, MHX, which introduces an improvement in the selection of the next city in the event of a loop. However, the GX method has been modified by [39] as a Very Greedy Crossover, VGX, which modifies the behavior of the original method in case the nearest neighbor found causes a loop. In such a situation, GX selects a random city and VGX tries to select additional neighbors that are located at further distances. The Neighborhood Relationship Crossover methods, NRX [28], and the sequential constructive crossover, SCX [40], which brings very good results, similarly to the previous ones, also base the selection of the next gene on the distances of the neighbors of the current city in the crossed parents. Proposed by [41], Ordered Distance Vector, ODV, uses the ODV matrix and focuses on individual initialization techniques, and its improved version of the ODV-based crossover operator, ODVX in [42] additionally uses the multiparent technique [43] and modifies and extends the failure reduction method described in [43]. The algorithm by [21], which uses the Crossover Neighbor algorithm, CNN, and Sequential Insertion algorithm, CSI [21], also achieves good results. The authors of [44] have developed an algorithm that stepwise compares subsequent parent sequences. As presented above, newer crossover methods for TSP are being developed. However, it is worth noting that they are mainly based on complete randomness or, on the contrary, fully deterministic selection of the best fragments of the parental sequence. However, random algorithms require a large number of iterations to find a solution. In contrast, deterministic algorithms are at risk of getting stuck in a local minimum.

This paper proposes and confirms the effectiveness of a new crossover operator for evolutionary algorithms that implement task sequencing. This operator is inspired by a mutation operator previously proposed in [45]. In this mutation operator, the probability of selecting the cut site within a sequence is proportional to the cost of transition between adjacent tasks. Building on this principle, the proposed new crossover operator deviates from the usual blind and completely stochastic selection of the sequence fragment exchanged with the second individual. Instead, it employs a method where the probability of sequence selection is linked to the total cost of internal connections in the exchanged sequence fragment. Therefore, the proposed method is an intermediate solution between completely random and completely deterministic crossover. As part of the performance assessment, the new crossover method was compared with the efficient, well-known random crossover methods PMX [22], OX [23], Single-Point Crossover [14,15] and the newer deterministic SCX method [40]. The authors of [46,47] indicated the SCX method as one of the most effective for TSP problems.

2. Modified Evolutionary Algorithm for Task Sequencing

This research was deliberately based on a basic, classic evolutionary algorithm (Figure 1), in which the mutation operator is not used to ensure isolation of studies of the influence of the crossover operator. Such approaches can be considered permissible because in the case of the task sequencing problem, the crossover operators themselves, together with the accompanying chain repair algorithms, introduce fluctuations in the task distribution, which can be considered the equivalent of mutations that prevents the population gene pool from averaging out. By excluding mutations, this approach isolates the impact of the crossover operator on the results.

2.1. Selection Operator

According to the generally very well-known scheme in Figure 1, in the first step of the algorithm, the initial population is randomly generated. In the next step of the algorithm, the fitness function is determined for each individual of the population. The fittest individual is remembered. Then, reproduction occurs using the selection operator. The new population is generated based on one of the most popular and again classic selection method such as proportional (1) selection [13]. The authors allow themselves to quote the well-known formula for the probability of an individual passing to a new generation, because part of the idea of the new crossover operator is based on the same principle:

P_{i} = {(1 - \frac{f_{i} - f_{m i n}}{\sum_{j = 1}^{N} (f_{j} - f_{m i n})})}^{a}

(1)

where

P_{i}

—probability of selecting individual i,

f_{i}

—evaluation function (e.g., fitness function) for individual i,

f_{m i n}

—the minimum value of the fitness function for the entire population, N is the number of individuals, a—exponent controlling the strength of selection.

2.2. Sequence Encoding

Before describing the new crossover operators in detail, we define a method for encoding task sequences in the chromosomes of individuals. Figure 2 shows an example of a chromosome for a sequence of 5 tasks. Each task is described by a set of parameters

{\bar{P}}_{i}

. For typical production planning problems involving sequencing production tasks, the size of the set

\bar{P}

may be significant and describes the parameters of the technological operation.

Each chromosome is represented by a cyclic graph (Figure 3), which is closed during optimization. Chromosome opening is performed only for the final individual—the best one found during optimization. Opening the final chromosome involves breaking the most expensive connection between the tasks, which in Figure 3 is presented as the connection length; the longer the connection, the more expensive it is.

2.3. New Crossover Operator

During the evolution process, individuals in the new population undergo modifications using genetic operators. Typically, crossover and mutation operators are employed, but in this study, individuals will be modified only using the crossover operator. As previously mentioned, the exclusion of the mutation operator is dictated by the need to exclude its influence on the analyzed results.

The authors proposed a new, in contrast to the existing crossover methods (PMX, OX, Single-Point Crossover, and SCX), partially deterministic method, preferring the exchange of sequence fragments with a lower cost of external connections. The new crossover method consists of the following stages:

Two individuals are selected randomly from the population for the crossover operation. One acts as a donor of a sequence fragment, and the other acts as a recipient of a sequence fragment.
For the donor individual in the randomly selected pair, all fragments of the task sequence are evaluated with a length constituting a metaparameter of the algorithm. The evaluation is based on the total cost of connections between tasks within a sequence fragment:

$C = \sum_{i = 1}^{M - 1} c ({\bar{P}}_{i}, {\bar{P}}_{i + 1})$

(2)

where M—number of tasks in the analyzed fragment of the sequence (fragment length), ${\bar{P}}_{i}$ —parameters of the i-th task in the fragment of the sequence, $c ()$ —the cost of transitioning between two tasks.
Having the cost of each fragment of the sequence, we can select the fragment transferred from the donor to the recipient using a method analogous to the proportional selection operator:

$P_{i}^{F} = {(1 - \frac{C_{i} - C_{m i n}}{\sum_{j = 1}^{N} (C_{i} - C_{m i n})})}^{a}$

(3)

where $P_{i}^{F}$ —probability of selecting the sequence fragment i; $C_{i}$ —cost of internal transitions for the i-th fragment, $C_{m i n}$ —internal cost of the cheapest fragment, N is the number of fragments (consistent with the number of tasks in the sequence), a—exponent controlling the strength of fragment selection.
The coefficient a allows you to control the strength of selection. The value 0 means a completely random selection of a fragment of the sequence, which is analogous to solutions known in the literature [15,22,23]. Increasing the value of the coefficient a increases the deterministic impact of the internal cost of a sequence fragment. Further increasing the value of the coefficient a towards infinity brings us to a completely deterministic selection of the best fragment (with the lowest cost). The coefficient a is the next metaparameter of the discussed algorithm. The probabilities determined according to the Equation (1) are finally scaled to a sum equal to 1.
On the recipient side, for the same length of a sequence fragment, the cost of internal connections in each fragment is determined based on Equation (2).
Then, a fragment is cut out from the recipient’s chromosome (sequence), and a fragment taken from the donor will be inserted in its place. The probability of selecting such a fragment can be determined by the proportional (4) method. As you can see, the determined probabilities are complements to probabilities (3).

$P_{i}^{F} = {(\frac{C_{i} - C_{m i n}}{\sum_{j = 1}^{N} (C_{i} - C_{m i n})})}^{a}$

(4)
Division of genes (tasks) deleted from parent 2 (recipient) into two groups (Figure 4). During this stage, we compare the genes in both fragments obtained in the previous stages in order to determine the genes that will be duplicated in the child (recipient after modification). The item marked in yellow will not be replicated in the recipient because it is present in both the fragment taken from the donor and the fragment removed from the recipient. However, genes marked in red will be retained in memory as missing in the recipient. Genes marked in blue will cause duplicates to appear in the recipient because they were not present in the fragment removed from the recipient.
At this stage, we insert the fragment obtained from the donor in the first stage into the free place in the recipient that was created after cutting the chain (Figure 5). After this operation, the new chromosome is usually damaged because it contains duplicated genes (marked in red in the individual in Figure 5). In addition, the child is missing certain genes that were cut out from the recipient when the fragment was removed.
The final step of the crossover operator involves repairing the resulting chromosome (Figure 6). Following the clockwise direction from the first gene located after the fragment is inserted into the recipient, the duplicate genes are replaced with subsequent missing genes (due to the removal of the recipient fragment).

Figure 7 presents the crossover algorithm discussed above in the form of a flow diagram. The exchange of chain fragments is performed for all pairs of individuals (randomly selected at the beginning of the crossover stage).

3. Experiment and Results Discussion

The main aim of the research was to assess the impact of the use of a new crossover method on the effectiveness of the evolutionary algorithm for the problem of task scheduling compared with crossover methods described in the literature. The experiments were conducted for a modified symmetric traveling salesman problem, in which each graph node (task) is described by many parameters. Thanks to this, we are dealing with a reduction in the cost of the path in the high-dimensional space. This is a model equivalent to the popular issue of sequencing production tasks, but it should be emphasized that it is still only an abstract TSP in which the set of parameters and the distances between the sequenced nodes are not related to any real production tasks and setup costs. This research was carried out for a synthetically generated sequence of 250, 500, and 1000 tasks described by a set of ten continuous parameters. Random parameter values were normalized and were in the range <0;1> (uniform distribution). The minimized objective function was the sum of the transition costs between all tasks in the sequence, excluding the cost of the most expensive connection. As mentioned in Section 2.2, after the optimization is performed, the circular graph of the best individual is broken at the place where the connection between neighboring tasks is the most expensive. For the purposes of the study, the cost of transition between tasks was defined based on the Euclidean distance (5), the square of this value, and the Manhattan distance (6):

c_{i}^{(E)} ({\bar{P}}_{i}, {\bar{P}}_{i + 1}) = \sqrt{\sum_{k = 1}^{K} {(p_{i, k} - p_{i + 1, k})}^{2}}

(5)

c_{i}^{(M)} ({\bar{P}}_{i}, {\bar{P}}_{i + 1}) = \sum_{k = 1}^{K} | p_{i, k} - p_{i + 1, k} |

(6)

where K—dimension of the parameter space describing the sequenced tasks;

p_{i, k}

—the k-th parameter of the i-th task.

Although completely synthetic, these three distances (costs of transitions between tasks) have varying scales and degrees of non-linearity, reflecting the complexity of real-world costs, e.g., in production task sequencing. Consequently, they offer some level of representativeness for comparative analysis. The total cost of executing a sequence (the fitness function for the optimization) is defined by the formula:

C_{T} = \sum_{i = 1}^{N} c_{i}^{(D)} - c_{m a x}^{(D)}

(7)

where N—the number of tasks in the optimized sequence,

c_{i}^{(D)}

—the cost of the i-th connection for the chosen distance D (either Euclidean or Manhattan),

c_{m a x}^{(D)}

—the cost of the most expensive connection in the sequence ring. Please note that after optimization, the cost of the most expensive connection (transition between tasks) is subtracted because at this point the cyclic chromosome graph will always be split at this point.

3.1. Optimization of Algorithm Metaparameters

The proposed crossover method uses two metaparameters: the length of a transferred fragment and the selection strength coefficient a used in the proposed fragment selection method. To optimize these parameters, we conducted preliminary research before the comparative analysis. The criterion of the best individual (defined in Equation (7)) reaches its minimum (best) value at a high value (30) of the a coefficient (Figure 8). It strongly favors sequence fragments with the lowest (for the donor) and highest (for the recipient) internal cost. However, the randomness of the crossover operator’s operation is still preserved, distinguishing it from the deterministic operator.

Figure 9 shows an analysis of the influence of the fragment length on the obtained minimum value for the example of the sequencing problem of 100 tasks. As can be seen, the optimal fragment lengths for different cost functions (different sequencing problem definitions) are similar, although they differ slightly. The fragment being selected must be long enough to transfer significant, valuable information to the second individual. However, as the length of the fragments increases, the means (8) of the connections within them begin to converge.

{\bar{C}}_{j} = \frac{1}{M - 1} \sum_{i = 1 + j}^{M - 1 + j} c ({\bar{P}}_{i}, {\bar{P}}_{i + 1})

(8)

where

{\bar{C}}_{j}

is the average value of connections for the j-th fragment.

At this point, the probabilities (3) and (4) for selecting individual fragments also converge. Consequently, the selection pressure decreases, and the process effectively becomes a random drawing of fragments. As a result, the partially directed nature of the new crossover operator, its basic feature, disappears.

In general, the standard deviation of the mean connections in fragments,

{\bar{C}}_{j}

, is inversely proportional to the square root of the fragment length:

std ({\bar{C}}_{j}) \propto \frac{1}{\sqrt{M - 1}}

(9)

The given formula is only an estimation, assuming that the cost values between tasks are independent. In the presence of some correlation between these costs, the value will differ to some extent, but the general trend will be preserved. The exact rate at which the connections between the fragments analyzed in the selection process become too similar (a function of M in the denominator) depends on the specificity and complexity of the problem, expressed by functions of the costs of connections between tasks, and has no relation to the global number of tasks.

To confirm this theory, an analysis was performed on the influence of the length of the optimized sequence on the optimal length of the transmitted fragment (Figure 10) for different cost definitions (different problems). A stabilized value for the optimal fragment length is visible. Some fluctuations are due only to the limited number of samples (10 experiments) performed for a given fragment length.

Based on these analyses, a method for selecting the fragment length metaparameter can be proposed. The procedure is to determine metaparameters for an arbitrary number of tasks, although preferably similar to the scale of the number of tasks that will occur in the target problem size. An effective method is to determine the optimal length of the exchanged fragment for the expected marginal number of tasks in the sequence, possibly supplemented by sampling within the middle of this range. Then, the average value determined from the samples of optimal fragment numbers should be adopted (red lines in Figure 10). The conducted experimental analysis and additional theoretical analysis have shown that the determined absolute size of the fragment will be universal. However, the key to success is to determine them based on the exact definition of the problem, expressed by the cost function of connections between tasks, as in the target problem.

The comparative analysis in the following section demonstrates that the metaparameters selected in this way provided the new crossover operator with an advantage. In future applications for sequencing real production tasks, the structure of task parameters and the cost function definition will be fixed, with only the number of tasks to be sequenced likely to change. This will enable the creation of an optimizer tailored to a specific application, and this proposed, straightforward method of metaparameter tuning could offer an advantage over other optimization solutions (with other crossover operators).

3.2. Comparative Analysis

After determining the optimal parameter values for the example task, a comparison of the obtained total sequence costs was carried out for the algorithm using the new crossover method and algorithms using previously developed crossover methods (Single-Point Crossover [14,15], PMX [22], OX [23], and SCX [40]). In order to facilitate the analysis of the results, an identical stopping condition was adopted for all comparable crossover operators—reaching 1000 generations, and after such a number of iterations, the obtained values of the minimized criteria (Equation (7)) were compared. A constant population size was used—200 individuals. In a single crossover operation, two individuals participate and the way genes are exchanged between them determines the efficiency of the crossover operator. For this reason, it seems that comparative studies can be based on the constant population size. However, the chromosome length (the number of optimized tasks) can have an influence on the crossover efficiency. Therefore, the crossover operators were compared for three sequence lengths (tasks 250, 500, and 1000). These sizes are significantly larger compared with the size for which the metaparameter values were determined to confirm their scalability.

Various degrees of complexity in the shape of solutions hypersurface are provided by using three different cost definitions (based on the Euclidean distance, the square of this distance, and the Manhattan distance).

As can be seen in the results presented in Figure 11, Figure 12 and Figure 13 and Table 1, Table 2 and Table 3 for all tested sequence lengths (250, 500 and 1000 tasks) and for the three definitions of the transition cost between tasks, the new crossover method provides a significant advantage over previously developed sequence crossover methods.

Interestingly and worth emphasizing, these four reference crossover operators achieve a very similar level of the minimized criterion in their group. Against this background, the new crossover operator distinguishes itself very clearly for each cost definition and seems to introduce a significant improvement. In our opinion, the experimental conditions did not favor the new operator in any way. For different cost definitions and problem sizes, the new crossover operator maintains its advantage. This suggests that the developed operator represents a new and more effective class of crossover operators.

In order to confirm the statistical significance of the reduction in the mean criterion value obtained for the new crossover in comparison to the previous crossover methods (shown in Table 1, Table 2 and Table 3), the t-test was performed. For an independent two-sample t-test, the variances of the two groups should be approximately equal. Therefore, this test was preceded by an F-test. For both tests, the populations from which the samples are drawn should be normally distributed. This condition was confirmed for all samples by the Shapiro–Wilk test. The results of which are shown in Table 4, Table 5 and Table 6. The analysis was carried out for the four literature crossover methods compared with the new proposed method. A significance level of

α = 0.01

was adopted for both tests. If the p-value is less than the accepted value of

α

, the null hypothesis (

H_{0}

) should be rejected in favor of the alternative hypothesis (

H_{1}

). In the case of the F-test, the null hypothesis assumes equality of variances, and in the case of the t-test, equality of means. For each variant, the equality of variances and a statistically significant change in the mean were confirmed.

Table 4, Table 5 and Table 6 also present the percentage reductions in the criterion values obtained in comparison with the previous crossover methods, together with the confidence intervals. Reducing the cost of executing a series of tasks by at least 9% (taking into account the obtained confidence intervals) compared with evolutionary algorithms based on previous crossover methods makes the solution attractive in practical applications. Reducing the time of executing a series of production tasks as a result of shortening the time of device changeovers (increasing efficiency) or/and reducing the cost of executing such a series of tasks as a result of reducing the costs of, for example, changeovers, device cleaning, and raw material waste after the previous task without the need for new equipment are already attractive to companies, even for much smaller reductions.

The validation of the new crossover method was based on synthetic data. Of course, this does not reflect the complexity of real problems, e.g., sequencing of industrial tasks. In order to somewhat approach these issues, the studies were supplemented with distributions of task parameters that differ from the basic uniform distribution and that may occur in industrial conditions. In the first test, it was checked whether the use of a continuous normal distribution of task parameters (which occurs more often in real problems than the continuous uniform distribution) will affect the degree of superiority of our method. Figure 14 shows a comparison of results for such a distribution of parameters of the analyzed crossover methods. As can be seen, the level of superiority of our method has not changed significantly in comparison with parameters with a uniform distribution (Figure 11).

The second test involved the use of parameters selected from a limited set of values. This corresponds to the multilevel (but limited set) device settings that often occur in industry. Figure 15, Figure 16 and Figure 17 show comparative graphs for three, four, and five value levels. Also, in this case, the new crossover method retained its advantage.

The crossover operators compared in this work also differ in computational complexity. Completely random operators like PMX, OX, and Single-Point Crossover are the fastest, as shown in Figure 18, because they do not take into account the cost of connections between tasks during selecting crossover points and they do not have to analyze all connections. In contrast, the SCX operator and the new probabilistic method presented in this work are slower than completely random operators. This is because they require calculating the distance between all tasks in individuals before deciding on the location of the intersection points of the chain. The SCX method is slower than the probabilistic operator presented in this work because it accurately compares the distance from the current task to the following task in both parents when generating an offspring.

The analysis of the optimization progress presented in Figure 19, Figure 20 and Figure 21 turns out to be interesting. The proposed crossover method gains an advantage over the compared crossover methods already at the beginning of the optimization. This compensates for the longer duration of the new crossover.

In the studies discussed above, a constant population size of 200 individuals was assumed. To eliminate the possibility that the population size influenced the advantage of the new crossover operator, a supplementary analysis was conducted to assess the impact of population size on the results obtained for the various operators in the example variant. As shown in Figure 22, the new operator maintains its advantage across the entire population size range examined. Notably, only the new method demonstrates some improvement in efficiency with an increase in population size.

For the other methods, the number of generations used ensures that they reach their respective local minima, and increasing the population size does not improve their solutions. In contrast, the new crossover method is able to benefit from a larger population size, enabling it to improve its solution by sampling more of the solution space within a single generation. However, this improvement comes at the cost of longer computation times per generation.

4. Conclusions

The novelty of the developed crossover operator is that it is an intermediate form between the most popular, purely random solutions and the recently developed fully deterministic implementations of the crossover operator. Despite its simplicity and almost a direct copy of the idea of the selection operator, in the conducted research, it demonstrated superior performance compared with existing crossover operators.

The simplicity of the new operator provides great opportunities for its quick, often trivial integration with a huge database of existing solutions in the area of evolutionary task sequencing. The proposed crossover operator was modeled on the most basic, proportional variant of the selection operator and has already demonstrated its power. An interesting field for further research would be variants of the crossover operator modeled on other types of selection from the quite extensive set available in the bibliography for evolutionary algorithms. Validation of the new crossover operator has been performed for a symmetric variant of task sequencing. However, it seems that further research should also cover the application of this operator for task scheduling with an asymmetric (dependent on the transition direction) cost function.

Author Contributions

Conceptualization, methodology, and writing—review and editing, P.C. and S.G.; investigation and visualization, P.C. All authors have read and agreed to the published version of the manuscript.

Funding

Publication supported by the Excellence Initiative—Research University programme implemented at the Silesian University of Technology, year 2023, grant number 11/040/SDU/10-22-01.

Data Availability Statement

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author.

Conflicts of Interest

The authors declare no conflicts of interest.

References

Bagchi, T.P.; Gupta, J.N.; Sriskandarajah, C. A review of TSP based approaches for flowshop scheduling. Eur. J. Oper. Res. 2006, 169, 816–854. [Google Scholar] [CrossRef]
Funke, S.; Laue, S.; Naujoks, R.; Lotker, Z. Power assignment problems in wireless communication: Covering points by disks, reaching few receivers quickly, and energy-efficient travelling salesman tours. In Proceedings of the Distributed Computing in Sensor Systems: 4th IEEE International Conference, DCOSS 2008, Santorini Island, Greece, 11–14 June 2008; pp. 282–295. [Google Scholar]
Toaza, B.; Esztergár-Kiss, D. A review of metaheuristic algorithms for solving TSP-based scheduling optimization problems Image 1. Appl. Soft Comput. 2023, 148, 110908. [Google Scholar] [CrossRef]
Emambocus, B.A.S.; Jasser, M.B.; Amphawan, A.; Mohamed, A.W. An Optimized Discrete Dragonfly Algorithm Tackling the Low Exploitation Problem for Solving TSP. Mathematics 2022, 10, 3647. [Google Scholar] [CrossRef]
Wang, Y.; Han, Z. Ant colony optimization for traveling salesman problem based on parameters optimization. Appl. Soft Comput. 2021, 107, 107439. [Google Scholar] [CrossRef]
Yang, X.S. A New Metaheuristic Bat-Inspired Algorithm. In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010); Springer: Berlin/Heidelberg, Germany, 2010; pp. 65–74. [Google Scholar] [CrossRef]
Gendreau, M.; Hertz, A.; Laporte, G. New insertion and postoptimization procedures for the traveling salesman problem. Oper. Res. 1992, 40, 1086–1094. [Google Scholar] [CrossRef]
França, P.M.; Gendreau, M.; Laporte, G.; Müller, F.M. The m-traveling salesman problem with minmax objective. Transp. Sci. 1995, 29, 267–275. [Google Scholar] [CrossRef]
França, P.M.; Gendreau, M.; Laporte, G.; Müller, F.M. A tabu search heuristic for the multiprocessor scheduling problem with sequence dependent setup times. Int. J. Prod. Econ. 1996, 43, 79–89. [Google Scholar] [CrossRef]
Qamar, M.S.; Tu, S.; Ali, F.; Armghan, A.; Munir, M.F.; Alenezi, F.; Muhammad, F.; Ali, A.; Alnaim, N. Improvement of Traveling Salesman Problem Solution Using Hybrid Algorithm Based on Best-Worst Ant System and Particle Swarm Optimization. Appl. Sci. 2021, 11, 4780. [Google Scholar] [CrossRef]
Stodola, P.; Michenka, K.; Nohel, J.; Rybanský, M. Hybrid Algorithm Based on Ant Colony Optimization and Simulated Annealing Applied to the Dynamic Traveling Salesman Problem. Entropy 2020, 22, 884. [Google Scholar] [CrossRef]
Mavrovouniotis, M.; Müller, F.M.; Yang, S. Ant colony optimization with local search for dynamic traveling salesman problems. IEEE Trans. Cybern. 2016, 47, 1743–1756. [Google Scholar] [CrossRef]
Malik, A. A study of genetic algorithm and crossover techniques. Int. J. Comput. Sci. Mob. Comput. 2019, 8, 335–344. [Google Scholar]
Syswerda, G. Uniform crossover in genetic algorithms. In Proceedings of the ICGA, Fairfax, VA, USA, 4–7 June 1989; Volume 3, pp. 2–9. [Google Scholar]
Ishola, K.; James, O. Cost Reduction of Traveling Salesman Problem with an Enhanced Genetic Algorithm. Int. J. Res. Sci. Innov. 2020, 7, 110–117. [Google Scholar]
Cavus, M.; Allahham, A. Enhanced Microgrid Control through Genetic Predictive Control: Integrating Genetic Algorithms with Model Predictive Control for Improved Non-Linearity and Non-Convexity Handling. ENERGIES 2024, 17, 4458. [Google Scholar] [CrossRef]
De Jong, K.A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems; University of Michigan: Ann Arbor, MI, USA, 1975. [Google Scholar]
Edmondson, L.V. Genetic Algorithms with 3-Parent Crossover; University of Missouri: Rolla, MO, USA, 1993. [Google Scholar]
Zbigniew, M. Genetic algorithms+ data structures= evolution programs. Comput. Stat. 1996, 24, 372–373. [Google Scholar]
Kora, P.; Yadlapalli, P. Crossover operators in genetic algorithms: A review. Int. J. Comput. Appl. 2017, 162, 34–36. [Google Scholar] [CrossRef]
Satyananda, D. Modification of Crossover Operator on GA Application for TSP. In Proceedings of the International Conference on Research, Implementation and Education of Mathematics and Sciences, Yogyakarta, Indonesia, 14–15 September 2015. [Google Scholar]
Goldberg, D.E.; Lingle, R. Alleles, Loci and the Traveling Salesman Problem. In Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburg, PA, USA, 24–26 July 1985; pp. 154–159. [Google Scholar]
Davis, L. Job Shop Scheduling with Genetic Algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburg, PA, USA, 24–26 July 1985; pp. 136–140. [Google Scholar]
Oliver, I.M.; Smith, D.J.; Holland, J.R.C. A study of permutation crossover operators on the traveling salesman problem. In Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, Cambridge, MA, USA, 28–31 July 1987; pp. 224–230. [Google Scholar]
Whitley, D.; Starkweather, T.; Shaner, D. The Traveling salesman and Sequence Scheduling: Quality Solutions Using Genetic Edge Recombination. In Handbook of Genetic Algorithms; Van Nostrand Reinhold: New York, USA, 1991; pp. 350–372. [Google Scholar]
Radcliffe, N.J.; Surry, P.D. Fitness variance of formae and performance prediction. In Foundations of Genetic Algorithms; Elsevier: Amsterdam, The Netherlands, 1995; Volume 3, pp. 51–72. [Google Scholar]
Poon, P.W.; Carter, J.N. Genetic algorithm crossover operators for ordering applications. Comput. Oper. Res. 1995, 22, 135–147. [Google Scholar] [CrossRef]
Aşveren, T.; Molitor, P. New crossover methods for sequencing problems. In Proceedings of the International Conference on Parallel Problem Solving from Nature, Berlin, Germany, 22–26 September 1996; pp. 287–299. [Google Scholar]
Moon, C.; Kim, J.; Choi, G.; Seo, Y. An efficient genetic algorithm for the traveling salesman problem with precedence constraints. Eur. J. Oper. Res. 2002, 140, 606–617. [Google Scholar] [CrossRef]
Choi, I.C.; Kim, S.I.; Kim, H.S. A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem. Comput. Oper. Res. 2003, 30, 773–786. [Google Scholar] [CrossRef]
Cicirello, V.A. Non-wrapping order crossover: An order preserving crossover operator that respects absolute position. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, DC, USA, 8–12 July 2006; pp. 1125–1132. [Google Scholar]
Yuan, S.; Skinner, B.; Huang, S.; Liu, D. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. Eur. J. Oper. Res. 2013, 228, 72–82. [Google Scholar] [CrossRef]
Hussain, A.; Muhammad, Y.S.; Sajid, M.N.; Hussain, I.; Shoukry, A.M.; Gani, S. Genetic algorithm for traveling salesman problem with modified cycle crossover operator. Comput. Intell. Neurosci. 2017, 2017, 7430125. [Google Scholar] [CrossRef]
Hussain, A.; Muhammad, Y.S.; Sajid, M.N. A simulated study of genetic algorithm with a new crossover operator using traveling salesman problem. J. Math. 2019, 51, 61. [Google Scholar]
Koohestani, B. A crossover operator for improving the efficiency of permutation-based genetic algorithms. Expert Syst. Appl. 2020, 151, 113381. [Google Scholar] [CrossRef]
Iqbal, Z.; Bashir, N.; Hussain, A.; Cheema, S.A. A novel completely mapped crossover operator for genetic algorithm to facilitate the traveling salesman problem. Comput. Math. Methods 2020, 2, e1122. [Google Scholar] [CrossRef]
Grefenstette, J.J. Incorporating problem specific knowledge in genetic algorithms. In Genetic Algorithms and Simulated Annealing; Stanford University: Stanford, CA, USA, 1987; pp. 42–60. [Google Scholar]
Jog, P.; Suh, J.Y.; Gucht, D.V. The Effects of Population Size, Heuristic Crossover and Local Improvement on a Genetic Algorithm for the Traveling Salesman Problem. In Proceedings of the 3rd International Conference on Genetic Algorithms, Fairfax, VA, USA, 4–7 June 1989; pp. 110–115. [Google Scholar]
Julstrom, B.A. Very greedy crossover in a genetic algorithm for the traveling salesman problem. In Proceedings of the 1995 ACM Symposium on Applied Computing, Nashville, TN, USA, 26–28 February 1995; pp. 324–328. [Google Scholar]
Ahmed, Z.H. Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator. Int. J. Biom. Bioinform. (IJBB) 2010, 3, 96. [Google Scholar] [CrossRef]
Paul, P.V.; Ramalingam, A.; Baskaran, R.; Dhavachelvan, P.; Vivekanandan, K.; Subramanian, R. A new population seeding technique for permutation-coded Genetic Algorithm: Service transfer approach. J. Comput. Sci. 2014, 5, 277–297. [Google Scholar] [CrossRef]
Victer Paul, P.; Ganeshkumar, C.; Dhavachelvan, P.; Baskaran, R. A novel ODV crossover operator-based genetic algorithms for traveling salesman problem. Soft Comput. 2020, 24, 12855–12885. [Google Scholar] [CrossRef]
Ting, C.K. Multi-parent extension of edge recombination. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, London, UK, 7–11 July 2007; p. 1535. [Google Scholar]
Akter, S.; Nahar, N.; ShahadatHossain, M.; Andersson, K. A new crossover technique to improve genetic algorithm and its application to TSP. In Proceedings of the 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE), Cox’s Bazar, Bangladesh, 7–9 February 2019; pp. 1–6. [Google Scholar]
Ciepliński, P.; Golak, S.; Wieczorek, T. Analysis of modification of the evolutionary algorithm for sequencing production tasks. Comput. Methods Mater. Sci. 2022, 22, 3. [Google Scholar]
Dou, X.A.; Yang, Q.; Gao, X.D.; Lu, Z.Y.; Zhang, J. A Comparative Study on Crossover Operators of Genetic Algorithm for Traveling Salesman Problem. In Proceedings of the 15th International Conference on Advanced Computational Intelligence (ICACI), Seoul, Republic of Korea, 6–9 May 2023; pp. 1–8. [Google Scholar]
Ahmed, Z.H.; Al-Otaibi, N.; Al-Tameem, A.; Saudagar, A.K.J. Genetic Crossover Operators for the Capacitated Vehicle Routing Problem. Comput. Mater. Contin. 2023, 75, 1575–1605. [Google Scholar]

Figure 1. Flow diagram of the used evolutionary algorithm.

Figure 2. The chromosome encodes the task sequence. Each task is described by a set of parameters,

\bar{P}

. Each node is connected to two neighbors by a connection, the length of which represents the cost C of the transition between tasks and is a function of the parameters of the adjacent tasks. During optimization, the chromosome forms a cyclic graph with no indication of the start of the sequence.

Figure 2. The chromosome encodes the task sequence. Each task is described by a set of parameters,

\bar{P}

Figure 3. Example of a chromosome in the form of a ring (cycle) graph for 12 tasks.

Figure 4. The operation of selecting a sequence fragment to be transferred from the donor and a fragment to be removed from the recipient. Green items indicate selected sequence fragments. Yellow items are repeated in both fragments and do not require repair. Blue items are genes that will cause task duplication in the recipient. Red items represent tasks removed from the recipient and the lack of these tasks in the recipient’s chromosome.

Figure 5. Creating offspring. Light blue items represent new genes inserted into the recipient chromosome. Dark red items are old recipient genes that cause erroneous duplication of tasks.

Figure 6. Repairing the child. In place of each duplicate task in the recipient (green items), the task removed from the recipient chromosome at the stage of inserting the donor fragment is inserted (red items).

Figure 7. Flow diagram of the proposed crossover operator. This crossover subalgorithm is implemented in each generation of the evolutionary algorithm.

Figure 8. Preliminary impact analysis of metaparameter a on the effectiveness of the new crossover method (the criterion value of the best individual) for sequencing 100 tasks to determine its optimal value. The determined value (red dot) for the minimum was used in the main comparative analysis of the new operator and the existing operators.

Figure 9. Preliminary impact analysis of exchanged sequence fragment length on the effectiveness of the new crossover method (the criterion value of the best individual) for sequencing 100 tasks to determine its optimal value for different cost definitions: Euclidean (A), Euclidean² (B), and Manhattan (C). The determined value (red dot) for the minimum was used in the main comparative analysis of the new operator and the existing operators.

Figure 10. Influence of the number of sequencing tasks on the optimal exchanged sequence fragment length for different cost definitions: Euclidean (A), Euclidean² (B), and Manhattan (C). The red lines represent the mean values used as metaparameter values in further studies.

Figure 11. Effectiveness of the crossover operator for the 250-task problem. The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 12. Effectiveness of the crossover operator for the 500-task problem. The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 13. Effectiveness of the crossover operator for the 1000-task problem. The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 14. Effectiveness of the crossover operator for the 250-task problem with normally distributed parameters. The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 15. Effectiveness of the crossover operator for the 250-task problem with discrete parameters (three levels of values). The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 16. Effectiveness of the crossover operator for the 250-task problem with discrete parameters (four levels of values). The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 17. Effectiveness of the crossover operator for the 250-task problem with discrete parameters (five levels of values). The mean criterion value (three definitions of cost: Euclidean, Euclidean², and Manhattan) of the best individual achieved after 1000 generations.

Figure 18. Comparison of execution time of 200 generations for the 500-task problem.

Figure 19. Change in the criterion value over time for the 500-task problem (cost based on Euclidean distance) over 1000 generations.

Figure 20. Change in the criterion value over time for the 500-task problem (cost based on Euclidean² distance) over 1000 generations.

Figure 21. Change in the criterion value over time for the 500-task problem (cost based on Manhattan distance) over 1000 generations.

Figure 22. Influence of the population size on the effectiveness of the crossover operators for the 500-task problem (cost based on Euclidean distance) over 1000 generations.

Table 1. Mean values and variances of the optimization criterion (total cost) achieved after 1000 generations for the 250-task problem.

Crossover Method	Cost Definition	Mean	$σ^{2}$
PMX	Euclidean	$3.07 \times 10^{2}$	$2.38 \times 10^{- 2}$
OX	Euclidean	$3.03 \times 10^{2}$	$2.91 \times 10^{- 2}$
Single-Point Crossover	Euclidean	$2.98 \times 10^{2}$	$2.18 \times 10^{- 2}$
SCX	Euclidean	$3.08 \times 10^{2}$	$1.88 \times 10^{- 2}$
New method	Euclidean	$2.53 \times 10^{2}$	$1.26 \times 10^{- 1}$
PMX	Euclidean²	$3.93 \times 10^{2}$	$7.50 \times 10^{- 2}$
OX	Euclidean²	$3.84 \times 10^{2}$	$8.76 \times 10^{- 2}$
Single-Point Crossover	Euclidean²	$3.76 \times 10^{2}$	$5.81 \times 10^{- 2}$
SCX	Euclidean²	$3.93 \times 10^{2}$	$8.92 \times 10^{- 2}$
New method	Euclidean²	$2.73 \times 10^{2}$	$6.99 \times 10^{- 1}$
PMX	Manhattan	$8.04 \times 10^{2}$	$1.56 \times 10^{- 1}$
OX	Manhattan	$7.90 \times 10^{2}$	$2.86 \times 10^{- 1}$
Single-Point Crossover	Manhattan	$7.78 \times 10^{2}$	$2.52 \times 10^{- 1}$
SCX	Manhattan	$8.01 \times 10^{2}$	$1.78 \times 10^{- 1}$
New method	Manhattan	$6.34 \times 10^{2}$	$2.00 \times 10^{- 1}$

Table 2. Mean values and variances of the optimization criterion (total cost) achieved after 1000 generations for the 500-task problem.

Crossover Method	Cost Definition	Mean	$σ^{2}$
PMX	Euclidean	$6.16 \times 10^{2}$	$1.11 \times 10^{- 2}$
OX	Euclidean	$6.08 \times 10^{2}$	$9.64 \times 10^{- 3}$
Single-Point Crossover	Euclidean	$6.08 \times 10^{2}$	$1.50 \times 10^{- 2}$
SCX	Euclidean	$6.14 \times 10^{2}$	$1.29 \times 10^{- 2}$
New method	Euclidean	$5.24 \times 10^{2}$	$6.05 \times 10^{- 2}$
PMX	Euclidean²	$7.89 \times 10^{2}$	$9.84 \times 10^{- 2}$
OX	Euclidean²	$7.74 \times 10^{2}$	$3.03 \times 10^{- 2}$
Single-Point Crossover	Euclidean²	$7.66 \times 10^{2}$	$1.18 \times 10^{- 1}$
SCX	Euclidean²	$7.90 \times 10^{2}$	$3.68 \times 10^{- 2}$
New method	Euclidean²	$5.74 \times 10^{2}$	$2.83 \times 10^{- 1}$
PMX	Manhattan	$1.61 \times 10^{3}$	$6.26 \times 10^{- 2}$
OX	Manhattan	$1.59 \times 10^{3}$	$1.27 \times 10^{- 1}$
Single-Point Crossover	Manhattan	$1.58 \times 10^{3}$	$1.81 \times 10^{- 1}$
SCX	Manhattan	$1.61 \times 10^{3}$	$4.05 \times 10^{- 2}$
New method	Manhattan	$1.33 \times 10^{3}$	$4.43 \times 10^{- 1}$

Table 3. Mean values and variances of the optimization criterion (total cost) achieved after 1000 generations for the 1000-task problem.

Crossover Method	Cost Definition	Mean	$σ^{2}$
PMX	Euclidean	$1.24 \times 10^{3}$	$3.66 \times 10^{- 3}$
OX	Euclidean	$1.24 \times 10^{3}$	$9.36 \times 10^{3}$
Single-Point Crossover	Euclidean	$1.23 \times 10^{3}$	$2.39 \times 10^{- 2}$
SCX	Euclidean	$1.24 \times 10^{3}$	$1.12 \times 10^{- 2}$
New method	Euclidean	$1.08 \times 10^{3}$	$6.48 \times 10^{- 2}$
PMX	Euclidean²	$1.60 \times 10^{3}$	$3.45 \times 10^{- 2}$
OX	Euclidean²	$1.59 \times 10^{3}$	$5.06 \times 10^{- 2}$
Single-Point Crossover	Euclidean²	$1.57 \times 10^{3}$	$8.57 \times 10^{- 2}$
SCX	Euclidean²	$1.60 \times 10^{3}$	$1.77 \times 10^{- 2}$
New method	Euclidean²	$1.24 \times 10^{3}$	$4.72 \times 10^{- 1}$
PMX	Manhattan	$3.25 \times 10^{3}$	$7.48 \times 10^{- 2}$
OX	Manhattan	$3.23 \times 10^{3}$	$6.31 \times 10^{- 2}$
Single-Point Crossover	Manhattan	$3.22 \times 10^{3}$	$4.49 \times 10^{- 2}$
SCX	Manhattan	$3.26 \times 10^{3}$	$2.56 \times 10^{- 2}$
New method	Manhattan	$2.78 \times 10^{3}$	$5.73 \times 10^{- 1}$

Table 4. F-test and t-test confirming a statistically significant reduction in the mean value of the optimization criterion (total cost) achieved after 1000 generations for the 250-task problem and the percentage value of the criterion reduction for the new crossover compared with the previous methods with confidence intervals for a confidence level of 0.99.

Crossover Method	Cost Definition	F-Test (p)	t-Test (p)	Reduction
PMX	Euclidean	$1.86 \times 10^{- 1}$	$1.42 \times 10^{- 14}$	$17.43 \pm 4.58 %$
OX	Euclidean	$2.31 \times 10^{- 1}$	$1.25 \times 10^{- 14}$	$16.04 \pm 4.31 %$
Single-Point Crossover	Euclidean	$1.73 \times 10^{- 1}$	$1.78 \times 10^{- 13}$	$15.05 \pm 3.95 %$
SCX	Euclidean	$1.49 \times 10^{- 1}$	$3.57 \times 10^{- 14}$	$17.66 \pm 4.64 %$
PMX	Euclidean²	$1.07 \times 10^{- 1}$	$2.56 \times 10^{- 13}$	$30.56 \pm 8.03 %$
OX	Euclidean²	$1.25 \times 10^{- 1}$	$3.30 \times 10^{- 13}$	$29.08 \pm 7.64 %$
Single-Point Crossover	Euclidean²	$8.31 \times 10^{- 2}$	$2.62 \times 10^{- 12}$	$27.44 \pm 7.21 %$
SCX	Euclidean²	$1.28 \times 10^{- 1}$	$1.36 \times 10^{- 13}$	$39.62 \pm 8.04 %$
PMX	Manhattan	$7.78 \times 10^{- 1}$	$1.83 \times 10^{- 24}$	$21.08 \pm 5.54 %$
OX	Manhattan	$1.43 \times 10^{0}$	$2.38 \times 10^{- 22}$	$19.69 \pm 5.17 %$
Single-Point Crossover	Manhattan	$1.26 \times 10^{0}$	$2.39 \times 10^{- 22}$	$18.50 \pm 4.86 %$
SCX	Manhattan	$8.87 \times 10^{- 1}$	$2.44 \times 10^{- 24}$	$20.82 \pm 5.47 %$

Table 5. F-test and t-test confirming a statistically significant reduction in the mean value of the optimization criterion (total cost) achieved after 1000 generations for the 500-task problem and the percentage value of the criterion reduction for the new crossover compared with the previous methods with confidence intervals for a confidence level of 0.99.

Crossover Method	Cost Definition	F-Test (p)	t-Test (p)	Reduction
PMX	Euclidean	$1.84 \times 10^{- 1}$	$1.29 \times 10^{- 15}$	$14.87 \pm 3.91 %$
OX	Euclidean	$1.59 \times 10^{- 1}$	$7.62 \times 10^{- 15}$	$13.80 \pm 3.63 %$
Single-Point Crossover	Euclidean	$2.48 \times 10^{- 1}$	$6.84 \times 10^{- 16}$	$13.78 \pm 3.62 %$
SCX	Euclidean	$2.14 \times 10^{- 1}$	$6.17 \times 10^{- 16}$	$14.72 \pm 3.87 %$
PMX	Euclidean²	$3.48 \times 10^{- 1}$	$6.50 \times 10^{- 18}$	$27.22 \pm 7.15 %$
OX	Euclidean²	$1.07 \times 10^{- 1}$	$1.36 \times 10^{- 14}$	$25.89 \pm 6.80 %$
Single-Point Crossover	Euclidean²	$4.16 \times 10^{- 1}$	$1.02 \times 10^{- 17}$	$25.03 \pm 6.57 %$
SCX	Euclidean²	$1.30 \times 10^{- 1}$	$2.74 \times 10^{- 15}$	$27.31 \pm 7.17 %$
PMX	Manhattan	$1.41 \times 10^{- 1}$	$1.09 \times 10^{- 15}$	$17.55 \pm 4.61 %$
OX	Manhattan	$2.87 \times 10^{- 1}$	$3.48 \times 10^{- 17}$	$16.54 \pm 4.35 %$
Single-Point Crossover	Manhattan	$4.09 \times 10^{- 1}$	$5.82 \times 10^{- 18}$	$15.87 \pm 4.17 %$
SCX	Manhattan	$9.14 \times 10^{- 2}$	$6.14 \times 10^{- 15}$	$17.65 \pm 4.63 %$

Table 6. F-test and t-test confirming a statistically significant reduction in the mean value of the optimization criterion (total cost) achieved after 1000 generations for the 1000-task problem and the percentage value of the criterion reduction for the new crossover compared with the previous methods with confidence intervals for a confidence level of 0.99.

Crossover Method	Cost Definition	F-Test (p)	t-Test (p)	Reduction
PMX	Euclidean	$5.64 \times 10^{- 2}$	$1.63 \times 10^{- 14}$	$12.87 \pm 3.38 %$
OX	Euclidean	$1.44 \times 10^{- 1}$	$8.80 \times 10^{- 16}$	$12.48 \pm 3.28 %$
Single-Point Crossover	Euclidean	$3.69 \times 10^{- 1}$	$2.87 \times 10^{- 18}$	$12.11 \pm 3.18 %$
SCX	Euclidean	$1.73 \times 10^{- 1}$	$2.00 \times 10^{- 16}$	$12.96 \pm 3.40 %$
PMX	Euclidean²	$7.32 \times 10^{- 2}$	$5.53 \times 10^{- 14}$	$22.45 \pm 5.90 %$
OX	Euclidean²	$1.07 \times 10^{- 1}$	$2.49 \times 10^{- 14}$	$21.81 \pm 5.73 %$
Single-Point Crossover	Euclidean²	$1.82 \times 10^{- 1}$	$3.45 \times 10^{- 15}$	$21.27 \pm 5.59 %$
SCX	Euclidean²	$3.76 \times 10^{- 2}$	$1.89 \times 10^{- 13}$	$22.60 \pm 5.94 %$
PMX	Manhattan	$7.48 \times 10^{- 2}$	$1.00 \times 10^{- 15}$	$14.55 \pm 3.82 %$
OX	Manhattan	$6.31 \times 10^{0}$	$3.52 \times 10^{- 15}$	$13.99 \pm 3.67 %$
Single-Point Crossover	Manhattan	$4.49 \times 10^{- 2}$	$1.46 \times 10^{- 14}$	$13.71 \pm 3.60 %$
SCX	Manhattan	$2.56 \times 10^{- 2}$	$2.51 \times 10^{- 14}$	$14.66 \pm 3.85 %$

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2024 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Ciepliński, P.; Golak, S. Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm. Appl. Sci. 2024, 14, 11786. https://doi.org/10.3390/app142411786

AMA Style

Ciepliński P, Golak S. Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm. Applied Sciences. 2024; 14(24):11786. https://doi.org/10.3390/app142411786

Chicago/Turabian Style

Ciepliński, Piotr, and Sławomir Golak. 2024. "Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm" Applied Sciences 14, no. 24: 11786. https://doi.org/10.3390/app142411786

APA Style

Ciepliński, P., & Golak, S. (2024). Crossover Operator Inspired by the Selection Operator for an Evolutionary Task Sequencing Algorithm. Applied Sciences, 14(24), 11786. https://doi.org/10.3390/app142411786

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu