Based on the Proximate Optimality Principle in metaheuristics, a Population Based Guided Local Search (P-GLS) framework for dealing with difficult combinatorial optimization problems is suggested in this paper. In P-GLS, several guided local search (GLS) procedures (agents) run in a parallel way. These agents exchange information during some time points in the search. The information exchanged is the best solutions found so far by these agents. Each agent use such information to adjust its search behavior for moving to a more promising search region. Some preliminary experiments have been conducted on the traveling salesman problem to study the effectiveness of P-GLS.