Postei essa pergunta anteriormente no stackoverflow, onde foi fechada como off-topic. Espero que sobreviva aqui.
No nosso ginásio de escalada, as rotas precisam ser redefinidas de tempos em tempos. As seguintes regras se aplicam:
- Temos suportes de escalada com várias cores diferentes em quantidades variadas. - Quando uma rota é definida em um setor, nenhuma outra rota da mesma cor deve ser definida nesse setor ou nos setores próximos para evitar confusão.
- Algumas combinações de cores devem ser evitadas em um setor, como branco / cinza ou vermelho / rosa.
- O objetivo é ter quatro rotas em cada setor, menos está ok se quatro violarem as regras acima.
Eu tentei duas abordagens diferentes até agora. O primeiro foi o Simulated Annealing, onde eu inicializei a parede com um padrão aleatório de cores (mas com um determinado peso de cor) e calculei um valor ruim para cada combinação de cores. Essa maldade também foi calculada para combinações entre um setor e seus vizinhos. Em cada iteração, uma rota escolhida aleatoriamente do pior setor foi trocada por uma rota de outro setor escolhido aleatoriamente. Isso mostrou algum tipo de convergência, mas o resultado não foi utilizável (ou seja, o estado resultante continha setores com cores duplas ou triplas).
Então, abordei o problema do lado oposto e comecei com uma parede vazia. Dessa vez, todas as cores tinham uma concentração que se deteriorava de um setor para os setores adjacentes. A concentração de cores semelhantes também foi aumentada, ou seja, uma rota vermelha aumentou a concentração de laranja em um setor e nas proximidades. Uma fonte aleatória ponderada de cores (o balde) me deu a próxima cor para a parede, que foi colocada no setor com a menor concentração dessa cor. Se uma concentração estava acima de um certo limite, a cor não era adicionada (mas recolocada no balde). Isso foi um sucesso parcial porque o estado do resultado não continha cores duplas - mas alguns setores estavam vazios ou continham apenas uma cor.
Então: Qual poderia ser um algoritmo apropriado para resolver esse problema, dadas as regras acima? Felizmente, adicionarei mais informações quando necessário.
Editar 1 - Mais informações:
- meu caso de teste tem 15 setores,
- cada setor deve conter 4 rotas
- o verdadeiro ginásio tem 3 edifícios com uma média de 50 setores cada
- alguns setores estão dispostos em torno de pilares, outros são conectados por telhados
- temos cerca de 10 cores diferentes de espera
- a altura dos setores varia entre 6 (seção do iniciante) e 20 metros (13 verticais + 7 no teto); portanto, consomem diferentes quantidades de porões. No entanto, a média é de cerca de 12 e isso pode ser considerado constante.
- existe uma quantidade limitada de cada cor, as quantidades não são iguais
- algumas cores são mais fáceis, outras mais difíceis (ou seja, podemos criar uma rota amarela de qualquer dificuldade, enquanto a criação de uma rota laranja muito fácil para as crianças será quase impossível)
- alguns setores são "mais fáceis", portanto cores fáceis devem ir para lá (isso é opcional, nossos criadores de rotas podem tornar as coisas mais difíceis ou fáceis em uma ampla variedade).
- podemos dizer com segurança quais cores combinam bem em um setor ou setores vizinhos e quais combinações não combinam. Há algumas surpresas, como branco e preto (combinação ruim): ambos ficam cinza enquanto borracha (sapatos) ou giz (mãos) são deixados neles.
- algumas cores de espera são combinações como violeta / branco (em um padrão listrado).
Edit 2: Algumas Perguntas sobre Algoritmos Genéticos
Agora baixei e compilei o ParadisEO e até recebi meu IDE (estou usando o Code :: Blocks) para compilar o exemplo do QuickStart. O ParadisEO oferece algoritmos genéticos com um único objetivo, bem como AG de múltiplos objetivos. A GertVdE sugeriu calcular a adequação de cada setor e maximizar a soma das adequações de todos os setores como um único objetivo. Eu também poderia maximizar a adequação de cada setor com uma AG de múltiplos objetivos? Seriam cerca de 50 objetivos.
Além disso, estou lutando com a definição de uma função de crossover sensível. Como a quantidade máxima de cada cor é fixa, o cruzamento pode levar a estados ilegais. Se eu permitir mais do que a quantidade máxima fornecida anteriormente, o padrão geral poderá convergir para uma repetição de combinações menos "difíceis", onde as cores problemáticas foram jogadas fora. Por outro lado, também posso descartar cores em excesso até atingir o máximo, tornando a função de crossover não conservadora.
(Eu sou completamente novo em algoritmos genéticos)
fonte
Respostas:
Eu resolveria o problema declarado acima usando uma abordagem de algoritmo genético. Você codifica cada solução como um vetor de números inteiros:
Em seguida, você define uma função de adequação como uma soma ponderada da diferença mínima de cores em cada setor e a quantidade de rotas em um setor (a quantidade de zeros no vetor). Você pode usar a estrutura Paradiseo ou Inspyred para uma implementação de Algoritmos Genéticos.
fonte
Aqui está uma breve visão geral da minha implementação atual, tentarei seguir os conceitos e não entrar em detalhes da linguagem. Eu usei o ParadisEO Framework, que é uma biblioteca de modelos C ++ para algoritmos genéticos, e acrescentei algumas vantagens aqui e ali.
Escalada segurar cores
As cores de espera são armazenadas em um arquivo XML como um par de nome e quantidade de cores. Os valores encontrados em um arquivo são somados e normalizados. Isso permite expressar uma quantidade como uma contagem total de rotas que podem ser definidas com essa cor ou como uma porcentagem. Um ID é atribuído a cada cor, começando com 1. Zero é reservado para uma rota "vazia".
Sanções por combinação de cores
Algumas cores não combinam bem em um setor ou em setores adjacentes. Toda combinação de cores não tão boas é descrita pelos dois nomes de cores (como no arquivo XML anterior, veja acima) e por uma "maldade" arbitrária. Internamente, os valores de defeito são armazenados em uma matriz indexada por IDs de cores.
A parede
The Wall é uma classe que deriva da classe de representação do genoma do ParadisEO, para que o ParadisEO possa manipulá-lo e avaliá-lo, mas mais algumas funcionalidades são adicionadas. Cada gene representa uma cor de rota por ID (incluindo zero ou vazio). Os setores são representados por um par de índices para os genes, para que cada setor tenha um começo e um fim. Eu usei os iteradores para os genes primeiro, mas o objeto Wall deve ser copiável construtível, o que invalidaria os iteradores sem trabalho adicional. Atualmente, todos os setores têm 4 rotas, mas que serão configuráveis no futuro.
A parede também possui um balde de cores. Esse intervalo contém um contador para cada cor, distribuído conforme descrito no arquivo XML de cores. As contagens de cores somam o número total de rotas na parede. Uma cor pode ser escolhida no balde, diminuindo o contador, e também pode ser recolocada, aumentando o contador.
Uma cor só pode ser adicionada a um setor se o setor ainda não a contiver (o setor deve permanecer "legal" quando a cor é adicionada).
Operador de Avaliação
O operador de avaliação resume todos os valores de maldade em um setor usando a matriz de maldade descrita acima. O valor de cada setor é armazenado no vetor fitness (que também faz parte da classe Wall), portanto, este é um GA de múltiplos objetivos. Eu posso mudar isso se for necessário.
Operador de crossover de dois pontos
O operador de cruzamento pega dois pais, cria uma cópia de cada um (os descendentes) e executa um cruzamento de dois pontos recombinando setores inteiros . A vantagem disso é que os setores permanecem legais (sem cores duplas). A desvantagem de qualquer operação de cruzamento (para esse problema) é que os filhos resultantes podem conter cores em excesso se as cores estiverem agrupadas nos pais. Foi adicionada uma função de reparo que remove rotas em excesso (cor zero) aleatoriamente. Os filhos, portanto, têm menos rotas do que os pais do reparo mudaram os filhos.
Mutação 1: adicionar rota
A possível redução de rotas nas crias é explicada por um operador "adicionar rota". Ele pega uma cor do balde da parede e a adiciona em algum lugar. Se essa não é uma operação legal, ela não faz nada (às vezes não há lugar legal para a cor restante).
Mutação 2: Troca aleatória
Duas rotas aleatórias de dois setores aleatórios são trocadas. Esse par de trocas é gerado até que os setores resultantes sejam legais e, em seguida, a troca é executada.
Mutação 3: Mudança
Um número de setores é deslocado um lugar para a esquerda.
Agora estou sem tempo, mas posso adicionar mais informações mais tarde. Especialmente, a avaliação é bastante simples e os componentes foram programados como prova de conceito. O GA de fato otimiza o Wall em certa medida, mas os resultados não estão prontos para uso real. Tenho certeza de que isso melhorará quando conversar com os criadores de rotas e mais regras de avaliação estiverem disponíveis. As imagens também aparecerão quando estiverem disponíveis.
fonte