Collective motion occurs when individuals use social interaction rules to respond to the movements and positions of their neighbors. How readily these social decisions are shaped by selection remains unknown. Through artificial selection on fish (guppies, Poecilia reticulata) for increased group polarization, we demonstrate rapid evolution in how individuals use social interaction rules. Within only three generations, groups of polarization-selected females showed a 15% increase in polarization, coupled with increased cohesiveness, compared to fish from control lines. Although lines did not differ in their physical swimming ability or exploratory behavior, polarization-selected fish adopted faster speeds, particularly in social contexts, and showed stronger alignment and attraction responses to multiple neighbors. Our results reveal the social interaction rules that change when collective behavior evolves.