Skip to main content
main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 11th International Conference on Simulated Evolution and Learning, SEAL 2017, held in Shenzhen, China, in November 2017.
The 85 papers presented in this volume were carefully reviewed and selected from 145 submissions. They were organized in topical sections named: evolutionary optimisation; evolutionary multiobjective optimisation; evolutionary machine learning; theoretical developments; feature selection and dimensionality reduction; dynamic and uncertain environments; real-world applications; adaptive systems; and swarm intelligence.

Inhaltsverzeichnis

Frontmatter

Evolutionary Optimisation

Frontmatter

Maximum Likelihood Estimation Based on Random Subspace EDA: Application to Extrasolar Planet Detection

This paper addresses maximum likelihood (ML) estimation based model fitting in the context of extrasolar planet detection. This problem is featured by the following properties: (1) the candidate models under consideration are highly nonlinear; (2) the likelihood surface has a huge number of peaks; (3) the parameter space ranges in size from a few to dozens of dimensions. These properties make the ML search a very challenging problem, as it lacks any analytical or gradient based searching solution to explore the parameter space. A population based searching method, called estimation of distribution algorithm (EDA), is adopted to explore the model parameter space starting from a batch of random locations. EDA is featured by its ability to reveal and utilize problem structures. This property is desirable for characterizing the detections. However, it is well recognized that EDAs can not scale well to large scale problems, as it consists of iterative random sampling and model fitting procedures, which results in the well-known dilemma curse of dimensionality. A novel mechanism to perform EDAs in interactive random subspaces spanned by correlated variables is proposed and the hope is to alleviate the curse of dimensionality for EDAs by performing the operations of sampling and model fitting in lower dimensional subspaces. The effectiveness of the proposed algorithm is verified via both benchmark numerical studies and real data analysis.

Bin Liu, Ke-Jia Chen

Evolutionary Game Network Reconstruction by Memetic Algorithm with l 1/2 Regularization

Evolutionary Game (EG) theory is effective approach to understand and analyze the widespread cooperative behaviors among individuals. Reconstructing EG networks is fundamental to understand and control its collective dynamics. Most existing approaches extend this problem to the l1-regularization optimization problem, leading to suboptimal solutions. In this paper, a memetic algorithm (MA) is proposed to address this network reconstruction problem with l1/2 regularization. The problem-specific initialization operator and local search operator are integrated into MA to accelerate the convergence. We apply the method to evolutionary games taking place in synthetic and real networks, finding that our approach has competitive performance to eight state-of-the-art methods in terms of effectiveness and efficiency.

Kai Wu, Jing Liu

A Simple Brain Storm Optimization Algorithm via Visualizing Confidence Intervals

Visualizing confidence intervals method developed recently for benchmarking stochastic optimization algorithm is adopted in this paper to benchmark and study the brain storm optimization algorithm in depth. Through analyzing numerical effects of different components of brain storm optimization, a simplified brain storm optimization algorithm is developed. It is tested and shown to perform better than the original brain storm optimization algorithm in the objective space.

YingYing Cao, Wei Chen, Shi Cheng, Yifei Sun, Qunfeng Liu, Yun Li, Yuhui Shi

Simulated Annealing with a Time-Slot Heuristic for Ready-Mix Concrete Delivery

The concrete delivery problem (CDP) is an NP-hard, real world combinatorial optimization problem. The CDP involves tightly interrelated routing and scheduling constraints that have to be satisfied by considering the tradeoff between production and distribution costs. Various exact and heuristic methods have been developed to address the CDP. However, due to the limitation of the exact methods for dealing with such a complex problem, (meta-)heuristics have been more popular. For this purpose, the present study proposes a hybrid algorithm combining simulated annealing (SA) with a time-slot heuristic (TH) for tackling the CDP. The TH is applied for generating new solutions through perturbation while simulated annealing is utilized to decide on whether to accept these solutions. The proposed algorithm, i.e. SA-TH, is compared to an existing CDP heuristic on a diverse set of CDP benchmarks. The computational results conducted through a series of experiments validate the efficiency and success of SA-TH.

Muhammad Sulaman, Xinye Cai, Mustafa Mısır, Zhun Fan

A Sequential Learnable Evolutionary Algorithm with a Novel Knowledge Base Generation Method

Sequential learnable evolutionary algorithm (SLEA) provides an algorithm selection framework for solving the black box continuous design optimization problems. An algorithm pool consists of set of established algorithms. A knowledge base is trained offline. SLEA uses the algorithm-problem features to select the best algorithm from the algorithm pool. Given a problem, the default algorithm is run for the initial round. After that, an algorithm-problem feature is collected and used to map to the most similar problem in the knowledge base. Then the best algorithm for solving the problem is used in the second round. This process iterates until $$ n $$ rounds have been made. It is revealed that the algorithm-problem feature is a good problem identifier, thus SLEA performs well on the known problems that have been encountered. However, the performance on those unknown problems is limited if the knowledge base is biased. In this paper, we propose a modified SLEA, which performs the training process using a novel method. A relatively unbiased knowledge base is formed. Experimental results show that the modified SLEA maintains the performance of SLEA on solving the CEC 2013 test suite, while it performs better than SLEA on solving a set of randomly generated max-set of Gaussian test problems.

Yang Lou, Shiu Yin Yuen

Using Parallel Strategies to Speed up Pareto Local Search

Pareto Local Search (PLS) is a basic building block in many state-of-the-art multiobjective combinatorial optimization algorithms. However, the basic PLS requires a long time to find high-quality solutions. In this paper, we propose and investigate several parallel strategies to speed up PLS. These strategies are based on a parallel multi-search framework. In our experiments, we investigate the performances of different parallel variants of PLS on the multiobjective unconstrained binary quadratic programming problem. Each PLS variant is a combination of the proposed parallel strategies. The experimental results show that the proposed approaches can significantly speed up PLS while maintaining about the same solution quality. In addition, we introduce a new way to visualize the search process of PLS on two-objective problems, which is helpful to understand the behaviors of PLS algorithms.

Jialong Shi, Qingfu Zhang, Bilel Derbel, Arnaud Liefooghe, Sébastien Verel

Differential Evolution Based Hyper-heuristic for the Flexible Job-Shop Scheduling Problem with Fuzzy Processing Time

In this paper, a differential evolution based hyper-heuristic (DEHH) algorithm is proposed to solve the flexible job-shop scheduling problem with fuzzy processing time (FJSPF). In the DEHH scheme, five simple and effective heuristic rules are designed to construct a set of low-level heuristics, and differential evolution is employed as the high-level strategy to manipulate the low-level heuristics to operate on the solution domain. Additionally, an efficient hybrid machine assignment scheme is proposed to decode a solution to a feasible schedule. The effectiveness of the DEHH is evaluated on two typical benchmark sets and the computational results indicate the superiority of the proposed hyper-heuristic scheme over the state-of-the-art algorithms.

Jian Lin, Dike Luo, Xiaodong Li, Kaizhou Gao, Yanan Liu

ACO-iRBA: A Hybrid Approach to TSPN with Overlapping Neighborhoods

The traveling salesman problem with neighborhoods (TSPN) is a generalization of TSP and can be regarded as a combination of TSP and TPP (Touring Polygons Problem). In this paper, we propose a hybrid TSPN solution named ACO-iRBA in which the TSP and TPP tasks are tackled simultaneously by ACO (Ant Colony Optimization) and iRBA, an improved version of RBA (Rubber Band Algorithm), respectively. A major feature of ACO-iRBA is that it can properly handle situations where the neighborhoods are heavily overlapped. Experiment results on benchmark problems composed of random ellipses show that ACO-iRBA can solve TSPN instances with up to 70 regions effectively and generally produce higher quality solutions than a recent heuristic method CIH.

Yuanlong Qin, Bo Yuan

An Evolutionary Algorithm with a New Coding Scheme for Multi-objective Portfolio Optimization

A portfolio optimization problem involves optimal allocation of finite capital to a series of assets to achieve an acceptable trade-off between profit and risk in a given investment period. In the paper, the extended Markowitz’s mean-variance portfolio optimization model is studied. A major challenge with this model is that it contains both discrete and continuous decision variables, which represent the assignment and allocation of assets respectively. To deal with this hard problem, this paper proposes an evolutionary algorithm with a new coding scheme that converts discrete variables into continuous ones. By this way, the mixed variables can be handled, and some of the constraints are naturally satisfied. The new approach is empirically studied and the experiment results indicate its efficiency.

Yi Chen, Aimin Zhou, Rongfang Zhou, Peng He, Yong Zhao, Lihua Dong

Exact Approaches for the Travelling Thief Problem

Many evolutionary and constructive heuristic approaches have been introduced in order to solve the Travelling Thief Problem (TTP). However, the accuracy of such approaches is unknown due to their inability to find global optima. In this paper, we propose three exact algorithms and a hybrid approach to the TTP. We compare these with state-of-the-art approaches to gather a comprehensive overview on the accuracy of heuristic methods for solving small TTP instances.

Junhua Wu, Markus Wagner, Sergey Polyakovskiy, Frank Neumann

On the Use of Dynamic Reference Points in HypE

In evolutionary multiobjective optimization, hypervolume indicator is one of the most commonly-used performance metrics. To reduce its high computational costs in many objective optimization, Monte Carlo method is used in HypE (Hypervolume Estimation algorithm for multi-objective optimization) for approximating hypervolume values. However, the diversity preservation of HypE can be poor under inappropriate settings of the reference point. In this paper, the influence of the reference point on HypE is discussed and two variants of HypE algorithm with dynamic reference points are proposed to improve the performance of HypE. Our experimental results suggest that the new algorithms outperform HypE with fixed reference points on a set of multiobjective test instances with different shapes of Pareto fronts.

Jingda Deng, Qingfu Zhang, Hui Li

Multi-Factorial Evolutionary Algorithm Based on M2M Decomposition

