In deregulated electricity markets, generation companies (GENCOs) make unit commitment (UC) decisions based on a profit maximization objective in what is termed profit based unit commitment (PBUC). PBUC is done for the GENCOs demand which is a summation of its bilateral demand and allocations from the spot energy market. While the bilateral demand is known, allocations from the spot energy market depend on the GENCOs bidding strategy. A GENCO thus requires an optimal bidding strategy (OBS) which when combined with a PBUC approach would maximize operating profits. In this paper, a solution of the combined OBS-PBUC problem is presented. An evolutionary particle swarm optimization (EPSO) algorithm is implemented for solving the optimization problem. Simulation results carried out for a test power system with GENCOs of differing market strengths show that the optimal bidding strategy depends on the GENCOs market power. Larger GENCOs with significant market power would typically bid higher to raise market clearing prices while smaller GENCOs would typically bid lower to capture a larger portion of the spot market demand. It is also illustrated that the proposed EPSO algorithm has a better performance in terms of solution quality than the classical PSO algorithm.