This paper proposes an electromechanical impedance (EMI) method for monitoring bolt loosening in wing truss structures, optimizing the selection of conductance frequency intervals to enhance structural health assessment efficiency. Traditional full-frequency band data input often leads to low training efficiency and feature redundancy in deep learning models. To address this, an intelligent algorithm is introduced to autonomously extract optimal frequency sub-bands as input for a convolutional neural network (CNN), improving damage identification accuracy. Experimental tests were conducted on a wing truss structure with multiple bolt loosening scenarios, including single-bolt loosening at varying torque levels (9 N·m to 0 N·m) and mixed multi-bolt loosening. Conductance and susceptance signals were acquired within a 100–300 kHz frequency range using an impedance analyzer. Results revealed that bolt loosening induces resonance frequency shifts and amplitude fluctuations, but raw data alone cannot reliably quantify loosening severity. Damage indices demonstrated higher sensitivity in conductance than susceptance, yet exhibited irregular trends with increasing damage, limiting their reliability. To overcome these limitations, a CNN model was trained on noise-augmented conductance data, achieving over 99.1667% classification accuracy in distinguishing bolt loosening faults. The optimized frequency band selection reduced computational load while preserving critical features, enabling efficient real-time monitoring.