For the purpose of maximizing the spread of influence caused by a certain small number k of nodes in a social network, we are asked to find a k-subset of nodes (i.e., a seed set) with the best capacity to influence the nodes not in it. This problem of influence maximization (IM) has wide application, belongs to subset problems, and is NP-hard. To solve it, we should theoretically examine all seed sets and evaluate their influence spreads, which is time-consuming. Therefore, metaheuristic strategies are generally employed to gain a good seed set within a reasonable time. We observe that many algorithms for the IM problem only adopt a uniform mechanism in the whole solution search process, which lacks a response measure when the algorithm becomes trapped in a local optimum. To address this issue, we propose a phased hybrid evaluation-enhanced (PHEE) approach for IM, which utilizes two distinct search strategies to enhance the search of optimal solutions: a randomized range division evolutionary (RandRDE) algorithm to improve the solution quality, and a fast convergence strategy. Our approach is evaluated on 10 real-world social networks of different sizes and types. Experimental results demonstrate that our algorithm is efficient and obtains the best influence spread for all the datasets compared with three state-of-the-art algorithms, outperforms the time consuming CELF algorithm on four datasets, and performs worse than CELF on only two networks.