Algoritmo de combinação de programação de mentoria

Question

Há algum tempo, tentei ajudar um sujeito a desenvolver um programa de mentoria matchmaking, respondendo a um questionário para combinar mentores e pupilos de acordo com suas respectivas habilidades e horários disponíveis:

Um mentor é definido com:

• Identificador (e-mail, nome completo)
• X intervalos de tempo (UTC)
• Quantos pupilos o mentor pode cuidar, semanalmente
• N habilidades que o mentor pode ensinar

e um pupilo com:

• Identificador (e-mail, nome completo)
• Y intervalos de tempo (UTC)
• Com quantos mentores o pupilo pode interagir, semanalmente
• Habilidades M que o pupilo está disposto a aprender

Heurísticas:

• Um mentor deve ter as habilidades necessárias para fornecer uma orientação adequada
• Os horários dos mentores e pupilos devem se sobrepor (assim que tudo for convertido para UTC)
• Se houver uma situação de impasse => ordene os mentores e pupilos de acordo com o tempo de envio do questionário

Eu verifiquei algumas perguntas, mas ainda não tenho certeza de qual algoritmo se encaixa no cenário que acabei de descrever acima, alguma ideia?

• Algoritmo para mapear usuários para uma programação com base na disponibilidade de tempo
• Algoritmo para programar turnos
• Algoritmo de programação do calendário?

EDIT 1 - Autor do projeto

Posso explicar o algoritmo que foi usado para desenvolver o projeto. Estamos apenas procurando maneiras interessantes de melhorar os pares que ele gera. Antes de entrar nas explicações, devo dizer que para uma dada habilidade, fornecemos um valor heurístico para mostrar o quão rara ela é. Dados dois jogos iguais, aquele com a habilidade mais rara deve, portanto, vencer.

A partir da infraestrutura, analisamos os dados extraídos do questionário em duas listas separadas, onde cada lista representa pupilos e mentores. A partir daí, tentamos encontrar primeiro todos os pares potenciais . Fazemos isso encontrando cada pupilo que corresponda às habilidades de um mentor e tenha uma programação coincidente.

Para criar pares únicos, estamos usando conjuntos como caches para os pupilos e mentores que foram combinados. À medida que percorremos o espaço de busca, se um mentor está na capacidade ou um pupilo já foi correspondido, eles vão para um dos caches e continuamos verificando todas as correspondências potenciais.

A única maneira de quantificarmos as correspondências é fornecendo uma heurística para a raridade da habilidade e, de certa forma, fornecemos uma heurística para o cronograma sobreposto. O que quero dizer com isso é que recorremos a possíveis correspondências com o número de horas de sobreposição que temos. Tecnicamente, as correspondências são verificadas da maioria das horas de sobreposição para menos. Então, buscamos as habilidades mais raras, enquanto pupilos e mentores não são compatíveis.

Pelo que vejo na resposta, não estamos muito longe.

Answer 1

Existem metodologias para lidar com problemas que não sabemos resolver. Vamos tentar.

Em primeiro lugar, vamos apresentar uma função de utilidade. A ideia é que devemos ser capazes de alimentar uma possível solução para o problema para a função de utilidade, e ela retornará um valor que nos diz uma estimativa de quão boa é essa solução.

Teremos um agente tentando maximizar essa função de utilidade. Se você quiser imaginar isso como se estivéssemos projetando um videogame para as pessoas fazerem isso, isso também funciona.

Criar uma boa função de utilidade envolve entender o espaço do problema. Então, vamos ver ...

Um mentor deve ter as habilidades necessárias para fornecer uma orientação adequada

A solução terá pares de mentores e pupilos. O pupilo tem uma lista de habilidades, e o mentor também. Para cada habilidade que se sobrepõe em um par, conceda alguns pontos. A função de utilidade é a soma dos pontos.

Os horários dos mentores e pupilos devem se sobrepor (assim que tudo for convertido para UTC)

Da mesma forma, eles têm intervalos de tempo. Quando eles se sobrepõem, conceda alguns pontos.

Como isso interage com a regra acima? As habilidades do mentor são inúteis se o mentor não puder interagir com o pupilo. Da mesma forma - pelo menos neste modelo - o mentor que não tem nenhuma das habilidades que o pupilo está procurando, não serve, mesmo que seu tempo se sobreponha.

