Protein redesign is an enzyme engineering strategy that enhances a template enzyme's properties by introducing mutations. Although the method is broadly employed for enzyme design, finding optimal mutation combinations with high reproducibility within a limited time frame remains a major technical hurdle. In this study, we report GArNet, a Genetic Algorithm-based protein redesign approach to optimize mutation combinations informed by Network theory. GArNet uses a template structure and its homologous sequences to generate mutants of which their combinations are optimized in two phases. In Phase I, repeated virtual evolution processes produce "complete network data", in which nodes and edges represent introduced mutations and their co-occurrence, respectively. These data are merged into a single mutation network. In Phase II, the network is converted into a scale-free mutation network, and the high-centrality nodes (mutations) are selected to produce a list of mutation candidates and a mutated structure. We benchmarked GArNet using two distinct enzymes─S-hydroxynitrile lyase (S-HNL) and NAD+-dependent l-threonine 3-dehydrogenase (TDH). Computational analysis indicated that, under three independent runs, GArNet achieved >73.5% mutational reproducibility in S-HNL design, surpassing the 25% achieved by a conventional method. Experimental tests demonstrated that GArNet generated active S-HNLs and TDH mutants with enhanced thermostability and soluble expression compared to native ones. Taken together, these findings indicate that representing introduced mutations and their co-occurrence as a network effectively identifies beneficial mutations. GArNet is available at https://github.com/shognakano/GArNet.