This paper presents a new approach, the COSEARCH approach, for solving the Problem of Assigning Frequencies (FAP) on antennas of a cellular telecommunication network. The COSEARCH approach is a co-evolutionist method in which complementary metaheuristics, such as genetic algorithm (GA) or tabu search (TS), cooperate in parallel via an adaptive memory (AM). We introduce an original encoding and two new cross-over operators suited to FAP. COSEARCH for the FAP is compared with other studies and its efficiency is revealed on both medium and large instances.