In order to deal with the problem that in the stage of fitness evaluation while the traditional evolutionary design algorithm is used for polymorphic self-checking circuits, the potential solution is lost, therefore, an improved fitness evaluation method is proposed. As the candidate circuit is evaluated by randomly selecting the output in the traditional algorithm, the fitness evaluation expansion is introduced to adopt full evaluation. The dynamic selection of the output is used to make the most appropriate evaluation for the candidate circuits, avoiding the loss of potential solution. Regarding the result of fitness evaluation expansion for polymorphic circuits, the comparison and selection are proposed to chooce the output with the highest fitness under the both modes, and then the optimal structure is configured. The simulation results of the extrinsic evolution show that the proposed method is able to detect all the stuck-at-faults in the combinational circuits, only using four test vectors. Additional input or output signals are not needed to indicate the faults in the circuits. The carry-out output of the adder is used to show the faults based on oscillations and the original input signals of the circuits could be used as the test signals. Comparing with the traditional evolutionary design algorithm, the evolution generation and the gate number in the circuit are decreased by 90.6%—91.7% and 8%—9.7% respectively. The proposed method gains the advantages of less iterations and lower resources consumption.