In the context of black box optimization, one of the most common ways to handle deceptive attractors is to periodically restart the algorithm. In this paper, we explore the benefits of combining the simple (1+1) Evolutionary Algorithm (EA) with the Luby Universal Strategy - the (1 + 1) EAU , a meta-heuristic that does not require parameter tuning. We first consider two artificial pseudo-Boolean landscapes, on which the (1 + 1) EA exhibits exponential run time. We prove that the (1 + 1) EAU has polynomial run time on both instances. We then consider the Minimum Vertex Cover on two classes of graphs. Again, the (1 + 1) EA yields exponential run time on those instances, and the (1 + 1) EAU finds the global optimum in polynomial time. We conclude by studying the Makespan Scheduling. We consider an instance on which the (1 + 1) EA does not find a (4/3 − )- approximation in polynomial time, and we show that the (1 + 1) EAU reaches a (4/3 −)-approximation in polynomial time. We then prove that the (1 + 1) EAU serves as an Efficient Polynomial-time Approximation Scheme (EPTAS) for the Partition Problem, for a (1 +)-approximation with > 4/n.