This paper presents a Binary Gravitational Search Algorithm (BGSA) methodology for the optimal placement of Phasor Measurement Units (PMUs) to achieve full and maximum observability of the power system. The gravitational search technique has been extended in this investigation to incorporate binary variables for this purpose. The objective of proposed methodology is to minimize the total number of PMUs installed at various buses, which in turn minimize installation cost of the PMUs and improves observability redundancy by including an additional objective. Thus, the PMU placement problem has been expressed as a multi-objective problem. Besides, single PMU outage or single line outage cases in the presence of zero injection buses have been investigated. In this algorithm, the searcher agents are the collection of masses, which interact with each other using Newton's laws of gravity and motion. The proposed BGSA has been applied to the IEEE 14-bus, -30-bus, -118-bus, Northern Regional Power Grid 246-bus Indian system, and Polish 2383-bus system. Case studies reveal that the lower number of PMUs or equal number of PMUs has been produced by the proposed method compared to methods reported in the literature. In cases of equal number of PMUs, the observability produced by proposed method is higher or at least equal.