Research On Large Scale Global Optimization Algorithms

Many real world problems can be modeled as global optimization problems to solve.Some problems that contain a large number of parameters or decision variables can be modeled as large scale global optimization(LSGO)problems.Large scale means the problem is high-dimensional(with a huge number of parameters or decision variables).In the latest LSGO benchmark suites,each test problem contains 1000 decision variables.LSGO is a kind of the most difficult problems remain to be solved,the main difficulty includes: 1)the extremely large search space.The search space grows exponentially with the increase of the dimensionality which makes the optimization algorithms unable to explore such a huge space within limited computational resources(or time);2)many LSGO problems are non-convex,not differentiable,thus,many classic efficient algorithms can not be applied to these kind of problems;3)as the increase of the dimensionality,the the number of local optimal solutions also increases which makes it hard for optimization algorithms to escape from all the local optimal solutions to find the global one.Besides,many existing effective optimization algorithms are only effective for small scale or medium scale problems but not effective for large scale problems.One effective way to solve the LSGO problem is the decomposition-based method using the cooperative co-evolutionary framework.The main idea of this approach is to design efficient grouping method to decompose the large scale problems into smaller sub problems and then solve each sub problem separately.In this framework,grouping method can greatly affect the effectiveness of the LSGO algorithms.Besides the decomposition-based approach,another approach for LSGO is to design or adopt various efficient search algorithms to make direct optimization.Based on the current research findings and the key issues of the LSGO problem,we propose some new algorithms.Our main work and innovation is as follows:1.For some optimization problems,there exists a lot of local optimal solutions,thus,the optimization algorithm can be trapped in these solutions and failed to find the global optimal solutions.To alleviate this problem,we design an auxiliary function method to help the algorithm escape from local optimal solutions.Based on this auxiliary function and an evolutionary algorithm,a new algorithm is propose to solve small scale optimization problems.Numerical experiments show that this auxiliary function method is effective.2.Filled function method is one effective approach for global optimization.By constructing an auxiliary function named filled function at the current local optimal solution,it can not only help the algorithm escape from the local optimal solution easily,but also can guide the algorithm to enter a new region which contains better solutions.We design a parameter-free filled function which is continuous and differentiable.It overcomes the disadvantage of the existing filled functions: 1)with one or two parameters not so easy to tune;and 2)noncontinuous non-differentiable.Based on the proposed filled function,a new algorithm is proposed to solve small and medium scale optimization problems.Experiments on widely used benchmark problems show that the new filled function method is more effective than the state-of-the-art filled function algorithms.3.The cooperative co-evolutionary algorithms are currently the most widely used framework for solving LSGO problem.In this framework,the grouping method is very important for the effectiveness of the LSGO algorithms.To overcome the disadvantages of the existing grouping methods,a formula based grouping method is proposed.This new grouping method can correctly and efficiently detect the separability of the LSGO problem and decompose separable LSGO problem.Based on it,a new cooperative coevolutionary algorithm is proposed for LSGO problems.The algorithm is tested on the newest LSGO benchmark functions as well as a scalable benchmark functions in which the scalability of the proposed algorithm is tested on 2000 and 5000 dimensions respectively.The experiment results show the algorithm is effective.4.To efficiently scan the huse search space caused by the high dimensionality of the LSGO problem,we propose a self-adaptive discrete scan method.Also,to make the allocation of computational resources more efficient in order to obtain better optimization results,we design a self-adaptive grouping search method.This method can self-adaptively allocate computational resources to sub groups according to their contributions to the whole problem.The sub groups with higher contributions will not only be optimized earlier but will also get more computational resources.Based on these methods and the formula based grouping method,we design a new algorithm to solve the LSGO problems.Experiments indicate that the proposed algorithm is effective.5.For the most difficult LSGO problem: the non-separable problem,we propose a contribution based grouping method.This method can decompose the non-separable LSGO problem in an effective and reasonable way thus the large scale non-separable problem can be transformed to a number of small scale problems to solve,which makes the problem solve easier.Based on it,an effective algorithm named contribution based two phase hybrid algorithm is proposed.The proposed algorithm is tested on the most difficulty LSGO benchmark suite,and is compared with the best performing algorithms,the state-of-the-art algorithms and other well known algorithms.Comparison results show that the proposed algorithm is the best performing algorithm of all existing LSGO algorithms.