Improved Grey Wolf Optimization Algorithm and Application

Yuxiang Hou, Huanbing Gao, Zijian Wang, Chuansheng DuSensors 2022 · DOI

TL;DR

This paper introduces an enhanced Grey Wolf Optimizer (GWO) algorithm designed to improve stability and convergence accuracy for mobile robot path planning. By incorporating chaotic tent mapping for initialization, a nonlinear convergence factor, and a dynamic weighting strategy, the proposed GWO demonstrates superior performance in both benchmark function tests and real-world path planning scenarios.

What Problem Does This Paper Address?

Mobile robot path planning is a critical task that involves finding an optimal trajectory from a starting point to a destination while avoiding obstacles. While various optimization algorithms exist, such as A*, PSO, and GA, the standard Grey Wolf Optimizer (GWO) faces challenges with slow convergence, low solution accuracy, and a tendency to get stuck in local optima. These limitations hinder its effectiveness in complex and dynamic environments. This paper aims to overcome these drawbacks by proposing a series of improvements to the GWO algorithm, specifically targeting its initialization, convergence mechanism, and position update strategy, to make it more robust and efficient for mobile robot path planning.

Methods

The authors propose an "Improved Grey Wolf Optimizer" (IGWO) by enhancing three key components of the standard GWO:

  • Wolf Pack Initialization: Instead of random initialization, IGWO uses an "improved chaotic tent mapping" to generate initial wolf positions. This method aims to improve global search ability by ensuring a more diverse and uniformly distributed initial population within the search space.
  • Nonlinear Convergence Factor: The standard GWO uses a linearly decreasing convergence factor. IGWO introduces a nonlinear convergence factor based on a Gaussian distribution change curve. This aims to better balance global exploration in the early stages and local exploitation in the later stages of the search, preventing premature convergence to local optima.
  • Dynamic Proportional Weighting Strategy: The paper proposes an improved dynamic weighting strategy to update the positions of the grey wolves. This strategy, inspired by fitness and location, aims to make the wolf pack find the optimal solution more precisely and accelerate convergence.

These improvements are then applied to the path planning problem for mobile robots.

Datasets

The paper evaluates the proposed IGWO algorithm using two types of benchmarks:

  • 15 International Standard Benchmark Test Functions: These functions are used to assess the algorithm's performance in terms of convergence accuracy and speed across various optimization landscapes (single-peak and multi-peak).
  • Mobile Robot Path Planning Scenarios: The algorithm is tested on simulated environments with randomly generated obstacles to evaluate its effectiveness in finding safe and optimal paths.

No new datasets were introduced; standard benchmark functions and simulated robot environments were utilized.

Key Insights and Ideas

  • Initialization Matters: The choice of initialization strategy significantly impacts GWO's performance. Chaotic tent mapping, with its improved ergodicity and uniform distribution, proves more effective than random initialization for enhancing global search.
  • Nonlinearity for Balance: A linear convergence factor is too simplistic for the dynamic needs of optimization. A nonlinear, Gaussian-based convergence factor allows for a more nuanced balance between exploring new areas and exploiting promising ones, crucial for avoiding local optima.
  • Dynamic Weighting for Precision: Simply averaging wolf positions isn't optimal. A dynamic weighting strategy that considers fitness and location allows the algorithm to more intelligently guide the search towards the best solutions.
  • GWO's Potential for Robotics: Despite its limitations, GWO's core principles are well-suited for complex optimization tasks like path planning. The proposed improvements unlock this potential, making it a more viable option for real-world applications.

Key Results

The experimental results demonstrate that the improved GWO algorithm (IGWO) significantly outperforms the standard GWO and several other improved GWO variants (MGWO, NGWO, GWO-fuzzy, GWO-EPD) in both benchmark function tests and mobile robot path planning.

  • Benchmark Functions: IGWO achieved higher accuracy and faster convergence speeds across most of the 15 benchmark functions. For single-peak functions (f1-f4, f8, f10), it often reached the theoretical optimal value of 0, with significantly lower mean and standard deviation values compared to other algorithms. For multi-peak functions, it also showed superior performance in finding optimal or near-optimal solutions.
  • Mobile Robot Path Planning: In simulated path planning scenarios, IGWO successfully planned safe paths with optimal costs and satisfied constraints. The convergence curves showed that IGWO converged faster and more stably than other compared algorithms. The paper highlights that IGWO effectively avoids the trap of local optima, which is crucial for real-time path planning.

Limitations and Future Work

  • Computational Complexity: The paper notes that the improved GWO algorithm's complexity is O (N² × d × Tmax), which is higher than some other algorithms. However, they argue that the improved accuracy and convergence speed justify this trade-off.
  • Future Research: The authors plan to continue improving the algorithm and applying it to more practical mobile robot scenarios. They also suggest further research into applying the improved algorithm to more complex and dynamic environments.

Summary updated

Abstract

This paper proposed an improved Grey Wolf Optimizer (GWO) to resolve the problem of instability and convergence accuracy when GWO is used as a meta-heuristic algorithm with strong optimal search capability in the path planning for mobile robots. We improved chaotic tent mapping to initialize the wolves to enhance the global search ability and used a nonlinear convergence factor based on the Gaussian distribution change curve to balance the global and local searchability. In addition, an improved dynamic proportional weighting strategy is proposed that can update the positions of grey wolves so that the convergence of this algorithm can be accelerated. The proposed improved GWO algorithm results are compared with the other eight algorithms through several benchmark function test experiments and path planning experiments. The experimental results show that the improved GWO has higher accuracy and faster convergence speed.
BibTeX
@inproceedings{hou2022improved,
  author = {Yuxiang Hou and Huanbing Gao and Zijian Wang and Chuansheng Du},
  title = {{Improved Grey Wolf Optimization Algorithm and Application}},
  booktitle = {Sensors},
  year = {2022},
  doi = {10.3390/s22103810},
}
Figure