Hybrid Beamforming for RIS-Aided Communications: Fitness Landscape Analysis and Niching Genetic Algorithm

Bai Yan, Qi Zhao, Jin Zhang 0001, J. Andrew Zhang, Xin Yao

Abstract

This paper addresses the complex optimization challenge of Reconfigurable Intelligent Surfaces (RIS) in 6G wireless networks. By first proving that the optimization "fitness landscape" is highly rugged and multi-modal, the authors demonstrate why traditional local search methods fail. To overcome these challenges, they propose a Niching Genetic Algorithm (NGA) that partitions the search population into distinct "species" to explore multiple local optima simultaneously. The proposed NGA achieves up to 15dB capacity gains over traditional sequential search methods in large-scale RIS scenarios.

Introduction

Reconfigurable Intelligent Surfaces (RIS) represent a transformative 6G technology—passive arrays capable of "steering" radio waves to enhance signal quality without the significant power consumption of active relays. However, the practical deployment of RIS requires the joint optimization of Base Station (BS) beamforming and the RIS's discrete phase shifts.

The primary hurdle is the high interdependence of these phase shifts. Existing algorithms often rely on sequential search or simple quantization, which frequently fail because they ignore the underlying "ruggedness" of the optimization landscape. In these complex mathematical terrains, standard algorithms often become trapped in local optima (false peaks) rather than reaching the global maximum.

Fitness Landscape Analysis

Before developing an optimizer, the authors conducted a rigorous structural analysis of the problem using Fitness Distance Correlation (FDC) and Autocorrelation. A critical innovation in this analysis is the introduction of a "cycle-q distance" metric. This metric accounts for the periodic nature of phase shifts (e.g., recognizing that 350° is closer to 10° than to 180°), which is essential for accurately measuring distances in the search space.

Fitness landscape analysis showing increasing ruggedness and multi-modality as the number of RIS elements (N) grows.

The analysis confirms that as the number of RIS elements ($N$) increases, the landscape becomes increasingly multi-modal. The FDC analysis reveals near-zero correlation between a solution's fitness and its distance to the global optimum in large systems, explaining why local search methods lack the necessary "compass" to find optimal configurations.

The Niching Genetic Algorithm (NGA)

To navigate this rugged terrain, the authors developed the Niching Genetic Algorithm (NGA), featuring two primary innovations:

  1. Nearest-Better Clustering (NBC): This technique partitions the population into different "species" based on their proximity in the search space. Each species explores its own neighborhood, preventing the entire population from prematurely converging on a single local peak.
  2. Dynamic Minimum Species Size: A parameter ($N_{min}$) that increases over generations allows for high exploration (many small species) at the start and high exploitation (fewer, larger species for refinement) toward the end of the process.

Performance Evaluation

The system was evaluated in a simulated downlink MU-MISO environment with 4 BS antennas and 4 users, with RIS sizes ranging from $N=20$ to $N=200$. The results highlight the superiority of the NGA approach in complex environments.

Sum rate performance comparison of NGA against baseline algorithms across different RIS sizes.

Key findings include:

  • Significant Capacity Gains: In large-scale scenarios ($N=200$), the NGA achieved a 15dB gain in sum rate compared to sequential search, simulated annealing, and standard genetic algorithms.
  • Scalability: The NGA's complexity is polynomial ($O(N_Q^2 \times N)$), making it far more practical than optimal Branch-and-Bound methods which scale exponentially.
  • The 2-Bit Sweet Spot: Results indicate that moving from 1-bit to 2-bit phase shifts provides massive gains, while higher resolutions offer diminishing returns, suggesting 2-bit hardware is sufficient for practical use.

Conclusion

The NGA provides a robust solution for RIS optimization by maintaining population diversity and avoiding premature convergence. While the current model assumes perfect Channel State Information (CSI), future work will focus on addressing the challenges of imperfect CSI and hardware impairments. Additionally, parallel implementation of the NGA could further reduce computational overhead for real-time millisecond-scale wireless applications.

Summary updated

BibTeX
@article{yan2022hybrid,
  author = {Bai Yan and Qi Zhao and Jin Zhang and J. Andrew Zhang and Xin Yao},
  title = {{Hybrid Beamforming for RIS-Aided Communications: Fitness Landscape Analysis and Niching Genetic Algorithm}},
  journal = {Applied Soft Computing},
  year = {2022},
  doi = {10.1016/j.asoc.2022.109725},
}
Figure