Editorial scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems

This editorial note presents the motivations, objectives, and structure of the special issue on scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems. In addition, it provides the link to an associated Website where complementary material to the special issue is available.     

Scheduling using tabu search methods with intensification and diversification

After spending five years in Medical School, physician students have to complete additional study including several interships before becoming full members of their professional guild. In this paper, we deal with the annual scheduling of internships taking into account the supervision capacities of the hospitals. The problem is modeled as an assignment-type problem. Several variants of Tabu Search procedures including intensification and diversification strategies are proposed and tested to deal with this problem. The numerical results indicate that the solution quality can be improved using intensification and diversification, at the expense of increasing solution time.Scope and purposeAfter spending five years in Medical School, future physicians have to complete additional study including several internships before becoming full members of their professional guild. The number of internships to be completed, their subject area, and their length depend on the student specialization. In this paper, we analyze the problem faced by the medical school each year to specify the schedule for each student's internships. For each of his internships, a student specifies preferences about its time period and the location. The objective function is to maximize the overall satisfaction of the students. The constraints correspond to the bounds (lower and upper) on the number of students that the hospitals are ready to supervise for each type of internships and for each period of the year. The problem is formulated as an assignment-type problem. To deal with this problem, we propose several variants of local search heuristic procedures including strategies to intensify the search in specific region of the feasible domain (intensification), and others to search the whole feasible domain more extensively (diversification). These variants are tested and compared to establish the tradeoff between solution time and solution quality.     

Coevolving memetic algorithms: a review and progress report.

Coevolving memetic algorithms are a family of metaheuristic search algorithms in which a rule-based representation of local search (LS) is coadapted alongside candidate solutions within a hybrid evolutionary system. Simple versions of these systems have been shown to outperform other nonadaptive memetic and evolutionary algorithms on a range of problems. This paper presents a rationale for such systems and places them in the context of other recent work on adaptive memetic algorithms. It then proposes a general structure within which a population of LS algorithms can be evolved in tandem with the solutions to which they are applied. Previous research started with a simple self-adaptive system before moving on to more complex models. Results showed that the algorithm was able to discover and exploit certain forms of structure and regularities within the problems. This "metalearning" of problem features provided a means of creating highly scalable algorithms. This work is briefly reviewed to highlight some of the important findings and behaviors exhibited. Based on this analysis, new results are then presented from systems with more flexible representations, which, again, show significant improvements. Finally, the current state of, and future directions for, research in this area is discussed.     

Ranking and comparing evolutionary algorithms with Hellinger-TOPSIS

When multiple algorithms are applied to multiple benchmarks as it is common in evolutionary computation, a typical issue rises, how can we rank the algorithms? It is a common practice in evolutionary computation to execute the algorithms several times and then the mean value and the standard deviation are calculated. In order to compare the algorithms performance it is very common to use statistical hypothesis tests. In this paper, we propose a novel alternative method based on the Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) to support the performance comparisons. In this case, the alternatives are the algorithms and the criteria are the benchmarks. Since the standard TOPSIS is not able to handle the stochastic nature of evolutionary algorithms, we apply the Hellinger-TOPSIS, which uses the Hellinger distance, for algorithm comparisons. Case studies are used to illustrate the method for evolutionary algorithms but the approach is general. The simulation results show the feasibility of the Hellinger-TOPSIS to find out the ranking of algorithms under evaluation.     

An effective model of multiple multi-objective evolutionary algorithms with the assistance of regional multi-objective evolutionary algorithms: VIPMOEAs

