Forward search algorithms, such as Monte Carlo Tree Search (MCTS), often struggle under the computational constraints of video games and other real-time environments. We address these issues by generating domain-specific macro-actions using evolutionary optimisation. Macro-actions—action abstractions that treat predefined sequences of discrete actions as a single action—can significantly improve the performance of forward search techniques by effectively increasing their look-ahead depth for the same computational cost. Evolved macro-actions can capture important structural aspects of a domain and substantially improve performance, even under tight computational constraints. We present an analysis of an evolved macro-action approach to decision-making with MCTS in real-time video games. We evaluate the effectiveness of this strategy across a large and diverse set of domains from the Arcade Learning Environment (ALE), and assess its generality, strengths, and limitations. Our results show that evolved macro-actions considerably improve performance across all tested domains and are particularly effective in games with a medium decision horizon and predictable dynamics.

Knowledge Graph Retrieval-Augmented Generation (KG-RAG) extends the RAG paradigm by incorporating structured knowledge from knowledge graphs, enabling Large Language Models (LLMs) to perform more precise and explainable reasoning. While KG-RAG improves factual accuracy in complex tasks, existing KG-RAG models are often severely overconfident, producing high-confidence predictions even when retrieved sub-graphs are incomplete or unreliable, which raises concerns for deployment in high-stakes domains. To address this issue, we propose Ca2KG, a Causality-aware Calibration framework for KG-RAG. Ca2KG integrates counterfactual prompting, which exposes retrieval-dependent uncertainties in knowledge quality and reasoning reliability, with a panel-based re-scoring mechanism that stabilises predictions across interventions. Extensive experiments on two complex QA datasets demonstrate that Ca2KG consistently improves calibration while maintaining or even enhancing predictive accuracy. The source code can be found at~ https://aisuko.github.io/ca2kg/.

Implicit sentiment analysis (ISA) aims to infer sentiment that is implied rather than explicitly stated, requiring models to perform deeper reasoning over subtle contextual cues. While recent prompting-based methods using large language models (LLMs) have shown promise in ISA, they often rely on majority voting over chain-of-thought (CoT) reasoning paths without evaluating their causal validity, making them susceptible to internal biases and spurious correlations. To address this challenge, we propose CAPITAL, a causal prompting framework that incorporates front-door adjustment into CoT reasoning. CAPITAL decomposes the overall causal effect into two components: the influence of the input prompt on the reasoning chains, and the impact of those chains on the final output. These components are estimated using encoder-based clustering and the NWGM approximation, with a contrastive learning objective used to better align the encoder’s representation with the LLM’s reasoning space. Experiments on benchmark ISA datasets with three LLMs demonstrate that CAPITAL consistently outperforms strong prompting baselines in both accuracy and robustness, particularly under adversarial conditions. This work offers a principled approach to integrating causal inference into LLM prompting and highlights its benefits for bias-aware sentiment reasoning. The source code and case study are available at:https://github.com/whZ62/CAPITAL.

This is an erratum for the article “Introduction to the Special Issue on Large-Scale Optimization and Learning” published in ACM Trans. Evol. Learn. Optim. 5, 4, Article 23 (December 2025), 3 pages.

Comprehensible neural network explanations are foundations for a better understanding of decisions, especially when the input data are infused with malicious perturbations. Existing solutions generally mitigate the impact of perturbations through adversarial training, yet they fail to generate comprehensible explanations under unknown perturbations. To address this challenge, we propose AGAIN, a factor graph-based interpretable neural network, which is capable of generating comprehensible explanations under unknown perturbations. Instead of retraining like previous solutions, the proposed AGAIN directly integrates logical rules by which logical errors in explanations are identified and rectified during inference. Specifically, we construct the factor graph to express logical rules between explanations and categories. By treating logical rules as exogenous knowledge, AGAIN can identify incomprehensible explanations that violate real-world logic. Furthermore, we propose an interactive intervention switch strategy rectifying explanations based on the logical guidance from the factor graph without learning perturbations, which overcomes the inherent limitation of adversarial training-based methods in defending only against known perturbations. Additionally, we theoretically demonstrate the effectiveness of employing factor graph by proving that the comprehensibility of explanations is strongly correlated with factor graph. Extensive experiments are conducted on three datasets and experimental results illustrate the superior performance of AGAIN compared to state-of-the-art baselines.

Detecting driver fatigue is critical for road safety, as drowsy driving remains a leading cause of traffic accidents. Many existing solutions rely on computationally demanding deep learning models, which result in high latency and are unsuitable for embedded robotic devices with limited resources (such as intelligent vehicles/cars) where rapid detection is necessary to prevent accidents. This paper introduces LiteFat, a lightweight spatio-temporal graph learning model designed to detect driver fatigue efficiently while maintaining high accuracy and low computational demands. LiteFat involves converting streaming video data into spatio-temporal graphs (STG) using facial landmark detection, which focuses on key motion patterns and reduces unnecessary data processing. LiteFat uses MobileNet to extract facial features and create a feature matrix for the STG. A lightweight spatio-temporal graph neural network is then employed to identify signs of fatigue with minimal processing and low latency. Experimental results on benchmark datasets show that LiteFat performs competitively while significantly reduced computational complexity and latency as compared to current state-of-the-art methods. This work advances the development of real-time, resource-efficient human fatigue detection systems that can be implemented upon embedded robotic devices.

We explored the ubiquitous phenomenon of serial scammers, each of whom deployed dozens to thousands of addresses to conduct a series of similar Rug Pulls on popular decentralized exchanges.We first constructed two datasets of around 384,000 scammer addresses behind all one-day Simple Rug Pulls on Uniswap (Ethereum) and Pancakeswap (BSC), and identified distinctive scam patterns including star, chain, and major (scam-funding) flow.These patterns, which collectively cover about 40% of all scammer addresses in our datasets, reveal typical ways scammers run multiple Rug Pulls and organize the money flow among different addresses.We then studied the more general concept of scam cluster, which comprises scammer addresses linked together via direct ETH/BNB transfers or behind the same scam pools.We found that scam token contracts are highly similar within each cluster (average similarities > 70%) and dissimilar across different clusters (average similarities < 30%), corroborating our view that each cluster belongs to the same scammer/scam organization.Lastly, we analyze the scam profit of individual scam pools and clusters, employing a novel cluster-aware profit formula that takes into account the important role of wash traders.The analysis shows that the existing formula inflates the profit by at least 32% on Uniswap and 24% on Pancakeswap.

Introduction to the Special Issue on Large-Scale Optimization and LearningMany real-world optimization problems involve a large number of decision variables.The proliferation of big-data analytic applications has led to the emergence of Large-Scale Optimization Problems (LSOP) at the heart of many data analytics and learning problems [Bottou et al., 2018;Zhou et al., 2014].The curse of dimensionality has made large-scale optimization an exceedingly difficult task, and current optimization methods are often ill-equipped to deal with such problems.To overcome this scalability issue, a wide range of mathematical, metaheuristic, and learningbased optimization algorithms have been developed [Bengio et al., 2021;Omidvar et al., 2022].For example, decomposition methods based on variable interaction analysis have been developed for black-box LSOPs that learn and exploit problem structures [Omidvar et al., 2014].Similarly, there is an emerging set of techniques that leverage Machine Learning (ML) and data mining to significantly reduce the problem size for large-scale combinatorial optimization problems [Sun et al., 2021].This sort of ML-based methods can be incorporated into an optimization algorithm to boost its performance for solving large-scale combinatorial optimization problems [Sun et al., 2022].In recent years, there has been a growing recognition of the synergy between optimization and learning.ML techniques can be used effectively to solve large-scale continuous and combinatorial problems by learning and exploiting problem structures, predicting optimal solutions using data extracted from solved problem instances, reducing problem size, and boosting the performance of existing optimization algorithms.In turn, large-scale optimization can help ML by providing the backbone for many learning algorithms and applications.For example, large-scale optimization is essential for training deep neural networks, where optimization problems with billions of decision variables need to be solved [Hinton and Salakhutdinov, 2006].Therefore, the integration of optimization and learning will play a critical role in addressing the scalability issues that arise in many real-world applications.This special issue was conceived to fill this gap in research that explores the intersection between these two fields.After a rigorous peer-review process, it is our greatest pleasure to introduce the five accepted papers in this special issue.In "Island-Based Evolutionary Computation with Diverse Surrogates and Adaptive Knowledge Transfer for High-Dimensional Data-Driven Optimization" by Xian-Rong Zhang, Yue-Jiao Gong, Zhiguang Cao, and Jun Zhang, an offline data-driven evolutionary algorithm is proposed to make use of surrogate models to approximate an objective function with only a limited amount of

This study introduces novel tunable benchmark test problems for continuous box-constrained multimodal optimization (MMO). It first introduces a new approach to control the non-uniformity of distribution of global minima, a notable challenge in MMO. Then, it builds upon an existing procedure to create composite functions in which the severity of two distinguishable groups of MMO challenges can be controlled: i) challenges shared with global optimization (GO), such as ill-conditioning, and ii) challenges specific to MMO, such as non-uniform distribution of global minima. Eight new scalable and tunable MMO functions are then proposed, based on which a test suite of 16 continuous MMO test problems is suggested. This test suite is designed to be i) comprehensive, which means they simulate most, if not all, prominent challenges associated with MMO, ii) discriminating, which means test problems can disclose the gap between the performance of diverse MMO methods, and iii) illuminating, which means test problems can reveal and compare strengths and weaknesses of MMO methods. The code of these problems is made available in two different programming languages to encourage its adoption by the research community.

Network flow optimisation has various applications such as communication, transportation, computer networks and logistics. The minimum cost flow problem (MCFP) is the most common network flow problem, which can be formulated as a multi-objective optimisation, with multiple criteria such as time, cost, distance and risk. In many real-world scenarios, decision-makers (DMs) aim for solutions in a preferred region(s). Using a reference point(s) allows the algorithm to efficiently search in the vicinity of the preferred regions instead of the entire search space. This paper introduces evolutionary multi-objective algorithms (EMOs) by employing a novel probability tree-based representation scheme (denoted as PTbNSGA-II and PTbMOEA/D) to address multi-objective integer minimum cost flow problems (MOIMCFPs) incorporating nonlinear cost functions. We also propose user-preference based EMO algorithms to solve MOIMCFPs using preference information (denoted as r-PTbNSGA-II and R-PTbMOEA/D). Since the algorithms utilise preference-based information, they have significantly lower computational costs compared to those of conventional EMOs. The performance of the proposed methods is evaluated on a set of 30 MOIMCFP instances. The experimental results demonstrate the superiority of PTbNSGA-II over PTbMOEA/D in finding high-quality solutions as well as the superiority of r-PTbNSGA-II over R-PTbMOEA/D in efficiently finding the high-quality solutions close to the preferred region.

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.

Column generation (CG) is a powerful technique for solving optimization problems that involve a large number of variables or columns. This technique begins by solving a smaller problem with a subset of columns and gradually generates additional columns as needed. However, the generation of columns often requires solving difficult subproblems repeatedly, which can be a bottleneck for CG. To address this challenge, we propose a novel method called machine learning enhanced ant colony optimization (MLACO), to efficiently generate multiple high-quality columns from a sub-problem. Specifically, we train a ML model to predict the optimal solution of a subproblem, and then integrate this ML prediction into the probabilistic model of ACO to sample multiple high-quality columns. Our experimental results on the bin packing problem with conflicts show that the MLACO method significantly improves the performance of CG compared to several state-of-the-art methods. Furthermore, when our method is incorporated into a Branch-and-Price method, it leads to a significant reduction in solution time.

Clustering in dynamic environments is of increasing importance, with broad applications ranging from real-time data analysis and online unsupervised learning to dynamic facility location problems. While meta-heuristics have shown promising effectiveness in static clustering tasks, their application for tracking optimal clustering solutions or robust clustering over time in dynamic environments remains largely underexplored. This is partly due to a lack of dynamic datasets with diverse, controllable, and realistic dynamic characteristics, hindering systematic performance evaluations of clustering algorithms in various dynamic scenarios. This deficiency leads to a gap in our understanding and capability to effectively design algorithms for clustering in dynamic environments. To bridge this gap, this paper introduces the Dynamic Dataset Generator (DDG). DDG features multiple dynamic Gaussian components integrated with a range of heterogeneous, local, and global changes. These changes vary in spatial and temporal severity, patterns, and domain of influence, providing a comprehensive tool for simulating a wide range of dynamic scenarios.