Assim, sugiro conceder pontos proporcionais ao tempo sobreposto vezes as habilidades sobrepostas.

Se houver uma situação de impasse => ordene os mentores e pupilos de acordo com o tempo de envio do questionário

Em vez de uma função de utilidade, podemos trabalhar com utilidade relativa. Ou seja, teríamos uma função que compara soluções e diz qual é a melhor. Ainda precisamos nos preocupar em garantir que o pedido não resulte em um loop estranho ou semelhante. Essa regra de deadlock pode ser usada com isso.

Ainda assim, acho que existe uma solução mais simples: some pontos para um bom tempo de envio do questionário. Porém, quanto mais tempo é pior, certo? Eu sugiro evitar penalidades, então não faça isso removendo pontos. Adicione o inverso multiplicativo do tempo, por algum fator q. Não sei o que é o fator q, mas deve ser pequeno, visto que se destina a desatar soluções, deve resultar em frações de um ponto.

Assim, nossa função de utilidade ficaria assim:

f(p) = p.overlapping_skills * p.overlapping_time + q/p.total_q_time
utility(s) = sum i=1->n {f(s[n])}

Agora, podemos projetar nosso agente. Lembre-se de que não devemos exceder o número máximo de mentores por mentor, nem o número máximo de mentores por mentor. Assim, cada vez que escolhemos um par, ele deve ser validado. Além disso, toda vez que escolhemos um mentor ou pupilo (ou os envolvemos), temos a chance de priorizar pelo tempo do questionário.

Podemos seguir uma abordagem determinística: faça um loop sobre cada pupilo, para cada um escolha o mentor que daria mais utilidade e atribua-o. Faça um loop até que nenhum mentor possa aceitar mais pupilos, ou nenhum pupilo possa aceitar mais mentores.

Podemos tentar algo semelhante ao recozimento simulado: começando sem nenhum par designado, escolha um mentor e um pupilo aleatoriamente. Se o mentor estiver lotado, estamos considerando substituir o pupilo que contribui com menos utilidade. Da mesma forma, se o pupilo estiver lotado, estamos considerando substituir o mentor que contribui com menos utilidade. Veja se a atribuição resulta em mais utilidade do que antes, se der, mantenha-a, caso contrário, descarte-a. Faça um loop até concluir uma grande quantidade de iterações (ou uma grande quantidade de iterações sem melhorias).

Podemos tentar um algoritmo genético. A lista de pares é o genoma. Podemos começar com uma população aleatória, cruzá-los, transformá-los, selecionar o melhor e repetir. Até que tenhamos feito uma grande quantidade de iterações, ou não vejamos nenhuma melhoria de uma geração para a próxima.

Podemos tentar encontrar o caminho. Use o inverso da utilidade como heurística da distância. Quanto melhor a solução, melhor será sua utilidade. E assim, a heurística será menor. O que significa que está mais perto de "a solução". Implemente A * ou algoritmo localizador de caminho heurístico semelhante, em que os nós são a solução e os vértices são cada emparelhamento possível que você pode fazer. Este gráfico tem um grande fator de ramificação, portanto, você terá problemas de memória com A *, considere Iterative Deepening A * ou Memory bounded A *.

Ah, e quem disse que esses agentes têm que ser artificiais? Você poderia começar pedindo às pessoas que façam isso manualmente, ver quais padrões emergem do que fazem, automatizá-los e repetir. Você acabaria com um sistema especialista que pode resolver a maioria dos casos automaticamente e deixar os humanos lidarem com os outliers.

Olha, podemos lançar vários tipos diferentes de agentes para esse problema. Passamos de "temos esse problema com essas restrições" para "aqui está um monte de coisas que podemos tentar resolver". Você pode até imaginar chegando com um grande conjunto de dados e testando qual funciona melhor.

Além disso, provavelmente podemos melhorar a função de utilidade. Eu lembro a você que chegar a uma boa função de utilidade é saber o espaço do problema. E você sabe disso melhor do que eu. Por exemplo: devemos preferir que um mentor interaja com o pupilo, um de cada vez? Devemos preferir apenas um mentor por habilidade que o pupilo deseja? Devemos preferir mais ou menos mentores por pupilo? Ou devemos preferir mais ou menos pupilos por mentor? Eu não sei.