This paper proposes a decomposition-based multi-objective multi-factorial evolutionary algorithm (MFEA/D-M2M). The MFEA/D-M2M adopts the M2M approach to decompose multi-objective optimization problems into multiple constrained sub-problems for enhancing the diversity of population and convergence of sub-regions. An machine learning model augmented version is also been implemented, which utilized discriminative models for pre-selecting solutions. Experimental studies on nine multi-factorial optimization (MFO) problem sets are conducted. The experimental results demonstrated that MFEA/D-M2M outperforms the vanilla MFEA on six MFO benchmark problem sets and achieved comparable results on the other three problem sets with partial intersection of global optimal.

Jiajie Mo, Zhun Fan, Wenji Li, Yi Fang, Yugen You, Xinye Cai

An Efficient Local Search Algorithm for Minimum Weighted Vertex Cover on Massive Graphs

The minimum weighted vertex cover (MWVC) problem is a well known NP-hard problem with various real-world applications. In this paper, we design an efficient algorithm named FastWVC to solve MWVC problem in massive graphs. Two strategies are proposed. One is the ConstructWVC procedure, aiming to generate a quality initial vertex cover. The other is a new exchange step for reconstructing a vertex cover. Experiments on 102 instances were conducted to confirm the effectiveness of our algorithm. The results show that the FastWVC algorithm outperforms other algorithms in terms of both solution quality and computational time in most of the instances.

Yuanjie Li, Shaowei Cai, Wenying Hou

Interactive Genetic Algorithm with Group Intelligence Articulated Possibilistic Condition Preference Model

Interactive evolutionary computation assisted with surrogate models derived from the user’s interactions is a feasible method for solving personalized search problems. However, in the initial stage, the estimation of the surrogates is very rough due to fewer interactions, which will mislead the search. Social group intelligence can be of great benefit to solve this problem. Besides, the evaluation uncertainty must be carefully treated. Motivated by this, we here propose an interactive genetic algorithm assisted with possibilistic conditional preference models by articulating group intelligence and the preference uncertainty. The valuable social group is determined according to the given keywords and historical searching of the current user. We respectively construct the possibilistic conditional preference models for the social group and the current user to approximate the corresponding uncertain preferences. We further enhance the current user’s preference model by integrating the social one. Thus, the accuracy of the user’s preference model is greatly improved, and the fitness estimation from the preference model is more reliable. The proposed algorithm is applied to the personalized search for books and the advantage in exploration is experimentally demonstrated.

Xiaoyan Sun, Lixia Zhu, Lin Bao, Lian Liu, Xin Nie

GP-Based Approach to Comprehensive Quality-Aware Automated Semantic Web Service Composition

Comprehensive quality-aware semantic web service composition aims to optimise semantic matchmaking quality and Quality of service (QoS) simultaneously. It is an NP-hard problem due to its huge search space. Therefore, heuristics have to be employed to generate near-optimal solutions. Existing works employ Evolutionary Computation (EC) techniques to solve combinatorial optimisation problems in web service composition. In particular, Genetic Programming (GP) has shown its promise. The tree-based representation utilised in GP is flexible to represent different composition constructs as inner nodes, but the semantic matchmaking information can not be directly obtained from the representation. To overcome this disadvantage, we propose a tree-like representation to directly cope with semantic matchmaking information. Meanwhile, a GP-based approach to comprehensive quality-aware semantic web service composition is proposed with explicit support for our representation. We also design specific genetic operation that effectively maintain the correctness of solutions during the evolutionary process. We conduct experiments to explore the effectiveness and efficiency of our GP-based approach using a benchmark dataset with real-world composition tasks.

Chen Wang, Hui Ma, Aaron Chen, Sven Hartmann

Matrix Factorization Based Benchmark Set Analysis: A Case Study on HyFlex

The present paper offers an analysis strategy to examine benchmark sets of combinatorial search problems. Experimental analysis has been widely used to compare a set of algorithms on a group of instances from such problem domains. These studies mostly focus on the algorithms’ performance rather than the quality of the target benchmark set. In relation to that, the insights about the algorithms’ varying performance happen to be highly limited. The goal here is to introduce a benchmark set analysis strategy that can tell the quality of a benchmark set while allowing to retrieve some insights regarding the algorithms’ performance. A matrix factorization based strategy is utilized for this purpose. A Hyper-heuristic framework, i.e. HyFlex, involving 6 problem domains is accommodated as the testbed to perform the analysis on.

Mustafa Mısır

Learning to Describe Collective Search Behavior of Evolutionary Algorithms in Solution Space

Evolutionary algorithms (EAs) are a kind of population-based meta-heuristic optimization methods, which have proven to have superiorities in solving NP-complete and NP-hard optimization problems. But until now, there is lacking in the researches of effective representation method to describe the collective search behavior of the Evolutionary Algorithm, while it is useful for researchers and engineers to understand and compare different EAs better. In the past, most of the theoretical researches cannot directly guide for practical applications. To bridge the gap between theoretical research and practice, we present a generic and reusable framework for learning features to describe collective behavior of EAs in this paper. Firstly, we represent the collective behavior of EAs with a parent-child difference of population distribution encoded by self-organizing map (SOM). Then, we train a Convolutional Neural Network (CNN) to learn problem-invariant features from the samples of EAs’ collective behavior. Lastly, experiment results demonstrate that our framework can effectively learn discriminative features representing collective behavior of EAs. In the behavioral feature space stretched by the obtained features, the collective behavior samples of various EAs on various testing problems exhibit obvious aggregations that highly correlated with EAs but very weakly related to testing problems. We believe that the learned features are meaningful in analyzing EAs, i.e. it can be used to measure the similarity of EAs according to their inner behavior in solution space, and further guide in selecting an appropriate combination of sub-algorithm of a hybrid algorithm according to the diversity of candidate sub-algorithm instead of blind.

Lei Liu, Chengshan Pang, Weiming Liu, Bin Li

Evolutionary Multiobjective Optimisation

Frontmatter

A Hierarchical Decomposition-Based Evolutionary Many-Objective Algorithm

The evolutionary multiobjective algorithms have been demonstrated the effectiveness in dealing with multiobjective optimization problems. However, when solving the problems with many objectives, i.e., the number of objectives is greater than three, it needs a large population size to maintain population diversity and provide a good approximation to the Pareto front. The dilemma between limited computational resources and the exponentially increasing population size is a big challenge. Thus, we suggest a hierarchical decomposition-based evolutionary algorithm for solving many-objective optimization problems in this paper. Specifically, it constructs a binary tree on a set of large-scale uniform weight vectors. We only compare a candidate solutions with the solutions on the path from root to a leaf node of the tree to assign it into an appropriate node. The proposed algorithm has lower time complexity. Theoretical analysis shows the complexity of the proposed algorithm is $$\mathcal {O}(Mlog(\mathbb {N}))$$ for dealing with a new candidate solution. Empirical results fully demonstrate the effectiveness and competitiveness of the proposed algorithm.

Fangqing Gu, Hai-Lin Liu

Adjusting Parallel Coordinates for Investigating Multi-objective Search

Visualizing a high-dimensional solution set over the evolution process is a viable way to investigate the search behavior of evolutionary multi-objective optimization. The parallel coordinates plot which scales well to the data dimensionality is frequently used to observe solution sets in multi-objective optimization. However, the solution sets in parallel coordinates are typically presented by the natural order of the optimized objectives, with rare information of the relation between these objectives and also the Pareto dominance relation between solutions. In this paper, we attempt to adjust parallel coordinates to incorporate this information. Systematic experiments have shown the effectiveness of the proposed method.

Liangli Zhen, Miqing Li, Ran Cheng, Dezhong Peng, Xin Yao

An Elite Archive-Based MOEA/D Algorithm

MOEA/D is a novel multiobjective evolutionary algorithm based on decomposition approach, which has attracted much attention in recent years. However, when tackling the problems with irregular (e.g., disconnected or degenerated) Pareto fronts (PFs), MOEA/D is found to be ineffective and inefficient, as uniformly distributed weight vectors used in decomposition approach cannot guarantee the even distribution of the optimal solutions on PFs. In this paper, an elite archive-based MOEA/D algorithm (ArchMOEA/D) is proposed to tackle the above problem. An external archive is used to store non-dominated solutions that help to spread the population diversity. Moreover, this external archive is evolved and used to compensate the search area that decomposition-based approaches cannot reach. The external archive and the main population cooperate with each other using Pareto- and decomposition-based techniques during the evolutionary process. Some experiments in solving benchmark problems with various properties have been used to verify the efficiency and effectiveness of ArchMOEA/D. Experimental results demonstrate the superior performance of ArchMOEA/D over other kinds of MOEA/D variants.

Qingling Zhu, Qiuzhen Lin, Jianyong Chen

A Constraint Partitioning Method Based on Minimax Strategy for Constrained Multiobjective Optimization Problems

Constrained multiobjective optimization problem (CMOP) is an important research topic in the field of evolutionary computation. In terms of constraint handling, most of the existing evolutionary algorithms consider more about the proportion of infeasible solutions in population, but less concern about the distribution of infeasible solutions. Therefore, we propose a constraint partitioning method based on minimax strategy (CPM/MS) to solve CMOP. Firstly, we analyze the impact of the distribution of infeasible solutions on selecting solutions and give a preconditioning method for infeasible solutions. Secondly, we divide the preconditioned solutions into different regions by minimax strategy. Finally, we update individuals based on feasibility criteria method in each region. The effectiveness of CPM/MS algorithm is extensively evaluated on a suite of 10 bound-constrained numerical optimization problems, where the results show that CPM/MS algorithm is able to obtain considerably better fronts for some of the problems compared with some the state-of-the-art multiobjective evolutionary algorithms.

Xueqiang Li, Shen Fu, Han Huang

A Fast Objective Reduction Algorithm Based on Dominance Structure for Many Objective Optimization

