Transfer weight functions for injecting problem information in the multi-objective CMA-ES

The covariance matrix adaptation evolution strategy (CMA-ES) is one of the state-of-the-art evolutionary algorithms for optimization problems with continuous representation. It has been extensively applied to single-objective optimization problems, and different variants of CMA-ES have also been proposed for multi-objective optimization problems (MOPs). When applied to MOPs, the traditional steps of CMA-ES have to be modified to accommodate for multiple objectives. This fact is particularly evident when the number of objectives is higher than 3 and, with a high probability, all the solutions produced become non-dominated. An open question is to what extent information about the objective values of the non-dominated solutions can be injected in the CMA-ES model for a more effective search. In this paper, we investigate this general question using several metrics that describe the quality of the solutions already evaluated, different transfer weight functions, and a set of difficult benchmark instances including many-objective problems. We introduce a number of new strategies that modify how the probabilistic model is learned in CMA-ES. By conducting an exhaustive empirical analysis on two difficult benchmarks of many-objective functions we show that the proposed strategies to infuse information about the quality indicators into the learned models can achieve consistent improvements in the quality of the Pareto fronts obtained and enhance the convergence rate of the algorithm. Moreover, we conducted a comparison with a state-of-the-art algorithm from the literature, and achieved competitive results in problems with irregular Pareto fronts.     

Neuroevolution strategies for episodic reinforcement learning

Because of their convincing performance, there is a growing interest in using evolutionary algorithms for reinforcement learning. We propose learning of neural network policies by the covariance matrix adaptation evolution strategy (CMA-ES), a randomized variable-metric search algorithm for continuous optimization. We argue that this approach, which we refer to as CMA Neuroevolution Strategy (CMA-NeuroES), is ideally suited for reinforcement learning, in particular because it is based on ranking policies (and therefore robust against noise), efficiently detects correlations between parameters, and infers a search direction from scalar reinforcement signals. We evaluate the CMA-NeuroES on five different (Markovian and non-Markovian) variants of the common pole balancing problem. The results are compared to those described in a recent study covering several RL algorithms, and the CMA-NeuroES shows the overall best performance.     

An effective heuristic for the two-dimensional irregular bin packing problem

This paper proposes an adaptation, to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD), originally designed for the one-dimensional bin packing problem. In the two-dimensional case, not only is it the case that the piece’s size is important but its shape also has a significant influence. Therefore, DJD as a selection heuristic has to be paired with a placement heuristic to completely construct a solution to the underlying packing problem. A successful adaptation of the DJD requires a routine to reduce computational costs, which is also proposed and successfully tested in this paper. Results, on a wide variety of instance types with convex polygons, are found to be significantly better than those produced by more conventional selection heuristics.     

On the limitations of classical benchmark functions for evaluating robustness of evolutionary algorithms

Although evolutionary algorithms (EAs) have some operators which let them explore the whole search domain, still they get trapped in local minima when multimodality of the objective function is increased. To improve the performance of EAs, many optimization techniques or operators have been introduced in recent years. However, it seems that these modified versions exploit some special properties of the classical multimodal benchmark functions, some of which have been noted in previous research and solutions to eliminate them have been proposed.In this article, we show that quite symmetric behavior of the available multimodal test functions is another example of these special properties which can be exploited by some EAs such as covariance matrix adaptation evolution strategy (CMA-ES). This method, based on its invariance properties and good optimization results for available unimodal and multimodal benchmark functions, is considered as a robust and efficient method. However, as far as black box optimization problems are considered, no special trend in the behavior of the objective function can be assumed; consequently this symmetry limits the generalization of optimization results from available multimodal benchmark functions to real world problems. To improve the performance of CMA-ES, the Elite search sub-algorithm is introduced and implemented in the basic algorithm. Importance and effect of this modification is illustrated experimentally by dissolving some test problems in the end.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.     

Polymorphic evolution sequence and evolutionary branching

We are interested in the study of models describing the evolution of a polymorphic population with mutation and selection in the specific scales of the biological framework of adaptive dynamics. The population size is assumed to be large and the mutation rate small. We prove that under a good combination of these two scales, the population process is approximated in the long time scale of mutations by a Markov pure jump process describing the successive trait equilibria of the population. This process, which generalizes the so-called trait substitution sequence (TSS), is called polymorphic evolution sequence (PES). Then we introduce a scaling of the size of mutations and we study the PES in the limit of small mutations. From this study in the neighborhood of evolutionary singularities, we obtain a full mathematical justification of a heuristic criterion for the phenomenon of evolutionary branching. This phenomenon corresponds to the situation where the population, initially essentially single modal, is driven by the selective forces to divide into two separate subpopulations. To this end we finely analyze the asymptotic behavior of three-dimensional competitive Lotka?CVolterra systems.     

