Several power system stabilizers (PSS) connected in number of machines in a multi-machine power systems, pose the problem of appropriate tuning of their parameters so that overall system dynamic stability can be improved in a robust way. Based on the foraging behavior of Escherichia coli bacteria in human intestine, this paper attempts to optimize simultaneously three constants each of several PSS present in a multi-machine power system. The tuning is done taking an objective function that incorporates a multi-operative condition, consisting of nominal and various changed conditions, into it. The convergence with the proposed rule based bacteria foraging (RBBF) optimization technique is superior to the conventional and genetic algorithm (GA) techniques. Robustness of tuning with the proposed method was verified, with transient stability analysis of the system by time domain simulations subjecting the power system to different types of disturbances.