The performance of the most existing classical evolutionary multiobjective optimization (EMO) algorithms, especially for Pareto-based EMO algorithms, generally deteriorates over the number of objectives in solving many-objective optimization problems (MaOPs), in which the number of objectives is greater than three. Objective reduction methods that transform an MaOP into the one with few objectives, are a promising way for solving MaOPs. The dominance-based objective reduction methods, e.g. k-EMOSS and $$\delta $$-MOSS, omitting an objective while preserving the dominant structure of the individuals as much as possible, can achieve good performance. However, these algorithms have higher computational complexity. Therefore, this paper presents a novel measure for measuring the capacity of preserving the dominance structure of an objective set, i.e., the redundancy of an objective to an objective set. Subsequently, we propose a fast algorithm to find a minimum set of objectives preserving the dominance structure as much as possible. We compare the proposed algorithm with its counterparts on eleven test instances. Numerical studies show the effectiveness of the proposed algorithm.

Fangqing Gu, Hai-Lin Liu, Yiu-ming Cheung

A Memetic Algorithm Based on Decomposition and Extended Search for Multi-Objective Capacitated Arc Routing Problem

The capacitated arc routing problem is a classical NP-hard problem to solve in the field of combinatorial optimization. In recent years, due to its extensive use in our daily life, its importance has gradually emerged. Multi-objective capacitated arc routing problem (MO-CARP) is more close to real life, so it arouses widespread concern. The Multi-objective evolution algorithm based on decomposition provides a suitable frame for solving MO-CARP. In this paper, a memetic algorithm based on decomposition and extended search (ED-MAENS) is proposed to deal with MO-CARP. Firstly, decompose the MO-CARP into many single-objective sub-problems using weight vectors. Then assign represent solution for each single-objective problem. To make sure that each single-objective problems can get a reasonable represent solution, the rank conception is proposed. After that, MAENS algorithm is adopted to solve each single-objective problem using the information of its neighborhood. Finally, we proposed an extended search operator to enlarge the searching space to improve the solution quality. The new proposed algorithm is evaluated on medium and large scale instance set and experimental results demonstrate the proposed method can obtain the better non-dominated solution than compared algorithms especially on large-scale instance.

Ronghua Shang, Yijing Yuan, Bingqi Du, Licheng Jiao

Improvement of Reference Points for Decomposition Based Multi-objective Evolutionary Algorithms

A multi-objective optimization problem (MOP) involves simultaneous minimization or maximization of more than one conflicting objectives. Such problems are commonly encountered in a number of domains, such as engineering, finance, operations research, etc. In the recent years, algorithms based on decomposition have shown commendable success in solving MOPs. In particular they have been helpful in overcoming the limitation of Pareto-dominance based ranking when the number of objectives is large. Decomposition based evolutionary algorithms divide an MOP into a number of simpler sub-problems and solve them simultaneously in a cooperative manner. In order to define the sub-problems, a reference point is needed to construct reference vectors in the objective space to guide the corresponding sub-populations. However, the effect of the choice of this reference point has been scarcely studied in literature. Most of the existing works simply construct the reference point using the minimum objective values in the current nondominated population. Some of the recent studies have gone beyond and suggested the use of optimistic, pessimistic or dynamic reference point specification. In this study, we first qualitatively examine the implications of using different strategies to construct the reference points. Thereafter, we suggest an alternative method which relies on identifying promising reference points rather than specifying them. In the proposed approach, each objective is individually minimized in order to estimate a point close to the true ideal point to identify such reference points. Some initial results and analysis are presented to demonstrate the potential benefits and limitations of the approach. Overall, the approach demonstrates promising results but needs further development for achieving more significant improvements in solving MOPs.

Hemant Kumar Singh, Xin Yao

Multi-Objective Evolutionary Optimization for Autonomous Intersection Management

This paper investigates the real-time application of multi-objective evolutionary algorithm (MOEA) for managing traffic at an intersection with its focus on autonomous vehicles. Most of the existing works on intersection management emphasize using MOEAs to optimize parameters for traffic-light based intersections, or they target human drivers. However, the advent of autonomous vehicles has changed the field of intersection management. To maximize the use of autonomous vehicles, the intersections should be autonomous also. This paper proposes an autonomous intersection management (AIM) system that controls the speed for each vehicle approaching at an intersection by using MOEA. The proposed system first looks at splitting the continuous problem of intersection management into smaller independent scenarios. Then it utilizes the MOEA to find solutions for each scenario by optimizing multiple objectives with different goals in terms of overall performance. In order to give the MOEA low level control of traffic at intersections, the autonomous vehicles are modelled as travelling along a predefined path, with a speed determined by the MOEA.

Kazi Shah Nawaz Ripon, Jostein Solaas, Håkon Dissen

Study of an Adaptive Control of Aggregate Functions in MOEA/D

This paper proposed a new adaptive control mechanism of aggregation functions (scalarizing functions) in MOEA/D, “ADaptive control of Aggregation function dePending on a search condiTion (ADAPT)”. Although MOEA/D has been well known as one of the most powerful EMO algorithms, it hasn’t been resolved which aggregation function should be choose. It is strongly depended on characteristics of the problem which aggregation function of MOEA/D is best suited and very difficult to predict which one is best suited in advance. Our proposed ADAPT changes adaptively an aggregation function of MOEA/D according to the search condition. ADAPT uses multiple aggregation functions and multiple archives corresponding to each aggregation function. The important points of ADAPT is that the number of function calls is same as that of original MOEA/D.In numerical examples, the characteristics and effectiveness of ADAPT were verified by comparing the performance of ADAPT with that of original MOEA/D (using a fixed aggregation function). The results of experiments indicated that ADAPT could obtain the solutions as same quality as that of original MOEA/D with the best suited aggregation function.

Shinya Watanabe, Takanori Sato

Use of Inverted Triangular Weight Vectors in Decomposition-Based Many-Objective Algorithms

A number of decomposition-based algorithms have been proposed for many-objective problems using a set of uniformly distributed weight vectors in the literature. In those algorithms, a many-objective problem is decomposed into single-objective problems. Each single-objective problem is optimized in a cooperative manner with other single-objective problems. Their performance strongly depends on the Pareto front shape of a test problem. This is because weight vectors are generated using a triangular simplex lattice structure. It is easy for decomposition-based algorithms to obtain uniformly distributed solutions on triangular Pareto fronts. However, it is not easy for them to handle non-triangular Pareto fronts such as inverted-triangular and disconnected Pareto fronts. In our former study, we examined the performance of MOEA/D when the triangular simplex lattice structure was replaced with the inverted triangular structure for generating weight vectors. The use of those weight vectors deteriorated the performance of MOEA/D for almost all test problems including those with inverted triangular Pareto fronts. In this paper, we examine the use of the inverted triangular simplex lattice structure in two variants of MOEA/D (MOEA/D-DE and MOEA/D-STM) and other four decomposition-based algorithms (NSGA-III, θ-DEA, MOEA/DD, and Global WASF-GA). Their performance is reported for many-objective problems with triangular and inverted triangular Pareto fronts.

Ken Doi, Ryo Imada, Yusuke Nojima, Hisao Ishibuchi

Surrogate Model Assisted Multi-objective Differential Evolution Algorithm for Performance Optimization at Software Architecture Level*

This paper proposes a surrogate model assisted differential evolutionary algorithm for performance optimization at the software architecture (SA) level, which is named SMDE4PO. In SMDE4PO, different strategies of crossover and mutation are adopted to enhance the algorithm’s search capability and speed up its convergence. Random forests are used as surrogate models to reduce the time of performance evaluation (i.e., fitness evaluation). Our comparative experiments on four different sizes of cases between SMDE4PO and NSGA-II are conducted. From the results, we can conclude that (1) SMDE4PO is significantly better than NSGA-II according to the three quality indicators of Contribution, Generation Distance and Hyper Volume; (2) By using random forests as surrogates, the run time of SMDE4PO is reduced by up to 48% in comparison with NSGA-II in our experiments.

Du Xin, Ni Youcong, Wu Xiaobin, Ye Peng, Xin Yao

Normalized Ranking Based Particle Swarm Optimizer for Many Objective Optimization

Nearly all solutions are Pareto non-dominated for multi-objective problems with more than three conflicting objectives. Thus, the comparison of solutions is a critical issue in many objective optimization. A simple but effective normalized ranking metric based method is proposed to compare solutions in this paper. All solutions are ranked by the sum of normalized fitness value of each objective. A solution with a small value is considered to be a good solution for minimum optimization problems. To enhance the population diversity of all solutions, the solutions with small values and the solutions with better fitness values on each objective are kept in an archive and updated per iteration. This ranking metric is further utilized in a particle swarm optimization algorithm to solve multiobjective and many objective problems. Four benchmark problems are utilized to test the proposed algorithm. Experimental results demonstrate that the proposed algorithm is a promising approach for solving the multiobjective and many objective optimization problems.

Shi Cheng, Xiujuan Lei, Junfeng Chen, Jiqiang Feng, Yuhui Shi

Evolutionary Machine Learning

Frontmatter

A Study on Pre-training Deep Neural Networks Using Particle Swarm Optimisation

Deep learning is a “hot-topic” in machine learning at the moment. Currently deep learning networks are constrained in their size and complexity due to the algorithms used to optimise being computationally expensive. This paper examines the potential of optimising deep neural networks using particle swarm optimisation (PSO) as a substitute for the most common methods of contrastive divergence (CD) or stochastic gradient descent. It investigates the problems caused by using PSO in such high-dimensional problem spaces and the issues around applying divide-and-conquer techniques to neural networks. A novel network architecture is proposed to overcome the limitations caused by the low dimensional capabilities of PSO, dubbed semi-disjoint expanded networks (SdENs). A comparative analysis is performed between the proposed model and more popular techniques. Our experiment results suggest that the proposed techniques could perform similar functions to the more traditional pre-training technique of CD, however it is identified that the deeper networks required suffer from the vanishing gradient problem. This paper serves to highlight the issues prevalent in this new and fertile ground of research.

Angus Kenny, Xiaodong Li

Simple Linkage Identification Using Genetic Clustering

The paper proposes a simple linkage identification method for binary optimization problems. The method is basically equivalent to the genetic clustering method, called GC, inspired by the speciation due to segregation distortion genes that was previously proposed by us. A genetic algorithm using the method, called GAuGC, is also proposed. The GAuGC is applied to decomposable, nearly decomposable, and indecomposable problems. The results show that the GAuGC better solves problems with weak decomposability than the linkage tree genetic algorithm for comparison and also show that it cannot handle the deception well.

