Recently, underwater acoustic sensor networks (UASNs) have been considered as a promising approach for monitoring and exploring the oceans in lieu of traditional underwater wireline instruments. As a result, a broad range of applications exists ranging from oil industry to aquaculture and includes oceanographic data collection, disaster prevention, offshore exploration, assisted navigation, tactical surveillance, and pollution monitoring. However, the unique characteristics of underwater acoustic communication channels, such as high bit error rate, limited bandwidth, and variable delay, lead to a large number of packet drops, low throughput, and significant waste of energy because of packets retransmission in these applications. Hence, designing an efficient and reliable data communication protocol between sensor nodes and the sink is crucial for successful data transmission in underwater applications. Accordingly, this paper is intended to introduce a novel nature-inspired evolutionary link quality-aware queue-based spectral clustering routing protocol for UASN-based underwater applications. Because of its distributed nature, link quality-aware queue-based spectral clustering routing protocol successfully distributes network data traffic load evenly in harsh underwater environments and avoids hotspot problems that occur near the sink. In addition, because of its double check mechanism for signal to noise ratio and Euclidean distance, it adopts opportunistically and provides reliable dynamic cluster-based routing architecture in the entire network. To sum up, the proposed approach successfully finds the best forwarding relay node for data transmission and avoids path loops and packet losses in both sparse and densely deployed UASNs. Our experimental results obtained in a set of extensive simulation studies verify that the proposed protocol performs better than the existing routing protocols in terms of data delivery ratio, overall network throughput, end-to-end delay, and energy efficiency.