Division of the evolutionary search among multiple multi-objective evolutionary algorithms (MOEAs) is a recent advantage in MOEAs design, particularly in effective parallel and distributed MOEAs. However, most these algorithms rely on such a central (re) division that affects the algorithms’ efficiency. This paper first proposes a local MOEA that searches on a particular region of objective space with its novel evolutionary selections. It effectively searches for Pareto Fronts (PFs) inside the given polar-based region, while nearby the region is also explored, intelligently. The algorithm is deliberately designed to adjust its search direction to outside the region – but nearby – in the case of a region with no Pareto Front. With this contribution, a novel island model is proposed to run multiple forms of the local MOEA to improve a conventional MOEA (e.g. NSGA-II or MOEA/D) running along – in another island. To dividing the search, a new division technique is designed to give particular regions of objective space to the local MOEAs, frequently and effectively. Meanwhile, the islands benefit from a sophisticated immigration strategy without any central (re) collection, (re) division and (re) distribution acts. Results of three experiments have confirmed that the proposed island model mostly outperforms to the clustering MOEAs with similar division technique and similar island models on DTLZs. The model is also used and evaluated on a real-world combinational problem, flexible logistic network design problem. The model definitely outperforms to a similar island model with conventional MOEA (NSGA-II) used in each island.     

Building with ParadisEO reusable parallel and distributed evolutionary algorithms

Numerous parallel and distributed evolutionary algorithms (PDEAs) and their implementations have been proposed and are available on the Web. A robust approach to make easier their code and design reuse is the framework approach. In this paper, we present some existing frameworks for PDEAs and their development requirements, and propose a new C++ open source framework, named Parallel and distributed Evolving Objects (ParadisEO). ParadisEO is basically devoted to the reusable and flexible design of parallel and distributed metaheuristics, but we focus here only on PDEAs. Compared to other related frameworks, ParadisEO allows more reuse flexibility, and provides more implemented parallel and distributed models. Furthermore, these models can be exploited by the user in a transparent way, and deployed as well on shared memory multi-processors as on distributed memory machines. The architecture has been experimented on two real-world applications: the radio network design and the spectroscopic data mining. The experimental results demonstrate the efficiency and robustness of the different models.     

Hybrid metaheuristics for scheduling of machines and transport robots in job shop environment

In real manufacturing environments, the control of some elements in systems based on robotic cells, such as transport robots has some difficulties when planning operations dynamically. The Job Shop scheduling Problem with Transportation times and Many Robots (JSPT-MR) is a generalization of the classical Job Shop scheduling Problem (JSP) where a set of jobs additionally have to be transported between machines by several transport robots. Hence, the JSPT-MR is more computationally difficult than the JSP presenting two NP-hard problems simultaneously: the job shop scheduling problem and the robot routing problem. This paper proposes a hybrid metaheuristic approach based on clustered holonic multiagent model for the JSPT-MR. Firstly, a scheduler agent applies a Neighborhood-based Genetic Algorithm (NGA) for a global exploration of the search space. Secondly, a set of cluster agents uses a tabu search technique to guide the research in promising regions. Computational results are presented using two sets of benchmark literature instances. New upper bounds are found, showing the effectiveness of the presented approach.     

Multi-objective evolutionary algorithms and phylogenetic inference with multiple data sets

