Network virtualization (NV) has emerged as a momentous facilitator for a notable triumph of future networks by allowing a flexibility, cost-efficiency and on-demand services through the deployment of heterogeneous network service requests on a shared physical infrastructure. The most major challenge of NV is to efficiently and effectively map diversified virtual network requests (VNRs), comprising a set of virtual nodes connected by virtual links, onto a shared substrate network meeting various stringent resource constraints. Most of the research papers in this field have merely focused on separate virtual node mapping (VNoM) or virtual link mapping (VLiM) with scalable heuristic algorithms for simple implementations. Unfortunately, the lack of a coordination between node and link mapping stages might cause low embedding results. In this paper, we present a new approach relied upon Genetic Algorithm (GA), that jointly coordinates virtual node and link mappings where the link mapping is based on three different path searching methods. Moreover, a novel heuristic conciliation mechanism is proposed to deal with a set of possibly infeasible link mappings while exploring embedding solutions within the operations of GA algorithm. Extensive performance results indicate that our proposed GA-based algorithms outperform state-of-the-art virtual mapping algorithms in all evaluation metrics we adopt.