Column generation (CG) is a well-established method for solving large-scale linear programs. It involves iteratively optimizing a subproblem containing a subset of columns and using its dual solution to generate new columns with negative reduced costs. This process continues until the dual values converge to the optimal dual solution to the original problem. A natural phenomenon in CG is the heavy oscillation of the dual values during iterations, which can lead to a substantial slowdown in the convergence rate. *Stabilization* techniques are devised to accelerate the convergence of dual values by using information beyond the state of the current subproblem. However, there remains a significant gap in obtaining more accurate dual values at an earlier stage. To further narrow this gap, this paper introduces a novel approach consisting of 1) a *machine learning* approach for accurate prediction of optimal dual solutions and 2) an *adaptive stabilization* technique that effectively capitalizes on accurate predictions. On the graph coloring problem, we show that our method achieves a significantly improved convergence rate compared to traditional methods.

Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning-based variable ordering methods with conventional domain-based approaches through tie-breaking.

Multiobjectivization has emerged as a new promising paradigm to solve single-objective optimization problems (SOPs) in evolutionary computation, where an SOP is transformed into a multiobjective optimization problem (MOP) and solved by an evolutionary algorithm to find the optimal solutions of the original SOP. The transformation of an SOP into an MOP can be done by adding helper-objective(s) into the original objective, decomposing the original objective into multiple subobjectives, or aggregating subobjectives of the original objective into multiple scalar objectives. Multiobjectivization bridges the gap between SOPs and MOPs by transforming an SOP into the counterpart MOP, through which multiobjective optimization methods manage to attain superior solutions of the original SOP. Particularly, using multiobjectivization to solve SOPs can reduce the number of local optima, create new search paths from local optima to global optima, attain more incomparability solutions, and/or improve solution diversity. Since the term "multiobjectivization" was coined by Knowles et al. in 2001, this subject has accumulated plenty of works in the last two decades, yet there is a lack of systematic and comprehensive survey of these efforts. This article presents a comprehensive multifacet survey of the state-of-the-art multiobjectivization methods. Particularly, a new taxonomy of the methods is provided in this article and the advantages, limitations, challenges, theoretical analyses, benchmarks, applications, as well as future directions of the multiobjectivization methods are discussed.

Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a subproblem with a subset of columns (i.e., variables) and gradually includes new columns that can improve the solution of the current subproblem. The new columns are generated as needed by repeatedly solving a pricing problem, which is often NP-hard and is a bottleneck of the CG approach. To tackle this, we propose a Machine-Learning-based Pricing Heuristic (MLPH) that can generate many high-quality columns efficiently. In each iteration of CG, our MLPH leverages an ML model to predict the optimal solution of the pricing problem, which is then used to guide a sampling method to efficiently generate multiple high-quality columns. Using the graph coloring problem, we empirically show that MLPH significantly enhances CG as compared to six state-of-the-art methods, and the improvement in CG can lead to substantially better performance of the branch-and-price exact method.

Evolutionary multitasking (EMT) is an emerging research direction in the field of evolutionary computation. EMT solves multiple optimization tasks simultaneously using evolutionary algorithms with the aim to improve the solution for each task via intertask knowledge transfer. The effectiveness of intertask knowledge transfer is the key to the success of EMT. The multifactorial evolutionary algorithm (MFEA) represents one of the most widely used implementation paradigms of EMT. However, it tends to suffer from noneffective or even negative knowledge transfer. To address this issue and improve the performance of MFEA, we incorporate a prior-knowledge-based multiobjectivization via decomposition (MVD) into MFEA to construct strongly related meme helper-tasks. In the proposed method, MVD creates a related multiobjective optimization problem for each component task based on the corresponding problem structure or decision variable grouping to enhance positive intertask knowledge transfer. MVD can reduce the number of local optima and increase population diversity. Comparative experiments on the widely used test problems demonstrate that the constructed meme helper-tasks can utilize the prior knowledge of the target problems to improve the performance of MFEA.

The divide-and-conquer strategy has been widely used in cooperative co-evolutionary algorithms to deal with large-scale global optimization problems, where a target problem is decomposed into a set of lower-dimensional and tractable subproblems to reduce the problem complexity. However, such a strategy usually demands a large number of function evaluations to obtain an accurate variable grouping. To address this issue, a merged differential grouping (MDG) method is proposed in this article based on the subset–subset interaction and binary search. In the proposed method, each variable is first identified as either a separable variable or a nonseparable variable. Afterward, all separable variables are put into the same subset, and the nonseparable variables are divided into multiple subsets using a binary-tree-based iterative merging method. With the proposed algorithm, the computational complexity of interaction detection is reduced to$O(\max \{n,n_{ns}\times \log _{2} k\})$, where$n$,$n_{ns}(\leq n)$, and$k( < n)$indicate the numbers of decision variables, nonseparable variables, and subsets of nonseparable variables, respectively. The experimental results on benchmark problems show that MDG is very competitive with the other state-of-the-art methods in terms of efficiency and accuracy of problem decomposition.

Scalability of optimization algorithms is a major challenge in coping with the ever-growing size of optimization problems in a wide range of application areas from high-dimensional machine learning to complex large-scale engineering problems. The field of large-scale global optimization is concerned with improving the scalability of global optimization algorithms, particularly, population-based metaheuristics. Such metaheuristics have been successfully applied to continuous, discrete, or combinatorial problems ranging from several thousand dimensions to billions of decision variables. In this two-part survey, we review recent studies in the field of large-scale black-box global optimization to help researchers and practitioners gain a bird’s-eye view of the field, learn about its major trends, and the state-of-the-art algorithms. Part I of the series covers two major algorithmic approaches to large-scale global optimization: 1) problem decomposition and 2) memetic algorithms. Part II of the series covers a range of other algorithmic approaches to large-scale global optimization, describes a wide range of problem areas, and finally, touches upon the pitfalls and challenges of current research and identifies several potential areas for future research.

This article is the second part of a two-part survey series on large-scale global optimization. The first part covered two major algorithmic approaches to large-scale optimization, namely, decomposition methods and hybridization methods, such as memetic algorithms and local search. In this part, we focus on sampling and variation operators, approximation and surrogate modeling, initialization methods, and parallelization. We also cover a range of problem areas in relation to large-scale global optimization, such as multiobjective optimization, constraint handling, overlapping components, the component imbalance issue and benchmarks, and applications. The article also includes a discussion on pitfalls and challenges of the current research and identifies several potential areas of future research.

This work proposes a Bayesian optimisation with Gaussian Process approach to learn decision maker (DM) preferences in the attribute search space of a multi-objective optimisation problem (MOP). The DM is consulted periodically during optimisation of the problem and asked to provide their preference over a series of pairwise comparisons of candidate solutions. After each consultation, the most preferred solution is used as the reference point in an appropriate multiobjective optimisation evolutionary algorithm (MOEA). The rationale for using Bayesian optimisation is to identify the most preferred location in the decision search space with the least number of DM queries, thereby minimising DM cognitive burden and fatigue. This enables non-expert DMs to be involved in the optimisation process and make more informed decisions. We further reduce the number of preference queries required, by progressively redefining the Bayesian search space to reflect the MOEA's decision bounds as it converges toward the Pareto Front. We demonstrate how this approach can locate a reference point close to an unknown preferred location on the Pareto Front, of both benchmark and real-world problems with relatively few pairwise comparisons.

This paper proposes a novel primal heuristic for Mixed Integer Programs, by employing machine learning techniques. Mixed Integer Programming is a general technique for formulating combinatorial optimization problems. Inside a solver, primal heuristics play a critical role in finding good feasible solutions that enable one to tighten the duality gap from the outset of the Branch-and-Bound algorithm (B&B), greatly improving its performance by pruning the B&B tree aggressively. In this paper, we investigate whether effective primal heuristics can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Convolutional Network on solved problem instances with known optimal solutions. This in turn can predict the values of decision variables in the optimal solution for an unseen problem instance of a similar type. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search (PB-DFS) approach, aiming to find (near-)optimal solutions quickly. The experimental results show that this new heuristic can find better primal solutions at a much earlier stage of the solving process, compared to other state-of-the-art primal heuristics.

In this article, we investigate problem reduction techniques using stochastic sampling and machine learning to tackle large-scale optimization problems. These techniques heuristically remove decision variables from the problem instance, that are not expected to be part of an optimal solution. First we investigate the use of statistical measures computed from stochastic sampling of feasible solutions compared with features computed directly from the instance data. Two measures are particularly useful for this: 1) a ranking-based measure, favoring decision variables that frequently appear in high-quality solutions; and 2) a correlation-based measure, favoring decision variables that are highly correlated with the objective values. To take this further we develop a machine learning approach, called Machine Learning for Problem Reduction (MLPR), that trains a supervised learning model on easy problem instances for which the optimal solution is known. This gives us a combination of features enabling us to better predict the decision variables that belong to the optimal solution for a given hard problem. We evaluate our approaches using a typical optimization problem on graphs-the maximum weight clique problem. The experimental results show our problem reduction techniques are very effective and can be used to boost the performance of existing solution methods.

Feature selection has been shown to be beneficial for many data mining and machine learning tasks, especially for big data analytics. Mutual Information (MI) is a well-known information-theoretic approach used to evaluate the relevance of feature subsets and class labels. However, estimating high-dimensional MI poses significant challenges. Consequently, a great deal of research has focused on using low-order MI approximations or computing a lower bound on MI called Variational Information (VI). These methods often require certain assumptions made on the probability distributions of features such that these distributions are realistic yet tractable to compute. In this paper, we reveal two sets of distribution assumptions underlying many MI and VI based methods: Feature Independence Distribution and Geometric Mean Distribution. We systematically analyze their strengths and weaknesses and propose a logical extension called Arithmetic Mean Distribution, which leads to an unbiased and normalised estimation of probability densities. We conduct detailed empirical studies across a suite of 29 real-world classification problems and illustrate improved prediction accuracy of our methods based on the identification of more informative features, thus providing support for our theoretical findings.

Multi-modal journey planning, which allows multiple modes of transport to be used within a single trip, is becoming increasingly popular, due to a vast practical interest and the increasing availability of data. In real-life situations, transport networks often involve uncertainty, and yet, most approaches assume a deterministic environment, making plans more prone to failures such as significant delays in the arrival or waiting for a long time at stations. In this paper, we tackle the multi-criteria stochastic journey planning problem in multi-modal transportation networks. We consider the problem as a probabilistic conditional planning problem, and we use Markov Decision Processes to model the problem. Journey plans are optimised simultaneously against five criteria, namely: travel time, journey convenience, monetary cost, CO2, and personal energy expenditure (PEE). We develop an NSGA-III-based solver as a baseline search method for producing optimal policies for travelling from a given origin to a given destination. Our empirical evaluation uses Melbourne transportation network using probabilistic density functions for estimated departure/arrival time of the trips. Numerical results demonstrate the effectiveness of the proposed method for practical purposes and provide strong evidence in favour of contingency planning for journey planning problem.

This paper presents a new method to automatically decompose general Mixed Integer Programs (MIPs). To do so, we represent the constraint matrix for a general MIP problem as a hypergraph and relax constraints by removing hyperedges from the hypergraph. A Breadth First Search algorithm is used to identify the individual partitions that now exist and the resulting decomposed problem. We propose that good decompositions have both a small number of constraints relaxed and small subproblems in terms of the number of variables they contain. We use the multiobjective Nondominated Sorting Genetic Algorithm II (NSGA-II) to create decompositions which minimize both the size of the subproblems and the number of constraints relaxed. We show through our experiments the types of decompositions our approach generates and test empirically the effectiveness of these decompositions in producing bounds when used in a Lagrangian Relaxation framework. The results demonstrate that the bounds generated by our decompositions are significantly better than those attained by solving the Linear Programming relaxation, as well as the bounds found via random and greedy constraint relaxation and decomposition generation.

