In real life, independent networks exist widely and their robustness has received significant attention. When an interdependent network faces attacks, the failure can propagate along inter-links to the whole network and the damage caused by malicious attacks is more serious. However, in terms of designing the robust inter-links of interdependent networks, most of the existing strategies target at random attacks and make little use of the inner structure of interdependent networks. In this paper, we propose a specific memetic algorithm (MA) for optimizing the inter-links to enhance the robustness of interdependent networks against malicious attacks, termed as MA-RINint. Moreover, we design an effective crossover operator based on retaining the inter-links of adjacent nodes and a local search operator according to the degree of nodes. In the experiments, we compare the proposed algorithm with five existing methods on three types of interdependent networks with different sizes, and the experimental results show that MA-RINint performs excellently in enhancing the robustness of interdependent networks.