Algoritmo de agendamento especial (expansão de padrão)

Question

Pergunta
Você acha que vale a pena testar algoritmos genéticos para o problema abaixo ou irei atingir problemas de mínimos locais?

Acho que talvez alguns aspectos do problema sejam ótimos para uma configuração de estilo gerador / função de fitness.(Se você estragou um projeto semelhante, eu adoraria ouvir sua opinião e não fazer algo semelhante)

Obrigado por qualquer dica sobre como estruturar as coisas e acertar.

O problema
Estou procurando um bom algoritmo de agendamento para usar no seguinte problema do mundo real.

Tenho uma sequência com 15 slots assim (Os dígitos podem variar de 0 a 20):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

(E existem no total 10 sequências diferentes deste tipo)

Cada sequência precisa se expandir em um array, onde cada slot pode ocupar 1 posição.

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

As restrições na matriz são que:

• [em linha, ou seja,horizontalmente] O número de unidades colocadas deve ser 11 ou 111
• [linha] A distância entre duas sequências de 1 precisa ser no mínimo 00
• A soma de cada coluna deve corresponder ao array original.
• O número de linhas na matriz deve ser otimizado.

A matriz então precisa alocar uma das 4 matrizes diferentes, que podem ter um número diferente de linhas:

A, B, C, D

A, B, C e D são departamentos do mundo real.A carga precisa ser colocada razoavelmente justa durante um período de 10 dias, para não interferir nas outras metas do departamento.

Cada matriz é comparada com a expansão de 10 sequências originais diferentes, então você tem:

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

Certos locais podem ser reservados (não tenho certeza se devo torná-lo apenas reservado/não reservado ou baseado em função). Os lugares reservados poderão ser reuniões e outros eventos

A soma de cada linha (por exemplo, todos os A) deve ser aproximadamente a mesma dentro de 2%.ou sejasum(A1 a A10) deve ser aproximadamente igual a (B1 a B10) etc.

O número de linhas pode variar, então você tem, por exemplo:

A1:5 linhas A2:5 linhas A3:1 linha, onde essa única linha poderia ser, por exemplo:

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

etc..

Subproblema*

Ficarei muito feliz em resolver apenas parte do problema.Por exemplo, ser capaz de inserir:

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

E obtenha uma matriz apropriada de sequências com 1 e 0 minimizados no número de linhas seguindo as restrições acima.

Answer 1

Tentativa de solução de subproblema

Bem, aqui está uma ideia.Esta solução não se baseia na utilização de um algoritmo genético, mas algumas ideias poderiam ser utilizadas para ir nessa direção.

Vetores básicos

Primeiro de tudo, você deve gerar o que considero vetores de base.Por exemplo, se sua sequência tivesse 3 números em vez de 15, os vetores de base seriam:

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

Qualquer solução para comprimento de sequência 3 seria uma combinação linear desses três vetores usando apenas números inteiros positivos.Em outras palavras, a solução geral seria

a*v1 + b*v2 + c*v3

onde a, b e c são inteiros positivos.Para a sequência [1 2 1], a solução é v1 = 1, v2 = 1, v3 = 0.O que você deseja fazer primeiro é encontrar todos os vetores de base possíveis de comprimento 15.Pelos meus cálculos aproximados, acho que existem algo entre 300-400 vetores básicos de comprimento 15.Posso dar algumas dicas para gerá-los, se você quiser.

Encontrando soluções

Agora, o que você quer fazer é classificar esses vetores de base por suas somas/magnitudes.Então, ao procurar sua solução, você começa com os vetores de base que possuem as maiores somas.Começamos com os vetores que possuem as maiores somas porque levam a um menor total de linhas.Também temos um array, veccoefs, que contém uma entrada para o coeficiente linear de cada vetor base.No início da busca pela solução, todos os veccoefs são 0.

Então pegamos o primeiro vetor base (aquele com a maior soma/magnitude) e subtraímos esse vetor da sequência até criarmos um resultado insolúvel (com 0 1 0 nele, por exemplo) ou qualquer um dos números no resultado é negativo.Armazenamos o número de vezes que subtraímos o vetor em veccoefs.Usamos o resultado após subtrair o vetor base da sequência como a sequência do próximo vetor base.Se restarem apenas zeros no resultado, paramos o loop.

Não tenho certeza da eficiência/precisão desse método, mas pode pelo menos lhe dar algumas idéias.

Outras soluções possíveis

Outra ideia para resolver isso é usar os vetores de base e formar o problema como um problema de otimização/mínimos quadrados.Você forma uma matriz dos vetores de base de modo que o problema básico será minimizar Sum[(Ax - b)^2] onde A é a matriz dos vetores de base, b é a sequência de entrada e x são os coeficientes do vetor de base.No entanto, você também deseja minimizar o número de linhas, para poder adicionar um termo como x^T*x à função de minimização onde x^T é a transposta de x.A parte difícil, na minha opinião, é encontrar termos diferenciáveis ​​para adicionar que encorajem coeficientes de vetores inteiros.Se você conseguir pensar em uma maneira de fazer isso, então a otimização pode muito bem ser uma boa maneira de fazer isso.

Além disso, você pode considerar uma solução Monte Carlo do tipo Metropolis.Você escolheria aleatoriamente se deseja adicionar um vetor, remover um vetor ou substituir um vetor em cada etapa.O vetor a ser adicionado/removido/substituído seria escolhido aleatoriamente.A probabilidade desta mudança ser aceita seria uma razão entre as adequações das soluções antes e depois da mudança.A adequação pode ser igual à diferença entre a solução atual e a sequência, elevada ao quadrado e somada, menos o número de linhas/vetores de base envolvidos na solução.Você precisaria inserir constantes apropriadas para vários termos para tentar obter uma taxa de aceitação em torno de 50%.Duvido que isso funcione muito bem, mas achei que você ainda deveria considerar isso ao procurar possíveis soluções.

Answer 2

O GA pode ser aplicado a esse problema, mas não será uma tarefa de 5 minutos. Você precisa montar várias coisas, sem saber qual implementação de cada uma delas é melhor.
Então:

1. Representação da solução - Como você representará a possível solução? Usar Matrix parece ser mais direto. Usar a coleta de matrizes unidimensionais também é possível. Mas você tem algumas restrições, então talvez vale a pena considerar o Supergene?
2. Você deve usar os operadores de mutação/crossover adequados para determinada representação de genes.
3. Como você aplicará restrições de soluções? Destruindo aqueles que não são adequados? E se eles contiverem informações valiosas? Talvez deixe -os permanecer na população, mas acrescentar um pouco de penalidade à aptidão, para que eles contribuam para os filhos, mas não entrarão nas próximas gerações?

De qualquer forma, acho que o GA pode ser aplicado a esse problema. Vale a pena? Normalmente, o GA não é o melhor algoritmo, mas são algoritmos decentes se outros falharem. Eu iria com a GA, só porque seria muito divertido, mas procuraria uma solução alternativa (apenas por precaução).

PS Insight Personal: Eu estava resolvendo o problema do N Queens, para 70 <n <100 (placa nxn, n queens). O algoritmo estava funcionando bem para o mais baixo (talvez estivesse tentando toda a combinação?), Mas com n nesse intervalo, não consegui encontrar uma solução adequada. O fitness saltou rapidamente para cerca de 90% do Max, mas no final sempre havia duas rainhas conflitantes. Mas foi uma implementação muito ingênua.