Decomposition-based Evolutionary Algorithm for Large Scale Problems

by Eman Sayed

Institution: University of New South Wales
Department: Engineering & Information Technology
Year: 2014
Keywords: Decomposition-based Evolutionary Algorithms; Large Scale Optimisation; Problem Decomposition; Unconstrained Optimisation; Constrained Optimisation; Variable Interaction Identification; Differential Evolution
Record ID: 1059916
Full text PDF: http://handle.unsw.edu.au/1959.4/53657


Large scale optimisation is a challenging area of research because of the complex structure of the optimisation problem and the large number of decision variables in its objective function or constraints. EAs have been proven to be successful in optimisation. However, their performance decreases when the problem dimensionality increases. This drawback has been handled by using decomposition approaches that have been very successful with problems that can be decomposed into independent subproblems. However, once there is any interaction between subproblems, the performance of an EA decreases. Therefore, an approach that groups interacting variables into subproblems that have minimum interdependency is required. To date, only a few simple decomposition techniques which have this property have been developed for unconstrained problems, and none have been developed for constrained problems. Therefore, this thesis addresses how to design novel variable interaction identification techniques, that are also used as part of new decomposition-based EAs for both unconstrained and constrained large scale optimisation problems. To this end, this thesis provides two novel appropriate test suites of benchmark problems for unconstrained and constrained problems, that can be used to test any decomposition-based algorithm. The key elements of this thesis are the new variable interaction identification techniques for unconstrained (VIIU) and constrained (VIIC) problems. These techniques produce arrangements of variables with minimum interdependency, over different subproblems, among their variables in the objective function and constraints. Finally, the VIIU and VIIC are used to design two new decomposition-based EAs that use Differential Evolution (DE), DEVIIU and DEVIIC. These two algorithms have been compared to another two designed algorithms that use Random Grouping (RG) for decomposition. All algorithms have been tested on the proposed test suites and a real-life constrained problem (Dynamic Economic Dispatch problem) on different large dimensions. The results showed that by first identifying the interacting variables and by then optimising them in common subproblems of minimum interdependency clearly improves performance. The comparisons showed that DEVIIU was better for all of the problems for all of the tested dimensions. Moreover, DEVIIC showed significantly better and more reliable performance on both the larger scale and the more complex problems.