Kei Ohnishi, Chang Wook Ahn

Learning of Sparse Fuzzy Cognitive Maps Using Evolutionary Algorithm with Lasso Initialization

Fuzzy cognitive maps (FCMs), characterized by a great deal of abstraction, flexibility, adaptability, and fuzzy reasoning, are widely used tools for modeling dynamic systems and decision support systems. Research on the problem of finding sparse FCMs from observed data is outstanding. Evolutionary algorithms (EAs) play a key role in learning FCMs from time series without expert knowledge. In this paper, we first involve sparsity penalty in the objective function optimized by EAs. To improve the performance of EAs, we develop an effective initialization operator based on the Lasso, a convex optimization approach. Comparative experiments on synthetic data with varying sizes and densities compared with other state-of-the-art methods demonstrate the effectiveness of the proposed approach. Moreover, the proposed initialization operator is able to promote to performance of EAs in learning sparse FCMs from time series.

Kai Wu, Jing Liu

A Bayesian Restarting Approach to Algorithm Selection

A Bayesian algorithm selection framework for black box optimization problems is proposed. A set of benchmark problems is used for training. The performance of a set of algorithms on the problems is recorded. In the beginning, an algorithm is randomly selected to run on the given unknown problem. A Bayesian approach is used to measure the similarity between problems. The most similar problem to the given problem is selected. Then the best algorithm for solving it is suggested for the second run. The process repeats until n algorithms have been run. The best solution out of n runs is recorded. We have experimentally evaluated the property and performance of the framework. Conclusions are (1) it can identify the most similar problem efficiently; (2) it benefits from a restart mechanism. It performs better when more knowledge is learned. Thus it is a good algorithm selection framework.

Yaodong He, Shiu Yin Yuen, Yang Lou

Evolutionary Learning Based Iterated Local Search for Google Machine Reassignment Problems

Iterated Local Search (ILS) is a simple yet powerful optimisation method that iteratively invokes a local search procedure with renewed starting points by perturbation. Due to the complexity of search landscape, different ILS strategies may better suit different problem instances or different search stages. To address this issue, this work proposes a new ILS framework which selects the most suited components of ILS based on evolutionary meta-learning. It has three additional components other than ILS: meta-feature extraction, meta-learning and classification. The meta-feature and meta-learning steps are to generate a multi-class classifier by training on a set of existing problem instances. The generated classifier then selects the most suitable ILS setting when performing on new instances. The classifier is generated by Genetic Programming. The effectiveness of the proposed ILS framework is demonstrated on the Google Machine Reassignment Problem. Experimental results show that the proposed framework is highly competitive compared to 10 state-of-the-art methods reported in the literature.

Ayad Turky, Nasser R. Sabar, Abdul Sattar, Andy Song

Geometric Semantic Genetic Programming with Perpendicular Crossover and Random Segment Mutation for Symbolic Regression

Geometric semantic operators have been a rising topic in genetic programming (GP). For the sake of a more effective evolutionary process, various geometric search operators have been developed to utilise the knowledge acquired from inspecting the behaviours of GP individuals. While the current exact geometric operators lead to over-grown offsprings in GP, existing approximate geometric operators never consider the theoretical framework of geometric semantic GP explicitly. This work proposes two new geometric search operators, i.e. perpendicular crossover and random segment mutation, to fulfil precise semantic requirements for symbolic regression under the theoretical framework of geometric semantic GP. The two operators approximate the target semantics gradually and effectively. The results show that the new geometric operators bring a notable benefit to both the learning performance and the generalisation ability of GP. In addition, they also have significant advantages over Random Desired Operator, which is a state-of-the-art geometric semantic operator.

Qi Chen, Mengjie Zhang, Bing Xue

Constrained Dimensionally Aware Genetic Programming for Evolving Interpretable Dispatching Rules in Dynamic Job Shop Scheduling

This paper investigates the interpretability of the Genetic Programming (GP)-evolved dispatching rules for dynamic job shop scheduling problems. We incorporate the physical dimension of the features used in the terminal set of GP, and assume that the rules that aggregate the features with the same physical dimension are more interpretable. Based on this assumption, we define a new interpretability measure called dimension gap, and develop a Constrained Dimensionally Aware GP (C-DAGP) that optimises the effectiveness and interpretability simultaneously. In C-DAGP, the fitness is defined as a penalty function with a newly proposed penalty coefficient adaptation scheme. The experimental results show that the proposed C-DAGP can achieve better tradeoff between effectiveness and interpretability compared against the baseline GP and an existing DAGP.

Yi Mei, Su Nguyen, Mengjie Zhang

Visualisation and Optimisation of Learning Classifier Systems for Multiple Domain Learning

Learning classifier system (LCSs) have the ability to solve many difficult benchmark problems, but they have to be applied individually to each separate problem. Moreover, the solutions produced, although accurate, are not compact such that important knowledge is obscured. Recently a multi-agent system has been introduced that enables multiple, different LCSs to address multiple different problems simultaneously, which reduces the need for human system set-up, recognises existing solutions and assigns a suitable LCS to a new problem. However, the LCSs do not collaborate to solve a problem in a compact or human observable manner. Hence the aim is to extract knowledge from problems by combining solutions from multiple LCSs in a compact manner that enables patterns in the data to be visualised. Results show the successful compaction of multiple solutions to a single, optimum solution, which shows important feature knowledge that would otherwise have been hidden.

Yi Liu, Bing Xue, Will N. Browne

Adaptive Memetic Algorithm Based Evolutionary Multi-tasking Single-Objective Optimization

Evolutionary multitasking optimization has recently emerged as an effective framework to solve different optimization problems simultaneously. Different from the classic evolutionary algorithms, multi-task optimization (MTO) is designed to take advantage of implicit genetic transfer in a multitasking environment. It deals with multiple tasks simultaneously by leveraging similarities and differences across different tasks. However, MTO still suffers from a few issues. In this paper, a multifactorial memetic algorithm is introduced to solve the single-objective MTO problems. Particularly, the proposed algorithm introduces a local search method based on quasi-Newton, reinitializes a port of worse individuals, and suggests a self-adapt parent selection strategy. The effectiveness of the proposed algorithm is validated by comparing with the multifactorial evolutionary algorithm proposed in CEC’17 competition.

Qunjian Chen, Xiaoliang Ma, Yiwen Sun, Zexuan Zhu

Effective Policy Gradient Search for Reinforcement Learning Through NEAT Based Feature Extraction

To improve the effectiveness of commonly used Policy Gradient Search (PGS) algorithms for Reinforcement Learning (RL), many existing works considered the importance of extracting useful state features from raw environment inputs. However, these works only studied the feature extraction process, but the learned features have not been demonstrated to improve reinforcement learning performance. In this paper, we consider NeuroEvolution of Augmenting Topology (NEAT) for automated feature extraction, as it can evolve Neural Networks with suitable topologies that can help extract useful features. Following this idea, we develop a new algorithm called NEAT with Regular Actor Critic for Policy Gradient Search, which integrates a popular Actor-Critic PGS algorithm (i.e., Regular Actor-Critic) with NEAT based feature extraction. The algorithm manages to learn useful state features as well as good policies to tackle complex RL problems. The results on benchmark problems confirm that our proposed algorithm is significantly more effective than NEAT in terms of learning performance, and that the learned features by our proposed algorithm on one learning problem can maintain the effectiveness while it is used with RAC on another related learning problem.

Yiming Peng, Gang Chen, Mengjie Zhang, Yi Mei

Generalized Hybrid Evolutionary Algorithm Framework with a Mutation Operator Requiring no Adaptation

This paper presents a generalized hybrid evolutionary optimization structure that not only combines both nondeterministic and deterministic algorithms on their individual merits and distinct advantages, but also offers behaviors of the three originating classes of evolutionary algorithms (EAs). In addition, a robust mutation operator is developed in place of the necessity of mutation adaptation, based on the mutation properties of binary-coded individuals in a genetic algorithm. The behaviour of this mutation operator is examined in full and its performance is compared with adaptive mutations. The results show that the new mutation operator outperforms adaptive mutation operators while reducing complications of extra adaptive parameters in an EA representation.

Yong Wee Foo, Cindy Goh, Lipton Chan, Lin Li, Yun Li

A Multitree Genetic Programming Representation for Automatically Evolving Texture Image Descriptors

Image descriptors are very important components in computer vision and pattern recognition that play critical roles in a wide range of applications. The main task of an image descriptor is to automatically detect micro-patterns in an image and generate a feature vector. A domain expert is often needed to undertake the process of developing an image descriptor. However, such an expert, in many cases, is difficult to find or expensive to employ. In this paper, a multitree genetic programming representation is adopted to automatically evolve image descriptors. Unlike existing hand-crafted image descriptors, the proposed method does not rely on predetermined features, instead, it automatically identifies a set of features using a few instances of each class. The performance of the proposed method is assessed using seven benchmark texture classification datasets and compared to seven state-of-the-art methods. The results show that the new method has significantly outperformed its counterpart methods in most cases.

Harith Al-Sahaf, Bing Xue, Mengjie Zhang

Theoretical Developments

Frontmatter

Running-Time Analysis of Particle Swarm Optimization with a Single Particle Based on Average Gain

Running-time analysis of the particle swarm optimization (PSO) is a hard study in the field of swarm intelligence, especially for the PSO whose solution and velocity are encoded continuously. In this study, running-time analysis on particle swarm optimization with a single particle (PSO-SP) is analyzed. Elite selection strategy and stochastic disturbance are combined into PSO-SP in order to improve optimization capacity and adjust the direction of the velocity of the single particle. Running-time analysis on PSO-SP based on the average gain model is applied in two different situations including uniform distribution and standard normal distribution. The theoretical results show running-time of the PSO-SP with stochastic disturbance of both distributions is exponential. Besides, in the same accuracy and the same fitness difference value, running-time of the PSO-SP with stochastic disturbance of uniform distribution is better than that of standard normal distribution.

