Embodiments of the present invention are generally directed to the use of a genetic algorithm for the purpose of providing progressive and adaptive auditory training (rehabilitation) to a recipient of a hearing prosthesis. In general, the genetic algorithm is used to adapt the training process to automatically increase the difficulty of the training based on recipient feedback and performance. That is, the genetic algorithm progressively removes perceivable sounds from the training process so as to generate groups of sounds that are difficult for a recipient to perceive.