Network Function Virtualization (NFV) is anemerging technology to consolidate network functions onto highvolume storages, servers and switches located anywhere in thenetwork. Virtual Network Functions (VNFs) are chainedtogether to provide a specific network service. Therefore, aneffective service chain placement strategy is required tooptimize the resource allocation and consequently to reduce theoperating cost of the substrate network. To this end, we proposefour genetic-based algorithms using roulette wheel andtournament selection techniques in order to place service chainsconsidering two different placement strategies. Since mappingof service chains sequentially (One-at-a-time strategy) may leadto suboptimal placement, we also propose Simultaneous strategythat places all service chains at the same time to improveperformance. Our goal in this work is to reduce deployment costof VNFs while satisfying constraints. We consider Geantnetwork as the substrate network along with its characteristicsextracted from SndLib. The proposed algorithms are able toplace service chains with any type of service graph. Theperformance benefits of the proposed algorithms arehighlighted through extensive simulations.