Multiobjective evolutionary algorithms based on decomposition (MOEA/D) have attracted tremendous attention and achieved great success in the fields of optimization and decision-making. MOEA/Ds work by decomposing the target multiobjective optimization problem (MOP) into multiple single-objective subproblems based on a set of weight vectors. The subproblems are solved cooperatively in an evolutionary algorithm framework. Since weight vectors define the search directions and, to a certain extent, the distribution of the final solution set, the configuration of weight vectors is pivotal to the success of MOEA/Ds. The most straightforward method is to use predefined and uniformly distributed weight vectors. However, it usually leads to the deteriorated performance of MOEA/Ds on solving MOPs with irregular Pareto fronts. To deal with this issue, many weight vector adjustment methods have been proposed by periodically adjusting the weight vectors in a random, predefined, or adaptive way. This article focuses on weight vector adjustment on a simplex and presents a comprehensive survey of these weight vector adjustment methods covering the weight vector adaptation strategies, theoretical analyses, benchmark test problems, and applications. The current limitations, new challenges, and future directions of weight vector adjustment are also discussed.

Theme parks visits can be very playful events for families, however, waiting in the ride’s queues can often be the cause of great frustration. We developed a novel augmented reality game to be played in the theme park’s queue, and an in-the-wild study with X participants using log data and interviews demonstrated that every minute playing was perceived to the same extent of about 5 minutes of not playing the game. We articulate a design space for researchers and strategies for game designers aiming to reduce perceived waiting time in queues. With our work, we hope to extend how we use games in everyday life to make our lives more playful.

In this paper we use a divide-and-conquer approach to tackle large-scale optimization problems with overlapping components. Decomposition for an overlapping problem is challenging as its components depend on one another. The existing decomposition methods typically assign all the linked decision variables into one group, thus cannot reduce the original problem size. To address this issue we modify the Recursive Differential Grouping (RDG) method to decompose overlapping problems, by breaking the linkage at variables shared by multiple components. To evaluate the efficacy of our method, we extend two existing overlapping benchmark problems considering various level of overlap. Experimental results show that our method can greatly improve the search ability of an optimization algorithm via divide-and-conquer, and outperforms RDG, random decomposition as well as other state-of-the-art methods. We further evaluate our method using the CEC’2013 benchmark problems and show that our method is very competitive when equipped with a component optimizer.

Using evolutionary algorithms to solve optimisation problems with multiple objectives has proven very successful over the past few decades. The ability of these methods to efficiently find sets of solutions representing trade-offs between conflicting objectives has enhanced decision making in a wide variety of fields. Increasingly though, such techniques are being adapted to incorporate end-user preferences in order to reduce search spaces and provide smaller sets of targeted solutions. Eliciting these preferences interactively during optimisation has also become popular and helps a decision maker explore and learn and the problem and its range of solutions. Interactivity also facilitates the correction of mistakes and inaccurate preferences, leading to more satisfactory solutions, faster. In order to achieve these benefits an algorithm must be able to rapidly respond to changes in preferences. This work explores the use of secondary population archives to ensure a preference-based algorithm can change its search focus efficiently and effectively. When preferences change and the search is redirected to a new region of interest, an archive of previously found solutions can be consulted and solutions close to the new region can be included in the current population. This work shows how such archives can be implemented and how they can improve responsiveness for certain problems.

Conventional mixed-integer programming (MIP) solvers can struggle with many large-scale combinatorial problems, as they contain too many variables and constraints. Meta-heuristics can be applied to reduce the size of these problems by removing or aggregating variables or constraints. Merge search algorithms achieve this by generating populations of solutions, either by heuristic construction [4], or by finding neighbours to an initial solution [12]. This paper presents a merge search algorithm that improves the population generation heuristic in [12] and utilises a variable grouping heuristic that exploits the common information across a population to aggregate groups of variables in order to create a reduced subproblem. The algorithm is tested on some well known benchmarks for a complex problem called the constrained pit (CPIT) problem and it is compared to results produced by a merge search algorithm previously used on the same problem and the results published on the minelib [9] website.

The first cooperative co-evolutionary algorithm (CCEA) was proposed by Potter and De Jong in 1994 and since then many CCEAs have been proposed and successfully applied to solving various complex optimization problems. In applying CCEAs, the complex optimization problem is decomposed into multiple subproblems, and each subproblem is solved with a separate subpopulation, evolved by an individual evolutionary algorithm (EA). Through cooperative co-evolution of multiple EA subpopulations, a complete problem solution is acquired by assembling the representative members from each subpopulation. The underlying divide-and-conquer and collaboration mechanisms enable CCEAs to tackle complex optimization problems efficiently, and hence CCEAs have been attracting wide attention in the EA community. This paper presents a comprehensive survey of these CCEAs, covering problem decomposition, collaborator selection, individual fitness evaluation, subproblem resource allocation, implementations, benchmark test problems, control parameters, theoretical analyses, and applications. The unsolved challenges and potential directions for their solutions are discussed.

Cooperative co-evolution (CC) is an effective framework that can be used to solve large-scale optimization problems. It typically divides a problem into components and uses one optimizer to solve the components in a round-robin fashion. However the relative contribution of each component to the overall fitness value may vary. Furthermore, using one optimizer may not be sufficient when solving a wide range of components with different characteristics. In this paper, we propose a novel CC framework which can select an appropriate optimizer to solve a component based on its contribution to the fitness improvement. In each evolutionary cycle, the candidate optimizer and component that make the greatest contribution to the fitness improvement are selected for evolving. We evaluated the efficacy of the proposed CC with Optimizer Selection (CCOS) algorithm using large-scale benchmark problems. The numerical experiments showed that CCOS outperformed the CC model without optimizer selection ability. When compared against several other state-of-the-art algorithms, CCOS generated competitive solution quality.

Problem decomposition plays an essential role in the success of cooperative co-evolution (CC), when used for solving large-scale optimization problems. The recently proposed recursive differential grouping (RDG) method has been shown to be very efficient, especially in terms of time complexity. However, it requires an appropriate parameter setting to estimate a threshold value in order to determine if two subsets of decision variables interact or not. Furthermore, using one global threshold value may be insufficient to identify variable interactions in components with different contribution to the fitness value. Inspired by the different grouping 2 (DG2) method, in this paper, we adaptively estimates a threshold value based on computational round-off errors for RDG. We derive an upper bound of the round-off errors, which is shown to be sufficient when identifying variable interactions across a wide range of large-scale benchmark problems. Comprehensive numerical experimental results showed that the proposed RDG2 method achieved higher decomposition accuracy than RDG and DG2. When embedded into a CC framework, it achieved statistically equal or significantly better solution quality than RDG and DG2, when used to solve the benchmark problems.

Multi-modal journey planning, which allows multiple modes of transport to be used within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life situations, transport networks often involve uncertainty, and yet, most approaches assume a deterministic environment, making plans more prone to failures such as major delays in the arrival or waiting for a long time at stations. In this paper, we tackle the multi-objective stochastic journey planning problem in multi-modal transportation networks. The problem is modeled as a Markov decision process with two objective functions: expected arrival time and journey convenience. We develop a GA-based MDP solver as a baseline search method for producing optimal policies for traveling from a given origin to a given destination. Our empirical evaluation uses Melbourne transportation network using probabilistic density functions for estimated departure/arrival time of the trips. Numerical results suggest that the proposed method is effective for practical purposes and provide strong evidence in favor of switching from deterministic to non-deterministic planning.

Many large-scale combinatorial problems contain too many variables and constraints for conventional mixed-integer programming (MIP) solvers to manage. To make the problems easier for the solvers to handle, various meta-heuristic techniques can be applied to reduce the size of the search space, by removing, or aggregating, variables and constraints. A novel meta-heuristic technique is presented in this paper called merge search, which takes an initial solution and uses the information from a large population of neighbouring solutions to determine promising areas of the search space to focus on. The population is merged to produce a restricted sub-problem, with far fewer variables and constraints, which can then be solved by a MIP solver. Merge search is applied to a complex problem from open-pit mining called the constrained pit (CPIT) problem, and compared to current state-of-the-art results on well known benchmark problems minelib [7] and is shown to give better quality solutions in five of the six instances.

For optimisation problems with multiple objectives and large search spaces, it may not be feasible to find all optimal solutions. Even if possible, a decision maker (DM) is only interested in a small number of these solutions. Incorporating a DM's solution preferences into the process reduces the problem's search space by focusing only on regions of interest. Allowing a DM to interact and alter their preferences during a single optimisation run facilitates learning and mistake correction, and improves the search for desired solutions. In this paper, we apply an interactive framework to four leading multi-objective evolutionary algorithms (MOEAs), which use reference points to model preferences. Furthermore, we propose a new performance metric for algorithm responsiveness to preference changes, and evaluate these algorithms using this metric. Interactive algorithms must respond to changes in DM preferences and we show how our new metric is able to differentiate between the four algorithms when run on the ZDT suite of test problems. Finally, we identify characteristics of these methods that determine their level of response to change.

For a large-scale global optimization (LSGO) problem, divide-and-conquer is usually considered an effective strategy to decompose the problem into smaller subproblems, each of which can then be solved individually. Among these decomposition methods, variable grouping is shown to be promising in recent years. Existing variable grouping methods usually assume the problem to be black-box (i.e., assuming that an analytical model of the objective function is unknown), and they attempt to learn appropriate variable grouping that would allow for a better decomposition of the problem. In such cases, these variable grouping methods do not make a direct use of the formula of the objective function. However, it can be argued that many real-world problems are white-box problems, that is, the formulas of objective functions are often known a priori. These formulas of the objective functions provide rich information which can then be used to design an effective variable group method. In this article, a formula-based grouping strategy (FBG) for white-box problems is first proposed. It groups variables directly via the formula of an objective function which usually consists of a finite number of operations (i.e., four arithmetic operations “[Formula: see text]”, “[Formula: see text]”, “[Formula: see text]”, “[Formula: see text]” and composite operations of basic elementary functions). In FBG, the operations are classified into two classes: one resulting in nonseparable variables, and the other resulting in separable variables. In FBG, variables can be automatically grouped into a suitable number of non-interacting subcomponents, with variables in each subcomponent being interdependent. FBG can easily be applied to any white-box problem and can be integrated into a cooperative coevolution framework. Based on FBG, a novel cooperative coevolution algorithm with formula-based variable grouping (so-called CCF) is proposed in this article for decomposing a large-scale white-box problem into several smaller subproblems and optimizing them respectively. To further enhance the efficiency of CCF, a new local search scheme is designed to improve the solution quality. To verify the efficiency of CCF, experiments are conducted on the standard LSGO benchmark suites of CEC'2008, CEC'2010, CEC'2013, and a real-world problem. Our results suggest that the performance of CCF is very competitive when compared with those of the state-of-the-art LSGO algorithms.

Reinforcement learning (RL) is a machine learning paradigm behind many successes in games, robotics, and control applications. RL agents improve through trial-and-error, therefore undergoing a learning phase during which they perform suboptimally. Research effort has been put into optimizing behavior during this period, to reduce its duration and to maximize after-learning performance. We introduce a novel algorithm that extracts useful information from expert demonstrations (traces of interactions with the target environment) and uses it to improve performance. The algorithm detects unexpected decisions made by the expert and infers what goal the expert was pursuing. Goals are then used to bias decisions while learning. Our experiments in the video game Pac-Man provide statistically significant evidence that our method can improve final performance compared to a state-of-the-art approach.

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method.

