Wireless traffic prediction is of great significance to operators in network construction, wireless resources management and user experiences improvement. We develop a hierarchical clustered Federated Learning (FL) framework for wireless traffic prediction. Base stations with similar traffic distributions are grouped into clusters. Within each cluster, the central server continues to form sub-clusters which helps in mitigating the impact of non-IID data by addressing it within more homogeneous clusters. Furthermore, the sub-cluster formation process is modeled as an optimal federation formation problem, which is a NP-hard problem. The evolutionary-based heuristic approach (PSO-GA) are proposed to search for the intra-cluster optimal federation structures (including the number of the federations, as well as the members in each federations). Extensive experiments are conducted using real-world mobile traffic dataset to show that the two evolutionary-based FL outperforms previous state-of-the-art methods in terms of convergence rate as well as prediction accuracy.