Wu Hongyue, Huang Han, Yang Shuling, Zhang Yushan

Evolutionary Computation Theory for Remote Sensing Image Clustering: A Survey

This paper presents a survey of evolutionary computation theory for remote sensing image clustering. With the ongoing development of Earth observation techniques, remote sensing data has entered the era of big data, so it is difficult for researchers to get more prior knowledge. In recent years, many experts and scholars have a strong interest in remote sensing clustering due to it does not require training samples. However, remote sensing image clustering has always been a challenging task because of the inherent complexity of remote sensing images, the huge amount of data and so on. Normally, the clustering problem of remote sensing images is transformed into the optimization problem of fuzzy clustering objective function, the goal of which lies in the identification of correct cluster centers in the eigenspace. But traditional clustering approaches belong to hill climbing methods, which are greatly affected by initial values and easily get stuck in local optima. Evolutionary computation techniques are inspired by biological evolution, which can provide possible solutions to find the better clustering centers. So, researchers have carried out a series of related studies. Here, we provide an overview, including: (1) evolutionary single-objective; (2) evolutionary multi-objective; (3) memetic algorithm.

Yuting Wan, Yanfei Zhong, Ailong Ma, Liangpei Zhang

Feature Selection and Dimensionality Reduction

Frontmatter

New Representations in Genetic Programming for Feature Construction in k-Means Clustering

k-means is one of the fundamental and most well-known algorithms in data mining. It has been widely used in clustering tasks, but suffers from a number of limitations on large or complex datasets. Genetic Programming (GP) has been used to improve performance of data mining algorithms by performing feature construction—the process of combining multiple attributes (features) of a dataset together to produce more powerful constructed features. In this paper, we propose novel representations for using GP to perform feature construction to improve the clustering performance of the k-means algorithm. Our experiments show significant performance improvement compared to k-means across a variety of difficult datasets. Several GP programs are also analysed to provide insight into how feature construction is able to improve clustering performance.

Andrew Lensen, Bing Xue, Mengjie Zhang

Transductive Transfer Learning in Genetic Programming for Document Classification

Document classification tasks generally have sparse and high dimensional features. It is important to effectively extract features. In document classification tasks, there are some similarities existing in different categories or different datasets. It is possible that one document classification task does not have labelled training data. In order to obtain effective classifiers on this specific task, this paper proposes a Genetic Programming (GP) system using transductive transfer learning. The proposed GP system automatically extracts features from different source domains, and these GP extracted features are combined to form new classifiers being directly applied to a target domain. From experimental results, the proposed transductive transfer learning GP system can evolve features from source domains to effectively apply to target domains which are similar to the source domains.

Wenlong Fu, Bing Xue, Mengjie Zhang, Xiaoying Gao

Automatic Feature Construction for Network Intrusion Detection

The notion of cyberspace became impossible to separate from the notions of cyber threat and cyberattack. Since cyberattacks are getting easier to run, they are also becoming more serious threats from the economic damage perspective. Consequently, we are evident of a continuous adversarial relationship between the attackers trying to mount as powerful as possible attacks and defenders trying to stop the attackers in their goals. To defend against such attacks, defenders have at their disposal a plethora of techniques but they are often falling behind the attackers due to the fact that they need to protect the whole system while the attacker needs to find only a single weakness to exploit. In this paper, we consider one type of a cyberattack – network intrusion – and investigate how to use feature construction via genetic programming in order to improve the intrusion detection accuracy. The obtained results show that feature construction offers improvements in a number of tested scenarios and therefore should be considered as an important step in defense efforts. Such improvements are especially apparent in scenario with the highly unbalanced data, which also represents the most interesting case from the defensive perspective.

Binh Tran, Stjepan Picek, Bing Xue

A Feature Subset Evaluation Method Based on Multi-objective Optimization

To remove the irrelevant and redundant features from the high-dimensional data while ensuring classification accuracy, a supervised feature subset evaluation method based on multi-objective optimization has been proposed in this paper. Four aspects, sparsity of feature space, classification accuracy, information loss degree and feature subset stability, were took into account in the proposed method and the Multi-objective functions were constructed. Then the popular NSGA-II algorithm was used for optimization of the four objectives in the feature selection process. Finally the feature subset was selected based on the obtained feature weight vector according the four evaluation criteria. The proposed method was tested on 4 standard data sets using two kinds of classifier. The experiment results show that the proposed method can guarantee the higher classification accuracy even though only few numbers of features selected than the other methods. On the other hand, the information loss degrees of the proposed method are the lowest which demonstrates that the selected feature subsets of the proposed method can represent the original data sets best.

Mengmeng Li, Zhigang Shang, Caitong Yue

A Hybrid GA-GP Method for Feature Reduction in Classification

Feature reduction is an important pre-processing step in classification and other artificial intelligent applications. Its aim is to improve the quality of feature sets. There are two main types of feature reduction: feature construction and feature selection. Most current feature reduction algorithms focus on just one of the two types because they require different representations. This paper proposes a new representation which supports a feature reduction algorithm that combines feature selection and feature construction. The algorithm uses new genetic operators to update the new representation. The proposed algorithm is compared with two conventional feature selection algorithms, a genetic algorithms-based feature selection algorithm, and a genetic programming-based algorithm which evolves feature sets containing both original and high-level features. The experimental results on 10 different datasets show that the new representation can help to produce a smaller number of features and improve the classification accuracy over using all features on most datasets. In comparison with other feature selection or construction algorithms, the proposed algorithm achieves similar or better classification performance on all datasets.

Hoai Bach Nguyen, Bing Xue, Peter Andreae

Kernel Construction and Feature Subset Selection in Support Vector Machines

Kernel functions have an important role in the performance of Support Vector Machines (SVMs), since they form the geometry of the feature space. Manual designing of kernel functions is an expensive task and requires domain-specific knowledge. In this article, we propose a new method to automatically construct kernel functions and select optimal subsets of features. We achieve this by combining primitive kernels and subsets of features using Genetic Programming (GP). Our experiments show that the proposed method drastically improves the prediction accuracy of SVMs.

Shinichi Yamada, Kourosh Neshatian

KW-Race and Fast KW-Race: Racing-Based Frameworks for Tuning Parameters of Evolutionary Algorithms on Black-Box Optimization Problems

Setting proper parameters is vital for using Evolutionary Algorithms (EAs) to optimize problems, while parameter tuning is a time-consuming task. Previous approaches focus on tuning parameter configurations that are suitable for multiple problems or problem instances. However, according to the No Free Lunch (NFL) theorem, there is no generic parameter configuration that is fit for all problems. Moreover, practitioners are usually concerned with their particular optimization problem at hand and desire to obtain an acceptable result with less computational cost. Therefore, in this paper, the KW-Race framework is first proposed for solving the parameter tuning task of EAs on certain black-box optimization problem. Then a measure of convergence speed is embedded in the preceding framework to form the Fast KW-Race (F-KW-Race) framework for further reducing the computational cost of the tuning procedure. Experimental studies illustrate remarkable results and further demonstrate the validity and efficiency of the proposed frameworks.

Mang Wang, Xin Tong, Bin Li

Dynamic and Uncertain Environments

Frontmatter

A Probabilistic Learning Algorithm for the Shortest Path Problem

Ant colony optimization (ACO) has been shown effectiveness for solving combinatorial optimization problems. Inspired by the basic principles of ACO, this paper proposes a novel evolutionary algorithm, called probabilistic learning (PL). In the algorithm, a probability matrix is created based on weighted information of the population and a novel random search operator is proposed to adapt the PL to dynamic environments. The algorithm is tested on the shortest path problem (SPP) in both static and dynamic environments. Experimental results on a set of carefully designed 3D-problems show that the PL algorithm is effective for solve SPPs and outperforms several popular ACO variants.

Yiya Diao, Changhe Li, Yebin Ma, Junchen Wang, Xingang Zhou

A First-Order Difference Model-Based Evolutionary Dynamic Multiobjective Optimization

This paper presents a novel algorithm to solve dynamic multiobjective optimization problems. In dynamic multiobjective optimization problems, multiple objective functions and/or constraints may change over time, which requires a multiobjective optimization algorithm to track the moving Pareto-optimal solutions and/or Pareto-optimal front. A first-order difference model is designed to predict the new locations of a certain number of Pareto-optimal solutions based on the previous locations when an environmental change is detected. In addition, a part of old Pareto-optimal solutions are retained to the new population. The prediction model is incorporated into a multiobjective evolutionary algorithm based on decomposition to solve the dynamic multiobjective optimization problems. In such a way, the changed POS or POF can be tracked more quickly. The proposed algorithm is tested on a number of typical benchmark problems with different dynamic characteristics and difficulties. Experimental results show that the proposed algorithm performs competitively when addressing dynamic multiobjective optimization problems in comparisons with the other state-of-the-art algorithms.

Leilei Cao, Lihong Xu, Erik D. Goodman, Hui Li

A Construction Graph-Based Evolutionary Algorithm for Traveling Salesman Problem

In a traveling salesman problem (TSP), the contribution of a variable to fitness depends on the state of other variables. This characteristic can be referred to as entire linkage, utilizing which evolutionary algorithms can significantly enhance performance, especially in cases of large scale problems. In this paper, a construction graph-based evolutionary algorithm (CGEA) to learn variable interactions in TSP is presented. The proposed method employs real adjacency matrix-coding based on construction graph to make population individuals as carriers of variable interaction degrees through evolution. Iteratively, variable interactions are discovered by a parameterless search scheme, called matrix recombination-difference. In order to explore features of CGEA, an entire linkage index (ELI) is proposed to measure the entire linkage level of TSP. The experimental results show CGEA is promising for TSP, especially with a high entire linkage level.

Gang Li, Zhi feng Hao, Hang Wei, Han Huang

Real-world Applications

Frontmatter

Bi-objective Water Cycle Algorithm for Solving Remanufacturing Rescheduling Problem