Balancing exploration and exploitation according to evolutionary states is crucial to meta-heuristic search (M-HS) algorithms. Owing to its simplicity in theory and effectiveness in global optimization, gravitational search algorithm (GSA) has attracted increasing attention in recent years. However, the tradeoff between exploration and exploitation in GSA is achieved mainly by adjusting the size of an archive, named , which stores those superior agents after fitness sorting in each iteration. Since the global property of remains unchanged in the whole evolutionary process, GSA emphasizes exploitation over exploration and suffers from rapid loss of diversity and premature convergence. To address these problems, in this paper, we propose a dynamic neighborhood learning (DNL) strategy to replace the model and thereby present a DNL-based GSA (DNLGSA). The method incorporates the local and global neighborhood topologies for enhancing the exploration and obtaining adaptive balance between exploration and exploitation. The local neighborhoods are dynamically formed based on evolutionary states. To delineate the evolutionary states, two convergence criteria named limit value and population diversity, are introduced. Moreover, a mutation operator is designed for escaping from the local optima on the basis of evolutionary states. The proposed algorithm was evaluated on 27 benchmark problems with different characteristic and various difficulties. The results reveal that DNLGSA exhibits competitive performances when compared with a variety of state-of-the-art M-HS algorithms. Moreover, the incorporation of local neighborhood topology reduces the numbers of calculations of gravitational force and thus alleviates the high computational cost of GSA.

Finding an optimal design for a truss structure involves optimizing its topology, size, and shape. A truss design problem is usually multimodal, meaning that the problem offers multiple optimal designs in terms of topology and/or size of the members, but they are evaluated to have similar or equally good objective function values. From a practical standpoint, it is desirable to find as many alternative designs as possible, rather than finding a single design, as often practiced. A few metaheuristics based methods with niching techniques have been used for finding multiple topologies for the truss design problem, but these studies have ignored any emphasis in finding multiple solutions in terms of size. To overcome this issue, this paper proposes to formulate the truss problem as a bilevel optimization problem, where stable topologies can be found in the upper level and the optimized sizes of the members of these topologies can be found in the lower level. As a result, a new bilevel niching method is proposed to find multiple optimal solutions for topology level as well as for the size level simultaneously. The proposed method is shown to be superior over the state-of-the-art methods on several benchmark truss-structure design problems.

Pit planning and long-term production scheduling are important tasks within the mining industry. This is a great opportunity for optimisation techniques, as the scale of a lot of mining operations means that a small percentage increase in efficiency can translate to millions of dollars in profit. The precedence constrained production scheduling problem (PCPSP) combines both of these aspects of mine optimisation and aims to find a solution which tells a mining company what part of the orebody to mine, and at what time during the life of the mine. This paper presents a GRASP-Mixed Integer Programming hybrid metaheuristic algorithm for solving the PCPSP which consists of two parts: a fast, period-by-period, random construction phase and a local improvement heuristic. It is compared to the current published state-of-the-art results on well known benchmark problems from minelib [5] and is shown to give better quality results in four of the six instances, and within 2% of the LP upper bound in the remaining two. The PCPSP is a good candidate for hybrid metaheuristics as the size of the problems make solving them with mathematical solvers alone intractable.

The capacitated arc routing problem (CARP) is a challenging optimization problem with lots of applications in the real world. Numerous approaches have been proposed to tackle this problem. Most of these methods, albeit showing good performance on CARP instances of small and median sizes, do not scale well to large-scale CARPs, e.g., taking at least a few hours to achieve a satisfactory solution on a CARP instance with thousands of tasks. In this paper, an efficient and scalable approach is proposed for CARPs. The key idea of the proposed approach is to hierarchically decompose the tasks involved in a CARP instance into subgroups and solve the induced subproblems recursively. The output of the subproblems at the lower layer in the hierarchy is treated as virtual tasks and new subproblems are formulated based on these virtual tasks using clustering techniques. By this means, the number of tasks (or virtual tasks) decreases rapidly from the bottom to the top layers of the hierarchy, and the sizes of all subproblems at each layer can be kept tractable even for very large-scale CARPs. Empirical studies are conducted on CARP instances with up to 3584 tasks, which are an order of magnitude larger than the number of tasks involved in all CARP instances investigated in the literature. The results show that the proposed approach significantly outperforms existing methods in terms of scalability. Since the proposed hierarchical decomposition scheme is designed to obtain a good permutation of tasks in a CARP instance, it may also be generalized to other hard optimization problems that can be formulated as permutation-based optimization problems.

Multimodal optimization (MMO) aiming to locate multiple optimal (or near-optimal) solutions in a single simulation run has practical relevance to problem solving across many fields. Population-based meta-heuristics have been shown particularly effective in solving MMO problems, if equipped with specifically-designed diversity-preserving mechanisms, commonly known as niching methods. This paper provides an updated survey on niching methods. This paper first revisits the fundamental concepts about niching and its most representative schemes, then reviews the most recent development of niching methods, including novel and hybrid methods, performance measures, and benchmarks for their assessment. Furthermore, this paper surveys previous attempts at leveraging the capabilities of niching to facilitate various optimization tasks (e.g., multiobjective and dynamic optimization) and machine learning tasks (e.g., clustering, feature selection, and learning ensembles). A list of successful applications of niching methods to real-world problems is presented to demonstrate the capabilities of niching methods in providing solutions that are difficult for other optimization methods to offer. The significant practical value of niching methods is clearly exemplified through these applications. Finally, this paper poses challenges and research questions on niching that are yet to be appropriately addressed. Providing answers to these questions is crucial before we can bring more fruitful benefits of niching to real-world problem solving.

Identification of variable interaction is essential for an efficient implementation of a divide-and-conquer algorithm for large-scale black-box optimization. In this paper, we propose an improved variant of the differential grouping (DG) algorithm, which has a better efficiency and grouping accuracy. The proposed algorithm, DG2, finds a reliable threshold value by estimating the magnitude of roundoff errors. With respect to efficiency, DG2 reuses the sample points that are generated for detecting interactions and saves up to half of the computational resources on fully separable functions. We mathematically show that the new sampling technique achieves the lower bound with respect to the number of function evaluations. Unlike its predecessor, DG2 checks all possible pairs of variables for interactions and has the capacity to identify overlapping components of an objective function. On the accuracy aspect, DG2 outperforms the state-of-the-art decomposition methods on the latest large-scale continuous optimization benchmark suites. DG2 also performs reliably in the presence of imbalance among contribution of components in an objective function. Another major advantage of DG2 is the automatic calculation of its threshold parameter ($\epsilon $ ), which makes it parameter-free. Finally, the experimental results show that when DG2 is used within a cooperative co-evolutionary framework, it can generate competitive results as compared to several state-of-the-art algorithms.

Cooperative co-evolution (CC) is an explicit means of problem decomposition in multipopulation evolutionary algorithms for solving large-scale optimization problems. For CC, subpopulations representing subcomponents of a large-scale optimization problem co-evolve, and are likely to have different contributions to the improvement of the best overall solution to the problem. Hence, it makes sense that more computational resources should be allocated to the subpopulations with greater contributions. In this paper, we study how to allocate computational resources in this context and subsequently propose a new CC framework named CCFR to efficiently allocate computational resources among the subpopulations according to their dynamic contributions to the improvement of the objective value of the best overall solution. Our experimental results suggest that CCFR can make efficient use of computational resources and is a highly competitive CCFR for solving large-scale optimization problems.

Cooperative Co-evolution (CC) is a promising framework for solving large-scale optimization problems. However, the round-robin strategy of CC is not an efficient way of allocating the available computational resources to components of imbalanced functions. The imbalance problem happens when the components of a partially separable function have non-uniform contributions to the overall objective value. Contribution-Based Cooperative Co-evolution (CBCC) is a variant of CC that allocates the available computational resources to the individual components based on their contributions. CBCC variants (CBCC1 and CBCC2) have shown better performance than the standard CC in a variety of cases. In this paper, we show that over-exploration and over-exploitation are two major sources of performance loss in the existing CBCC variants. On that basis, we propose a new contribution-based algorithm that maintains a better balance between exploration and exploitation. The empirical results show that the new algorithm is superior to its predecessors as well as the standard CC.

Q-learning associates states and actions of a Markov Decision Process to expected future reward through online learning. In practice, however, when the state space is large and experience is still limited, the algorithm will not find a match between current state and experience unless some details describing states are ignored. On the other hand, reducing state information affects long term performance because decisions will need to be made on less informative inputs. We propose a variation of Q-learning that gradually enriches state descriptions, after enough experience is accumulated. This is coupled with an ad-hoc exploration strategy that aims at collecting key information that allows the algorithm to enrich state descriptions earlier. Experimental results obtained by applying our algorithm to the arcade game Pac-Man show that our approach significantly outperforms Q-learning during the learning process while not penalizing long-term performance.

The Steiner tree problem in graphs (STPG) is a well known NP-hard combinatorial problem with various applications in transport, computational biology, network and VLSI design. Exact methods have been developed to solve this problem to proven optimality, however the exponential nature of these algorithms mean that they become intractable with large-scale instances of the problem. Because of this phenomenon, there has been considerable research into using metaheuristics to obtain good quality solutions in a reasonable time. This paper presents a hybrid local search technique which is an extension of techniques from the literature with an added random jump operator which prevents the algorithm from becoming stuck in local minima. It is compared against greedy local search, the hybrid local search technique it extends and two metaheuristic techniques from the current literature and is shown to outperform them in nearly all cases.

In this paper we present a challenging problem that many decision makers in coal mining industry face. The coal processing and blending problem (CPBP) builds upon the traditional blending problem known in operations research (OR) by including decision variables around coal processing, novel constraints as well as arbitrary user-defined profit functions which express price bonuses and penalties. The added complexity turns the traditional blending problem into a challenging black-box optimisation problem. We give an informal and mathematical description of this problem and present nine real-world problem instances as benchmark. Finally, we provide preliminary results for solving the problem by using a Genetic Algorithm (GA) and compare the results with those from a commercial Linear Programming (LP) solver. The results show that the GA significantly outperforms the LP solver in many problem instances while being marginally worse in others.

The International Classification of Diseases (ICD) is a type of meta-data found in many Electronic Patient Records. Research to explore the utility of these codes in medical Information Retrieval (IR) applications is new, and many areas of investigation remain, including the question of how reliable the assignment of the codes has been. This paper proposes two uses of the ICD codes in two different contexts of search: Pseudo-Relevance Judgments (PRJ) and Pseudo-Relevance Feedback (PRF). We find that our approach to evaluate the TREC challenge runs using simulated relevance judgments has a positive correlation with the TREC official results, and our proposed technique for performing PRF based on the ICD codes significantly outperforms a traditional PRF approach. The results are found to be consistent over the two years of queries from the TREC medical test collection.

Abstract In this paper, the interdependence between sub-problems in a complex overall problem is investigated using a benchmark problem called Travelling Thief Problem (TTP), which is a combination of Travelling Salesman Problem (TSP) and Knapsack Problem (KP). First, the analysis on the mathematical formulation shows that it is impossible to decompose the problem into independent sub-problems due to the non-linear relationship in the objective function. Therefore, the algorithm for TTP is not straightforward although each sub-problem alone has been investigated intensively. Then, two meta-heuristics are proposed for TTP. One is the Cooperative Co-evolution (CC) that solves the sub-problems separately and transfers the information between them in each generation. The other is the Memetic Algorithm (MA) that solves TTP as a whole. The comparative results showed that MA consistently obtained much better results than both the standard and dynamic versions of CC within comparable computational budget. This indicates the importance of considering the interdependence between sub-problems in an overall problem like TTP.

In particle swarm optimization (PSO), the inertia weight is an important parameter for controlling its search capability. There have been intensive studies of the inertia weight in continuous optimization, but little attention has been paid to the binary case. This paper comprehensively investigates the effect of the inertia weight on the performance of binary PSO (BPSO), from both theoretical and empirical perspectives. A mathematical model is proposed to analyze the behavior of BPSO, based on which several lemmas and theorems on the effect of the inertia weight are derived. Our research findings suggest that in the binary case, a smaller inertia weight enhances the exploration capability while a larger inertia weight encourages exploitation. Consequently, this paper proposes a new adaptive inertia weight scheme for BPSO. This scheme allows the search process to start first with exploration and gradually move toward exploitation by linearly increasing the inertia weight. The experimental results on 0/1 knapsack problems show that the BPSO with the new increasing inertia weight scheme performs significantly better than that with the conventional decreasing and constant inertia weight schemes. This paper verifies the efficacy of increasing inertia weight in BPSO.