A branch and bound algorithm for the acyclic subgraph problem

A branch and bound algorithm for the acyclic subgraph problem (feedback are set problem) is described. The branching scheme lexicographically enumerates all permutations, skipping initial segments known by some easy tests not to have any optimal completion. A lower bound for the number of feedback arcs is given by the size of any collection of disjoint cycles. We propose a heuristic algorithm to find a large collection. The size of the problems our branch and bound algorithm can solve varies from 25 to 34 nodes, depending on the nature of the problem.     

An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs

The problem of scheduling in a flowshop is considered with the objective of minimizing the total weighted flowtime of jobs. A heuristic algorithm is developed by the introduction of lower bounds on the completion times of jobs and the development of heuristic preference relations for the scheduling problem under study. An improvement scheme is incorporated in the heuristic to enhance the quality of its solution. The proposed heuristic, with and without the improvement scheme, and the existing heuristics are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various problem sizes are presented. It has been observed that both versions of the proposed heuristic perform better than the existing heuristics in giving a superior solution quality and that the proposed heuristic without the improvement scheme yields a good solution by requiring a negligible CPU time. In addition, an experimental investigation is carried out to evaluate the effectiveness of the improvement scheme when implemented in the proposed heuristic and the existing heuristics, as well as the effectiveness of a variant of the scheme. The results are also discussed.     

Default policies for global optimisation of noisy functions with severe noise

Global optimisation of unknown noisy functions is a daunting task that appears in domains ranging from games to control problems to meta-parameter optimisation for machine learning. We show how to incorporate heuristics to Stochastic Simultaneous Optimistic Optimization (STOSOO), a global optimisation algorithm that has very weak requirements from the function. In our case, heuristics come in the form of Covariance Matrix Adaptation Evolution Strategy (CMA-ES). The new algorithm, termed Guided STOSOO (STOSOO-G), combines the ability of CMA-ES for fast local convergence (due to the algorithm following the “natural” gradient) and the global optimisation abilities of STOSOO. We compare all three algorithms in the “harder” parts of the Comparing Continuous Optimisers on Black-Box Optimization Benchmarking benchmark suite, which provides a default set of functions for testing. We show that our approach keeps the best of both worlds, i.e. the almost optimal exploration/exploitation of STOSOO with the local optimisation strength of CMA-ES.     

Scheduling preemptive open shops to minimize total tardiness

This article considers the problem of scheduling preemptive open shops to minimize total tardiness. The problem is known to be NP-hard. An efficient constructive heuristic is developed for solving large-sized problems. A branch-and-bound algorithm that incorporates a lower bound scheme based on the solution of an assignment problem as well as various dominance rules are presented for solving medium-sized problems. Computational results for the 2-machine case are reported. The branch-and-bound algorithm can handle problems of up to 30 jobs in size within a reasonable amount of time. The solution obtained by the heuristic has an average deviation of less than 2% from the optimal value, while the initial lower bound has an average deviation of less than 11% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 65% of the problems actually solved.     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

A hybrid heuristic for the diameter constrained minimum spanning tree problem

We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.     

An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem

In this paper we consider the two-dimensional (2D) rectangular packing problem, where a fixed set of items have to be allocated on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left (BL) stability, are hybridised with three meta-heuristic algorithms (genetic algorithms (GA), simulated annealing (SA), naı̈ve evolution (NE)) and local search heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms, their performance is compared to random search (RS) and heuristic packing routines.     

Differential evolution using a superior–inferior crossover scheme

Differential evolution (DE) is a new population-based stochastic optimization, which has difficulties in solving large-scale and multimodal optimization problems. The reason is that the population diversity decreases rapidly, which leads to the failure of the clustered individuals to reproduce better individuals. In order to improve the population diversity of DE, this paper aims to present a superior–inferior (SI) crossover scheme based on DE. Specifically, when population diversity degree is small, the SI crossover is performed to improve the search space of population. Otherwise, the superior–superior crossover is used to enhance its exploitation ability. In order to test the effectiveness of our SI scheme, we combine the SI with adaptive differential evolution (JADE), which is a recently developed DE variant for numerical optimization. In addition, the theoretical analysis of SI scheme is provided to show how the population’s diversity can be improved. In order to make the selection of parameters in our scheme more intelligently, a self-adaptive SI crossover scheme is proposed. Finally, comparative comprehensive experiments are given to illustrate the advantages of our proposed method over various DEs on a suite of 24 numerical optimization problems.     

Iterated local search with Powell’s method: a memetic algorithm for continuous global optimization

