Autonomous underwater vehicle (AUV) path planning in complex marine environments meets many chanllenges, such as many influencing factors, complex models and the performance of the optimization algorithm to be improved. To find a path with minimum cost of the actual environmental threats, navigation height changes and the minimum energy consumption of the AUV, an improved sparrow search algorithm is designed under the impact of the time-varying characteristics of the current in the complex marine environment on the AUV and the physical constraints of the AUV movement. In the proposed algorithm, an adaptive weight factor balance strategy is introduced into the position update of the discoverer to improve the convergence speed and search ability. In the follower position, the variable spiral search strategy is improved based on the position update formula to enhance the local jumping ability of the algorithm. After the position update, Levy flying strategy is added, and Cauchy–Gaussian mutation is performed on the optimal individual to increase the population diversity, which improves the anti-stagnation ability of the algorithm. Finally, the AUV global path with minimum cost in the sense of multi-objective weighting is obtained. The simulation results show that the proposed algorithm can plan a path with less cost and quickly converge to an optimized point, and finally it can meet the global path planning requirements of AUV when navigating in complex sea areas.

The quadratic minimum spanning tree problem (QMSTP) is a spanning tree optimization problem that considers the interaction cost between pairs of edges arising from a number of practical scenarios. This problem is NP-hard, and therefore there is not a known polynomial time approach to solve it. To find a close-to-optimal solution to the problem in a reasonable time, we present for the first time a clustering-enhanced memetic algorithm (CMA) that combines four components, i.e., (i) population initialization with clustering mechanism, (ii) a tabu-based nearby exploration phase to search nearby local optima in a restricted area, (iii) a three-parent combination operator to generate promising offspring solutions, and (iv) a mutation operator using Lévy distribution to prevent the population from premature. Computational experiments are carried on 36 benchmark instances from 3 standard sets, and the results show that the proposed algorithm is competitive with the state-of-the-art approaches. In particular, it reports improved upper bounds for the 25 most challenging instances with unproven optimal solutions, while matching the best-known results for all but 2 of the remaining instances. Additional analysis highlights the contribution of the clustering mechanism and combination operator to the performance of the algorithm.