In this paper, we investigate a multiple relay selection scheme for two-way relaying cognitive radio networks where primary users and secondary users operate on the same frequency band. More specifically, cooperative relays using Amplify-and-Forward (AF) protocol are optimally selected to maximize the sum rate of the secondary users without degrading the Quality of Service (QoS) of the primary users by respecting a tolerated interference threshold. A strong optimization tool based on genetic algorithm is employed to solve our formulated optimization problem where discrete relay power levels are considered. Our simulation results show that the practical heuristic approach achieves almost the same performance of the optimal multiple relay selection scheme either with discrete or continuous power distributions.