As a practical technique for enhancing relay and HARQ transmissions, Modulation Diversity (MoDiv) uses distinct constellation mappings for data retransmissions. In this work, we study the MoDiv optimization in a amplify-and-forward (AF) two-way relay channel (TWRC). The design of MoDiv design to minimize the bit-error rate (BER) is formulated into a successive Koopmans-Beckmann Quadratic Assignment Problem (QAP), which is solved sequentially with a robust tabu search method. The performance gain of our MoDiv scheme over retransmission without remapping and a heuristic MoDiv scheme is demonstrated with numerical results.