An investigation into sensor optimal placement for bridge structure based on Single Parents Genetic Algorithm with different fitness functions has been carried on. Five fitness functions are designed from several aspects on linear independence, orthogonality and energy of mode. The two-step method is proposed to determine the number of sensors firstly and then sensor position. An example of a large span arch bridge has proved the following facts: the Single Parents Genetic Algorithm is quite suitable to sensor optimal placement for bridge structure. Fitness functions designed by effective independence index and MAC and BHM combined index are more desirable than other evaluation indices. Two-step method used to determine the number of sensors and position is very effective.