In this paper, we improve Network-Structure-Search Evolutionary Algorithm (NSS-EA) that is a search method for inference of genetic networks by S-system. Search methods for inference of genetic networks by S-system should meet the following requirements; 1) efficient search of a set of satisfactory structures, 2) search of structures satisfying biological knowledge and 3) search of the true structure. NSS-EA is an excellent method from the viewpoints of Requirement 1 and 2. However, it has a problem from the viewpoint of Requirement 3, In order to solve this problem, first, we improve the parameter search process by using the time course data of disrupted strains as well as that of a wild type when evaluating genetic networks. Second, we propose four new structure-search operators taking account of mutual interactions among substances. We show the effectiveness of the proposed improvements for NSS-EA from the viewpoint of Requirement 3 by comparing the performance of the original NSS-EA and the improved NSS-EA on a five-substance benchmark problem.