This article proposes a competitive divide-and-conquer algorithm for solving large-scale black-box optimization problems for which there are thousands of decision variables and the algebraic models of the problems are unavailable. We focus on problems that are partially additively separable, since this type of problem can be further decomposed into a number of smaller independent subproblems. The proposed algorithm addresses two important issues in solving large-scale black-box optimization: (1) the identification of the independent subproblems without explicitly knowing the formula of the objective function and (2) the optimization of the identified black-box subproblems. First, a Global Differential Grouping (GDG) method is proposed to identify the independent subproblems. Then, a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is adopted to solve the subproblems resulting from its rotation invariance property. GDG and CMA-ES work together under the cooperative co-evolution framework. The resultant algorithm, named CC-GDG-CMAES, is then evaluated on the CEC’2010 large-scale global optimization (LSGO) benchmark functions, which have a thousand decision variables and black-box objective functions. The experimental results show that, on most test functions evaluated in this study, GDG manages to obtain an ideal partition of the index set of the decision variables, and CC-GDG-CMAES outperforms the state-of-the-art results. Moreover, the competitive performance of the well-known CMA-ES is extended from low-dimensional to high-dimensional black-box problems.

Cooperative Co-evolutionary (CC) techniques have demonstrated the promising performance in dealing with large-scale optimization problems. However, in many applications, their performance may drop due to the presence of imbalanced contributions to the objective function value from different subsets of decision variables. To remedy this drawback, Contribution-Based Cooperative Co-evolutionary (CBCC) algorithms have been proposed. They have presented significant improvements over traditional CC techniques when the decomposition is accurate and the imbalance level is very high. However, in real-world scenarios, we might not have the knowledge about the ideal decomposition and actual imbalance level of a problem to be solved. Therefore, this study aims at analysing the performance of existing CBCC techniques in more realistic settings, i.e., when the decomposition error is unavoidable and the imbalance level is low or moderate. Our in-depth analysis reveals that even in these situations, CBCC algorithms are superior alternatives to traditional CC techniques. We also observe that the variations of CBCC techniques may lead to the significantly different performance. Thus, we recommend practitioners to carefully choose a competent variant of CBCC which best suits their particular applications.

In many real-world applications, one needs to deal with a large multi-silo problem with interdependent silos. In order to investigate the interdependency between silos (subproblems), the Traveling Thief Problem (TTP) was designed as a benchmark problem. TTP is a combination of two well-known sub-problems, Traveling Salesman Problem (TSP) and Knapsack Problem (KP). Although each sub-problem has been intensively investigated, the interdependent combination has been demonstrated to be challenging, and cannot be solved by simply solving the sub-problems separately. The Two-Stage Memetic Algorithm (TSMA) is an effective approach that has decent solution quality and scalability, which consists of a tour improvement stage and an item picking stage. Unlike the traditional TSP local search operators adopted in the former stage, the heuristic for the latter stage is rather intuitive. To further investigate the effect of item picking heuristic, Genetic Programming (GP) is employed to evolve a gain function and a picking function, respectively. The resultant two heuristics were tested on some representative TTP instances, and showed competitive performance, which indicates the potential of evolving more promising heuristics for solving TTP more systematically by GP.

MOEA/D is an evolutionary multi-objective optimization algorithm, which relies on decomposition methods such as, weighted-sum, Tchebycheff and Penalty-based Boundary Intersection (PBI) to convert a multi-objective problem into a set of single-objective problems. It is known that PBI can generate a more uniform set of solutions than the other decomposition methods. The drawback of PBI is that it has a penalty parameter (θ) that has to be specified by the user. This penalty parameter can affect the convergence rate of MOEA/D as well as the uniformity of solutions. Unfortunately, there are very limited studies on sensitivity analysis of MOEA/D on the penalty parameter of PBI. This paper is dedicated to a comprehensive analysis of PBI's penalty parameter, and its effect on a user-preference algorithm (R-MEAD2) and a non-user-preference algorithm (MOEA/D). Unlike the previous studies that only rely on Hypervolume as their performance measure, we study the effect of θ on convergence, uniformity, and the combination of convergence and uniformity independently. The experimental results suggest that user-preference algorithms consistently perform better with a relatively larger θ value as compared to their non-user-preference counterparts. The results also suggest that on some problems, such as multi-modal functions, convergence is the dominant factor on the overall performance, where a smaller θ is preferable. Conversely, on some other problems, a larger θ is suggested where uniformity is the dominant factor. Finally, we briefly investigate the relationship between θ and the number of objectives.

The Storage Location Assignment Problem (SLAP) is a significant optimisation problem in warehouse management. Given a number of products, each with a set of items with different popularities (probabilities of being ordered), SLAP is to find the best locations for the items of the products in the warehouse to minimise the warehouse operational cost. Specifically, the operational cost is the expected cost of picking the orders. Grouping constraints are included to take the practical considerations into account in the problem. That is, the items belonging to the same product are more desirable to be placed together. In this paper, the SLAP with Grouping Constraints (SLAP-GC) is investigated, and an efficient Restricted Neighbourhood Tabu Search (RNTS) algorithm is proposed to solving it. RNTS adopts the problem-specific search operators to maintain solution feasibility, and the tabu list to prevent searching back and forth. RNTS was empirically compared with the mathematical programming method and a previously designed Genetic Programming method, which is demonstrated to be the state-of-the-art algorithm for SLAP-GC. The experimental results on the real-world data show that RNTS outperforms the state-of-the-art algorithms for SLAP-GC in terms of solution quality and speed. It managed to achieve optimal solutions for most of the small-scale instances much faster and outperformed the Genetic Programming method in terms of both solution quality and running time on all the test instances.

This paper proposes an improved performance metric for multiobjective evolutionary algorithms with user preferences. This metric uses the idea of decomposition to transform the preference information into m+1 points on a constructed preference-based hyperplane, then calculates the Euclidean distances and the angles between the obtained solutions by algorithms and those obtained m+1 points, respectively. By means of these distances and angles, the proposed metric can evaluate effectively both the convergence and diversity of the obtained solution set, with consideration of the preference information. This makes easier and allows meaningful comparisons between different multiobjective evolutionary algorithms using preference information.

In this paper, we propose the strategy of integrating multiple evolutionary processes for personalized procedural content generation (PCG). In this vein, we provide a concrete solution that personalizes game maps in a top-down action-shooter game to suit an individual player's preferences. The need for personalized PCG is steadily growing as the player market diversifies, making it more difficult to design a game that will accommodate a broad range of preferences and skills. In the solution presented here, the geometry of the map and the density of content within that geometry are represented and generated in distinct evolutionary processes, with the player's preferences being captured and utilized through a combination of interactive evolution and a player model formulated as a recommender system. All these components were implemented into a test bed game and experimented on through an unsupervised public experiment. The solution is examined against a plausible random baseline that is comparable to random map generators that have been implemented by independent game developers. Results indicate that the system as a whole is receiving better ratings, that the geometry and content evolutionary processes are exploring more of the solution space, and that the mean prediction accuracy of the player preference models is equivalent to that of existing recommender system literature. Furthermore, we discuss how each of the individual solutions can be used with other game genres and content types.

This work provides an in-depth investigation of the effects of population initialization on Differential Evolution (DE) for dealing with large scale optimization problems. Firstly, we conduct a statistical parameter sensitive analysis to study the effects of DE's control parameters on its performance of solving large scale problems. This study reveals the optimal parameter configurations which can lead to the statistically superior performance over the CEC-2013 large-scale test problems. Thus identified optimal parameter configurations interestingly favour much larger population sizes while agreeing with the other parameter settings compared to the most commonly employed parameter configuration. Based on one of the identified optimal configurations and the most commonly used configuration, which only differ in the population size, we investigate the influence of various population initialization techniques on DE's performance. This study indicates that initialization plays a more crucial role in DE with a smaller population size. However, this observation might be the result of insufficient convergence due to the use of a large population size under the limited computational budget, which deserve more investigations.

Although various population initialization techniques have been employed in evolutionary algorithms (EAs), there lacks a comprehensive survey on this research topic. To fill this gap and attract more attentions from EA researchers to this crucial yet less explored area, we conduct a systematic review of the existing population initialization techniques. Specifically, we categorize initialization techniques from three exclusive perspectives, i.e., randomness, compositionality and generality. Characteristics of the techniques belonging to each category are carefully analysed to further lead to several sub-categories. We also discuss several open issues related to this research topic, which demands further in-depth investigations.

Opposition-based learning (OBL) and cooperative co-evolution (CC) have demonstrated promising performance when dealing with large-scale global optimization (LSGO) problems. In this work, we propose a novel framework for hybridizing these two techniques, and investigate the performance of simple implementations of this new framework using the most recent LSGO benchmarking test suite. The obtained results verify the effectiveness of our proposed OBL-CC framework. Moreover, some advanced statistical analyses reveal that the proposed hybridization significantly outperforms its component methods in terms of the quality of finally obtained solutions.

Imitating human-like behaviour in action games is a challenging but intriguing task in Artificial Intelligence research, with various strategies being employed to solve the human-like imitation problem. In this research we consider learning human-like behaviour via Markov decision processes without being explicitly given a reward function, and learning to perform the task by observing expert's demonstration. Individual players often have characteristic styles when playing the game, and this method attempts to find the behaviours which make them unique. During play sessions of Super Mario we calculate player's behaviour policies and reward functions by applying inverse reinforcement learning to the player's actions in game. We conduct an online questionnaire which displays two video clips, where one is played by a human expert and the other is played by the designed controller based on the player's policy. We demonstrate that by using apprenticeship learning via Inverse Reinforcement Learning, we are able to get an optimal policy which yields performance close to that of an human expert playing the game, at least under specific conditions.

In this paper, a Variable Neighborhood Decomposition (VND) is proposed for Large Scale Capacitated Arc Routing Problems (LSCARP). The VND employs the Route Distance Grouping (RDG) scheme, which is a competitive decomposition scheme for LSCARP, and generates different neighborhood structures with different tradeoffs between exploration and exploitation. The search first uses a neighborhood structure that is considered to be the most promising, and then broadens the neighborhood gradually as it is getting stuck in a local optimum. The experimental studies show that the VND performed better than the state-of-the-art RDG-MAENS counterpart, and the improvement is more significant when the subcomponent size is smaller. This implies a great potential of combining the VND with small subcomponents.

Evolutionary algorithms that rely on dominance ranking often suffer from a low selection pressure problem when dealing with many-objective problems. Decomposition and user-preference based methods can help to alleviate this problem to a great extent. In this paper, a user-preference based evolutionary multi-objective algorithm is proposed that uses decomposition methods for solving many-objective problems. Decomposition techniques that are widely used in multi-objective evolutionary optimization require a set of evenly distributed weight vectors to generate a diverse set of solutions on the Pareto-optimal front. The newly proposed algorithm, R-MEAD2, improves the scalability of its previous version, R-MEAD, which uses a simplexlattice design method for generating weight vectors. This makes the population size is dependent on the dimension size of the objective space. R-MEAD2 uses a uniform random number generator to remove the coupling between dimension and the population size. This paper shows that a uniform random number generator is simple and able to generate evenly distributed points in a high dimensional space. Our comparative study shows that R-MEAD2 outperforms the dominance-based method R-NSGA-II on many-objective problems.

In this paper we investigate the performance of cooperative co-evolutionary (CC) algorithms on large-scale fully-separable continuous optimization problems. We have shown that decomposition can have significant impact on the performance of CC algorithms. The empirical results show that the subcomponent size should be chosen small enough so that the subcomponent size is within the capacity of the subcomponent optimizer. In practice, determining the optimal size is difficult. Therefore, adaptive techniques are desired by practitioners. Here we propose an adaptive method, MLSoft, that uses widely-used techniques in reinforcement learning such as the value function method and softmax selection rule to adapt the subcomponent size during the optimization process. The experimental results show that MLSoft is significantly better than an existing adaptive algorithm called MLCC on a set of large-scale fully-separable problems.

