Algoritimos Genéticos [AG] IV


bom continuando o artigo sobre algoritimo genético III, motrando um pocuo mais sobre parâmentros e exemplo de algumas funções,Exemplo de AG (Algoritmo Genético) Mínimo de uma Função.

sobre o problema
Como você já sabe do capítulo sobre espaço de soluções, a solução de um problema pode freqüentemente ser expressa como a procura pelo extremo de uma função definida em um espaço de soluções. Iremos resolver exatamente esse problema aqui.

Dada uma função, o AG tentará encontrar o mínimo dessa função. Para outros problemas, nós apenas temos que definir o espaço de soluções e a função de adequação (para a qual nós teremos que achar um extremo).

Exemplo

Tente executar o algoritmo genético do applet seguinte apertando o botão "Start". O gráfico representa o espaço de soluções e as linhas verticais representam as soluções (pontos do espaço de soluções). A linha vermelha é a melhor solução, as linhas verdes são as outras. A antiga e a nova população são mostradas na parte superior do applet. Cada população consiste de cromossomas binários - ponts vermelhos e azuis significam zeros e uns. Você pode ver o processo de formação de novas populações passo a passo com o applet.

O botão "Start" inicia o algoritmo, o botão "Step" executa um passo (ito é, forma uma nova geração), o botão "Stop" para o algoritmo e o botão "Reset" reinicia a população.
O melhor é começar executando o applet passo a passo (botão "Step") para ver em detalhe como funciona o AG. O esboço básico do AG foi introduzido num dos capítulos anteriores. Você pode ver o elitismo para os primeiros cromossomas e então formar as novas descendências através de cruzamentos e mutações até que uma nova população seja completada. assim como segue o exemplo no site do Dr marek que tenho sempre como referencia nos meus estudos! (:

Parâmetros dos AG

Há dois parâmetros básicos dos AG - Probabilidade de Cruzamento e de Mutação.

Probabilidade de Cruzamento: com qual freqüência o cruzamento é realizado. Se não não houver cruzamento, a descendência é uma cópia exata dos pais. Se ocorre o cruzamento a descendência é constituída de partes dos cromossomas de ambos os pais. Se a probabilidade de cruzamento é 100%, então toda a descendência é produzida por cruzamento. Se a probabilidade é 0%, toda a nova geração é formada por cópia exata dos cromossomas da população antiga (mas isso não significa que a nova geração é a mesma!).
Os cruzamentos são realizados na esperança de que os novos cromossomas contenham partes boas dos cromossomas antigos e que portanto os novos cromossomas serão melhores. Entretanto, é bom deixar uma parte da antiga população sobreviver para a próxima geração.

Probabilidade de Mutação: com qual freqüência as partes dos cromossomas sofrerão mutação. Se não houver mutação, a descendência é gerada imediatamente após o cruzamento (ou copiada diretamente) sem nenhuma alteração. Se ocorreu a mutação, uma ou mais partes do cromossoma é alterada. Se a probabilidade de mutação é 100%, todos os cromossomas são alterados, se é 0%, nenhum é alterado.
A mutação em geral evita que o AG caia num extremo (mínimo ou máximo) local. A mutação não deve ocorrer com muita freqüência porque senão o AG tornar-se-á de fato uma busca aleatória.

Outros Parâmetros

Temos também alguns outros parâmetros nos AG. Um particularmente importante é o tamanho da população.

Tamanho da População: quantos cromossomas existem na população (em uma geração). Se houver poucos cromossomas, o AG terá poucas possibilidade de realizar cruzamentos e somente uma parte pequena do espaço de soluções será explorada. Por outro lado, se houver muitos cromossomas, os AG tornar-se-ão lentos. Pesquisas mostram que após determinado limite (que depende principalmente da codificação e do problema), não é conveniente aumentar a população porque isso não resolve o problema mais rapidamente do que com tamanhos moderados de população.

Algumas recomendações para os parâmetros podem ser encontradas nos capítulos seguintes.

Exemplo
Aqui você pode ver um exemplo similar ao anterior. Porém aqui você pode mudar a probabilidade de cruzamento e de mutação. É possível também controlar o elitismo.
No gráfico abaixo você pode ver o desempenho do AG. A vermelha é a melhor solução, a azul é o valor médio (adequação) de toda a população.
Mude os parâmetros e veja como o AG se comporta.
Questão: Se você aumenta a probabilidade da mutação até 100%, o AG começará a se comportar de maneira muito estranha, de uma forma parecida como se a probabilidade de mutação fosse 0%. Você sabe por que? Você pode ver uma dica e se mesmo assim você não conseguir descobrir, veja a resposta em: solução!
segue o exemplo aqui!

Extremo de uma Função

Novamente o problema é encontrar o extremo (mínimo ou máximo) de uma função. Porém neste caso, mais uma dimensão foi adicionada.

Exemplo

O gráfico representa o espaço de soluções e as linhas representam as soluções (pontos no espaço de soluções). A linha vermelha é a melhor solução, e as linhas azuis são as outras.
Você pode entrar com sua própria função no campo de texto abaixo do gráfico (após introduzir a nova função pressione "enter" no teclado ou o botão "Change"). Abaixo você pode definir os limites da função. A função pode conter x, y, pi, e, (, ), /, *, +, -, !, ^ e as funções abs, acos, acosh, asin, asinh, atan, atanh, cos, cosh, ln, log, sin, sinh, sqr, sqrt, tan and tanh.
O gráfico pode ser girado clicando-se com o botão esquerdo do mouse sobre ele e arrastando.
É possivel mudar a probabilidade de cruzamento e de mutação. Através de botões de "ticar" é possivel selecionar quando se quer usar elitismo e se quer procurar mínimo ou máximo.
Experimente mudar a função e veja como o AG se comporta. Se você encontrar alguma função interessante, onde o AG se comporta muito bem, ou muito estranho, você pode enviá-la pra mim.Segue o exemplo aqui!

bom termino por aqui para que vocês possa ler e metitar sobre o assunto , nada mais que treino e mais treinos,bons estudos e ate a proxima!:D

[]'s











Algoritimos Genéticos [AG] IV Algoritimos Genéticos [AG]   IV Reviewed by Kembolle Amilkar on sexta-feira, janeiro 16, 2009 Rating: 5

Nenhum comentário