Research Statement
 

Overview

I am mostly interested in solving optimization problems using population-based stochastic techniques such as Evolutionary Algorithms (EAs). The term of “optimization” refers to the process of searching for the optimal solution to the problem of interest from a potentially huge set of candidates, which has found broad applications in manufacturing, engineering, finance, bioinformatics and logistics.

Although optimization problems may come in a variety of forms, they can all be formulated as an objective function controlled by a set of parameters. The goal of optimization is to find the best valid parameter settings in order to achieve optimal function values (finding the global maxima/minima). In practice, it may be to accomplish a task in the most efficient way or in the highest quality or to produce maximum yields given limited resources.

My research experience in the above area covers a wide range of topics at difference levels, including theoretical modeling of algorithm dynamics, empirical studies of algorithms, experimental methodology and real-world applications. I also have strong interest in combining the field of global optimization with advanced techniques from other areas such as Machine Learning and Statistics.

Postdoctoral Work

My Postdoctoral work was focused on the optimal robot routing problem in wireless sensor networks. Generally speaking, given a set of sparsely distributed sensors where it may be difficult for them to communicate with each other directly, a mobile robot is employed to travel to each sensor to download its data. The effective range of each sensor is typically specified by a disk (2D) or a sphere (3D) and the robot must at least reach its boundary to initiate the communication.

The primary objective of this routing problem is to design a path for the robot so that it can collect all the data and return to its base while the overall traveling distance is minimized. In its generic form, this problem can be regarded as a special case of a class of problems referred to as Traveling Salesman Problem with Neighborhoods (TSPN), which is an extension of the classical TSP. Since both TSP and TSPN are NP-hard, it is usually impractical to apply exact algorithms that can guarantee optimality, especially on large scale problems.

A new heuristic algorithm framework was proposed that can handle problems with hundreds of sensors and produce significantly improved results compared to current approximation algorithms. The first step is to design a heuristic that can effectively decompose each TSPN instance into a combinatorial optimization problem (the sequence of sensors to be visited) to be solved by an external TSP routine and a continuous optimization problem (the locations of hitting points). Next, the search space of the continuous problem is further reduced based on the spatial relationship among sensors. Finally, a competent optimization algorithm is applied to find the accurate solution to the continuous optimization problem, which is also the solution to the original TSPN instance.

Another project was on the data mining problem in the smart shopping centre, which is built on advanced techniques such as wireless networks and RFID. In this scenario, a smart trolley is equipped with wireless devices that can communicate with the smart shelves to record the path information of customers (represented by the sequence of sectors visited). Given a collection of such path records, a set of algorithms were proposed to conduct various interesting queries such as finding the most frequent common path with a fixed length and finding the longest common path with a given support.

PhD Work

My PhD work was concentrated on a key research question: How to conduct better experimental research on EAs? Due to the challenges in the theoretical analysis of EAs, empirical studies are still the primary methods to understand and compare their performance. Although empirical studies of EAs are often seemingly simple, the results can be significantly influenced by a variety of factors such as the test problems and the parameter settings. In fact, designing experiments with high scientific values is actually a much more complicated task than many practitioners may have realized.

Landscape Generator (web)

A continuous landscape (test problem) generator based on multivariate Gaussian components (LG-MVG) was proposed, which is capable of generating a large number of random problem instances with predefined structure in accordance with the specific objective of experimental studies. The major advantage of LG-MVG is that it can generate a variety of problems in terms of landscape structure and is parameterized by a flexible set of parameters, which have an intuitive influence on the structure of the problems generated. It can also overcome a number of well-known issues of many existing benchmark problems.

Case studies on a set of continuous Estimation of Distribution Algorithms (EDAs) have shown that a much wider range of interesting experiments can be conducted with LG-MVG than using traditional benchmark problems. In the meantime, some of the important properties of these EDAs have also been revealed that would otherwise be difficult to observe.

Statistical Racing Techniques

A major practical difficulty in conducting large scale experimental studies of EAs lies in the high computational cost incurred correspondingly. In order to ease this challenge, a statistical Racing technique originally proposed for solving model selection problems in Machine Learning was extended and adapted to the comparative studies of EAs for the purpose of reducing the computational cost while still maintaining high reliability of the results.

The typical task where Racing is mostly applicable is to find out the best performing algorithm from a set of candidate algorithms, which may include the same type of algorithm with different parameter settings or completely different algorithms. Instead of sequentially testing each algorithm on the test problem for a fixed number of trials, all algorithms are tested in parallel for a single trial at each step. For each algorithm, the results from all trials that have been conducted are maintained as the samples from its true performance distribution and used in some statistical test.

If there is enough evidence, as indicated by the result of the test, that one algorithm is significantly worse than another one, it will be removed from the experiment and undergo no further testing because it is very unlikely to be the best algorithm. By doing so, algorithms are forced to race against each other to compete for computational resources and only promising algorithms survive through to the next round of test. As a result, the overall cost can be significantly reduced by avoiding running unnecessary trials on inferior algorithms.

Mathematical Modeling of EDAs

A principled modeling technique was proposed to investigate the detailed dynamics of a simple EDA based on Gaussian distributions, which is one of the first attempts in this area. Unlike some existing work on the global convergence behavior of EDAs, this modeling technique is aimed at describing the specific behavior of the EDA at each generation under the influence of different algorithm and problem factors. Case studies were conducted with different algorithm parameter values on both unimodal and multimodal problems. It has been shown that the proposed technique can not only accurately predict the dynamics of the EDA from various aspects but also demonstrate some of its very interesting behaviors that were not known from previous experimental studies.

MRI Magnet Design (Poster)

Applications of continuous EDAs on large scale real-world problems have been relatively rare. In this part of work, two EDAs were compared on the magnet design task in MRI systems, to highlight the advantage of capturing dependences in solving practical problems. Another key contribution is an efficient statistical technique for estimating the number of optima in the search space, which could be potentially very useful for choosing the right optimization algorithm. Other important issues such as parallel computation and incorporating problem-specific knowledge were also discussed.

Other Work

In the past, I have conducted some research on evolving neural networks using EAs. One example is to design feedforward neural networks whose structure and weights were to be evolved simultaneously. A number of unusual neural networks were found in the experiments, which were dramatically different from the classical three-layer structure. Another example is to evolve a recurrent neural network with complex dynamics to learn a simple context-free language where the neural network was trained to count the occurrences of each language character. Furthermore, I have participated various projects on image processing, fractal image compression, pattern recognition and medical X-ray machine calibration.