This study proposes a method for solving real-world warehouse Storage Location Assignment Problem (SLAP) under grouping constraints by Genetic Programming (GP). Integer Linear Programming (ILP) formulation is used to define the problem. By the proposed GP method, a subset of the items is repeatedly selected and placed into the available current best location of the shelves in the warehouse, until all the items have been assigned with locations. A heuristic matching function is evolved by GP to guide the selection of the subsets of items. Our comparison between the proposed GP approach and the traditional ILP approach shows that GP can obtain near-optimal solutions on the training data within a short period of time. Moreover, the evolved heuristics can achieve good optimization results on unseen scenarios, comparable to that on the scenario used for training. This shows that the evolved heuristics have good reusability and can be directly applied for slightly different scenarios without any new search process.

In this paper, a divide-and-conquer approach is proposed to solve the large-scale capacitated arc routing problem (LSCARP) more effectively. Instead of considering the problem as a whole, the proposed approach adopts the cooperative coevolution (CC) framework to decompose it into smaller ones and solve them separately. An effective decomposition scheme called the route distance grouping (RDG) is developed to decompose the problem. Its merit is twofold. First, it employs the route information of the best-so-far solution, so that the quality of the decomposition is upper bounded by that of the best-so-far solution. Thus, it can keep improving the decomposition by updating the best-so-far solution during the search. Second, it defines a distance between routes, based on which the potentially better decompositions can be identified. Therefore, RDG is able to obtain promising decompositions and focus the search on the promising regions of the vast solution space. Experimental studies verified the efficacy of RDG on the instances with a large number of tasks and tight capacity constraints, where it managed to obtain significantly better results than its counterpart without decomposition in a much shorter time. Furthermore, the best-known solutions of the EGL-G LSCARP instances are much improved.

Cooperative co-evolution has been introduced into evolutionary algorithms with the aim of solving increasingly complex optimization problems through a divide-and-conquer paradigm. In theory, the idea of co-adapted subcomponents is desirable for solving large-scale optimization problems. However, in practice, without prior knowledge about the problem, it is not clear how the problem should be decomposed. In this paper, we propose an automatic decomposition strategy called differential grouping that can uncover the underlying interaction structure of the decision variables and form subcomponents such that the interdependence between them is kept to a minimum. We show mathematically how such a decomposition strategy can be derived from a definition of partial separability. The empirical studies show that such near-optimal decomposition can greatly improve the solution quality on large-scale global optimization problems. Finally, we show how such an automated decomposition allows for a better approximation of the contribution of various subcomponents, leading to a more efficient assignment of the computational budget to various subcomponents.

Highly multimodal landscapes with multiple local/global optima represent common characteristics in real-world applications. Many niching algorithms have been proposed in the literature which aim to search such landscapes in an attempt to locate as many global optima as possible. However, to locate and maintain a large number of global solutions, these algorithms are substantially influenced by their parameter values, such as a large population size. Here, we propose a new niching Differential Evolution algorithm that attempts to overcome the population size influence and produce good performance almost independently of its population size. To this end, we incorporate two mechanisms into the algorithm: a control parameter adaptation technique and an external dynamic archive along with a reinitialization mechanism. The first mechanism is designed to efficiently adapt the control parameters of the algorithm, whilst the second one is responsible for enabling the algorithm to investigate unexplored regions of the search space and simultaneously keep the best solutions found by the algorithm. The proposed approach is compared with two Differential Evolution variants on a recently proposed benchmark suite. Empirical results indicate that the proposed niching algorithm is competitive and very promising. It exhibits a robust and stable behavior, whilst the incorporation of the dynamic archive seems to tackle the population size influence effectively. Moreover, it alleviates the problem of having to fine-tune the population size parameter in a niching algorithm.

Several population initialization methods for evolutionary algorithms (EAs) have been proposed previously. This paper categorizes the most well-known initialization methods and studies the effect of them on large scale global optimization problems. Experimental results indicate that the optimization of large scale problems using EAs is more sensitive to the initial population than optimizing lower dimensional problems. Statistical analysis of results show that basic random number generators, which are the most commonly used method for population initialization in EAs, lead to the inferior performance. Furthermore, our study shows, regardless of the size of the initial population, choosing a proper initialization method is vital for solving large scale problems.

In this paper, a simple but effective Random Route Grouping (RRG) scheme is developed to decompose the LargeScale Capacitated Arc Routing Problem (LSCARP). A theoretical analysis is given to show that the decomposition is guaranteed to be improved by RRG along with the improvement of the best-sofar solution during the search process. Then, RRG is combined with a cooperative co-evolution model to solve LSCARP. The experimental results on the EGL-G LSCARP set showed that given the same computational budget, the proposed approach obtained much better results than its counterpart without using decomposition.

In this paper, we propose a metric for evaluating the performance of user-preference based evolutionary multiobjective algorithms by defining a preferred region based on the location of a user-supplied reference point. This metric uses a composite front which is a type of reference set and is used as a replacement for the Pareto-optimal front. This composite front is constructed by extracting the non-dominated solutions from the merged solution sets of all algorithms that are to be compared. A preferred region is then defined on the composite front based on the location of a reference point. Once the preferred region is defined, existing evolutionary multi-objective performance metrics can be applied with respect to the preferred region. In this paper the performance of a cardinality-based metric, a distance-based metric, and a volume-based metric are compared against a baseline which relies on knowledge of the Pareto-optimal front. The experimental results show that the distance-based and the volume-based metrics are consistent with the baseline, showing meaningful comparisons. However, the cardinality-based approach shows some inconsistencies and is not suitable for comparing the algorithms.

Differential evolution (DE) is one of the most powerful continuous optimizers in the field of evolutionary computation. This work systematically benchmarks a classic DE algorithm (DE/rand/1/bin) on the CEC-2013 single-objective continuous optimization testbed. We report, for each test function at different problem dimensionality, the best achieved performance among a wide range of potentially effective parameter settings. It reflects the intrinsic optimization capability of DE/rand/1/bin on this testbed and can serve as a baseline for performance comparison in future research using this testbed. Furthermore, we conduct parameter sensitivity analysis using advanced non-parametric statistical tests to discover statistically significantly superior parameter settings. This analysis provides a statistically reliable rule of thumb for choosing the parameters of DE/rand/1/bin to solve unseen problems. Moreover, we report the performance of DE/rand/1/bin using one superior parameter setting advocated by parameter sensitivity analysis.

Self-adaptive differential evolution (SaDE) is a wellknown DE variant, which has received considerable attention since it was developed. SaDE gradually adapts its trial vector generation strategy and the accompanying parameter setting via learning the preceding performance of multiple candidate strategies and their associated parameter settings. This work systematically investigates SaDE on the CEC-2013 real-parameter single-objective optimization testbed. Parameter sensitivity analysis is carried out by using advanced statistical hypothesis testing methods, aiming to detect statistically significantly superior parameter settings. This analysis reveals that SaDE is actually less sensitive to the parameter choice since quite a number of parameter settings can lead to the statistically significantly better performance than the other settings. Based on this finding, we report SaDE's performance using one of the parameter settings advocated by sensitivity analysis and statistically compare this performance with that of a widely used classic DE (DE/rand/1/bin). The comparison results significantly favor SaDE.

This paper demonstrates an approach to arranging content within maps of an action-shooter game. Content here refers to any virtual entity that a player will interact with during game-play, including enemies and pick-ups. The content layout for a map is indirectly represented by a Compositional Pattern-Producing Networks (CPPN), which are evolved through the Neuroevolution of Augmenting Topologies (NEAT) algorithm. This representation is utilized within a complete procedural map generation system in the game PCG: Angry Bots. In this game, after a player has experienced a map, a recommender system is used to capture their feedback and construct a player model to evaluate future generations of CPPNs. The result is a content layout scheme that is optimized to the preferences and skill of an individual player. We provide a series of case studies that demonstrate the system as it is being used by various types of players.

In this paper we propose a user-preference based evolutionary algorithm that relies on decomposition strategies to convert a multi-objective problem into a set of single-objective problems. The use of a reference point allows the algorithm to focus the search on more preferred regions which can potentially save considerable amount of computational resources. The algorithm that we proposed, dynamically adapts the weight vectors and is able to converge close to the preferred regions. Combining decomposition strategies with reference point approaches paves the way for more effective optimization of many-objective problems. The use of a decomposition method alleviates the selection pressure problem associated with dominance-based approaches while a reference point allows a more focused search. The experimental results show that the proposed algorithm is capable of finding solutions close to the reference points specified by a decision maker. Moreover, our results show that high quality solutions can be obtained using less computational effort as compared to a state-of-the-art decomposition based evolutionary multi-objective algorithm.

This paper provides a review of existing approaches to using evolutionary algorithms (EA) during procedural terrain generation (PTG) processes in video games. A reliable PTG algorithm would allow game maps to be created partially or completely autonomously, reducing the development cost of a game and providing players with more content. Specifically, the use of EA raises possibilities of more control over the terrain generation process, as well as the ability to tailor maps for individual users. In this paper we outline the prominent algorithms that use EA in terrain generation, describing their individual advantages and disadvantages. This is followed by a comparison of the core features of these approaches and an analysis of their appropriateness for generating game terrain. This survey concludes with open challenges for future research.

This paper presents a new cooperative coevolving particle swarm optimization (CCPSO) algorithm in an attempt to address the issue of scaling up particle swarm optimization (PSO) algorithms in solving large-scale optimization problems (up to 2000 real-valued variables). The proposed CCPSO2 builds on the success of an early CCPSO that employs an effective variable grouping technique random grouping. CCPSO2 adopts a new PSO position update rule that relies on Cauchy and Gaussian distributions to sample new points in the search space, and a scheme to dynamically determine the coevolving subcomponent sizes of the variables. On high-dimensional problems (ranging from 100 to 2000 variables), the performance of CCPSO2 compared favorably against a state-of-the-art evolutionary algorithm sep-CMA-ES, two existing PSO algorithms, and a cooperative coevolving differential evolution algorithm. In particular, CCPSO2 performed significantly better than sep-CMA-ES and two existing PSO algorithms on more complex multimodal problems (which more closely resemble real-world problems), though not as well as the existing algorithms on unimodal functions. Our experimental results and analysis suggest that CCPSO2 is a highly competitive optimization algorithm for solving large-scale and complex multimodal optimization problems.

Standard Cooperative Co-evolution uses a round-robin method to select subcomponents to undergo optimization. In a non-separable (epistatic) optimization problem, dividing the computational budget equally between all of the subcomponents is not necessarily the best strategy. When dealing with non-separable problems, there is usually an imbalance between the contribution of various subcomponents to the global fitness of the individuals. Using a round-robin fashion treats all of the subcomponents equally and wastes the computational budget. In this paper, we propose a Contribution Based Cooperative Co-evolution (CBCC) that selects the subcomponents based on their contributions to the global fitness. This alleviates the imbalance issue and allows the computational resources to be used more efficiently. Experiments on several benchmark functions with the "imbalance issue" show that this new scheme is promising, especially when it is combined with a grouping algorithm that captures interacting variables in common subcomponents.

Procedurally generating content for video games is gaining interest as an approach to mitigate rising development costs and meet users' expectations for a broader range of experiences. This paper explores the use of evolutionary algorithms to aid in the content generation process, especially the creation of three-dimensional terrain. We outline a prototype for the generation of in-game terrain by compiling smaller height-map patches that have been extracted from sample maps. Evolutionary algorithms are applied to this generation process by using crossover and mutation to evolve the layout of the patches. This paper demonstrates the benefits of an interactive two-level parent selection mechanism as well as how to seamlessly stitch patches of terrain together. This unique patch-based terrain model enhances control over the evolution process, allowing for terrain to be refined more intuitively to meet the user's expectations.

Web content quality assessment is a typical static ranking problem. Heuristic content and TFIDF features based statistical systems have proven effective for Web content quality assessment. But they are all language dependent features, which are not suitable for cross-language ranking. In this paper, we fuse a series of language-independent features including hostname features, domain registration features, two-layer hyperlink analysis features and third-party Web service features to assess the Web content quality. The experiments on ECML/PKDD 2010 Discovery Challenge cross-language datasets show that the assessment is effective.