This paper researches on the remanufacturing rescheduling problems (RRP) for new job insertion. The objective is to minimize the total flow time and the instability at the same time. A bi-objective function is developed for RRP and water cycle algorithm (WCA) is employed and improved to solve the problem. A discretization strategy is proposed to make the WCA applicable for handling the RRP. An ensemble of local search operators is developed to improve the performance of the discrete WCA (DWCA) algorithm. Six real-life remanufacturing cases with different scales are solved by DWCA. The results and comparisons indicate the superiority of the proposed DWCA scheme over the famous bi-objective algorithm, NSGAII.

Kaizhou Gao, Peiyong Duan, Rong Su, Junqing Li

A New Method for Constructing Ensemble Classifier in Privacy-Preserving Distributed Environment

How to build a classifier on datasets that are distributed across different sites under privacy constrains has attracted much attention during the past few years. In this paper, a new method for constructing classifier ensemble for privacy-preserving distributed data mining is proposed. Different from existing methods, the proposed method can obtain, without any auxiliary assumption and releasing the original data of stakeholders, the optimal weights for classifier combination. Experiments show that the ensemble based on our approach achieved high performance.

Yan Shao, Zhanjun Li, Ming Li

Greedy Based Pareto Local Search for Bi-objective Robust Airport Gate Assignment Problem

The present paper proposes a Greedy based Pareto Local Search (GB-PLS) algorithm for the bi-objective robust airport gate assignment problem (bRAGAP). The bRAGAP requires to minimize the total passenger walking distance and the total robust cost of gate assignment. The robust cost is measured through our proposed evaluation function considering the impact of delay cost on the allocation of idle time. GB-PLS uses the Random and Greedy Move (RGM) as a neighborhood search operator to improve the convergence and diversity of the solutions. Two populations are maintained in GB-PLS: the external population (EP) stores the nondominated solutions and the starting population (SP) maintains all the starting solutions for Pareto local search (PLS). The PLS is applied to search the neighborhood of each solution in the SP and the generated solutions are used to update the EP. A number of extensive experiments has been conducted to validate the performance of GB-PLS over Pareto Simulated Annealing (PSA).

Wenxue Sun, Xinye Cai, Chao Xia, Muhammad Sulaman, Mustafa Mısır, Zhun Fan

Multi-neighbourhood Great Deluge for Google Machine Reassignment Problem

Google Machine Reassignment Problem (GMRP) is a recent real world problem proposed at ROADEF/EURO challenge 2012. The aim of this problem is to maximise the usage of the available machines by reassigning processes among those machines while a numerous constraints must be not violated. In this work, we propose a great deluge algorithm with multi-neighbourhood operators (MNGD) for GMRP. Great deluge (GD) algorithm is a single solution based heuristic that accept non-improving solutions in order to escape from the local optimal point. The proposed algorithm uses multi-neighbourhood operators of various characteristics to effectively navigate the search space. The proposed algorithm is evaluated on a total of 30 instances. Computational results disclose that our proposed MNGD algorithm performed better than GD with single neighbourhood operator. Furthermore, MNGD algorithm obtains best results compared with other algorithms from the literature on some instances.

Ayad Turky, Nasser R. Sabar, Abdul Sattar, Andy Song

Evolutionary Optimization of Airport Security Inspection Allocation

Airport security inspection plays a vital role in protecting flights and passengers. However, assigning a large number of baggages to different inspection devices and personnel can be a difficult problem. In this paper, we present a security inspection assignment problem (SIAP) for maximizing the overall probability of detecting hazardous goods within a limited time period. We then propose a hybrid evolutionary algorithm, named DE-DNSPSO, which combines differential evolution (DE) with the diversity enhanced particle swarm optimization with neighborhood search (DNSPSO) to efficiently solve the problem. In DE-DNSPSO, DE operators are used to further improve the diversity enhancing mechanism of DNSPSO and thus better balance exploration and exploitation of the algorithm. Experimental results show that DE-DNSPSO performs better than DNSPSO and some other well-known algorithms on a set of test instances, and our approach contributes to the improvement of inspection capability of airports.

Zheng-Jie Fan, Yu-Jun Zheng

Evolving Directional Changes Trading Strategies with a New Event-Based Indicator

The majority of forecasting methods use a physical time scale for studying price fluctuations of financial markets, making the flow of physical time discontinuous. An alternative to this is event-based summaries. Directional changes (DC), which is a new event-based summary method, allows for new regularities in data to be discovered and exploited, as part of trading strategies. Under this paradigm, the timeline is divided in directional change events (upwards or downwards), and overshoot events, which follow exactly after a directional change has been identified. Previous work has shown that the duration of overshoot events is on average twice the duration of a DC event. However, this was empirically observed on the specific currency pairs DC was tested with, and only under the specific time periods the tests took place. Thus, this observation is not easily generalised. In this paper, we build on this regularity, by creating a new event-based indicator. We do this by calculating the average duration time of overshoot events on each training set of each individual dataset we experiment with. This allows us to have tailored duration values for each dataset. Such knowledge is important, because it allows us to more accurately anticipate trend reversal. In order to take advantage of this new indicator, we use a genetic algorithm to combine different DC trading strategies, which use our proposed indicator as part of their decision-making process. We experiment on 5 different foreign exchange currency pairs, for a total of 50 datasets. Our results show that the proposed algorithm is able to outperform its predecessor, as well as other well-known financial benchmarks, such as a technical analysis.

Michael Kampouridis, Adesola Adegboye, Colin Johnson

Constrained Differential Evolution for Cost and Energy Efficiency Optimization in 5G Wireless Networks

The majority of real-world problems involve not only finding the optimal solution, but also this solution must satisfy one or more constraints. Differential evolution (DE) algorithm with constraints handling has been proposed to solve one of the most fundamental problems in cellular network design. This proposed method has been applied to solve the radio network planning (RNP) in the forthcoming 5G Long Term Evolution (5G LTE) wireless cellular network, that satisfies both deployment cost and energy savings by reducing the number of deployed micro base stations (BSs) in an area of interest. Practically, this has been implemented using constrained strategy that must guarantee good coverage for the users as well. Three differential evolution variants have been adopted to solve the 5G RNP problem. Experimental results have shown that the constrained DE/best/1/bin has achieved best results over other variants in terms of deployment cost, coverage rate and quality of service (QoS).

Rawaa Dawoud AL-Dabbagh, Ahmed Jasim Jabur

Evolutionary Computation to Determine Product Builds in Open Pit Mining

This paper describes an approach to optimising processing and stockpiling decisions in an open pit mine in order to minimise the deviation from production targets. The solution involves determining decisions on the destination of ore as it is mined: whether to use ore in a product directly as it is extracted from the ground, or to stockpile and use later. Experimental results are provided for a variable threshold based selection heuristic and an approach that applies evolutionary computation to find better solutions.

Adam Ghandar

An Evolutionary Vulnerability Detection Method for HFSWR Ship Tracking Algorithm

A high-frequency surface-wave radar (HFSWR) ship tracking algorithm’s performance is significantly affected by the dynamics of ships, in which track fragmentation can be frequently observed. However, it is still unclear about in which scenarios the dynamics of ships sabotages the tracking performance. In this paper, an evolutionary-based vulnerability detection method is proposed to automatically collect scenarios of different ship motion dynamics that can cause quantitative failures in a HFSWR ship tracking algorithm. Firstly, a grammar-based scenario model which can describe multiple types of temporal relationships and generate autonomous motion of any number of ships with comparatively low-dimension data is proposed. Secondly, an encoding scheme of scenario is proposed and corresponding grammar-guided genetic programming (GGGP) algorithm is designed to evolve scenarios that can sabotages the tracking performance. Results show the effectiveness of this method in evolving and collecting scenarios that can cause more serious track fragmentation in the tracking results, with insights into the vulnerability of ship tracking algorithm provided.

Pengju Zhang, Kun Wang, Ling Zhang, Zexiao Xie, Liqin Zhou

Genetic Programming for Lifetime Maximization in Wireless Sensor Networks with a Mobile Sink

Maximizing the lifetime of Wireless Sensor Network (WSN) with a mobile sink is a challenging and important problem that has attracted increasing research attentions. In the literature, heuristic based approaches have been proposed to solve the problem, such as the Greedy Maximum Residual Energy (GMRE) based method. However, existing heuristic based approaches highly rely on expert knowledge, which makes them inconvenient for practical applications. Taking this cue, in this paper, we propose an automatic method to construct heuristic for sink routing based on Genetic Programming (GP) approach. Empirical study shows that the proposed method can generate promising heuristics that achieve superior performance against existing methods with respect to the global lifetime of WSN.

Ying Li, Zhixing Huang, Jinghui Zhong, Liang Feng

Unsupervised Change Detection for Remote Sensing Images Based on Principal Component Analysis and Differential Evolution

This paper proposed a novel method for unsupervised change detection of remote sensing images using principal component analysis and differential evolution (PDECD). PDECD consists of two main steps. Firstly, an eigenvector space is generated by principal component analysis (PCA) of image blocks. Difference image is projected onto the eigenvector space to extract image local features, which is essentially composed of local smoothing feature and edge fidelity features. Then PDECD regards change detection as an optimal clustering problem and utilizes the differential evolution algorithm (DE) to search for the optimal change detection results without any priori knowledge. Compared with the existing methods, PDECD is not only robust to image noise, but also sensitive to small changed details. In addition, PDECD can avoid tracking to the local optima in change detection process and improve the detection performance due to the powerful global optimization capability of DE. Considering the image data belonging to two clusters cannot separated by sharp boundaries, so the Jm index of standard fuzzy clustering method is used as the objective function of DE. In order to improve the robustness and automatic detection capability of PDECD, control parameters of DE have been adjusted adaptively. Experiments conducted on real SAR and optical remote sensing images demonstrate the effectiveness of the proposed method.

Mi Song, Yanfei Zhong, Ailong Ma, Liangpei Zhang

Parallel Particle Swarm Optimization for Community Detection in Large-Scale Networks