Evolutionary relationships among species are usually (1) illustrated by means of a phylogenetic tree and (2) inferred by optimising some measure of fitness, such as the total evolutionary distance between species or the likelihood of the tree (given a model of the evolutionary process and a data set). The combinatorial complexity of inferring the topology of the best tree makes phylogenetic inference an ideal candidate for evolutionary algorithms. However, difficulties arise when different data sets provide conflicting information about the inferred `best' tree(s). We apply the techniques of multi-objective optimisation to phylogenetic inference for the first time. We use the simplest model of evolution and a four species problem to illustrate the method.     

EASEA: specification and execution of evolutionary algorithms on GPGPU

EASEA is a framework designed to help non-expert programmers to optimize their problems by evolutionary computation. It allows to generate code targeted for standard CPU architectures, GPGPU-equipped machines as well as distributed memory clusters. In this paper, EASEA is presented by its underlying algorithms and by some example problems. Achievable speedups are also shown onto different NVIDIA GPGPUs cards for different optimization algorithm families.     

On balance and dynamism in procedural content generation with self-adaptive evolutionary algorithms

We consider search-based procedural content generation in the context of Planet Wars, an RTS game. The objective of this work is to generate maps for the aforementioned game, that result in an interesting game-play. In order to characterize interestingness we focus on the properties of balance and dynamism. The former captures the fact that no player is overwhelmed by the opponent during the game, whereas the latter tries to model the fact that there is a lot of action during the game. To measure these properties on a given map, we conduct several games on them using top AI bots and collect statistics which are, in turn, used as inputs of a fuzzy rule base. This system is embedded within an evolutionary algorithm that features self-adaptation of mutation parameters as well as variable-length chromosomes (thus implying maps of different sizes). The experimentation focuses both on the optimization of balance and dynamism as stand-alone properties and in the analysis of the different tradeoffs attainable through them. To reach this goal a multi objective approach is used. We analyze both the usefulness of map-size self-adaptation in each scenario, as well as the properties of maps leading to different tradeoffs between dynamism and balance.     

Design and analysis of migration in parallel evolutionary algorithms

Parallelization is becoming a more important issue for solving difficult optimization problems. Island models combine phases of independent evolution with migration where genetic information is spread out to neighbored islands. This can lead to an increased diversity within the population. Despite many successful applications, the reasons behind the success of island models are not well understood. We perform a first rigorous runtime analysis for island models and construct a function where phases of independent evolution as well as communication among the islands are essential. A simple island model with migration finds a global optimum in polynomial time, while panmictic populations as well as island models without migration need exponential time, with very high probability. Our results lead to new insights into the usefulness of migration, how information is propagated in island models, and how to set parameters such as the migration interval. This is a novel contribution to the theoretical foundation of parallel EAs. Further, we provide empirical results that complement the theoretical results, investigate the robustness with respect to the choice of the migration interval and compare various migration topologies using statistical tests.     

Mean-semivariance portfolio optimization with multiobjective evolutionary algorithms and technical analysis rules

Recent work has been devoted to study the use of multiobjective evolutionary algorithms (MOEAs) in stock portfolio optimization, within a common mean-variance framework. This article proposes the use of a more appropriate framework, mean-semivariance framework, which takes into account only adverse return variations instead of overall variations. It also proposes the use and comparison of established technical analysis (TA) indicators in pursuing better outcomes within the risk-return relation. Results show there is some difference in the performance of the two selected MOEAs – non-dominated sorting genetic algorithm II (NSGA II) and strength pareto evolutionary algorithm 2 (SPEA 2) – within portfolio optimization. In addition, when used with four TA based strategies – relative strength index (RSI), moving average convergence/divergence (MACD), contrarian bollinger bands (CBB) and bollinger bands (BB), the two selected MOEAs achieve solutions with interesting in-sample and out-of-sample outcomes for the BB strategy.     

Contrasting meta-learning and hyper-heuristic research: the role of evolutionary algorithms

The fields of machine meta-learning and hyper-heuristic optimisation have developed mostly independently of each other, although evolutionary algorithms (particularly genetic programming) have recently played an important role in the development of both fields. Recent work in both fields shares a common goal, that of automating as much of the algorithm design process as possible. In this paper we first provide a historical perspective on automated algorithm design, and then we discuss similarities and differences between meta-learning in the field of supervised machine learning (classification) and hyper-heuristics in the field of optimisation. This discussion focuses on the dimensions of the problem space, the algorithm space and the performance measure, as well as clarifying important issues related to different levels of automation and generality in both fields. We also discuss important research directions, challenges and foundational issues in meta-learning and hyper-heuristic research. It is important to emphasize that this paper is not a survey, as several surveys on the areas of meta-learning and hyper-heuristics (separately) have been previously published. The main contribution of the paper is to contrast meta-learning and hyper-heuristics methods and concepts, in order to promote awareness and cross-fertilisation of ideas across the (by and large, non-overlapping) different communities of meta-learning and hyper-heuristic researchers. We hope that this cross-fertilisation of ideas can inspire interesting new research in both fields and in the new emerging research area which consists of integrating those fields.     

An overview of evolutionary algorithms: practical issues and common pitfalls

An overview of evolutionary algorithms is presented covering genetic algorithms, evolution strategies, genetic programming and evolutionary programming. The schema theorem is reviewed and critiqued. Gray codes, bit representations and real-valued representations are discussed for parameter optimization problems. Parallel Island models are also reviewed, and the evaluation of evolutionary algorithms is discussed.     

Simulation and evolutionary optimization of electron-beam lithography with genetic and simplex-downhill algorithms

Genetic and simplex-downhill (SD) algorithms were used for the optimization of the electron-beam lithography (EBL) step in the fabrication of microwave electronic circuits. The definition of submicrometer structures involves complex exposure patterns that are cumbersome to determine experimentally and very difficult to optimize with linear search algorithms due to the high dimensionality of the search space. An SD algorithm was first used to solve the optimization problem. The large number of parameters and the complex topology of the search space proved too difficult for this algorithm, which could not yield satisfactory patterns. A hybrid approach using genetic algorithms (GAs) for global search, and an SD algorithm for further local optimization, was unable to drastically improve the structures optimized with GAs alone. A carefully studied fitness function was used. It contains mechanisms for reduced dependence on process tolerances. Several methods were studied for the selection, crossover, mutation, and reinsertion operators. The GA was used to predict scanning patterns for 100-nm T-gates and gate profiles with asymmetric recess and the structures were fabricated successfully. The simulation and optimization tool can help shorten response times to alterations of the EBL process by suppressing time-consuming experimental trial-and-error steps.     

Auto-tuning strategy for evolutionary algorithms: balancing between exploration and exploitation

Genetic Algorithms (GAs) and other Evolutionary Algorithms (EAs), as powerful and broadly applicable stochastic search and optimization techniques have been successfully applied in the area of management science, operations research and industrial engineering. In the past few years, researchers gave lots of great idea for improvement of evolutionary algorithms, which include population initialization, individual selection, evolution, parameter setting, hybrid approach with conventional heuristics etc. However, though lots of different versions of evolutionary computations have been created, all of them have turned most of its attention to the development of search abilities of approaches. In this paper, for improving the search ability, we focus on how to take a balance between exploration and exploitation of the search space. It is also very difficult to solve problem, because the balance between exploration and exploitation is depending on the characteristic of different problems. The balance also should be changed dynamically depend on the status of evolution process. Purpose of this paper is the design of an effective approach which it can correspond to most optimization problems. In this paper, we propose an auto-tuning strategy by using fuzzy logic control. The main idea is adaptively regulation for taking the balance among the stochastic search and local search probabilities based on the change of the average fitness of parents and offspring which is occurred at each generation. In addition, numerical analyses of different type optimization problems show that the proposed approach has higher search capability that improve quality of solution and enhanced rate of convergence.     

融合强化学习和进化算法的高超声速飞行器航迹规划

由于高超声速飞行器的复杂特性,对其进行航迹规划是一项非常困难的任务.本文针对高超声速飞行器巡航段,提出了一种将无模型的强化学习和交叉熵方法相结合的在线航迹规划算法.本文将航迹规划问题建模为环境信息缺失程度不同的马尔可夫决策过程,利用(PPO)算法在建立的飞行环境模拟器中离线训练智能体,并通过提高智能体的动作在时间上的相关性来保证航迹的曲率平滑.交叉熵方法则以已训练的智能体由观测到的状态给出的动作作为一种先验知识,进一步在线优化规划策略.实验结果表明了本文的方法可以生成曲率平滑的航迹,在复杂的飞行环境中具有较高的成功率,并且可以泛化到不同的飞行环境中.