The COR methodology allows the learning of Linguistic Fuzzy Rule-Based Systems by considering cooperation among rules. In order to do this, it uses search techniques, such as Genetic Algorithms, to find the set of candidate rules which will be used to build the final rule base. The performance of COR algorithms, in terms of the quality of the solutions and cost of the search, decreases as the problem size grows. In this paper, several local search algorithms for learning the rule base are tested, as an alternative to population-based methods. Experiments show that, in most cases, the results for the error of prediction improve upon those obtained with Genetic Algorithms. Moreover, this proposal allows a drastic reduction in the computational effort required to find the solutions.