Identification of variable interaction is essential for an efficient implementation of a divide-and-conquer algorithm for large-scale black-box optimization. In this paper, we propose an improved variant of the differential grouping algorithm, which has a better efficiency and grouping accuracy. The proposed algorithm, DG2, finds a reliable threshold value by estimating the magnitude of roundoff errors. With respect to efficiency, DG2 reuses the sample points that are generated for detecting interactions and saves up to half of the computational resources on fully separable functions. We mathematically show that the new sampling technique achieves the lower bound with respect to the number of function evaluations. Unlike its predecessor, DG2 checks all possible pairs of variables for interactions and has the capacity to identify overlapping components of an objective function. On the accuracy aspect, DG2 outperforms the state-of-the-art decomposition methods on the latest large-scale continuous optimization benchmark suites. DG2 also performs reliably in the presence of imbalance among contribution of components in an objective function. Another major advantage of DG2 is the automatic calculation of its threshold parameter (ǫ), which makes it parameter-free. Finally, the experimental results show that when DG2 is used within a cooperative co-evolutionary framework, it can generate competitive results as compared to several state-of-the-art algorithms.
Genetic programming has been a powerful technique for automated design of production scheduling heuristics. Many studies have shown that heuristics evolved by genetic programming can outperform many existing heuristics manually designed in the literature. The flexibility of genetic programming also allows it to discover very sophisticated heuristics to deal with complex and dynamic production environments. However, as compared to other applications of genetic programming or scheduling applications of other evolutionary computation techniques, the configurations and requirements of genetic programming for production scheduling are more complicated. In this paper, a unified framework for automated design of production scheduling heuristics with genetic programming is developed. The goal of the framework is to provide the researchers with the overall picture of how genetic programming can be applied for this task and the key components. The framework is also used to facilitate our discussions and analyses of existing studies in the field. Finally, this paper shows how knowledge from machine learning and operations research can be employed and how the current challenges can be addressed.
This paper proposes a competitive divide-and-conquer algorithm for unconstrained large scale black-box optimization, which has an unavailable algebraic model for the problem and thousands of decision variables. Assuming that the overall problem is composed of a number of smaller independent sub-problems, the proposed algorithm addresses two important issues in solving large scale black-box optimization: (1) identifying the independent sub-problems and (2) solving the identified black-box sub-problems. First, a Global Differential Grouping (GDG) method is proposed based upon the differential grouping method to find near optimal decomposition of the decision variables and the corresponding sub-problems. Then, a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is adopted to solve the nonseparable sub-problems due to its rotation invariance property. GDG and CMA-ES work together under the cooperative co-evolution framework. The resultant algorithm named CC-GDG-CMAES is then evaluated on the CEC’2010 large scale global optimization (LSGO) benchmark functions, which have a thousand decision variables and black-box objective functions. The experimental results show that on most test functions, GDG manages to obtain an ideal decomposition of the variables, and CC-GDG-CMAES outperformed the state-of-the-art results. Besides, the competitive performance of the well-known CMA-ES is extended from low-dimensional to high-dimensional black-box problems.
Cooperative co-evolution has been introduced into evolutionary algorithms with the aim of solving increasingly complex optimization problems through a divide-and-conquer paradigm. In theory, the idea of co-adapted subcomponents is desirable for solving large-scale optimization problems. However in practice, without prior knowledge about the problem, it is not clear how the problem should be decomposed. In this paper we propose an automatic decomposition strategy called differential grouping that can uncover the underlying interaction structure of the decision variables and form subcomponents such that the interdependence between them is kept to a minimum. We show mathematically how such a decomposition strategy can be derived from a definition of partial separability. The empirical studies show that such near-optimal decomposition can greatly improve the solution quality on large-scale global optimization problems. Finally, we show how such an automated decompo- sition allows for a better approximation of the contribution of various subcomponents, leading to a more efficient assignment of the computational budget to various subcomponents.
In this paper, a divide-and-conquer approach is proposed to solve the Large-Scale Capacitated Arc Routing Problem (LSCARP) more effectively. Instead of considering the problem as a whole, the proposed approach adopts the Cooperative Co- evolution (CC) framework to decompose it into smaller ones and solve them separately. An effective decomposition scheme called the Route Distance Grouping (RDG) is developed to decompose the problem. Its merit is twofold: Firstly, it employs the route information of the best-so-far solution, so that the quality of the decomposition is upper bounded by that of the best-so-far solution. Thus, it can keep improving the decomposition by updating the best-so-far solution during the search. Secondly, it defines a distance between routes, based on which the potentially better decompositions can be identified. Therefore, RDG is able to obtain promising decompositions and focus the search on the promising regions of the vast solution space. Experimental studies verified the efficacy of RDG on the instances with a large number of tasks and tight capacity constraints, where it managed to obtain significantly better results than its counterpart without decomposition in a much shorter time. Furthermore, the best- known solutions of the EGL-G LSCARP instances were much improved.
The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem with many real-world applications, e.g., salting route optimization and fleet management. There have been many attempts at solving CARP using heuristic and meta-heuristic approaches, including evolutionary algorithms. However, almost all such attempts formulate CARP as a single-objective problem although it usually has more than one objective, especially considering its real-world applications. This paper studies multiobjective CARP (MO-CARP). A new memetic algorithm (MA) called decomposition-based MA with extended neighborhood search (D-MAENS) is proposed. The new algorithm combines the advanced features from both the MAENS approach for single-objective CARP and multiobjective evolutionary optimization. Our experimental studies have shown that such combination outperforms significantly an off-the-shelf multiobjective evolutionary algorithm, namely nondominated sorting genetic algorithm II, and the state-of-the-art multiobjective algorithm for MO-CARP (LMOGA). Our work has also shown that a specifically designed multiobjective algorithm by combining its single-objective version and multiobjective features may lead to competitive multiobjective algorithms for multiobjective combinatorial optimization problems.