Metaheuristics are an impressive area of research with extremely important improvements in the solution of intractable optimization problems. Major advances have been made since the first metaheuristic was proposed and numerous new algorithms are still being proposed every day. There is no doubt that the studies in this field will continue to develop in the near future. However, there is an obvious demand to pick out the best performing metaheuristics that are expected to be permanent. In this survey, we distinguish fourteen new and outstanding metaheuristics that have been introduced for the last twenty years (between 2000 and 2020) other than the classical ones such as genetic, particle swarm, and tabu search. The metaheuristics are selected due to their efficient performance, high number of citations, specific evolutionary operators, interesting interaction mechanisms between individuals, parameter tuning/handling concepts, and stagnation prevention methods. After giving absolute foundations of the new generation metaheuristics, recent research trends, hybrid metaheuristics, the lack of theoretical foundations, open problems, advances in parallel metaheuristics and new research opportunities are investigated.