Os métodos estocásticos com múltiplas soluções são aqueles que, após serem executados, fornecem vários conjuntos de características que obtiveram bons resultados quando avaliados pela função critério. Além disso, uma característica importante desses métodos é que, a cada vez que eles são executados, eles podem fornecer um conjunto de soluções diferente do anterior.
Essa classe de métodos engloba o uso de algoritmos genéticos para seleção de características [Siedleki and Sklansky, 1989]. Nessa abordagem, o conjunto de características é representado como uma cadeia binária de caracteres de tamanho 
em que 
ou 
na posição 
indica a ausência ou presença da característica . Essa cadeia é chamada ``cromossomo''.
Inicialmente, uma população aleatória de cromossomos é criada. Cada cromossomo é avaliado, através da função critério, para determinar sua aptidão (fitness), a qual informa se o cromossomo irá ``sobreviver'' à próxima geração ou ``morrer''. A partir de mutações ou cruzamentos dos cromossomos atuais, são criados novos cromossomos.
Após várias iterações, a aptidão geral da população será melhorada e sempre haverá várias soluções. Porém, conforme mencionado anteriormente, como os resultados são obtidos a partir de processos aleatórios (portanto não-determinísticos), normalmente são obtidos sub-conjuntos diferentes quando o algoritmo é aplicado ao mesmo conjunto em outro momento. Em [Bruno et al., 1998], essa técnica foi aplicada para efetuar a classificação de formas biológicas.