Antifreeze proteins (AFPs) are of much interest for their ability to inhibit ice growth at low concentrations. In this work, we present a genetic algorithm for the in silico design of AFP mutants with improved antifreeze activity, measured as the predicted thermal hysteresis at a fixed concentration, ΔTC. Central to the algorithm is our recently developed neural network method for predicting ΔTC from molecular simulations [Kozuch et al., PNAS, 115, 13252 (2018)]. Applying the algorithm to three structurally diverse AFPs, wfAFP, rQAE, and RiAFP, we find that significantly improved mutants are discovered for rQAE and RiAFP. Testing of the optimized mutants shows an increase in ΔTC of 0.572 ± 0.11 K (262 ± 50.6%) and 1.33 ± 0.14 K (39.9 ± 4.19%) over the native structures for rQAE and RiAFP, respectively. Structural analysis of the optimized mutants reveals that the algorithm is able to exploit two pathways for enhancing the predicted antifreeze activity of the mutants: (1) increasing the local order of surface waters by encouraging the formation of internal water channels in the protein and (2) increasing the total ice-binding area by improving the planar structure of the ice-binding surface. Additionally, analysis of all mutants explored by the algorithm reveals that a subset of residues, mainly nonpolar, are particularly helpful in improving antifreeze activity at the ice-binding surface.