GECCO '18- Proceedings of the Genetic and Evolutionary Computation Conference CompanionFull Citation in the ACM Digital Library
POSTER SESSION: Poster: ant colony optimization and swarm intelligence
The Graph Coloring Problem is an important benchmark problem for decision and discrete optimization problems. In this work, we perform a comparative experimental study of four algorithms based on Swarm Intelligence for the 3-Graph Coloring Problem: Particle Swarm Optimization (PSO), Artificial Bee Colonies (ABC), Cuckoo Search (CS) and FireFly Algorithm (FFA). For each algorithm, we test parameter settings published in the literature, as well as parameters found by an automated tuning methodology (irace). This comparison may shed some light at the strengths and weaknesses of each algorithm, as well as their dependence on parameter values.
The Pareto Improving Particle Swarm Optimization algorithm (PI-PSO) has been shown to perform better than Global Best PSO on a variety of benchmark problems. However, these experiments used benchmark problems with a single dimension, namely 32d. Here we compare global best PSO and PI-PSO on benchmark problems of varying dimensions and with varying numbers of particles. The experiments show that PI-PSO generally achieves better performance than PSO as the number of dimensions increases. PI-PSO also outperforms PSO on problems with the same dimension but with the same or fewer particles.
We investigate the convergence speed, accuracy, robustness and scalability of PSOs structured by regular and random graphs with 3 ≤ k ≤ n. The main conclusion is that regular and random graphs with the same averaged connectivity k may result in significantly different performance, namely when k is low.
Multimodal optimization (MMO) aims at finding multiple optimal (or close to optimal) solutions, which plays a crucial role in various fields. However, most of the efforts have been devoted to the continuous MMO domain, while little attention has been paid to discrete problems like the traveling salesman problem (TSP). This paper makes a proof of principle study on multimodal TSP. Particularly, we design a test suite for multimodal TSP and then develop an ant colony algorithm to accomplish the optimization task. The traditional ant algorithms such as the ant colony system are unable to maintain multiple solutions because of the global convergence. To deal with this problem, we propose a novel niching ant colony system (NACS). The algorithm employs a niching strategy and multiple pheromone matrices to preserve population diversity and keep the trace of multiple paths. The experimental results are presented to validate the good performance of the proposed algorithm.
We demonstrate the applicability of inverted Ant Colony Optimization (iACO) for target search in a complex unknown indoor environment simulated by a maze. The colony of autonomous ants lay repellent pheromones to speed up exploration of the unknown maze instead of reinforcing presence in already visited areas. The role of a target-collocated beacon signal within the maze is evaluated in terms of its utility to guide the search. Variants of iACO were developed, with beacon initialization (iACO-B), and with increased sensing ranges (iACO-R with a 2-step far-sightedness) to quantify the most effective one. The presented models can be implemented with self-organizing wireless sensor networks carried by autonomous drones or vehicles and can offer life-saving services of localizing victims of natural disasters or during major infrastructure failures.
Test case prioritization which aims to improve the efficiency of regression testing by ordering test cases is an active research topic that has attracted increasing attention recently. This paper proposes an efficient Ant Colony System(ACS) framework to solve the coverage based test case prioritization problem. A tour based heuristic function and a tree shape pheromone updating rule are designed. The underlying rationale is to make full use of the ants' partially built solutions in their later traveling and to vary their search at the same time. The proposed method is tested on six benchmark problems with different scales, and the experimental results have demonstrated that the proposed method can outperform several state-of-the-art methods in terms of the Average Percentage of Statement Coverage(APSC).
Cuckoo search (CS), as a relatively recent emerged swarm intelligence algorithm, is powerful and popular for the complex real parameter global optimization. However, the premature convergence has greatly affected the performance of original CS. Inspired from the individuals in the population will converge to the weighted average of global best and personal best in particle swarm optimization (PSO), we proposed a novel Gaussian bare-bones CS algorithm, named GBCS, in which the new solution for a cuckoo is generated by the Lévy flight or the Gaussian bare-bones method in a random manner. Experimental results have proved that the proposed algorithm is promising.
Artificial bee colony algorithm based on adaptive local information sharing: approach for several dynamic changes
This paper focuses on Artificial Bee Colony (ABC) algorithm in dynamic optimization problems (DOPs), and proposes the improvements for ABC algorithm in DOPs as ABC algorithm based on adaptive local information sharing (ABC-alis). To investigate the tracking ability to dynamic change of ABC-alis, it is compared the improved algorithm to two cases of dynamic change. These two cases are "Case 1: Periodic Change" and "Case 2: Continuing Change". The experimental results revealed that the following implications: (1) ABC-alis can adapt with various dynamic changes; (2) ABC-alis has high tracking performance against continuous change.
Multiple swarm intelligence methods based on multiple population with sharing best solution for drastic environmental change
This paper proposes the multiple swarm optimization method composed of some numbers of populations, each of which is optimized by the different swarm optimization algorithm to adapt to dynamically change environment. To investigates the effectiveness of the proposed method, we apply it into the complex environment, where the objective function changes in a certain interval. The intensive experiments have revealed that the performance of the proposed method is better than the other conventional algorithms (i.e., particle swarm optimization (PSO), cuckoo search (CS), differential evolution (DE)) in terms of convergence and fitness.
We propose a scouting strategy to find better searching directions in fireworks algorithm (FWA) to enhance its exploitation capability. It generates spark individuals from a firework individual one by one by checking if the generated spark climbs up to a better direction, and this process continues until spark individual climbing down is generated, while canonical FWA generates spark individuals around a firework individual at once. We can know potential search directions from the number of consciously climbing up sparks. Besides this strategy, we use a filtering strategy for a random selection of FWA, where worse sparks are eliminated when their fitness is worse than their parents, i.e. fireworks, and become unable to survive in the next generation. We combined these strategies with the enhanced FWA (EFWA) and evaluated using 28 CEC2013 benchmark functions. Experimental results confirm that the proposed strategies are effective and show better performance in terms of convergence speed and accuracy. Finally, we analyze their applicability and provide some open topics.
Improving the accuracy of 2D-3D registration of femur bone for bone fracture reduction robot using particle swarm optimization
Population-based optimization algorithms have proved themselves very effective and efficient way for solving some complex problems, particularly for problems of non-linear and non-convex nature. 2D-3D registration is one such problem where inherent non-linearity and high-dimensionality along with non-convex optimization nature makes it very difficult to achieve satisfying accuracy especially when starting point for optimization is not ideal. Because of the underlying structure of population-based optimization algorithms, especially particle swarm optimization (PSO), 2D-3D registration with PSO is expected to yield better accuracy compared to conventional gradient-based optimization algorithms. Another considerable factor is that gradient approximation error makes non-gradient methods more favorable for the case of 2D-3D registration over gradient-based methods. Our experiment on 2D-3D registration using virtual X-ray shows that PSO has better accuracy and convergence rate than gradient based approaches like Stochastic Gradient Descent (SGD), Momentum Stochastic Gradient Descent (MSGD) and Nesterov Accelerated Gradient (NAG).
POSTER SESSION: Poster: complex systems (artificial life/artificial immune systems/generative and developmental systems/evolutionary robotics/evolvable hardware)
In this work, we focus on the Dendritic Cell Algorithm (DCA), a bio-inspired classifier, and its limitation when coping with very large datasets. To overcome this limitation, we propose a novel distributed DCA version for data classification based on the MapReduce framework to distribute the functioning of this algorithm through a cluster of computing elements. Our experimental results show that our proposed distributed solution is suitable to enhance the performance of the DCA enabling the algorithm to be applied over big data classification problems.
Promoting diversity in an evolving population is important for Evolutionary Computation (EC) because it reduces premature convergence on suboptimal fitness peaks while still encouraging both exploration and exploitation . However, some types of diversity facilitate finding global optima better than other types. For example, a high mutation rate may maintain high population-level diversity, but all of those genotypes are clustered in a local region of a fitness landscape. Fitness sharing , on the other hand, promotes diversity via negative density dependence forcing solutions apart. Lexicase selection  goes one step further, dynamically selecting for diverse phenotypic traits, encouraging solutions to actively represent many portions of the landscape.
Evolution in nature has allowed biological systems to develop and survive in many different environments. It can be attributed to one of the major features of natural evolution: its open-endedness, that can be considered as the ability to continuously produce novelty and/or complexity . This feature is critical to allow an agent to continuously adapt to its environment. We propose here an extension of Quality Diversity algorithms to make it more open-ended. Quality Diversity algorithms aim at generating a large set of diverse solutions [3, 10]. They can be used in a two-steps process in which (1) a diverse set of solutions is generated offline before (2) the agent can exploit it online to find the behavior that fits to the situation [2, 4--6]. QD algorithms main goal is to fill a behavior space whose dimensions are defined by behavior descriptors. Current QD algorithms can generate novelty and complexity, but within the frame of these behavior descriptors. To make the evolutionary process more open-ended, we extend Cully and Demiris framework  and introduce Multi-Container Quality Diversity algorithms (MCQD). MCQD are QD algorithms relying on multiple behavior spaces that can be added on the fly. MCQD thus aims at implementing an open-ended evolutionary process that would explore any new behavior space that could be found of interest during the search process.
We show that the Baldwin effect is capable of evolving few-shot supervised and reinforcement learning mechanisms, by shaping the hyperparameters and the initial parameters of deep learning algorithms. This method rivals a recent meta-learning algorithm called MAML "Model Agnostic Meta-Learning," which uses second-order gradients instead of evolution to learn a set of reference parameters that can allow rapid adaptation to tasks sampled from a distribution. The Baldwin effect does not require gradients to be backpropagated to the reference parameters or hyperparameters, and permits effectively any number of gradient updates in the inner loop, learning strong learning dependent biases.
Evolutionary hexapod robot gait control using a new recurrent neural network learned through group-based hybrid metaheuristic algorithm
This paper proposes a new recurrent neural network (RNN) structure evolved to control the gait of a hexapod robot for fast forward walking. In this evolutionary robot, the gait control problem is formulated as an optimization problem with the objective of a fast forward walking speed and a small deviation in the forward walking direction. Evolutionary optimization of the RNNs through a group-based hybrid metaheuristic algorithm is proposed to find the optimal RNN controller. Preliminary simulation results with comparisons show the advantage of the proposed approach1.
Muscle and tendon elasticity enables animals to interact with their environment softly, reducing ground impact force and increasing efficiency of locomotion. Traditional rigid body robots remain the commercially viable option, but incorporating flexibility can harness the benefits exhibited by natural organisms. In this paper, we examine how the addition of passive flexibility impacts performance and locomotive efficiency in a quadruped animat. Results show that the addition of flexibility in the spine and lower limbs of a quadruped animat significantly increases the distance traveled compared to a fully rigid-body animat. However, replacing these passively flexibile joints with actively controlled joints results in the farthest traveling individuals while maintaining similar efficiency. It appears that increases in DOF and joint configuration are the drivers of performance increases rather than passive flexibility.
The emergence and inter-play of cooperation versus competition in groups of individuals has been widely studied, for example using game-theoretic models of eusocial insects ,  experimental evolution in bacterium , and agent-based models of societal institutions . Game theory models have been demonstrated as indispensable analytical tools to complement our understanding of the emergence and social mechanics of natural phenomena such as cooperation and competition. For example, game theory models have supported the supposition that cooperation between individuals and competition between groups are critical factors in cultural evolution in human societies . However, such game theory models are ultimately limited by their own abstractions and lack consideration for the role of complex phenomena such as evolutionary and environmental change in shaping emergent social phenomena.
Policy (behavior) transfer is a method to speed-up and improve learning by leveraging knowledge from learning in related but simpler tasks. That is, learned information is reused and shared between a source and target tasks, where target tasks were used as a starting point for continuing learning . Policy transfer has been widely studied in the context of Reinforcement Learning (RL) methods , where various studies have consistently demonstrated that transferring knowledge learned on a source task accelerates learning and increases solution quality in target tasks by exploiting relevant prior knowledge .
We use an evolutionary robotics approach to demonstrate how the choice of robot morphology can affect one specific aspect of neural networks: their ability to resist catastrophic forgetting.
Wagner's modularity inducing problem domain is a key contribution to the study of the evolution of modularity, including both evolutionary theory and evolutionary computation. We study its behavior under classical genetic algorithms. Unlike what we seem to observe in nature, the emergence of modularity is highly conditional and dependent, for example, on the eagerness of search. In nature, modular solutions generally dominate populations, whereas in this domain, modularity, when it emerges, is a relatively rare variant. Emergence of modularity depends heavily on random fluctuations in the fitness function; with a randomly varied but unchanging fitness function, modularity evolved far more rarely. Interestingly, high-fitness non-modular solutions could frequently be converted into even-higher-fitness modular solutions by manually removing all inter-module edges. Despite careful exploration, we do not yet have a full explanation of why the genetic algorithm was unable to find these better solutions.
To date, efforts to automatically configure problem representations for classes of optimization problems have yielded few practical results. We show that a recently proposed approach for training neural G-P maps for optimization problems yields maps that generalize poorly to translated problem instances. We propose that alternative neural architectures---especially ones that allow the number of control genes to be greater than the number of phenotypic traits---may provide a means of learning maps that are better able to generalize to new problem instances.
POSTER SESSION: Poster: digital entertainment technologies and arts
A proposal for distributed interactive differential evolution: in a case of creating sign sounds for multiple users
Interactive Evolutionary Computation (IEC) is used for creating media contents suited to each user's feelings. To obtain media contents commonly suited to multiple users, distributed approach was employed in previous IECs based on Genetic Algorithm. This study proposes Distributed Interactive Differential Evolution (DIDE) by employing Differential Evolution (DE). Based on each user's subjective selection and scoring with Interactive DE, DIDE exchanges good solutions between users. Through the exchange, it is expected that the good solution for all users is obtained. A fundamental experiment was conducted with a simple DIDE system creating sign sounds for two users. Distance between DE vectors obtained by two users and fitness values were investigated.
Interactive Evolution (
Real-time video game problems are very challenging because of short response times and numerous state space issues. As global companies and research institutes such as Google, Facebook, Intel and Carnegie Mellon university continue to develop Artificial Intelligence(AI) and participated in various Game AI competitions, many AI developers are implementing algorithms, such as Monte Carlo Tree Search (MCTS) and Deep Reinforcement Learning (DRL), to solve problems. However, these algorithms also have a number of limitations, including the inability to effectively calculate the number of possible cases present in the games and the large amount of time required for computation. We combine the genetic algorithm, which is very effective in finding general solutions to solve the constraints of AI, and the MCTS, which dominates the recent Fighting Game AI Competition, into a hierarchical structure. We propose to call it Hybrid Fighting Game AI.
Silhouette-based three dimensional image registration using CMA-ES with joint scheme of partial restart and variable fixing
This paper proposes a three-dimensional (3D) entire shape reconstruction method that performs simultaneous 3D registration of multiple depth images obtained from multiple viewpoints. With the combination of a silhouette-based objective function and evolutionary computation algorithms, the proposed method realizes the entire shape reconstruction from small number (two or three) of depth images, which do not involve enough overlapping regions for other 3D registration methods. In particular, this paper proposes a CMA-ES algorithm with regional intensification techniques (CMA-ESPR+VF) to speed up the registration process. Experimental results show that the proposed CMA-ESPR+VF achieved a speedup that is at most 18 times faster than self-adaptive differential evolution.
POSTER SESSION: Poster: evolutionary combinatorial optimization and metaheuristics
Automatic Design of Algorithms (ADA) treats algorithm choice and design as a machine learning problem, with problem instances as training data. However, this paper reveals that, as with classification and regression, for ADA not all training sets are equally valuable.
We apply genetic programming ADA for bin packing to several new and existing benchmark sets. Using sets with narrowly-distributed features for training results in highly specialised algorithms, whereas those with well-spread features result in very general algorithms. Variance in certain features has a strong correlation with the generality of the trained policies.
Estimation of distribution algorithms have already demonstrated their utility when solving a broad range of combinatorial problems. However, there is still room for methodological improvements when approaching constrained type problems. The great majority of works in the literature implement external repairing or penalty schemes, or use ad-hoc sampling methods in order to avoid unfeasible solutions. In this work, we present a new way to develop ED As for this type of problems by implementing distance-based exponential probability models defined exclusively on the set of feasible solutions. In order to illustrate this procedure, we take the 2-partition balanced Graph Partitioning Problem as a case of study, and design efficient learning and sampling methods in order to use these distance-based probability models in EDAs.
We consider the design of a supply chain network for a blood bank system to satisfy the needs of hospitals in a certain region, by integrating strategic, tactical and operational decisions. In the current blood distribution network, hospitals keep their own inventory and procure bloods from a main blood bank. We propose an alternative model, in which, some of the hospitals are selected as local blood banks (LBBs) and serve the hospitals that are assigned to them. Thus, we try to solve a complex problem which aims to find optimal number and locations of LBBs, assignment of hospitals to opened LBBs and the weekly and daily routes between the facilities. We formulate a mixed integer nonlinear programming model to combine these decisions to minimize total system cost and propose a simulated annealing heuristic approach to find near optimal solutions. We analyze the performance of the heuristic via detailed numerical studies.
This paper investigates evolving routing policy for general Uncertain Capacitated Arc Routing Problems (UCARP) with any number of vehicles, and for the first time, designs a novel model for online decision making (i.e. meta-algorithm) for multiple vehicles in service simultaneously. Then, we develop a GPHH based on the meta-algorithm. The experimental studies show the GPHH can evolve much better policies than the state-of-the-art manually designed policy. In addition, the reusability of the evolved policies dramatically decreases when the number of vehicles changes, which suggests a retraining process when a new vehicle is brought or an existing vehicle breaks down.
Resource scheduling is always a highly concerned NP-hard problem in operations research. Taking advantage of estimation of distribution (EDA) algorithms, this paper develops a histogram EDA (HEDA) for resource scheduling. First, a histogram-based distribution model is adopted. The height of each bin in the histogram is updated using the accumulation strategy according to the ranking of individuals. Second, a repair strategy is applied to fix all the newly sampled solutions into feasible ones that satisfy the deadline constraint. Experimental results show that the proposed HEDA is promising, particularly in large-scale instances.
This study considers single machine scheduling with the machine operating at varying speed levels for different jobs with release dates and sequence-dependent setup times, in order to examine the trade-off between makespan and total energy consumption. A bi-objective mixed integer linear programming model is developed employing this speed scaling scheme. The augmented ε-constraint method with a time limit is used to obtain a set of non-dominated solutions for each instance of the problem. An energy-efficient multi-objective variable block insertion heuristic is also proposed. The computational results on a benchmark suite consisting of 260 instances with 25 jobs from the literature reveal that the proposed algorithm is very competitive in terms of providing tight Pareto front approximations for the problem.
In the domain of Service-Oriented Architecture, web services are selected and composed to meet users' functional and non-functional requirements. A few researchers have proposed Evolutionary Computation (EC) techniques for service composition problems, where semantic matchmaking quality and Quality of Service (QoS) are individually or jointly optimised. However, these EC-based approaches allow best individuals (i.e., composition solutions) to be carried across generations, but does not consider the knowledge of the promising individuals for breeding better solutions. Due to its capability of learning the knowledge of good solutions, Estimation of Distribution Algorithm (EDA) has been successfully applied to tackle semi-automated QoS-aware service composition, where an abstract composition workflow is assumed known. However, this assumption is not always satisfied, so learning the knowledge of solutions without pre-given workflows is very challenge. We propose an EDA-based service composition approach to jointly optimize QoS and semantic matchmaking quality in a fully automated way and our experiment evaluation demonstrates the efficiency and the effectiveness of our proposed approach.
Feature construction in genetic programming hyper-heuristic for dynamic flexible job shop scheduling
Genetic Programming Hyper-Heuristic (GPHH) has shown success in evolving dispatching rules for dynamic Flexible Job Shop Scheduling (FJSS). In this paper, we focus on feature construction to improve the effectiveness and efficiency of GPHH, and propose a GPHH with Cooperative Co-evolution with Feature Construction (CCGP-FC). The experimental results showed that the proposed CCGP-FC could improve the smoothness of the convergence curve, and thus improve the stability of the evolutionary process. There is a great potential to improve the FC methods, such as filtering the meaningless building blocks, and incorporating with feature selection to improve the terminal set.
A barrier tree is a model for representing the hierarchical distribution of local optima and valleys. While it is useful, constructing a barrier tree is challenging for a large problem instance. In this paper, we propose an efficient method to approximate the barrier tree. One important subgoal is to estimate a saddle point between two solutions, and it is achieved by exploiting the bias of the Great Deluge Algorithm. We also present a case study of a pseudo-boolean problem of size 296, which is roughly 6 times larger than the scale that the existing methods can handle.
he research in capacitated arc routing problems (CARPs) is getting more and more attention for its wide applications in reality. Memetic algorithms (MAs) are promising in solving CARPs, but the intensity of local search (LS) in MAs should adapt to the evolution of the population for achieving the maximal effectiveness. In this paper, a novel MA based on adaptive adjustment of LS intensity (LIMA) is proposed. LIMA dynamically adjusts the probability of LS according to the distance between the individual of the population and the solution lower bound for further deepening the LS depth of potential solutions. It makes the algorithm spend as much time as possible on more potential solutions, so as to shorten the computation time and speed up the convergence. Experimental results show that LIMA has faster convergence speed and better global search ability than traditional MAs. Adaptively tuning the LS intensity of a MA has high potential for solving complex problems.1
POSTER SESSION: Poster: evolutionary machine learning
This paper introduces a hybrid system called R-EDML, combining the sequential decision making of Reinforcement Learning (RL) with the evolutionary feature prioritizing process of Evolutionary Distance Metric Learning (EDML) in clustering aiming to optimize the input space by reducing the number of selected features while maintaining the clustering performance. In the proposed method, features represented by the elements of EDML distance transformation matrices are prioritized. Then a selection control strategy using Reinforcement Learning is learned. R-EDML was compared to normal EDML and conventional feature selection. Results show a decrease in the number of features, while maintaining a similar accuracy level.
Accelerating the evolution of convolutional neural networks with node-level mutations and epigenetic weight initialization
This paper examines three generic strategies for improving the performance of neuro-evolving convolutional neural networks (CNNs): node-level mutation operations, epigenetic weight initialization and pooling connections. These were implemented using the Evolutionary eXploration of Augmenting Convolutional Topologies (EXACT) algorithm. Results were gathered over the period of a month using a volunteer computing project, where over 225,000 CNNs were trained and evaluated across 16 different EXACT searches. The node mutation operations where shown to dramatically improve evolution rates over traditional edge mutation operations (as used by the NEAT algorithm), and epigenetic weight initialization was shown to further increase the accuracy and generalizability of the trained CNNs. As a negative but interesting result, allowing for pooling connections was shown to degrade the evolution progress. The best trained CNNs reached 99.46% accuracy on the MNIST test data in under 13,500 CNN evaluations - accuracy comparable with some of the best human designed CNNs.
Neuroevolution under unimodal error landscapes: an exploration of the semantic learning machine algorithm
Neuroevolution is a field in which evolutionary algorithms are applied with the goal of evolving Neural Networks (NNs). This paper studies different variants of the Semantic Learning Machine (SLM) algorithm, a recently proposed supervised learning neuroevolution method. Perhaps the most interesting characteristic of SLM is that it searches over unimodal error landscapes in any supervised learning problem where the error is measured as a distance to the known targets. SLM is compared with the NeuroEvolution of Augmenting Topologies (NEAT) algorithm and with a fixed-topology neuroevolution approach. Experiments are performed on a total of 9 real-world regression and classification datasets. The results show that the best SLM variants generally outperform the other neuroevolution approaches in terms of generalization achieved, while also being more efficient in learning the training data. The best SLM variants also outperform the common NN backpropagation-based approach under different topologies. The most efficient SLM variant used in combination with a recently proposed semantic stopping criterion is capable of evolving competitive neural networks in a few seconds on the vast majority of the datasets considered. A final comparison shows that a NN ensemble built with SLM is able to outperform the Random Forest algorithm in two classification datasets.
Sorting data into groups and clusters is one of the fundamental tasks of artificially intelligent systems. Classical clustering algorithms rely on heuristic (k-nearest neighbours) or statistical methods (k-means, fuzzy c-means) to derive clusters and these have performed well. Neural networks have also been used in clustering data, but researchers have only recently begun to adopt the strategy of having neural networks directly determine the cluster membership of an input datum. This paper presents a novel strategy, employing NeuroEvolution of Augmenting Topologies to produce an evoltionary neural network capable of directly clustering unlabelled inputs. It establishes the use of cluster validity metrics in a fitness function to train the neural network.
A recent approach for improving the accuracy of ensemble models is confidence-based modeling. Thereby, confidence measures, which indicate an ensemble prediction's reliability, are used for identifying unreliable predictions in order to improve a model's accuracy among reliable predictions. However, despite promising results in previous work, no comparable results for public benchmark data sets have been published yet.
This paper applies confidence-based modeling with GP-based symbolic binary classification ensembles on a set of medical benchmark problems to make statements about the concept's general applicability. Moreover, extensions for multiclass classification problems are proposed.
Adaptive boosting (AdaBoost) is a method for building classification ensemble, which combines multiple classifiers built in an iterative process of reweighting instances. This method proves to be a very effective classification method, therefore it was the major part of our evolutionary inspired classification algorithm.
In this paper, we introduce the Genetic Programming with AdaBoost (GPAB) which combines the induction of classification trees with genetic programming (GP) and AdaBoost for multiple class problems. Our method GPAB builds the ensemble of classification trees and uses AdaBoost through the evolution to weight instances and individual trees.
To evaluate the potential of the proposed evolutionary method, we made an experiment where we compared the GPAB with Random Forest and AdaBoost on several standard UCI classification benchmarks. The results show that GPAB improves classification accuracy in comparison to other two classifiers.
Subspace clustering techniques become popular in identifying local patterns from high dimensional data. In this paper, we present a multiobjective optimization based evolutionary algorithm in order to tackle the subspace clustering problem. Previous state-of-the-art algorithms on subspace clustering optimize implicitly or explicitly a single cluster quality measure. The proposed approach optimizes two cluster quality measures namely PBM-index and XB-index simultaneously. The developed algorithm is applied to seven standard real-life datasets for identifying different subspace clusters. Experimentation reveals that the proposed algorithm is able to take advantages of its evolvable genomic structure and multiobjective based framework and it can be applied to any data set.
Learning how to flock: deriving individual behaviour from collective behaviour with multi-agent reinforcement learning and natural evolution strategies
This work proposes a method for predicting the internal mechanisms of individual agents using observed collective behaviours by multi-agent reinforcement learning (MARL). Since the emergence of group behaviour among many agents can undergo phase transitions, and the action space will not in general be smooth, natural evolution strategies were adopted for updating a policy function. We tested the approach using a well-known flocking algorithm as a target model for our system to learn. With the data obtained from this rule-based model, the MARL model was trained, and its acquired behaviour was compared to the original. In the process, we discovered that agents trained by MARL can self-organize flow patterns using only local information. The expressed pattern is robust to changes in the initial positions of agents, whilst being sensitive to the training conditions used.
In this study, a neuroevolution strategy using Multi-Agent Incorporated Hierarchical Ensemble Model (MAIHEM) inspired by human incorporated company structure is proposed. It utilizes the hierarchical structure to ensemble modules of entities into firms to preserve complex structure at lower level, and at higher level incorporates firms into departments to facilitate multiple objectives. The corporate level structure from the top guides and reviews their overall performance. The ensemble structure not only compete within their own ranks, but also cooperate and swap/merger underlying units for fast adaptation without compromising their existing structures. The preliminary result with multi-constrained music melody generation shows this strategy can not only solve complex multi-objective tasks steadily but also preserve diversity in the population.
Automatic clustering problems, which need to detect the appropriate clustering solution without a pre-defined number of clusters, still remain challenging in unsupervised learning. In many related works, cluster validity indices (CVIs) play an important role to evaluate the goodness of partitioning of data sets. However, there is no CVI that is likely to ensure reliable results for different structures of data. In this paper, we present a study of evolutionary many-objective optimization (EMaO) based automatic clustering, in contrast to the weighted sum validity function defined in literature, several validity functions (more than 3) are considered to be optimized simultaneously here. Since the research of EMaO is still in its fancy, we take four state-of-the-art EMaO algorithms into consideration as the underlying optimization tool. To be more applicable and efficient for clustering problems, the encoding scheme and genetic operators are redesigned. Experiments show that, for the purpose of this study, it is promising to address automatic clustering problems based on a suitable EMaO approach.
POSTER SESSION: Poster: evolutionary multiobjective optimization
Probabilistic modeling in multi-objective optimization problems (MOPs) has mainly focused on capturing and representing the dependencies between decision variables in a set of selected solutions. Recently, some works have proposed to model also the dependencies between the objective variables, which are represented as random variables, and the decision variables. In this paper, we investigate the suitability of copula models to capture and exploit these dependencies in MOPs with a continuous representation. Copulas are very flexible probabilistic models able to represent a large variety of probability distributions.
Benchmarking multiobjective evolutionary algorithms and constraint handling techniques on a real-world car structure design optimization benchmark problem
While many of real-world industrial design problems involve several constraints, researches on multiobjective evolutionary algorithms (MOEAs) for problems with many constraints or the benchmark problems themselves are limited. The novel constrained multiobjective optimization benchmark problem based on a real-world car structure design optimization problem, termed Mazda CdMOBP, has more desirable characteristics as a constrained benchmark problem than the existing ones. The experimental results with 12 constrained MOEAs on this problem suggest the importance of balancing all of three factors of convergence, diversity, and feasibility and knowledge of proper settings of not only MOEA and CHT but also these parameters are imperative for application of MOEAs to industrial design problems.
Introducing a linkage identification considering non-monotonicity to multi-objective evolutionary optimization with decomposition for real-valued functions
In this paper, we propose MOEA/D-LIEM2 to optimize multiple real-valued objective functions which have complex interaction among variables by employing linkage identification. We compared the proposed algorithm with MOEA/D without linkage identification. As a result, we found that the proposed algorithm out-performs the original MOEA/D for problems consisting of two deceptive functions with linkage.
Accelerating a multi-objective memetic algorithm for feature selection using hierarchical k-means indexes
The (α, β)-k Feature Set Problem is a mathematical model proposed for multivariate feature selection. Unfortunately, addressing this problem requires a combinatorial search in a space that grows exponentially with the number of features. In this paper, we propose a novel index-based Memetic Algorithm for the Multi-objective (α, β)-k Feature Set Problem. The method is able to speed-up the search during the exploration of the neighborhood on the local search procedure. We evaluate our algorithm using six well-known microarray datasets. Our results show that exploiting the natural feature hierarchies of the data can have, in practice, a significant positive impact on both the solutions' quality and the algorithm's execution time.
A benchmark problem based on a real-world car structure design optimization1 is proposed. The benchmark problem is constructed by using a response surface method from the design optimization result of a car structure design optimization problem. Because this benchmark problem bases on actual car structure design optimization result conducted by Mazda, it contains features of real-world design optimization problems. Objectives are the minimization of the total weight of the different type of cars and maximization of the number of common gauge (standard plate thickness) parts among the different type of cars. This benchmark problem has 148 discrete design parameters and 36 design constraints for simultaneous design optimization of two types of cars and 222 discrete design parameters and 54 design constraints for simultaneous design optimization of three types of cars. Thus, it is a scalable and multiobjective design optimization problem with many and discrete design parameters and many and severe constraints. The benchmark problem is available on our website (http://ladse.eng.isas.jaxa.jp/benchmark/).
In this paper we adapt ϵ-lexicase selection, a parent selection strategy designed for genetic programming, to solve many-objective optimization problems, ϵ-lexicase selection has been shown to perform well in regression due to its use of full program semantics for conducting selection. A recent theoretical analysis showed that this selection strategy preserves individuals located near the boundaries of the Pareto front in semantic space. We hypothesize that this strategy of biasing search to extreme positions in objective space may be beneficial for many-objective optimization as the number of objectives increases. Here, we replace program semantics with objective fitness to define ϵ-lexicase selection for many-objective optimization. We then compare this method to multi-objective optimization methods from literature on problems ranging from 3 to 100 objectives. We find that ϵ-lexicase selection outperforms state-of-the-art optimization algorithms in terms of convergence to the Pareto front, spread of solutions, and CPU time for problems with more than 3 objectives.
Preference-based evolutionary algorithms for many-objective mission planning of agile earth observation satellites
The mission planning of agile earth observation satellite (AEOS) involves multiple objectives to be optimized simultaneously. Total profit, observed target number, averaged image quality, satellite usage balance and averaged timeliness are the five objectives considered in this paper. The problem is a mixed-integer problem with constraints and belongs to the class of NP-hard problems. Two preference-based evolutionary algorithms, i.e., T-NSGA-III and T-MOEA/D, are proposed with problem-specific coding and decoding strategies to solve the problem. Target region, which is defined by preferred range of each objective, is used for preference articulation. Experiments show that the proposed algorithms can obtain Pareto optimal solutions within the target region efficiently. They outperform Pareto-based T-NSGA-II with regard to Hypervolume indicator and CPU runtime.
Despite the extensive application of multi-objective evolutionary algorithms (MOEAs) to solve multi-objective optimization problems (MOPs), understanding their working principles is still open to research. One of the most popular and successful MOEA approaches is based on Pareto dominance and its relaxed version, Pareto ϵ-dominance. However, such approaches have not been sufficiently studied in problems of increased complexity. In this work, we study the effects of the working mechanisms of the various components of these algorithms on test problems with difficult Pareto set topologies. We focus on separable unimodal and multimodal functions with 2, 3, and 4 objectives, all having difficult Pareto set topologies. Our experimental study provides some interesting and useful insights to understand better Pareto dominance-based MOEAs.
The road to a better design of multi- and many-objective evolutionary algorithms requires a deeper understanding of their behavior. A step on this road has recently been taken with the proposal of compartmental models to study population dynamics. In this work, we push this step further by introducing a new set of features that we link with algorithm performance. By tracking the number of newly discovered Pareto Optimal (PO) solutions, the previously-found PO solutions and the remaining non-PO solutions, we can track the algorithm progression. By relating these features with a performance measure, such as the hypervolume, we can analyze their relevance for algorithm comparison. This study considers out-of-the-box implementations of recognized multi- and many-objective optimizers belonging to popular classes such as conventional Pareto dominance, extensions of dominance, indicator, and decomposition based approaches. In order to generate training data for the compartmental models, we consider multiple instances of MNK-landscapes with different numbers of objectives.
A large number of Multi-Objective Evolutionary Algorithms employ reference directions in order to establish relative preferences for each objective function. Uniform Design (UD), Simplex Lattice Design (SLD) and their variants are techniques commonly used to generate a set of uniformly distributed reference directions with the aim of capturing the whole Pareto optimal front. In this paper, we present a comparative study of UD and SLD methods when solving Many-objective Optimization problems and we design a new strategy that combines SLD with multiple layers and UD techniques. Our preliminary results indicate that our proposed approach is able to outperform state-of-the-art methods in many-objective optimization problems.
In many practical multi-objective optimization problems, evaluations of objectives and constraints are computationally time-consuming because they require expensive simulations of complicated models. In this paper, we propose a metamodel-based multi-objective evolutionary algorithm to make a balance between error uncertainty and progress. In contrast to other trust region methods, our method deals with multiple trust regions. These regions can grow or shrink in size according to the deviation between metamodel prediction and high-fidelity evaluation. We introduce a performance indicator based on hypervolume to control the size of the trust regions. We compare our results with a standard metamodel-based approach without trust region and a multi-objective evolutionary algorithm. The results suggest that our trust region based methods can effectively solve test and real-world problems using limited solution evaluations with increased accuracy.
Bilevel innovization: knowledge discovery in scheduling systems using evolutionary bilevel optimization and visual analytics
Determining a scheduling system's framework conditions (e.g. number of vehicles or employees) results in a hierarchical optimization problem, which can be solved through evolutionary bilevel optimization. In this paper, we propose an approach to gain better understanding of a scheduling system's behavior by applying visual analytics on the whole set of evaluated solutions during the bilevel optimization procedure. The results show that bilevel innovization can be used to support the decision making process in a strategic planning context by providing useful information regarding the scheduling system's behavior.
Balancing exploration and exploitation is fundamental to the performance of an evolutionary algorithm. In this paper, we propose a survival analysis method to address this issue. Results of the analysis is used to adaptively choose appropriate new solution creation operators which prefer either exploration or exploitation. In the developed algorithm, a differential evolution recombination operator is used for the exploration purpose, while a new clustering-based operator is proposed for exploitation. Empirical comparison with four well-known multi-objective evolutionary algorithms on test instances with complex Pareto sets and Pareto fronts indicates the effectiveness and outperformance of the developed algorithms on these test instances in terms of commonly-used metrics.
Visualization of the boundary solutions of high dimensional pareto front from a decision maker's perspective
For the last couple of years, the development of many-objective optimization problems opened new avenues of research in the evolutionary multi-objective optimization domain. There are already a number of algorithms to solve such problems, now the next challenge is to interpret the results produced by those algorithms. In this paper, we propose an alternative way to visualize high-dimensional Pareto fronts where the goal is to present the Pareto front in terms of a decision maker's perspective. A decision maker is more interested in the different aspects of the end results instead of the convergence and spread of a Pareto front solutions. They are interested in Pareto-optimal solutions that offer the most trade-off. They are also interested to know the boundary solutions of a Pareto front. In this paper, we present a way to visualize the Pareto front in high dimension by keeping those criteria in mind.
Nondominated sorting (NS) is commonly needed in multi-objective optimization to distinguish the fitness of solutions. Since it was suggested, several NS algorithms have been proposed to reduce its time complexity. In our study, we found that their performances are closely related to properties of the distribution of a data set, especially the number of fronts. To address this issue, we propose a novel NS algorithm Filter Sort. We also propose a new benchmark data generator for evaluating the performance of a NS algorithm. Experimental results show that our algorithm is superior to several state-of-the-art NS algorithms in most cases.
In parallel and distributed environments, generational evolutionary algorithms often do not exploit the full potential of the computation system since they have to wait until the entire population is evaluated before starting selection procedures. Steady-state algorithms can perform fitness evaluations asynchronously however, if the algorithm updates its state in a complicated way - which is common in multiobjective evolutionary algorithms - the threads will eventually have to wait until this update finishes.
The most expensive part of the update procedure in NSGA-II is non-dominated sorting. We turned the existing incremental non-dominated sorting algorithm into an asynchronous one using several concurrency techniques: a single entry-level lock, finer-grained locks on non-domination levels, and a non-blocking approach using compare-and-set operations. Our experimental results reveal the trade-off between the work-efficiency of the algorithm and the achieved amount of parallelism.