Community detection has great applications in many areas. Many algorithms have been proposed to solve this problem, while these algorithms could not detect communities in large-scale networks effectively and efficiently. In this paper, a parallel particle swarm optimization algorithm based on Apache Spark for community detection is put forward. In this algorithm, an effective representation and a specific updating strategy of discrete particle swarm optimization for parallel computing are designed. Modularity density is used as the objective function and GraphX is used to optimize modularity density parallel. To demonstrate the effectiveness of the proposed algorithm, various experiments on small real-world networks with ground-truth communities are carried out. At the same time, we test the performance of the proposed algorithm on large-scale networks. The experimental results indicate that the proposed method is effective and suitable for community detection in large-scale networks.

Shanfeng Wang, Maoguo Gong, Yue Wu, Xiaolei Qin

Multi-objective Memetic Algorithm Based on Three-Dimensional Request Prediction for Dynamic Pickup-and-Delivery Problem with Time Windows

A multi-objective memetic algorithm based on three-dimensional request prediction is proposed in this paper to solve dynamic pickup-and-delivery route problems with time windows. Dynamic requests are predicted in three dimensions including two space coordinates and time based on the statistical distribution of historical data. The predictive routes are planned firstly and tuned subsequently when the real requests occur. Tri-objective route planning problem based on route length, served time and workload is optimized by the proposed multi-objective memetic algorithm based on prediction, which combines multi-objective genetic algorithm with a locality-sensitive hashing based local search. The proposed algorithm is compared with the other two popular algorithms on two test problems and the experimental results show the efficiency of the proposed algorithm.

Yanming Yang, Xiaoliang Ma, Yiwen Sun, Zexuan Zhu

Optimization of Spectrum-Energy Efficiency in Heterogeneous Communication Network

Green communication has become a hot topic in the field of wireless communication. This paper aims to improve the Quality of Service (QoS) of the system and minimizes the energy consumption by the spectrum-energy cooperation between adjacent base stations. We formulate the proposed spectrum-energy cooperation model as a hybrid constrained many-objective optimization problem (MaOP). To improve the efficiency of optimization algorithm, an alternate optimization algorithm is presented to address the proposed complex MaOP. The evolutionary multiobjective algorithm is employed for spectrum cooperation optimization which is discrete optimization problem, meanwhile classical optimization method is employed for energy consumption optimization and energy cooperation optimization that are continuous optimization problems. Simulation results show the effectiveness of the algorithm.

Fangqing Gu, Ziquan Liu, Yiu-ming Cheung, Hai-Lin Liu

Large Scale WSN Deployment Based on an Improved Cooperative Co-evolution PSO with Global Differential Grouping

With the development of wireless sensor networks (WSNs), the applications of WSNs are becoming more and more, especially in military monitoring, target tracking and traffic control. Coverage is one of the key metrics for WSNs performance. As a number of typical WSN applications such as forest fire or hostile environments monitoring are likely to expand their service coverage, they have to deploy a large number of sensor nodes in the interest area. However, with the number of sensor nodes increase the dimensions of the problem are also getting higher, traditional WSNs deployment algorithms can not achieve the desired results. In this paper, we propose an improved cooperative co-evolution global differential grouping particle swarm optimization (ICC-GDG-PSO) algorithm to solve the problem of large scale deployment. Global Differential Grouping (GDG) algorithm has good performance in large scale problem optimization, especially when the WSN contains thousands of sensors. We using the GDG decomposition strategy on a cooperative coevolution (CC) framework. But GDG algorithm won’t update the grouping since the grouping information confirmed, we integrate the random grouping mechanism after the GDG algorithm to get more accurate grouping of variables. Experimental results show that our proposed ICC-GDG-PSO algorithm is superior to other algorithms in the large scale deployment problem.

Yazhen Zhang, Wei Fang

Adaptive Systems

Frontmatter

Learning Fuzzy Cognitive Maps Using a Genetic Algorithm with Decision-Making Trial and Evaluation

Fuzzy cognitive maps (FCMs) are inference networks, which are the combination of fuzzy logic and neural networks. Various evolutionary-based learning algorithms have been proposed to learn FCMs. However, evolutionary algorithms have shortcomings, such as easy to become premature and the local search ability is weak where the search may trap into local optima. Decision-making trial and evaluation laboratory (DEMATEL) has been widely accepted as one of the best tools to analyze the causal and effect relationships between concepts. Therefore, we combine real-coded genetic algorithm (RCGA) with DEMATEL method, termed as RCGADEMATEL-FCM, to learn FCM models. In RCGADEMATEL-FCM, the DEMATEL method is used as a directed neighborhood search operator to steer the search to the right direction in the objective space, which can overcome the premature problem and make the search jump out of the local optimum. Experimental results on both synthetic and real life data demonstrate the efficiency of the proposed algorithm. The comparison with existing learning algorithms shows that RCGADEMATEL-FCM can learn FCMs with higher accuracy without expert knowledge.

Xumiao Zou, Jing Liu

Dynamic and Adaptive Threshold for DNN Compression from Scratch

Despite their great success, deep neural networks (DNN) are hard to deploy on devices with limited hardware like mobile phones because of massive parameters. Many methods have been proposed for DNN compression, i.e., to reduce the parameters of DNN models. However, almost all of them are based on reference models, which were firstly trained. In this paper, we propose an approach to perform DNN training and compression simultaneously. More concretely, a dynamic and adaptive threshold (DAT) framework is utilized to prune a DNN gradually by changing the pruning threshold during training. Experiments show that DAT can not only reach comparable or better compression rate almost without loss of accuracy than state-of-the-art DNN compression methods, but also beat DNN sparse training methods by a large margin.

Chunhui Jiang, Guiying Li, Chao Qian

Cooperative Design of Two Level Fuzzy Logic Controllers for Medium Access Control in Wireless Body Area Networks

Wireless Body Area Networks (WBANs) consists of various sensors which are attached on or even implanted in the body to improve health care and the quality of life. Soft computing techniques including fuzzy logic have been successfully applied to WBANs. However, most of the existing research works considered only single-level fuzzy logic controls (FLCs). In this paper, we propose a two-level control scheme at both the sensor level and the coordinator level to improve both the reliability and performance of Medium Access Controls (MAC) in WBANs. We also propose to use Cooperative PSO (CPSO) to automate the design of our two-level control scheme. With the goal of improving network reliability while keeping the communication delay at a low level, we have particularly experimented on four different collaborator selection methods for CPSO. Specifically, we show that network knowledge can help CPSO to select collaborators more effectively. Moreover, the FLCs designed by our approach is also shown to outperform some recently developed algorithms and the IEEE 802.15.4 standard.

Seyed Mohammad Nekooei, Gang Chen, Ramesh Rayudu

Statistical Analysis of Social Coding in GitHub Hypernetwork

Social coding is a software development approach, which can facilitate hundreds of developers collaborating in one project simultaneously. Many researchers focus on the analysis of social network based on complex network models. However, the traditional complex network model cannot express the full information of collaboration. In this paper, in order to depict the properties of hypernetwork well and get a good simulation result, we investigate the time evolution of the GitHub dataset. We find that, (1) The hypernetworks show high level of self-organization; (2) From the neighbor connectivity of developers, some of the skilled developers wish to collaborate with skilled developers, whereas some skilled developers prefer to collaborate with freshman; (3) From the statistical properties of programming languages communities, the assortativity of Java community is obviously different from other communities, and the projects have a high probability of collaboration with those using the same programming languages.

Li Kuang, Feng Wang, Heng Zhang, Yuanxiang Li

Swarm Intelligence

Frontmatter

Sparse Restricted Boltzmann Machine Based on Multiobjective Optimization

This article proposes an efficient method for Restricted Boltzmann Machine (RBM) to learn sparse feature. Deep learning algorithms are used more and more often. The Deep Belief Network (DBN) model, which is composed of RBM, is considered as one of the most effective deep learning algorithms. RBM or auto-encoder (AE) is the basic model to build deep networks. However, RBM may produce redundant features without any constraints, then much improved RBM were proposed by added a regularization term to control sparsity of hidden units. Most of the proposed algorithms need a parameter to control the sparseness of the code. In this paper, we proposed a multiobjective optimization model to avoid user-defined constant that is a trade-off between the regularization term and the reconstruction error based on SR-RBM. We employ evolutionary algorithm to optimize the distortion function and the sparsity of hidden units simultaneously. Experimental results show that our novel approach can learn useful sparse feature without a user-define constant and it performs better than other feature learning models.

Yangyang Li, Xiaoyu Bai, Xiaoxu Liang, Licheng Jiao

A Knee Point Driven Particle Swarm Optimization Algorithm for Sparse Reconstruction

Sparse reconstruction is a technique to reconstruct sparse signal from a small number of samples. In sparse reconstruction problems, the sparsity and measurement error should be minimized simultaneously, therefore they can be solved by multi-objective optimization algorithms. Most multi-objective optimizers aim to obtain the complete Pareto front. However only solutions in knee region of Pareto front are preferred in sparse reconstruction problems. It is a waste of time to obtain the whole Pareto front. In this paper, a knee point driven multi-objective particle swarm optimization algorithm (KnMOPSO) is proposed to solve sparse reconstruction problems. KnMOPSO aims to find the local part of Pareto front so that it can solve the sparse reconstruction problems fast and accurately. In KnMOPSO personal best particles and global best particle are selected with knee point selection scheme. In addition, solutions which are more likely to be knee points are preferred to others.

Caitong Yue, Jing Liang, Boyang Qu, Hui Song, Guang Li, Yuhong Han

Multivariant Optimization Algorithm with Bimodal-Gauss

In multimodal problems, there is a trade-off between exploration and exploitation. Exploration contributes to move quickly toward the area where better solutions existed but is not beneficial for improving the quality of intermediate solution. Exploitation do well in refine the intermediate solution but increase the risk of being trapped into local optimum. Considering the trade-off and advantage of exploration and exploitation, a local search strategy based on bimodal-gauss was embedded into multivariant optimization algorithm by increasing the probability of locating global optima in solving multimodal optimization problems. The performances of the proposed method were compared with that of other multimodal optimization algorithms based on benchmark functions and the experimental results show the superiority of the proposed method. Convergence process of each subgroup was analyzed based on convergence curve.

