Large Scale Optimisation

Apr 27, 2016

Most real-world optimisation problems are very large. For example, in a vehicle routing problem, there can be thousands of customers to be served. In addition, these problems have many local optima, and it is easy to be trapped into poor local optima.

Large scale global optimisation is a very challenging problem that seeks for the “global optimum” in a very large search space. Although evolutionary computation algorithms have shown premise in solving the hard optimisation problems, their performance is usually restricted into small or medium problem sizes. When the problem size grows large, the performance of the algorithms can deteriorate rapidly (“curse of dimensionality”).

To address this challenge, we aim to develop novel divide-and-conquer approaches to reduce the search space without excluding the promising solutions. We have achieved success on the benchmark functions and real-world applications such as the arc routing problem, travelling thief problem, and warehouse layout design.

Large Scale Optimisation Divide-and-conquer Co-evolution
Yi Mei
Yi Mei
Senior Lecturer

My research interests include Evolutionary Computation and Learning, particularly hyper-heuristics for automated algorithm/heuristic design for complex dynamic real-world optimisation problems such as scheduling, vehicle routing, tourist trip recommendation, resource allocation.

Publications

Cooperative co-evolution with differential grouping for large scale optimization
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.
Mohammad Nabi Omidvar, Xiaodong Li, Yi Mei, Xin Yao
PDF Cite Code Project DOI