Author: Project Computing
A parte inferior desta página contém um applet Java simples que demonstra visualmente um enxame de partículas procurando um valor máximo em um cenário 3D. O applet Java é fornecido como um arquivo jar de 45 KB que foi testado com o JVM da Microsoft instalado no IE6, mas deve funcionar com qualquer JVM 1.1 ou superior.
A otimização de enxames de partículas é uma abordagem para problemas cujas soluções podem ser representadas como um ponto em um espaço de solução n-dimensional. Uma série de particulas são colocados aleatoriamente em movimento através deste espaço. Em cada iteração, eles observam a "aptidão" de si mesmos e seus vizinhos e "emulam" os vizinhos bem sucedidos (aqueles cuja posição atual representa uma melhor solução para o problema do que a deles), movendo-se em direção a eles. Vários esquemas para agrupar partículas em sistemas concorrentes, semi-independentes rebanhos podem ser utilizadas, ou todas as partículas podem pertencer a um único rebanho global. Esta abordagem extremamente simples tem sido suprisingly eficaz em uma variedade de domínios problema.
PSO foi desenvolvido por James Kennedy e Russell Eberhart em 1995, depois de ter sido inspirado pelo estudo do comportamento flocking pássaro pelo biólogo Frank Heppner. Está relacionado com técnicas de resolução de problemas inspiradas na evolução, como algoritmos genéticos.
Recursos
- Otimização de enxame de particulas, papel de James Kennedy e Russell Eberhart
- Livro: Inteligência de Swarm por James Kennedy, Russell C. Eberhart, com Yuhui Shi (Tabela de conteudos)
- Central de Enxames de Partículas - um diretório de recursos pertencentes ao PSO
Sinta-se livre para contatar Projeto de Computação para discutir aplicações de PSO.
PSO é tipicamente usado para resolver problemas com muitas incógnitas (de muitas "dimensões"). Esta visualização é comparativamente extremamente simples e trivial: o enxame procura através de 2 incógnitas (ou "dimensões"), eo valor de cada ponto nessas 2 dimensões foi plotado na terceira dimensão.
Este applet foi escrito por Kent Fitch, Project Computing, construindo e combinando versões modificadas destes dois programas:
- O código incluído no 3D computação gráfica: Passando de desenhos de armação de arame para modelos sólidos e sombreados por Todd Sundsted, que apareceu em JavaWorld, julho de 1997. Embora a API de Java 3D forneça a funcionalidade requerida, o código de Todd é simples e funciona sob Java 1.1
- A implementação do PSO adaptiveview.com, que é simples e foi fácil de executar em Java 1.1.
- Este applet gera um cenário semi-aleatório 3-D. Um enxame de partículas aleatoriamente gerado de 12 partículas tenta encontrar o "máximo global" na paisagem. O enxame não "sabe" qual é o valor máximo: é apenas dito para parar quando ele encontra-lo.
- Um novo enxame (com novas posições iniciais) pode ser gerado, assim como novas paisagens.
- O enxame de 12 partículas pode "trabalhar em conjunto" como um rebanho, ou pode ser dividido em 2, 3 ou 4 rebanhos semi-autónomos.
- O enxame pode ser executado até a conclusão (ou 100 iterações), "single stepped" e pausado.
- Diferentes cores são usadas para renderizar a posição das gerações atuais e anteriores e as faixas de movimento são renderizadas para ajudar a visualizar o progresso do enxame.
- Aguarde até que o applet seja carregado. Como o código é apenas 45KB, isso não deve demorar muito. Em seguida, você verá uma paisagem 3-D abaixo. Ou comece a clicar nos botões ou leia a explicação que se segue!
- O máximo global (que é o ponto que o enxame está procurando) é marcado com uma seta vermelha.
- Você pode girar a paisagem usando os botões Para Cima / Para Baixo / Esquerda / Direita, ou clicando na paisagem e usando as teclas de seta. Você não pode girar a paisagem usando o mouse.
- Clique no botão "etapa". Isso inicializará o enxame na paisagem. A posição inicial de cada partícula será mostrada por um pequeno marcador verde. Gire a paisagem para ver as partículas em relação umas às outras eo máximo.
- Clique no botão "step" novamente. Os quadrados verdes se moverão, geralmente na direção da partícula "mais apta". A localização anterior das partículas é marcada com um marcador amarelo, e uma linha verde é desenhada a partir do anterior para o local atual, "visualizar" o movimento.
- "Step" novamente: a geração original é agora magenta colorido, a segunda geração é agora de cor amarela ea localização da geração atual é novamente processado em verde. As linhas amarelas mostram os vetores tomados pela geração original que se deslocam para a segunda geração, e as linhas verdes mostram os vetores tomados por esta geração se movendo para a geração atual.
- "Passo" novamente: a geração original é agora de cor azul. Passo novamente, e esta geração é agora preta. Ou seja, as gerações são representadas usando as seguintes cores: verde, amarelo, magenta, azul, preto. As posições de todas as gerações mais antigas, as mais recentes, são renderizadas em preto. Os vetores de movimento são mostrados apenas para as 2 gerações mais recentes.
- Os vetores de movimento são sempre representados "no topo" da paisagem e podem ser vistos mesmo se a paisagem obscurecesse o vetor no "mundo real".
- As informações de status na parte inferior da janela do applet mostram o número de iterações concluídas, o valor máximo que o enxame está procurando, o valor máximo encontrado na última (mais recente) iteração eo valor máximo encontrado em qualquer iteração nesta execução.
- Primeiro passo-unico o enxame para ter uma idéia do que está acontecendo. Isso é mais fácil com apenas um rebanho, pois não há indicação visual de quais partículas estão agrupadas em um rebanho.
- Entao rode alguns testes até a conclusão, observando o rebanho movendo-se através da paisagem.
- Observe como os testes de rerunning na mesma paisagem produzem resultados surpreendentemente diferentes; Isto é, como algumas posições iniciais das partículas conduzem à localização rápida do máximo global e como outras posições levam à falha após 100 iterações.
- Teste os resultados de Diferentes números de rebanhos na mesma paisagem.
- Tente novas paisagens. Observe como algumas paisagens são apenas mais difíceis, como aquelas com máximos locais "atraentes" a alguma distância do máximo global.
- Observe que o enxame não tem memória diferente da geração atual. Ele revisita localizações anteriores que, se tivesse tal memória, seria "saber" não pode ser o máximo global. Observe também que, às vezes, padrões de repetição serão configurados, muitas vezes com múltiplas partículas simultaneamente percorrendo os mesmos vetores.
Zip contendo toda a fonte: backup11apr04psovis.zip