The Research On Applications Of Memetic Algorithms To Engineering Problems

Optimization problems are regularly encountered in various scientific studies and environmental engineerings.The way to tackle real-world applications efficiently is still an important research to be explored in the artificial intelligence.Traditional methods for solving optimization problems can obtain theoretically optimal solutions under specific conditions,but it is usually difficult for them to solve large-scale,and multi-constraint optimization problems.Therefore,this thesis aims to utilize an effective intelligent algorithm called the memetic algorithm to solve various optimization problems in a practical application scenario.Of course,some focused improvements have also been proposed in order to provide satisfactory solutions within acceptable time.As for the optimized problem level,four engineering problems are solved in this thesis,including the contention-aware mapping and scheduling optimization for No C-based MPSo Cs,the shortwave radio broadcast resource allocation problem,the energyaware multi-objective shortwave radio broadcast resource allocation problem,and the Kcamera placement problem.As for the algorithmic design level,four variants of the memetic algorithm are proposed regarding to the problems listed above,that is,the memetic algorithm based on multiple heuristics,the memetic algorithm based on the helper objective,the multiobjective memetic algorithm based on the push and pull operator,and the memetic algorithm based on the max-min ant system.To be specific,the main works and contributions of the thesis are as follows:(1)An improved memetic algorithm based on multiple heuristics is proposed to solve the contention-aware mapping and scheduling optimization for No C-based MPSo Cs.Firstly,to reduce the over-approximation of spatial(path-based)contention in mapping,we propose to evaluate the contention degree in terms of overlapped communication paths,and regard it as an objective to be minimized.Then,temporal contentions can be avoided by introducing latency into the involved communication during the scheduling stage.Thirdly,we consider a two-stage mapping in the heterogeneous architecture to save the makespan and communication cost.Some problem-related heuristics are proposed together with the memetic algorithm framework to deal with the optimization problem with multiple objectives.The heuristics consist of the topology-oriented task clustering,the capacity sensitive cluster refinement and the communication-oriented spiral mapping.Besides,in the global search stage of the memetic algorithm,a classical multi-objective genetic algorithm based on the non-dominating ranking and the crowded distance is applied.In the local search stage of the memetic algorithm,we adopt the pareto local search based on the insert operator to improve the excellent individuals.The comparative results show that the proposed algorithm performs well,especially on largescale benchmarks.(2)An improved memetic algorithm based on the helper objective is proposed to solve the shortwave broadcast resource allocation problem.In order to deal with the prematurity caused by the lack of population diversity,the algorithm introduces the diversity metric as a helper objective,transforming the orginal problem into a bi-objective optimization problem.Besides,the a-priori non-uniform decomposition method,derived from the Chebychev approach of MOEA/D,is adopted to solve this transformed problem effectively,which focuses more on the original objective to save computational resources.Also,we propose a parallel grouping technique to optimize those decomposed subproblems simultaneously,which can help enhance the efficiency of the algorithm.In the global search stage of this memetic algorithm,the genetic algorithm is used to recombine the parents,while in the local search stage,the guided perturbation operator is used to help jump out of the local optimum when the searching stagnation occurs.Experiments are performed on real-world scenarios of China to compare the proposed algorithm with other state-of-the-art competitors,and the experimental results validate the efficiency of the proposed memetic algorithm.(3)A push and pull multi-objective memetic algorithm is proposed to solve the energyaware multi-objective shortwave radio broadcast resource allocation problem.This thesis firstly proposes the model of the energy-aware multi-objective shortwave radio broadcast resource allocation problem for sustainability reasons,and optimizes the monitoring sites and energy consumption simultaneously.As for the problem,a push and pull operator is applied in the initialization process so as to deal with the constrained multi-objective optimization problem,accelerating the convergence speed of the algorithm.Moreover,a dynamic resource allocation strategy is used for different individuals in order to utilize the contribution of the elites to the survival of the fittest rule in the whole population.In the global search stage of the memetic algorithm,the genetic algorithm is used once again to explore the searching space.In the local search stage of the memetic algorithm,a fast aggregated local search based on the exchange and replace operator is proposed to further improve the individuals.Experimental results reveal that the proposed algorithm can deal with this energy-aware multi-objective shortwave radio broadcast resource allocation problem well.(4)An improved memetic algorithm based on the max-min ant system is proposed for solving the K-camera placement optimization.The K-camera placement optimization problem is firstly presented in case of the resource-constrained condition in the optimal camera placement problem,which provides preliminary work for surveillance systems.Given a limited number of cameras,this newly proposed problem aims to monitor the area as wide as possible.As for the problem,a double-layer selection heuristic is proposed to refine the previously defined greedy heuristic.Then,take the max-min ant system with memory ants as the global search of the memetic algorithm,which not only maintains the excellent structures of the solutions but also generates a well-distributed population.In the local search stage of the memetic algorithm,the scoring function and the delayed configuration checking strategies are introduced to balance the exploitation and exploration of the algorithm.Comparing experiments are conducted,and one can conclude from the results that the memetic algorithm performs better than other solvers.