Traditional anti-phishing methods and tools always worked in a passive way to receive users' submission and determine phishing URLs. Usually, they are not fast and efficient enough to find and take down phishing attacks. We analyze phishing reports from Anti-phishing Alliance of China(APAC) and propose a hybrid method to discover phishing attacks in an active way based on DNS query logs and known phishing URLs. We develop and deploy our system to report living phishing URLs automatically to APAC every day. Our system has become a main channel in supplying phishing reports to APAC in China and can be a good complement to traditional anti-phishing methods.

Niching is an important technique for multimodal optimization in Evolutionary Computation. Most existing niching algorithms are evaluated using only 1 or 2 dimensional multimodal functions. However, it remains unclear how these niching algorithms perform on higher dimensional multimodal problems. This paper compares several schemes of PSO update rules, and examines the effects of incorporating these schemes into a lbest PSO niching algorithm using a ring topology. Subsequently a new Cauchy and Gaussian distributions based PSO (CGPSO) is proposed. Our experiments suggest that CGPSO seems to be able to locate more global peaks than other PSO variants on multimodal functions which typically have many global peaks but very few local peaks.

The species conservation technique is a relatively new approach to finding multiple solutions of a multimodal optimization problem. When adopting such a technique, a species is defined as a group of individuals in a population that have similar characteristics and are dominated by the best individual, called the species seed. Species conservation techniques are used to identify species within a population and to conserve the identified species in the current generation. A `species-based evolutionary algorithm' (SEA) is the combination of a species conservation technique with an evolutionary algorithm, such as genetic algorithms, particle swarm optimization, or differential evolution. These SEAs have been demonstrated to be effective in searching multiple solutions of a multimodal optimization problem. This paper will briefly review its principles and its variants developed to date. These methods had been used to solve engineering optimization problems and found some new solutions.

Many evolutionary algorithms have been proposed for large scale optimization. Parameter interaction in non-separable problems is a major source of performance loss specially on large scale problems. Cooperative Co-evolution(CC) has been proposed as a natural solution for large scale optimization problems, but lack of a systematic way of decomposing large scale non-separable problems is a major obstacle for CC frameworks. The aim of this paper is to propose a systematic way of capturing interacting variables for a more effective problem decomposition suitable for cooperative co-evolutionary frameworks. Grouping interacting variables in different subcomponents in a CC framework imposes a limit to the extent interacting variables can be optimized to their optimum values, in other words it limits the improvement interval of interacting variables. This is the central idea of the newly proposed technique which is called delta method. Delta method measures the averaged difference in a certain variable across the entire population and uses it for identifying interacting variables. The experimental results show that this new technique is more effective than the existing random grouping method.

In this paper we propose three techniques to improve the performance of one of the major algorithms for large scale continuous global function optimization. Multilevel Cooperative Co-evolution (MLCC) is based on a Cooperative Co-evolutionary framework and employs a technique called random grouping in order to group interacting variables in one subcomponent. It also uses another technique called adaptive weighting for co-adaptation of subcomponents. We prove that the probability of grouping interacting variables in one subcomponent using random grouping drops significantly as the number of interacting variables increases. This calls for more frequent random grouping of variables. We show how to increase the frequency of random grouping without increasing the number of fitness evaluations. We also show that adaptive weighting is ineffective and in most cases fails to improve the quality of found solution, and hence wastes considerable amount of CPU time by extra evaluations of objective function. Finally we propose a new technique for self-adaptation of the subcomponent sizes in CC. We demonstrate how a substantial improvement can be gained by applying these three techniques.

In this paper, we illustrate the use of a reference point based many-objective particle swarm optimization algorithm to optimize low-speed airfoil aerodynamic designs. Our framework combines a flexible airfoil parameterization scheme and a computational flow solver in the evaluation of particles. Each particle, which represents a set of decision variables, is passed through this framework to construct and evaluate the airfoils and assign fitness. We used the baseline NLF0416 airfoil to obtain aspiration values, which are used to define the reference point. This reference point guides the swarm towards the preferred region of the objective landscape to find solutions of interest to the decision maker. The proficiency of the algorithm is highlighted by monitoring convergence and spread of solution using a hyper-volume calculation scheme suitable for user-preference based evolutionary many-objective algorithms. The results comparing the reference point based approach with a standard unguided non-dominated sorting based approach shows that the guided algorithm performs better in this many-objective problem instance. Final solutions found from the reference point based algorithm reveal an evident improvement over the NLF0416 airfoil across all operating conditions.

Accurate time series forecasting are important for displaying the manner in which the past continues to affect the future and for planning our day to-day activities. In recent years, a large literature has evolved on the use of evolving artificial neural networks (EANNs) in many forecasting applications. Evolving neural networks are particularly appealing because of their ability to model an unspecified nonlinear relationship between time series variables. This paper evaluates two methods to evolve neural networks architectures, one carried out with genetic algorithm and a second one carry out with differential evolution algorithm. A comparative study between these two methods, with a set of referenced time series will be shown. The object of this study is to try to improve the final forecasting getting an accurate system.

Niching is an important technique for multimodal optimization. Most existing niching methods require specification of certain niching parameters in order to perform well. These niching parameters, often used to inform a niching algorithm how far apart between two closest optima or the number of optima in the search space, are typically difficult to set as they are problem dependent. This paper describes a simple yet effective niching algorithm, a particle swarm optimization (PSO) algorithm using a ring neighborhood topology, which does not require any niching parameters. A PSO algorithm using the ring topology can operate as a niching algorithm by using individual particles'local memoriesto form a stable network retaining the best positions found so far, while these particles explore the search space more broadly. Given a reasonably large population uniformly distributed in the search space, PSO algorithms using the ring topology are able to form stable niches across different local neighborhoods, eventually locating multiple global/local optima. The complexity of these niching algorithms is onlyO(N), whereNis the population size. Experimental results suggest that PSO algorithms using the ring topology are able to provide superior and more consistent performance over some existing PSO niching algorithms that require niching parameters.

In the above titled paper (ibid., vol. 14, no. 1, pp. 150-169, Feb. 10), some of the results in Tables IV and VI were incorrect. An explanation is presented here.

This paper attempts to address the question of scaling up particle swarm optimization (PSO) algorithms to high dimensional optimization problems. We present a cooperative coevolving PSO (CCPSO) algorithm incorporating random grouping and adaptive weighting, two techniques that have been shown to be effective for handling high dimensional nonseparable problems. The proposed CCPSO algorithms out-performed a previously developed coevolving PSO algorithm on nonseparable functions of 30 dimensions. Furthermore, the scalability of the proposed algorithm to high dimensional nonseparable problems (of up to 1000 dimensions) is examined and compared with two existing coevolving differential evolution (DE) algorithms, and new insights are obtained. Our experimental results show the proposed CCPSO algorithms can perform reasonably well with only a small number of evaluations. The results also suggest that both the random grouping and adaptive weighting schemes are viable approaches that can be generalized to other evolutionary optimization methods.

This paper studies the multi-objectivization of single-objective optimization problems (SOOP) using evolutionary multi-objective algorithms (EMOAs). In contrast to the single-objective case, diversity can be introduced by the multi-objective view of the algorithm and the dynamic use of objectives. Using the travelling salesman problem as an example we illustrate that two basic approaches, a) the addition of new objectives to the existing problem and b) the decomposition of the primary objective into sub-objectives, can improve performance compared to a single-objective genetic algorithm when objectives are used dynamically. Based on decomposition we propose the concept "Multi-Objectivization via Segmentation" (MOS), at which the original problem is reassembled. Experiments reveal that this new strategy clearly outperforms both the traditional genetic algorithm (GA) and the algorithms based on existing multiobjective approaches even without changing objectives.

In this paper we propose to use a distance metric based on user-preferences to efficiently find solutions for many-objective problems. We use a particle swarm optimization (PSO) algorithm as a baseline to demonstrate the usefulness of this distance metric, though the metric can be used in conjunction with any evolutionary multi-objective (EMO) algorithm. Existing user-preference based EMO algorithms rely on the use of dominance comparisons to explore the search-space. Unfortunately, this is ineffective and computationally expensive for many-objective problems. In the proposed distance metric based PSO, particles update their positions and velocities according to their closeness to preferred regions in the objective-space, as specified by the decision maker. The proposed distance metric allows an EMO algorithm's search to be more effective especially for many-objective problems, and to be more focused on the preferred regions, saving substantial computational cost. We demonstrate how to use a distance metric with two user-preference based PSO algorithms, which implement the reference point and light beam search methods. These algorithms are compared to a user-preference based PSO algorithm relying on the conventional dominance comparisons. Experimental results suggest that the distance metric based algorithms are more effective and efficient especially for difficult many-objective problems.

This paper presents a modified PSO algorithm for solving constrained multi-objective optimization problems. Based on the constraint dominance concept, the proposed approach defines two sets of selection rules for determining the cognitive and social components of the PSO algorithm. The simulation results to the four constrained multi-objective optimization problems demonstrate the proposed approach is able to find Pareto-optimal solutions effectively.

This special issue contains seven papers describing recent research developments in the swarm intelligence (SI) field.

This paper presents a multi-objective constraint handling method incorporating the Particle Swarm Optimization (PSO) algorithm. The proposed approach adopts a concept of Pareto domination from multi-objective optimization, and uses a few selection rules to determine particles’ behaviors to guide the search direction. A goal-oriented programming concept is adopted to improve efficiency. Diversity is maintained by perturbing particles with a small probability. The simulation results on the three engineering benchmark problems demonstrate the proposed approach is highly competitive.

This paper proposes a method to use reference points as preferences to guide a particle swarm algorithm to search towards preferred regions of the Pareto front. A decision maker can provide several reference points, specify the extent of the spread of solutions on the Pareto front as desired, or include any bias between the objectives as preferences within a single execution. We incorporate the reference point method into two multi-objective particle swarm algorithms, the non-dominated sorting PSO, and the maximinPSO. This paper first demonstrates the usefulness of the proposed reference point based particle swarm algorithms, then compare the two algorithms using a hyper-volume metric. Both particle swarm algorithms are able to converge to the preferred regions of the Pareto front using several feasible or infeasible reference points.

Problems that are not aligned with the coordinate system can present difficulties to many optimization algorithms, including evolutionary algorithms, by trapping the search on a ridge. The ridge problem in single-objective optimization is understood, but until now little work has been done on understanding this issue in the multi-objective domain. Multi-objective problems with parameter interactions present difficulties to an optimization algorithm, which are not present in the single-objective domain. In this work, we have explained the nature of these difficulties, and investigated the behavior of the NSGA-II, which has difficulties with problems not aligned with the principle coordinate system. This study has investigated Simplex Crossover (SPX), Unimodal Normally Distributed Crossover (UNDX), Parent-Centric Crossover (PCX), and Differential Evolution (DE), as possible alternatives to the Simulated Binary Crossover (SBX) operator within the NSGA-II, on problems exhibiting parameter interactions through a rotation of the coordinate system. An analysis of these operators on three rotated bi-objective test problems, and a four-and eight-objective problem is provided. New observations on the behavior of rotationally invariant crossover operators in the multi-objective problem domain have been reported.

Traditionally Evolutionary Algorithms (EAs) choose candidate solutions based on their individual fitnesses, usually without directly looking for patterns in the fitness landscape discovered. These patterns often contain useful information that could be used to guide the EA to the optimum. While an EA is able to quickly locate the general area of a peak, it can take a considerable amount of time to refine the solution to accurately reflect its true location. We present a new technique that can be used with most EAs. A surface is fitted to the previously-found points using a least squares regression. By calculating the highest point of this surface we can guide the EA to the likely location of the optimum, vastly improving the convergence speed. This technique is tested on Moving Peaks, a commonly used dynamic test function generator. It was able to significantly outperform the current state of the art algorithm.

This paper describes two performance measures for measuring an EMO (evolutionary multiobjective optimization) algorithm's ability to track a time-varying Pareto-front in a dynamic environment. These measures are evaluated using a dynamic multiobjective test function and a dynamic multiobjective PSO,maximinPSOD, which is capable of handling dynamic multiobjective optimization problems.maximinPSODis an extension from a previously proposed multiobjective PSO,maximinPSO. Our results suggest that these performance measures can be used to provide useful information about how well a dynamic EMO algorithm performs in tracking a time-varying Pareto-front. The results also show thatmaximinPSODcan be made self-adaptive, tracking effectively the dynamically changing Pareto-front.

Existing metrics for dynamic optimisation are designed primarily to rate an algorithm's overall performance. These metrics show whether one algorithm is better than another, but do not indicate any specific aspects of the performance. In this paper we split the offline error metric into two component parts. We propose a new metric to measure convergence speed, and show how this, when combined with a population diversity metric, correlates strongly with the overall performance.

One of the most critical issues that remains to be fully addressed in existing multimodal evolutionary algorithms is the difficulty in pre-specifying parameters used for estimating how far apart optima are. These parameters are typically represented as some sorts of niching parameters in existing EAs. Without prior knowledge of a problem, it is almost impossible to determine appropriate values for such niching parameters. This paper proposes a PSO for multimodal optimization that removes the need of these niching parameters. Our results show that the proposed algorithm, Fitness Euclidean-distance Ratio based PSO (FER-PSO) is able to reliably locate multiple global optima on the search landscape over some widely used multimodal optimization test functions, given that the population size is sufficiently large.

Introduction: Multiobjective optimization represents an important class of optimization techniques which have a direct implication for solving many real-world problems. In recent years, using evolutionary algorithms to solve multiobjective optimization problems, commonly known as EMO (Evolutionary Multi-objective Optimization), has gained rapid popularity. Since Evolutionary Algorithms (EAs) make use of a population of candidate solutions, a diverse set of optimal solutions so called Pareto-optimal solutions can be found within a single run. EAs offer a distinct advantage over many traditional optimization methods where multiple solutions must be found in multiple separate runs.

Nature has been the source of inspiration for many machine learning algorithms. In particular, learning algorithms based on natural evolution have attracted much attention. Evolutionary computation...

Speciation encourages an evolutionary algorithm to locate multiple solutions in multimodal environments. Speciation algorithms often require a user to specify a parameter to de fi ne the species radius, which can be a major drawback since this knowledge may not be available a priori. This paper proposes a technique using a time-based convergence measure to overcome this problem. The proposed method is used to enhance the performance of a speciation-based PSO (SPSO) and has been shown to be robust over a wide range of values for this user-speci fy ed parameter.

Niching techniques play an important role in evolutionary algorithms. Existing niching methods often require user-specified parameters, limiting their usefulness. This paper proposes a niching method for Particle Swarm Optimisation (PSO) where population statistics are used to adaptively determine the niching parameters during a run. The proposed niching method is compared to another niching based PSO, SPSO. Our results show that the proposed adaptive niching PSO can solve difficult multimodal functions more reliably and with fewer evaluations.

This paper presents four rotatable multi-objective test problems that are designed for testing EMO (Evolutionary Multi-objective Optimization) algorithms on their ability in dealing with parameter interactions. Such problems can be solved efficiently only through simultaneous improvements to each decision variable. Evaluation of EMO algorithms with respect to this class of problem has relevance to real-world problems, which are seldom separable. However, many EMO test problems do not have this characteristic. The proposed set of test problems in this paper is intended to address this important requirement. The design principles of these test problems and a description of each new test problem are presented. Experimental results on these problems using a Differential Evolution Multi-objective Optimization algorithm are presented and contrasted with the Non-dominated Sorting Genetic Algorithm II (NSGA-II).

The field of Differential Evolution (DE) has demonstrated important advantages in single objective optimization. To date, no previous research has explored how the unique characteristics of DE can be applied to multi-objective optimization. This paper explains and demonstrates how DE can provide advantages in multi-objective optimization using directional information. We present three novel DE variants for multi-objective optimization, and a report of their performance on four multi-objective problems with different characteristics. The DE variants are compared with the NSGA-II (Nondominated Sorting Genetic Algorithm). The results suggest that directional information yields improvements in convergence speed and spread of solutions.

This paper describes an extension to a speciation-based particle swarm optimizer (SPSO) to improve performance in dynamic environments. The improved SPSO has adopted several proven useful techniques. In particular, SPSO is shown to be able to adapt to a series of dynamic test cases with varying number of peaks (assuming maximization). Inspired by the concept of quantum swarms, this paper also proposes a particle diversification method that promotes particle diversity within each converged species. Our results over the moving peaks benchmark test functions suggest that SPSO incorporating this particle diversification method can greatly improve its adaptability hence optima tracking performance.

This paper proposes an improved particle swarm optimizer using the notion of species to determine its neighborhood best values for solving multimodal optimization problems and for tracking multiple optima in a dynamic environment. In the proposed species-based particle swam optimization (SPSO), the swarm population is divided into species subpopulations based on their similarity. Each species is grouped around a dominating particle called the species seed. At each iteration step, species seeds are identified from the entire population, and then adopted as neighborhood bests for these individual species groups separately. Species are formed adaptively at each step based on the feedback obtained from the multimodal fitness landscape. Over successive iterations, species are able to simultaneously optimize toward multiple optima, regardless of whether they are global or local optima. Our experiments on using the SPSO to locate multiple optima in a static environment and a dynamic SPSO (DSPSO) to track multiple changing optima in a dynamic environment have demonstrated that SPSO is very effective in dealing with multimodal optimization functions in both environments.

The application of multi-objective evolutionary computation techniques to the genetic programming of classifiers has the potential to both improve the accuracy and decrease the training time of the classifiers. The performance of two such algorithms is investigated on the even 6-parity problem and the Wisconsin breast cancer, Iris and Wine data sets from the UCI repository. The first method explores the addition of an explicit size objective as a parsimony enforcement technique. The second represents a program's classification accuracy on each class as a separate objective. Both techniques give a lower error rate with less computational cost than was achieved using a standard GP with the same parameters.

In this paper differential evolution is extended by using the notion of speciation for solving multimodal optimization problems. The proposed species-based DE (SDE) is able to locate multiple global optima simultaneously through adaptive formation of multiple species (or subpopulations) in a DE population at each iteration step. Each species functions as a DE by itself. Successive local improvements through species formation can eventually transform into global improvements in identifying multiple global optima. In this study the performance of SDE is compared with another recently proposed DE variant Crowding DE. The computational complexity of SDE, the effect of population size and species radius on SDE are investigated. SDE is found to be more computationally e cient than CrowdingDE over a number of benchmark multimodal test functions.

Program Bloat - phenomenon of ever-increasing program size during a GP run - is a recognised and widespread problem. Traditional techniques to combat program bloat are program size limitations of parsimony pressure (penalty functions). These techniques suffer from a number of problems, in particular their reliance on parameters whose optimal values it is difficult to a priori determine. In this paper, we introduce POPE-GP, a system that makes use of the NSGA-II multiobjective evolutionary algorithm as an alternative, parameter-free technique for eliminating program bloat. We test it on a classification problem and find that while vastly reducing program size, it does improve generalisation performance.

A particle swarm optimisation model for tracking multiple peaks in a continuously varying dynamic environment is described. To achieve this, a form of speciation allowing development of parallel subpopulations is used. The model employs a mechanism to encourage simultaneous tracking of multiple peaks by preventing overcrowding at peaks. Possible metrics for evaluating the performance of algorithms in dynamic, multimodal environments are put forward. Results are appraised in terms of the proposed metrics, showing that the technique is capable of tracking multiple peaks and that its performance is enhanced by preventing overcrowding. Directions for further research suggested by these results are put forward.

This work presents a comparative study of particle swarm models on their abilities to track extrema in dynamic environments. A standard PSO, two randomized PSOs, and a fine-grained PSO are evaluated in non-trivial multimodal dynamic environments involving small constant step changes, different large step changes, and chaotic step changes of the extrema. DF1 proposed by Morrison and De Jong is used to generate these three types of dynamics (1999). Our results indicate that PSO and its variants are able to perform reasonably well in a 2-dimensional variable space, whereas perform well to a less extent in a 10-dimensional variable space. It is also found that the fine-grained PSO is able to outperform all other PSO variants in the 10-dimensional variable space, likely due to its ability in maintaining better population diversity.

Genetic algorithms (GA) have proved to be an effective technique for search and optimization over difficult domains. One common problem for GAs is the phenomenon of premature convergence to suboptimal solutions. We conjecture that premature convergence occurs in part because genetic algorithms lack critical dynamics. This paper proposes a novel algorithm, the genepile evolutionary algorithm, which makes use of the complex spatial dynamics of the sandpile model of self-organized criticality. It is suggested that the critical dynamics of this algorithm make it less prone to getting trapped at local optima. Though the genepile evolutionary algorithm did converge during testing, it has nonetheless proved to be an effective optimization tool, recording good performance across a broad suite of test functions and in many cases substantially outperforming two well-known control algorithms.

In deceptive problems many runs lead to suboptimal solutions and it can be difficult to escape from these local optima and find the global best solution. We propose a pyramid search strategy for these kinds of problems. In the pyramid strategy a number of populations are initialised and independently evolved for a number of generations at which point the worst performing populations are discarded. This evolve/discard process is continued until the problem is solved or one population remains. We show that for a number of deceptive problems the pyramid strategy results in a higher probability of success with fewer evaluations and a lower standard deviation of the number evaluations to success than the conventional approach of running to a maximum number of generations and then restarting.

Small changes in spatial pattern on a landscape can sometimes produce dramatic ecological responses. Such transition ranges are associated with critical environmental conditions such as tree density. As the landscape becomes dissected into smaller patches of trees, landscape connectivity may suddenly become disrupted, which may have important consequences for the behaviours of forest fire, i.e. how it spreads. Landscape connectivity depends not only on the tree density but also many other environmental conditions such as land height, flammability, and wind conditions. To determine how the critical densities are affected by the changes in these conditions, we developed a fire spread simulation model using a multi-agent (i.e. bottom-up) approach. This model simulates an artificial environment where bush is randomly generated and fire can be ignited and then spread across the environment according to some "interaction rules". The emergent fire spread behaviours at the landscape level are determined by such micro-level "interaction rules". This model takes into account some major environmental factors that influence fire growth. By varying these variables under controlled conditions, this research aims to show how varied environmental conditions affect the critical density, and hence influence the spread and growth of fire.

This paper introduces a new method for controlling selection pressure in fine-grained parallel GAs. Our model, inspired by percolation theory, employs a "seeding" mechanism, which provides a means of systematically increasing the population size until the carrying capacity of the lattice is reached. Initially, a relatively small number of individuals (solutions) occupy small isolated patches (demes). As time goes by, additional randomly generated individuals are added to the lattice. As the density increases, the small isolated demes gradually merge to form larger connected demes. This "percolation process" helps to balance the interplay between genetic and population forces. The implications of alternative migration schemes between demes are also investigated in terms of the population diversity, selection pressure and consequently algorithm performance. Experimental results using benchmark optimisation problems confirm that the "step-wise" increase in the population density does affect the quality of the solutions found in a given trial.

Current work on connectionist models has been focused largely on artificial neural networks that are inspired by the networks of biological neurons in the human brain. However, there are also other connectionistarchitectures that differ significantly from this biological exemplar. We proposed a novel connectionist learning architecture inspired by the physics associated with optical coatings of multiple layers of thin-films in a previous paper (Li and Purvis 1999, Annals of Mathematics and Artificial Intelligence, 26: 1-4). The proposed model differs significantly from the widely used neuron-inspired models. With thin-film layer thicknesses serving as adjustable parameters (as compared with connection weights in a neural network) for the learning system, the optical thin-film multilayer model (OTFM) is capable of approximating virtually any kind of highly nonlinear mappings. The OTFM is not a physical implementation using optical devices. Instead, it is proposed as a new connectionist learning architecture with its distinct optical properties as compared with neural networks. In this paper we focus on a detailed comparison of neural networks and the OTFM (Li 2001, Proceedings ofINNS-IEEE International Joint Conference on Neural Networks, Washington, DC, pp. 1727-1732). We describe the architecture of the OTFM and show how it can be viewed as a connectionist learning model. We then present experimental results on solving a classification problem and a time series prediction problem that are typical of conventional connectionist architectures to demonstrate the OTFM's learning capability.