The paper presents a methodology based on a Modified Binary Bat Algorithm (MBBA) and Improved Seed Population search that provides nearly optimal solutions to the power loss minimization problem, considering network reconfiguration and a large number of switches. The existence of many switches leads to a very large number of combinations, making it hard for algorithms to find a good solution. The proposed method is based on eliminating non-feasible solutions and defining an initial matrix with improved seed population for searching the optimal solution. This seed is used for the random process of the algorithm to produce new solutions and is continually updated to obtain better results close to the optimal solutions found during the searching process of the metaheuristic algorithm. This algorithm was tested against the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), and the Seed Population search alone on the modified versions of the IEEE 13-node test and IEEE 123-node test feeders. From several runs, the proposed method reached the optimal solution more times than the other algorithms and the remainder achieved near-optimal solutions. With this result, the MBBA provides good options to improve the solutions in the network reconfiguration problem with a large number of switches.