Study On Firefly Algorithm And Its Application In Task Assignment Of Multi-AUV System

The firefly algorithm (FA) is a recently developed metaheuristic algorithm,which is inspired by the social behavior of fireflies and abstracts a mathematical framework for optimization. The framework is composed with attraction and update.The optimization results obtained by firefly algorithm are quite well and the algorithm converges more quickly than other metaheuristic algorithm. Because firefly algorithm is easy to implement and have strong capability of searching, it has been applied to many applications.This dissertation focused on the theoretical foundation of FA, including convergence analysis and the choice of parameters. A multi-objective framework of FA is proposed and finally the new multi-objective algorithm is applied to multi-AUV task assignment.The mathematical study of FA is highly needed and there is few contributions about FA's convergence proof and parameter theoretical study. To boost the development of algorithm,a discussion about convergence of FA is proposed. The content is discussed based on two cases. One is considered without random walk. A complete proof is proposed to indicate FA will convergence in finite iterations. The other case is about complete FA with random walk affection. To quantify the effect of random movement, we use measure to observe the random walk and give a definition of attraction field to discuss the possibility of algorithm convergence. Based on convergence discussion, we give some advice about parameter choice.FA can be easily extended to multi-object form but there are several points needed to be modified. After analyzing different frames of existing multi-objective FA(MOFA), we choose archive to store optimal estimation front, which can guide FA solution processing. To enhance diversity of population, we use density monitor to locate the space with low density and gather other fireflies to this space. The result shows that the optimal solutions obtained by the new algorithm have nice approximation and uniformity.There have been many studies on the task assignment of a multi-AUV system. In this dissertation, we use FA to solve this problem and aim to find the best solution costs least energy. Cause task assignment is based on integer solution space, basic FA needs to be modified. A novel problem formulation based on order matrix is proposed to guide FA to search optimal solution. We also add a heuristic operator to help solutions jump out of local space that not fit constraints. Six tests have been operated to test single-object task assignment algorithm, which shows that the algorithm we proposed can get optimal solutions fit all the constraints.Except energy saving, navigation safety should also be considered in multi-AUV task assignment. To get the value of navigation safety, we calculate the danger degree of all the routes. The calculation method is inspired by D-S Evidence Theory. Several modification are also been proposed for new MOFA to fit task assignment problem.The results show that using new MOFA can get a group of optimal assignment solution satisfied all the constraint.