Algoritmo genético
Os Algoritmos Genéticos referem-se a uma classe de procedimentos de busca adaptativa, inspirada nos princípios evolutivos das populações genéticas da natureza, e foram concebidos por Holland (Michigan University) nos anos 60. Sua denominação originou-se da analogia entre a representação de uma estrutura complexa através de um vetor de componentes e a idéia da estrutura genética de um cromossoma.
Em ambos os contextos, o natural e o dos Algoritmos Genéticos, dois conceitos são fundamentais: (1) a evolução, que pode ser conceituada como a geração expontânea e contínua de estruturas funcionais inovativas [Bedau e Packard, 1992], e (2) a adaptação, que designa qualquer processo através do qual uma estrutura é progressivamente modificada para obter melhor desempenho no seu ambiente [Holland, 1992]. Durante o curso da evolução, as populações naturais evoluem conforme os princípios de seleção natural e sobrevivência da adaptação. Ou seja, indivíduos que adaptam-se melhor ao ambiente, possuem maiores chances de sobreviver e reproduzir, enquanto os indivíduos de menor ajuste tendem a ser eliminados. Isto significa que os genes dos indivíduos altamente aptos influenciarão um número crescente de indivíduos a cada geração, e sua espécie evolui para se tornar cada vez mais adaptada ao seu ambiente.
Um Algoritmo genético simula este processo, tomando uma população inicial de indivíduos e aplicando operadores genéticos artificiais em cada geração. Em condições de otimização, cada indivíduo da população é codificado em um string ou cromossoma, o qual representa uma solução possível para um determinado problema, enquanto a adaptação dos indivíduos é avaliada através de uma função de aptidão. Basicamente, aos indivíduos altamente aptos (melhores soluções) são dadas maiores oportunidades de reproduzirem-se trocando partes de informação genética, em um procedimento de acasalamento denominado Cruzamento; o operador de Mutação é utilizado para alterar alguns genes