This paper describes Genetic Algorithm with Relay Search Method, RS-GA, which is developed in this study to search the multiple design variables in the design space. RS-GA which is based on simple-GA, consists of some functions to search many variables from some wide variable space. It repeats simple-GA, that is the convergence process of simple-GA, which makes many time reiteration itself. From the results of the case studies, it was found that RS-GA can search all peak-variables from the 2-D functions including 5 peaks subject to a variable, whereas simple-GA can search only one or two peaks and fails to search more peak. Finally, RS-GA applied for design-strengthening problems in composite plate girder bridges using the external prestressing technique is also verified.