A parallel genetic algorithm for optimizing the location of sink nodes of a wireless sensor network is proposed. As an optimization criterion we consider a reliability of a wireless sensor network under the assumption that nodes of a wireless sensor network are subject of random independent failures due to scuffing, intrusions, or other reasons. As a result, some sensors can become disconnected from sink nodes that collect data from all the sensors. A random graph with unreliable nodes and absolutely reliable edges is used as a model of such wireless sensor networks. By wireless sensor network reliability we mean the mathematical expectation of the number of sensors connected to any sink node (MENC). For reliability calculation a well-known factoring method is used. Various optimization algorithms are considered: a canonical genetic algorithm, a module genetic algorithm, an island genetic algorithm, and an island genetic algorithm with migration. The results of the numerical experiments are given.