Research Into Distributed Evolutionary Computation Based Multi-Solution Optimization Algorithm And Its Application

Multi-solution optimization problem is a kind of complex optimization problem with multiple optimal solutions.Multimodal optimization problem and multi objective optimization problem are two typical multi-solution optimization problems.The development of advanced technologies(such as cloud computing and Internet of Things)and the increasingly complex application demands in the real world have spawned many multi-solution optimization problems,which arise an urgent need for efficient algorithms to solve them.Evolutionary computation algorithms are a kind of optimization algorithms inspired by the evolutionary laws and swarm intelligence phenomena in nature.They solve the optimization problems by population evolution.Since evolutionary computation algorithms have advantages such as they do not require a delicate mathematical model of the optimization problem,they have been widely used in solving various complex optimization problems and obtained promising results.However,traditional evolutionary computation algorithms usually use a single search mode and a single population,which makes them suffer from the performance bottleneck of premature convergence and being trapped in local optima when solving multi-solution optimization problems.To efficiently deal with this problem,this paper proposes the idea of distributed evolutionary computation,which achieves the distributed search through diverse search modes and the cooperation of multiple populations,and thus enhances the global search ability of algorithms.Following this idea,new evolutionary computation algorithms are proposed from four perspectives(i.e.,distributed search of individuals,distributed search of multiple populations,distributed sampling,and distributed two-layer cooperation)to efficiently solve the multi-solution optimization problems;Meanwhile,the proposed algorithms are also validated in some real-world optimization problems,including the cloud workflow scheduling problem and the lifetime maximization problem of wireless sensor networks in Internet of Things.The main research work and contributions of this paper include:(1)Propose a distributed individuals-based multimodal differential evolution algorithm,which enhances the algorithm performance on multimodal optimization problems by the distributed search of individuals in the populationIn the proposed algorithm,each individual in the population is a distributed search unit and each possesses a virtual population controlled by an adaptive range adjustment strategy.In this way,individuals in the population can sufficiently explore the search space and each locates an optimal solution.In addition,a lifetime mechanism is proposed,which assigns each individual a lifetime.The lifetime-exhausted individuals will be re-initialized to further enhance the population diversity for locating more optimal solutions.Meanwhile,the lifetime-exhausted individuals with good fitness will be stored in an external archive to save the optimal solutions located by individuals in their current lifetime.Then,an elite learning mechanism is proposed to further optimize the solutions in the external archive,making them achieve the accuracy requirement.Experimental results on the commonly used multimodal optimization benchmark set validate that the proposed algorithm has great performance.(2)Propose a distributed multi-population-based ant colony system algorithm,which provides a new efficient method for solving the multiobjective cloud workflow scheduling problemThe workflow execution time and execution cost are the two most important issues considered by the cloud computing users.A multi objective cloud workflow scheduling model is constructed,setting these two issues as the optimization objectives.In order to obtain efficient solutions for the problem,the idea of distributed multi-population is proposed,where two populations conduct distributed search to optimize the two objectives sufficiently.A new pheromone update rule and a complementary heuristic strategy are proposed to help the algorithm find a set of scheduling schemes that optimize the two objectives simultaneously.Moreover,an elite study strategy is proposed to further enhance the solution quality of the scheduling schemes.Experimental simulations are conducted by using workflows with various scales and the data of computing resource on the cloud computing platform.Experimental results show that the proposed algorithm is superior to a variety of existing workflow scheduling approaches.(3)Propose a distributed sampling-based estimation of distribution algorithm,which provides a new efficient method for solving the lifetime maximization problem of wireless sensor networksWireless sensor networks in Internet of Things are usually required to achieve full coverage of a set of targets.Focusing on the scenario of using sensors with adjustable sensing range,the lifetime maximization problem of wireless sensor networks is modeled as a multi-solution optimization problem.The algorithm is required to find a set of optimal sensor setting schemes that can achieve the coverage of all targets(termed as coverage schemes),and then a linear programming model is constructed to determine the optimal activation time of each coverage scheme for maximizing the lifetime of wireless sensor networks.To obtain a set of efficient coverage schemes,the proposed algorithm uses a distributed sampling strategy,which samples new individuals from various probabilistic models constructed by the neighborhoods of different individuals.The distributed sampling strategy can sufficiently enhance the population diversity to promote the full use of each sensor.In addition,a linear programming-based fitness evaluation strategy and a heuristic repair strategy are proposed to further enhance the search efficiency of the proposed algorithm.Experimental results on wireless sensor network instances with various scales validate the great performance of the proposed algorithm.(4)Propose a distributed two-layer cooperative multimodal differential evolution algorithm,which can simultaneously deal with the diversity and convergence challenges in solving multimodal optimization problemsThe proposed algorithm is based on a new distributed two-layer cooperative framework that includes an exploration layer and a refinement layer.In the exploration layer,each individual is a distributed search unit and each locates an optimal solution,and finally the located optimal solutions are sent to the refinement layer.In the refinement layer,the solutions sent from the exploration layer are clustered,then each cluster is treated as a population and uses the differential evolution algorithm for population evolution,which achieves the distributed multi-population evolution to refine the accuracy of the located optimal solutions.Experimental results on the commonly used multimodal optimization benchmark set show that the proposed algorithm has overall better performance than some existing multimodal optimization algorithms.In summary,this paper proposes the idea of distributed evolutionary computation;carries out the research on high-performance multi-solution optimization algorithms;validates the great performance of the proposed algorithms according to sufficient experimental tests,comparisons,and analysis;and applies the proposed algorithms in the real-world optimization problems of cloud workflow scheduling and lifetime maximization of wireless sensor networks in Internet of Things.The research in this paper not only provides new efficient algorithms for multi-solution optimization problems,but also greatly promote the development of evolutionary computation in solving multi-solution optimization problems.