In combinatorial solution spaces Iterated Local Search (ILS) turns out to be exceptionally successful. The question arises: is ILS also capable of improving the optimization process in continuous solution spaces? To demonstrate that hybridization leads to powerful techniques in continuous domains, we introduce a hybrid meta-heuristic that integrates Powell’s direct search method. It combines direct search with elements from population based evolutionary optimization. The approach is analyzed experimentally on a set of well known test problems and compared to a state-of-the-art technique, i.e., a restart variant of the Covariance Matrix Adaptation Evolution Strategy with increasing population sizes (G-CMA-ES). It turns out that the population-based Powell-ILS is competitive to the CMA-ES, in some cases even significantly faster and behaves more robust than the pure strategy of Powell in multimodal fitness landscapes. Further experiments on the perturbation mechanism, population sizes, and problems with noise complete the analysis of the hybrid methodology and lead to parameter recommendations.     

The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments

This paper studies a dynamic dial-a-ride problem bearing complex constraints on a time-dependent network. A flexible scheduling scheme is proposed to dynamically cope with different stochastic events, such as the travelling time fluctuation, new requests, absences of customers, vehicle breakdowns, cancellations of requests, traffic jams and so on. A fast heuristic is proposed to re-optimize the schedule when a new event occurs. This heuristic consists of a properly organized local search strategy and uses a secondary objective function to drive the search out of local optima. Intensive computational simulations were carried out to evaluate the performance of this scheduling scheme and the influence of different stochastic factors. The simulation results of different scenarios with different percentage of dynamic requests reveal that this scheduling scheme can generate high quality schedules and is capable of coping with various stochastic events.     

A numerical method for a nonlinear structured population model with an indefinite growth rate coupled with the environment

A numerical method is developed for a general structured population model coupled with the environment dynamics over a bounded domain where the individual growth rate changes sign. Sign changes notably exhibit nonlocal dependence on the population density and environmental factors (e.g., resource availability and other habitat variables). This leads to a highly nonlinear PDE describing the time‐evolution of the population density coupled with a nonlinear‐nonlocal system of ODEs describing the environmental time‐dynamics. Stability of the finite‐difference numerical scheme and its convergence to the unique weak solution are proved. Numerical experiments are provided to demonstrate the performance of the finite difference scheme and to illustrate a range of biologically relevant potential applications.     

改进种群多样性的双变异差分进化算法

差分进化算法(DE)是一种基于种群的启发式随机搜索技术,对于解决连续性优化问题具有较强的鲁棒性.然而传统差分进化算法存在种群多样性和收敛速度之间的矛盾,一种改进种群多样性的双变异差分进化算法(DADE),通过引入BFS-best机制(基于排序的可行解选取递减策略)改进变异算子"DE/current-to-best",将其与DE/rand/1构成双变异策略来改善DE算法中种群多样性减少的问题.同时,每个个体的控制参数基于排序自适应更新.最后,利用多个CEC2013标准测试函数对改进算法进行测试,实验结果表明,改进后的算法能有效改善种群多样性,较好地提高了算法的全局收敛能力和收敛速度.     

Robust adaptive control of linear time-delay systems with point time-varying delays via multiestimation

This paper presents an adaptive pole-placement based controller for continuous-time linear systems with unknown and eventually time-varying point delays under uncertainties consisting of unmodeled dynamics and eventual bounded disturbances. A multiestimation scheme is designed for improving the identification error performance and then to deal with possibly errors between the true basic delay compared to that used in regressor vector of measurements of the adaptive scheme and also to prevent the closed-loop system against potential instability. Each estimation scheme in the parallel disposal possesses a relative dead-zone which freezes the adaptation process for small sizes of the adaptation error compared to the estimated size of the absolute value of the contribution of the uncertainties to the filtered output versus time. All the estimation schemes run in parallel but only that which is currently in operation parameterizes the adaptive controller to generate the plant input at each time. A supervisor chooses the appropriate estimator in real time which respects a prescribed minimum residence time at each estimation algorithm in operation. That strategy is the main tool used to ensure the closed-loop stability under estimates switching. The relative dead-zone in the adaptation mechanism prevents the closed-loop system against potential instability caused by uncertainties.     

Mathematical Analysis of a Coarsening Model with Local Interactions

We consider particles on a one-dimensional lattice whose evolution is governed by nearest-neighbor interactions where particles that have reached size zero are removed from the system. Concentrating on configurations with infinitely many particles, we prove existence of solutions under a reasonable density assumption on the initial data and show that the vanishing of particles and the localized interactions can lead to non-uniqueness. Moreover, we provide a rigorous upper coarsening estimate and discuss generic statistical properties as well as some non-generic behavior of the evolution by means of heuristic arguments and numerical observations.