Baolei Li, Jing Liang, Caitong Yue, Boyang Qu

Enhanced Comprehensive Learning Particle Swarm Optimization with Exemplar Evolution

Enhanced comprehensive learning particle swarm optimization (ECLPSO) is a metaheuristic recently proposed by us for global optimization. ECLPSO is balanced in exploration and exploitation; however, it still cannot satisfactorily address some complex multimodal problems. In this paper, we investigate further improving the exploration performance of ECLPSO through exemplar evolution (EE). EE encourages information exchange among different dimensions of the search space and performs mutation and selection on personal best positions that are exemplars guiding the flight of particles. EE is able to prevent the dimensions from getting stuck in stagnancy. Experimental results on various benchmark functions demonstrate that the EE strategy significantly improves the exploration performance of ECLPSO and helps ECLPSO to locate the global optimum region on all of the functions.

Xiang Yu, Yunan Liu, Xiangsheng Feng, Genhua Chen

Recommending PSO Variants Using Meta-Learning Framework for Global Optimization

Since inception, particle swarm optimization (PSO) has raised a great interest across various disciplines, thus producing a large number of PSO variants with respective strengths. However, a variant may perform variously on diverse problems, which leads to the risk of the algorithm selection of PSOs for a specific problem without prior knowledge. Hence, it is worth investigating a link between problem characteristics and algorithm performance. To address this issue, we propose a recommendation system of PSO variants for global optimization problem using meta-learning framework. Benchmark functions in the learning instance repository are pictured by meta-features to obtain characteristics and solved by the candidate PSO heuristics to gather performance rankings. k-NN method is employed to develop meta-learning system for recommending the predicted rankings of candidate PSO-variants. Results show that the predicted rankings highly correlate to the ideal rankings and achieve high precision on best algorithm recommendation. Besides, problem surface characteristics play a key role in recommendation performance, followed by sample point characteristics. To sum up, the proposed framework can significantly reduce the risk of algorithm selection.

Xianghua Chu, Fulin Cai, Jiansheng Chen, Li Li

Augmented Brain Storm Optimization with Mutation Strategies

Brain storm optimization (BSO) is a recently proposed novel and promising swarm intelligence algorithm which models the human brainstorming problem-solving process. In BSO, the search areas are grouped into several clusters resulting in the diversity of population decrease in iterations. Hence, original BSO algorithm has suffered from low convergence speed and getting trapped into local optimum when solving global optimization problems since its inception. To address the issues, an augmented brain storm optimization with two mutation-based strategies (ABSO) is proposed in this study. First, a search technique based on non-uniform mutation is employed to accelerate the convergence speed of individuals locally. Second, a random mutation inspired by differential evolution is utilized to enhance the exploration capability globally. Finally, the performance of ABSO algorithm is tested on eighteen benchmark functions with various properties. Compared with the other algorithms, experimental results indicate that the proposed algorithm obviously enhance the performance of original BSO for global optimization in terms of solution accuracy and convergence speed.

Xianghua Chu, Jiansheng Chen, Fulin Cai, Chen Chen, Ben Niu

A New Precedence-Based Ant Colony Optimization for Permutation Problems

In this paper we introduce ACOP, a novel ACO algorithm for solving permutation based optimization problems. The main novelty is in how ACOP ants construct a permutation by navigating the space of partial orders and considering precedence relations as solution components. Indeed, a permutation is built up by iteratively adding precedence relations to a partial order of items until it becomes a total order, thus the corresponding permutation is obtained. The pheromone model and the heuristic function assign desirability values to precedence relations. An ACOP implementation for the Linear Ordering Problem (LOP) is proposed. Experiments have been held on a large set of widely adopted LOP benchmark instances. The experimental results show that the approach is very competitive and it clearly outperforms previous ACO proposals for LOP.

Marco Baioletti, Alfredo Milani, Valentino Santucci

A General Swarm Intelligence Model for Continuous Function Optimization

We consider a general form of the swarm intelligence as a function optimization tool. This form is derived from a basis of mathematical swarming differential equation model, where several parameters are included in the model. These parameters are corresponding to a repulsion effect, an attractive effect and a gradient direction. We mainly consider a repulsion effect and unknown gradient estimation in this study. The nature of the proposed model by some typical numerical simulation results is described. Then, the numerous simulation results show that the behaviors of the swarm will change significantly, for example, aggregation and clustering by parameter setting. We are able to see basic behaviors of the swarm intelligence by the introduced model, the model could give us the insight to understand search behavior of swarm intelligence.

Satoru Iwasaki, Heng Xiao, Toshiharu Hatanaka, Takeshi Uchitane

A Hybrid Particle Swarm Optimization for High-Dimensional Dynamic Optimization

High-Dimensional Dynamic Optimization Problems (HDDOPs) commonly exist in real-world applications. In evolutionary computation field, most of existing benchmark problems, which could simulate HDDOPs, are non-separable. Thus, we give a novel benchmark problem, called high-dimensional moving peaks benchmark to simulate separable, partially separable, and non-separable problems. Moreover, a hybrid Particle Swarm Optimization algorithm based on Grouping, Clustering and Memory strategies, i.e. GCM-PSO, is proposed to solve HDDOPs. In GCM-PSO, a differential grouping method is used to decompose a HDDOP into a number of sub-problems based on variable interactions firstly. Then each sub-problem is solved by a species-based particle swarm optimization, where the nearest better clustering is adopted as the clustering method. In addition, a memory strategy is also adopted in GCM-PSO. Experimental results show that GCM-PSO performs better than the compared algorithms in most cases.

Wenjian Luo, Bin Yang, Chenyang Bu, Xin Lin

Visualizing the Search Dynamics in a High-Dimensional Space for a Particle Swarm Optimizer

Visualization of an evolutionary algorithm may lead to better understanding of how it works. In this paper, three dimension reduction techniques (i.e. PCA, Sammon mapping, and recently developed t-SNE) are compared and analyzed empirically for visualizing the search dynamics of a particle swarm optimizer. Specifically, the search path of the global best position of a particle swarm optimizer over iterations is depicted in a low-dimensional space. Visualization results simulated on a variety of continuous functions show that (1) t-SNE could display the evolution of search path but its performance deteriorates as the dimension increases, and t-SNE tends to enlarge the search path generated during the later search stage; (2) the local search behavior (e.g. convergence to the optimum) can be identified by PCA with more stable performance than its two competitors, though for which it may be difficult to clearly depict the global search path; (3) Sammon mapping suffers easily from the overlapping problem. Furthermore, some important practical issues on how to appropriately interpret visualization results in the low-dimensional space are also highlighted.

Qiqi Duan, Chang Shao, Xiaodong Li, Yuhui Shi

Particle Swarm Optimization with Winning Score Assignment for Multi-objective Portfolio Optimization

The successful implementation of particle swarm optimization (PSO) for solving portfolio optimization problems is widely documented. However, its execution is restricted within a single-objective optimization framework. The challenge of utilizing PSO based upon a multi-objective optimization framework is identifying the global best solution since a set of compromising solutions is obtained rather than a single best solution. The majority of the multi-objective PSO (MOPSO) proposed in the literature employs the Pareto dominance relation for updating solutions and repository. By using this method, unfortunately, performance of MOPSO deteriorates if the number of optimized objective increases because the chance that solutions do not dominate each other rises. To overcome this problem, the winning score assignment method is developed by taking into account the interacting relations between optimized objectives during fitness assignment process. The proposed method is integrated into the MOPSO and the resulting algorithm is named as the “winning score MOPSO” denoted by WMOPSO. The WMOPSO is experimented for solving portfolio optimization problems containing up to four optimized objectives. The performance of WMOPSO is benchmarked with its original version based upon four standard comparison criteria. Regardless of performance criteria, the comparison results reveal that WMOPSO outperforms MOPSO. In addition, its superiority is more pronounced for the many-objective optimization problems.

Karoon Suksonghong, Kittipong Boonlong

Conservatism and Adventurism in Particle Swarm Optimization Algorithm

Particle Swarm Optimization (PSO) is a widely used optimization algorithm in industrial and academic fields. In this paper, three improved PSO variants are proposed. The main ideas of them are that a coefficient v is added to control the velocity augment of particles to the new position on different dimension. The first one is under the guidance of conservatism which is an inspiration of Differential Evolution (DE), namely, particles preserve more information from their previous positions and move in a smaller search space. This algorithm shows that particles are possible to escape from the current neighborhood and for promising search area if they take more previous information. The second one is guided by adventurism for better exploration, which means a larger search space to particles. The third one can be considered as a compromise between conservatism and adventurism. This algorithm shows that a balanced cooperation with a little conservative in more adventures will make PSO more competitive. Experimental results show that the proposed strategies of all the three algorithms are effective based on CEC2015 benchmarks. All of them are better than the traditional PSOs and the third improved variant performs better than all the other competitors.

Guangzhi Xu, Rui Li, Xinchao Zhao, Xingquan Zuo

A Competitive Social Spider Optimization with Learning Strategy for PID Controller Optimization

Tuning the parameters of PID controller is a difficult problem, since it is hard to get the optimum parameters by the traditional methods, new methods are required. Nature-inspired algorithms perform powerfully and efficiently on global optimization problems. Social spider optimization (SSO) is one of the novel nature-inspired algorithms, and it exhibits good performance on avoiding premature convergence. However, the efficiency of SSO degrades when used in applications such as PID controller optimization whose objective function with highly correlated variables. In order to overcome this disadvantage, based on the SSO, a competitive social spider optimization (CSSO) is proposed in this paper. To enhance the performance of SSO, we regroup the spiders and the diversity of population is increased. Inspired by the competitive mating behavior of spiders, the competitive mating mechanism is introduced, and a learning strategy is used for the new born spider. The CSSO is applied to optimize the parameters of PID controller, and the simulation results show that the performance of CSSO is promising in PID controller optimization.

Zhaolin Lai, Xiang Feng, Huiqun Yu

Backmatter

Weitere Informationen