{'fraction_non_alphanumeric': 0.028540373759685846, 'fraction_numerical': 0.012517092668560008, 'mean_word_length': 5.0415166278330865, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An investigation of tuning a memetic algorithm for cross-domain search

Memetic algorithms, which hybridise evolutionary algorithms with local search, are well-known metaheuristics for solving combinatorial optimisation problems. A common issue with the application of a memetic algorithm is determining the best initial setting for the algorithmic parameters, but these can greatly influence its overall performance. Unlike traditional studies where parameters are tuned for a particular problem domain, in this study we do tuning that is applicable to cross-domain search. We extend previous work by tuning the parameters of a steady state memetic algorithm via a `design of experiments' approach and provide surprising empirical results across nine problem domains, using a cross-domain heuristic search tool, namely HyFlex. The parameter tuning results show that tuning has value for cross-domain search. As a side gain, the results suggest that the crossover operators should not be used and, more interestingly, that single point based search should be preferred over a population based search, turning the overall approach into an iterated local search algorithm. The use of the improved parameter settings greatly enhanced the cross-domain performance of the algorithm, converting it from a poor performer in previous work to one of the stronger competitors.


I. INTRODUCTION
Memetic algorithms are well-known and highly effective population-based metaheuristics. They have been applied to a range of combinatorial optimisation problems, including educational timetabling [2], [21], parallel code optimisation [22], quadratic assignment [16], vehicle routing [18], the travelling salesman problem [13], protein structure prediction [12] and knapsack problems [10]. Parameter tuning, i.e. determining the best configuration for the algorithmic parameters, is crucial for improved metaheuristic performance. There are various parameter tuning methods available, including 'design of experiments' as well as automated approaches, which have already been applied to memetic algorithms [25], [8], [7]. Many studies which tuned the algorithm parameters focused on one problem domain and tailored the algorithm for that domain. This study considers the tuning of a memetic algorithm not for a single specific domain but across multiple domains using a 'design of experiments' approach, namely the Taguchi method [24]. It is known that parameter tuning has huge value within single domain. Our aim is to investigate whether similar tuning also has value for cross-domain search. To this end, parameter tuning experiments are performed using two sample instances from four problem domains in a training phase. The best setting obtained from the Taguchi method is then generalised for cross-domain search and used to solve the unseen instances from nine different domains. The best parameter setting is analysed further in order to verify the validity of the generality of the best setting which was detected via tuning.
There is a growing number of studies on hyper-heuristics, operating on a search space of heuristics (or heuristic components) rather than directly on the search space of potential solutions [5]. Selection hyper-heuristics perform improvement oriented iterative single point based search by managing and mixing a set of low level heuristics. One of the interfaces used in this area is referred to as HyFlex (Hyper-heuristics Flexible framework) [19], which provides a framework enabling the rapid development of general purpose metaheuristics, particularly selection hyper-heuristics for research. The initial version of HyFlex was implemented in Java and used in the first Cross-Domain Heuristic Search Challenge (CHeSC2011) to detect the best selection hyper-heuristic across multiple domains [4].
In this study, we have used HyFlex, which provides all of the genetic operators required by an evolutionary algorithm [20], for the implementation and performance evaluation of a memetic algorithm. The proposed memetic algorithm is a population based stochastic local search algorithm which can be considered as a hyper-heuristic, as it does not use any domain specific information and mixes multiple operators.
Ozcan et al. [23] implemented a trans-generational and steady state memetic algorithm and investigated their performances across six problem domains. They applied a basic sequence of experiments for parameter tuning. The steady state approach was reported to perform better, however single point based search hyper-heuristics performed significantly better than memetic algorithms. In this study, we extend the previous work in [23] performing two sets of experiments. We have partitioned forty five instances across nine problem domains into training and test instances for each experiment. The problem instances consist of thirty instances from the six problem domains used at CHeSC2011 and fifteen instances from the three extended HyFlex problem domains as provided by Adriaensen et al. [1]. Firstly, Taguchi's design of experiments approach has been employed to tune the parameters of the steady state memetic algorithm from [23] considering 25 different configurations for overall performance improvement. Two training instances from each of the four HyFlex problem domains, which were initially provided as public domains at CHeSC2011, are used during the tuning process. Then, the tuned steady state memetic algorithm with the best parameter setting is applied to all other 'unseen' instances across nine problem domains. The results show that the tuned steady state memetic algorithm delivers a significantly better performance for most of the instances. The parameter setting obtained through the tuning process generalises well from the limited number of training instances to unseen instances, even from the unseen domains. Moreover, surprisingly, the tuning process detects that crossover should not be used and single point based search should be preferred rather than population based search.
The subsequent sections of this paper are organised as follows. Section II describes HyFlex, including the details of the problem domains and CHeSC2011. Our methodology is discussed in Section III. The experimental results and analysis are presented in Section IV. Finally, we summarise our findings and explain our future work in Section V.

II. HYPER-HEURISTICS FLEXIBLE FRAMEWORK (HYFLEX)
Hyper-heuristics Flexible Framework (HyFlex) is an interface proposed to enable the development, testing and comparison of both single point and population-based meta/hyperheuristics across different combinatorial optimisation problems [19]. The objective of the initial Java version of the software is to help algorithm designers to develop general purpose heuristic optimisation algorithms without requiring problem domain expertise. In HyFlex, the high-level method and problem domain layers are separated via a domain barrier [6]. Due to this barrier, the hyper-heuristic does not have access to problem specific information, such as the solution representation or details of the changes that a low-level heuristic will actually make/has made to the solution. However, problem independent information, such as the fitness (cost) value, can be passed to the algorithm [4].
HyFlex was used for the first Cross-domain Heuristic Search Challenge (CHeSC2011). HyFlex supported six problem domains for the CHeSC2011 competition, namely Maximum Satisfiability (SAT), One Dimensional Bin Packing (BP), Permutation Flow Shop (PFS), Personnel Scheduling (PS), Traveling Salesman Problems (TSP) and Vehicle Routing Problems(VRP). Each domain contains a number of instances and problem specific components. Four of those domains (SAT, BP, PFS and PS) were made available to the participants when the competition started, while the other two domains were hidden.
HyFlex has four types of low-level heuristics (operators) to modify solutions, namely, mutational (MU), ruin and recreate (RR), crossover (XO) and local search (LS) [19]. Apart from crossover, all of the other low level heuristics are parameterised. For the mutation and ruin and re-create operators, the intensity of mutation parameter determines the extent of changes that the corresponding operator will make to the input solution. The depth of search parameter controls the number of steps that the local search heuristic will complete. Both of these parameters take values in the interval [0,1], thus the mutation, ruin and re-create and local search heuristics require parameter tuning. Adriaensen et al. [1] extended the HyFlex benchmark set with the addition of 3 problem domains after CHeSC2011: 0-1 Knapsack (0-1 KP), Max-Cut (CUT), and Quadratic Assignment (QAP). All of the extended set of HyFlex domains have been formulated as minimisation problems. In this study, we have used all nine domain implementations in our experiments. The number of low-level heuristics of each type in each domain is provided in Table I.
Twenty selection hyper-heuristics competed at CHeSC2011. The winning hyper-heuristic, with an overall score of 181, was AdapHH [17], which applies an adaptive heuristic selection combined with adaptive threshold move acceptance. A subset of heuristics are used and this subset is determined adaptively. Moreover, a low level heuristic from this set is chosen using an online learning mechanism. Then, a move acceptance method called "adaptive list-based threshold accepting mechanism" is used to decide whether to accept or reject the new solution at each step. This algorithm also determines the heuristic parameter settings, adaptively. For more information about CHeSC2011, including the tools used in the competition, a tutorial on those tools, details of the competing hyperheuristics, and the results, readers can refer to the CHeSC2011 website 1 .
Adriaensen et al. [1] applied six selection hyper-heuristics to all 9 of the extended HyFlex domains. Two of those hyperheuristics were taken from CHeSC2011, namely Adap-HH and EPH (ranking the 5 th ), which are publicly available. The remaining hyper-heuristics were proposed by the authors. FS-ILS follows the iterated local search logic, applying firstly a perturbative heuristic and then a local search heuristic in a tabu-portfolio. The solution is then accepted or rejected according to the acceptance criteria. Finally, the algorithm has two choices: either performing a new iteration, or restarting the search. The second algorithm is the same but without restarting and is labelled as NR-FS-ILS. They also provided 2 simple single point based search selection hyper-heuristics: AA-HH and ANW-HH. These randomly choose a heuristic in the categories of mutation, ruin-recreate and local search Algorithm 1 : Pseudocode of Steady-state Memetic Algorithm Create a population of popsize random individuals Set the parameter values for Intensity of Mutation (IoM), Depth of Search (DoS) and tournament size (toursize) Apply a random local search method (hill climbing) to each individual while (termination criterion is not satisfied) WorstOf(population) ← Child end while and apply that heuristic to the solution. All of the new solutions are accepted in AA-HH while only non-worsening solutions are accepted in ANW-HH. In this paper we compare the performance of our approach on the additional HyFlex domains to that of these 6 hyper-heuristics.

III. METHODOLOGY
In this study, we used a steady state memetic algorithm to solve a range of problems supported by HyFlex. The steady state approach iteratively creates new individuals and considers replacement of an individual from the population with the new one [27].
The steady state memetic algorithm is implemented based on HyFlex, utilising the mutation and crossover heuristics as genetic operators and the local search heuristics that already exist within the framework for each domain. Ruin and recreate heuristics are considered as mutation heuristics in this study, increasing the available number of mutation operators. The pseudocode of our approach for solving instances from each HyFlex domain is given in Algorithm 1 [23].
The Taguchi orthogonal arrays experimental design method is employed for parameter tuning to decide the most appropriate combination of parameter values for the steady state memetic algorithm. The following steps are executed [24]: 1) Planning of experiments • Determine the control parameters (design factors) • Determine the levels of each control parameter • Select a suitable orthogonal array based on the number of parameters and their levels, forming an experimental design table 2) Conduct the experiments based on the design table 3) Analyse the results and determine the optimum levels for the individual control parameters 4) Perform a confirmation run using a combination of the optimum individual parameter levels In this study, the parameter combinations consist of four control parameters: population size, intensity of mutation (used for the mutation and ruin and re-create heuristics), depth of search (used for the local search heuristics) and tour size for the tournament selection to choose parents for operators. These are problem independent parameters and common across all of the problem domains which respect the HyFlex API. The potential values (levels) for each parameter are listed in Table  II. Testing all of the combinations for all settings would mean testing 500 configurations, however, this has been reduced to testing 25 settings using the L 25 Taguchi orthogonal array.
In related work, Sun [26] used the same technique for parameter tuning of a genetic algorithm to solve a job shop scheduling problem. In that study, parameters, including population size, crossover rate, mutation rate and stopping condition, were considered as design factors. The differences between our study and that of Sun [26] are not only that we use different design factors, but, importantly, that we also tune the parameters for cross-domain search rather than for a particular domain.

IV. EXPERIMENTAL RESULTS
In this study, two sets of experiments are performed with the goal of (i) obtaining the best parameter setting for the steady state memetic algorithm, and (ii) assessing the generalisation capability of the setting obtained from the training phase to see whether parameter tuning has value for cross-domain search. In the first set of experiments, parameter tuning of the steady state memetic algorithm is performed. 25 different parameter settings, indicated by the L 25 Taguchi orthogonal array, were tested to obtain the best configuration for the steady state memetic algorithm, using two training instances from each of the four HyFlex problem domains, which were accessible prior to CHeSC2011. Then the best setting obtained through the tuning process as well as the same 25 settings were tested using the unseen instances from each of the 9 domains.

A. Experimental Settings
Five problem instances from each of the nine HyFlex domains, including the original six and additional three problem domains, are employed during the experiments. The same competition instances as in CHeSC2011 are used for the original six domains, while arbitrarily chosen instances with IDs 1, 3, 5, 7 and 9 are used from the three extended HyFlex problem domains.
All experiments were performed on an Intel Core 3.60 GHz machine with 16 GB RAM. According to the benchmarking tool which the organisers of CHeSC2011 provided, 415 seconds on that machine are equivalent to the 600 nominal seconds used on the competition machines, so this time limit was used as the termination criterion for the algorithm, to ensure a fair comparison.
Each trial was repeated 31 times, the same as for the CHeSC2011 competition rules. The competition used 'Formula 1' scoring, where the algorithms were assessed according to the median objective values from 31 trials for each instance, and points were awarded to only the top eight algorithms for each of the instances. 10, 8, 6, 5, 4, 3, 2 and 1 point(s) were allocated for first, second, third, fourth, etc, to eighth place algorithm, respectively. The same scoring system was utilised here as a performance indicator for the algorithms and configurations tested. Ties were broken by taking the mean of the scores that the tied algorithms would take for the tied positions and assigning that value as the score for each of the tied algorithms. e.g., algorithms tied for first and second place would each get a score of 9 (i.e., the mean of 10 and 8). At the end, the sum of the scores awarded to each algorithm across all of the instances was totalled to obtain the final score.

B. Parameter Tuning
25 combinations of parameter settings for the 'intensity of mutation', 'depth of search', 'population size' and 'tournament size' of the steady state memetic algorithm were tested on 8 'training' instances, consisting of 2 arbitrarily chosen instances from 4 HyFlex domains. The L 25 orthogonal array was used to determine the parameter values for each experiment. Since the tour size has 4 levels (settings/values), one of the possible settings was assigned randomly in place of the 5th level. The parameter setting and total score of each setting calculated using Formula 1 scoring system are given in Table III. Using the results from this initial set of experiments, the average effect of each parameter setting was computed. The score of all steady state memetic algorithms with each pa-  Figure 1. Since a higher Formula 1 score would be preferred, the parameter setting that has the highest value would be predicted as the best setting for each parameter from the main effects plot. Hence, the best configuration for the steady state memetic algorithm parameters is found to be 0.2 for IoM, 1.0 for DoS and 5 for popsize. The values 2 and 5 have the same average effect for toursize parameter. However, the toursize of 5 using the best setting for the remaining parameters performs better than 2 resulting with a Formula 1 score of 75 as opposed to 69, so the toursize of 5 is included as a part of the best configuration for the steady state memetic algorithm.
Anova analysis was performed with the total normalised mean objective values over 31 runs for each instance to determine the significant factors and percentage contribution of each factor. Table IV shows that the population size and depth of search parameters significantly contribute to the performance with a confidence level of 95%. Depth of search has the highest percentage contribution of 50.68%, followed by population size, intensity of mutation and tour  size respectively. A confirmation test, using the best parameter values, was performed on the same training instances. The purpose of this validation step is to verify that the optimum parameter values obtained from the Taguchi method provide improvement over the other tested settings. We put all of the 25 configurations along with the best configuration obtained through the Taguchi method into a competition and evaluated them using the Formula 1 scoring system. The results are illustrated in Figure 2. The tuned steady state memetic algorithm with the best identified parameter setting outperforms all of the other settings with a score of 45, followed by the setting S18 with a score of 25.88.

C. Parameter Tuning Validation with Unseen Instances
The Taguchi method was applied using all fourty five instances across nine problem domains considering 25 parameter settings in order to assess the generality of the discovered best setting, and to validate the outcome of the parameter tuning experiments. Figure 3 shows the main effects plot of the parameter levels based on the experimental results. As illustrated, the best parameter combination obtained via tuning on all instances across nine domains is consistent, being 0.2 for IoM, 1.0 for DoS, 5 for popsize and 5 for toursize. This is exactly the parameter configuration which was identified using the training instances. This gives evidence for parameter tuning with the Taguchi method having value for cross-domain search.

D. Performance Comparison of SSMA-Best to Previously Proposed SSMA and TGMA
The results obtained from SSMA with the best parameter setting denoted as SSMA-Best are here compared to the memetic algorithms, denoted as SSMA and TGMA from Ozcan et al. [23]. The parameter settings for both SSMA and TGMA in [23] were: (i) population size of 10, (ii) tour size for tournament selection of 2, and (iii) intensity of mutation as well as depth of search of 0.2. Table V shows the mean, median and best fitness values for SSMA-Best, SSMA, TGMA obtained for each CHeSC2011 instance. The same instances which were used in the competition and in [23] are used here, for a fair comparison. Table V provides a comparison of the performance of SSMA-Best compared to SSMA and TGMA. The "vs." column of this table shows the results of paired one-tail Wilcoxon signed ranked test results. "<" or ">" indicate that the result on the left is "worse" or "better", respectively, than the result to the right and that this performance difference is statistically significant within a 95% confidence interval. "≤" or "≥" indicate that the difference is slightly worse or better, respectively, but that the difference is not statistically significant. For example, SSMA-Best has a better performance than SSMA for Instance 1 of SAT problem and this performance difference is statistically significant; however, SSMA-Best has a slightly better performance than TGMA for Instance 2 of VRP but this performance difference is not statistically significant.
Considering the mean performance, SSMA-Best performs better than SSMA in 27 out of the 30 CHeSC2011 instances and 26 of those cases have a statistically significant performance difference. There are only 3 cases where SSMA performs better than SSMA-Best. Similarly, SSMA-Best performs better than TGMA in 28 CHeSC2011 instances and in 25 of those cases this performance difference is significant. There are 2 instances for which TGMA performs better than SSMA-S18. SSMA-Best achieves the best fitness values for 27 out of 30 instances (being joint best in one case). SSMA performs the best for Instance 1 of TSP (joint best) and TGMA finds the best fitness values for Instances 2, 3, 5 of BP and Instance 1 of SAT and TSP (joint best).
Overall, SSMA-Best was the best performing configuration for cross-domain combinatorial optimisation (Table V). SSMA-Best was the most successful approach, particularly for SAT, PS and PFS, significantly outperforming the others on all instances. However, it did not perform well on BP.

E. Performance Comparison of Memetic Algorithms to the CHeSC2011 Competitors
The performances of SSMA, TGMA and SSMA-Best are here compared to the selection hyper-heuristics which competed in CHeSC2011, based on the Formula 1 scoring which was used there. According to the study in [23], SSMA and TGMA were among the lowest ranking algorithms, with scores of 7.5 and 0, respectively. Figure 4 provides the relative ranking of these 3 algorithms with respect to the previously described selection hyperheuristics from the competition. SSMA-Best ranked 4 th overall among the 23 algorithms while SSMA and TGMA ranked 19 th and 23 nd , respectively. Even though SSMA-Best and SSMA have the same pseudocode, the performance improvement that was obtained from parameter tuning is remarkable. Indeed, when the total score was considered for each of the domains independently, SSMA-Best was the 2 nd for TSP and PS. SSMA-Best performed particularly poorly in the SAT and BP domains, compared to the competing hyper-heuristics, receiving no points for those domains. The overall score for SSMA-Best was 103.

F. Performance Comparison of SSMA-Best to Previously Proposed Hyper-heuristics on Additional HyFlex Domains
In order to further assess the performance and the level of generality of SSMA-Best, it was tested on the 3 additional HyFlex problem domains 2 provided by Adriaensen et al. [1]. The authors compared the performance of six selection hyperheuristics in their study. Two of these hyper-heuristics were taken from the competition, namely Adap-HH and EPH. The rest of the hyper-heuristics were proposed by the authors. Table VI summarises the results and gives a performance comparison of SSMA-Best to the hyper-heuristics in [1], based on the median fitness values for each instance. For the 0-1 KP domain, AdapHH, which was the winning algorithm at CHeSC2011, performs the best overall, by producing the best median fitnesses on 3 instances (joint best in one case). For the QAP domain, NR-FS-ILS outperforms the other algorithms for 3 out of 5 instances. SSMA-Best is the best algorithm on the CUT domain. SSMA-Best manages to outperform the other algorithms in terms of median fitness on 3 CUT instances. Figure 5 illustrates the ranking of all selection hyperheuristics and SSMA-Best across the 3 additional HyFlex domains. SSMA-Best ranks second, just after AdapHH. AdapHH combines many sophisticated ideas in its design and makes use of online learning and adaptation mechanisms, thus, being the second algorithm after AdapHH is a success for SSMA-Best, since it is a generic, although tuned, metaheuristic. We emphasize at this point, that it was not tuned by considering the instances upon which it was evaluated, which would obviously be an unfair comparison.

G. Further consideration of SSMA-Best
The SSMA-Best setting considers a population size of 5 and tournament size of 5 for parent selection. The success of this configuration is surprising, since these settings mean that SSMA-Best always selects the best individual (best fitness value) in the entire population as both Parent 1 and 2. Since both parents are exactly the same individuals, after the application of a chosen crossover, the new offspring will be identical to the parents, thus the crossover does nothing. Hence, SSMA under the best setting actually performs a single point based search rather than multipoint. This implies that, for the HyFlex domains and instances, the crossover operators do not seem to have much of a positive influence on the overall performance of SSMA. Under the best settings, none of the individuals other than the best solution are used during the search process, turning the overall algorithm into an Iterated Local Search [15], where mutation is followed by local search at each step.

V. CONCLUSION AND FUTURE WORK
In this study, the steady state memetic algorithm presented in [23] is applied to 3 additional domains and is exposed to parameter tuning experiments. The Taguchi orthogonal arrays method is utilised for configuring the parameters of the memetic algorithm for cross-domain search and the performance of the tuned steady state memetic algorithm is evaluated across nine problem domains. The empirical results show that the best setting obtained from the parameter tuning experiments on two instances from four problem domains also performed the best on all instances across nine domains, validating the generality of the tuned parameters. These results support our hypothesis that parameter tuning has actual value in cross-domain search.
The tuning experiments indicate the success of the steady state memetic algorithm with a specific configuration denoted as SSMA-Best, which, significantly, outperforms the two memetic algorithm variants in [23] and even some of the competing hyper-heuristics in CHeSC2011. That metaheuristic approaches are sensitive to parameter settings is a well known fact, which is reinforced by these experiments, which also show that tuning has benefits even across domains.
The cross-domain performance improvement achieved via design of experiments is substantial. Moreover, the key observations from the empirical results are that crossover should not be used in this case and that single point based search should be preferred. The steady state memetic algorithm without the crossover operator becomes an Iterated Local Search (ILS) [15] approach, in which the solution is perturbed using a mutation operator and then local search is employed at each step. Interestingly, there are a number of previously proposed 'successful' selection hyper-heuristics that also do not benefit from the usage of crossover operators, such as [3], [9], [11], [14]. In future work, we plan to further investigate this situation, with the further use of automated parameter tuning methods.