A set of k integers is a 2-basis if every positive integer up to n can be expressed as the sum of no more than 2 values from the set; an extremal 2-basis is one for which n is as large as possible. A new algorithm extends the lower bound of Mossige for symmetric bases. An assumed modulo structure is combined with local search. These 2-bases match all known extremal values for k from 11 to 20. Bases out to k = 82 are given.