Uma tendência relativamente nova no campo dos AG's é a incorporação de técnicas de busca local. Traz alguns resultados desalentadores dos AG's a ser aplicados a algum problema (especialmente os muito difíceis) de otimização combinatória, os investigadores começaram a buscar novas maneiras para estender os AG's e obter melhores resultados.

Um passo importante nesta direção foi dado por Muhlenbein com o desenvolvimento de "Algoritmos Genéticos Paralelos " (PGA's) que permitem que os indivíduos na população melhorem seu fitness mediante melhoras iterativas (conhecidas como hill climbing) . Nos PGA's também permitem que os indivíduos se selecionem entre eles por processos locais, o que facilita sua implementação em sistemas concorrentes.

 De certo modo, os AG's simples com busca local podem ser vistos como métodos sofisticados de descenso múltiplo. O processo de reinicialização está neste caso comandado por regras genéticas, e a fase de descenso é encerrada como de costume. O êxito dos métodos podem ser atribuídos ao seu equilíbrio entre ter uma busca rápida e manter uma diversidade para evitar a convergência prematura. Outro método pode consistir em desenvolver uma busca iterativa chamada Delta coding proposta por D. Whitley e seus colaboradores. Delta coding introduz diversidade gerando aleatoriamente uma população nova, no entanto preserva a informação das gerações anteriores baseando as novas codificações em soluções parciais previas.