Tendo o cromossoma, e mais concretamente a lista de DronePaths, conseguimos assim criar o ficheiro .out com a solução, precisamos de uma função que faça isto

O SA pode ter diferentes funções de cooling que modificam a forma como a temperatura baixa. Temos estas roubada dos amegos:

def exponential_cooling(self, T0, t):
        return T0 * 0.8 ** t
    
    def log_cooling(self, T0, t):
        return T0 / (1 + log(1 + t))

    def linear_cooling(self, T0, t):
        return T0 / (1 + t)
    
    def quadratic_cooling(self, T0, t):
        return T0 / (1 + t ** 2)

e podemos ir procurar mais, isto vai dar jeito para encher o relatório/apresentação

Usar apenas mutações que causam poucas penalizações (trocar drone, crossover*) se a nova solução tiver penalizações, faz mutação de novo.

Vai assim aceitar cromossomas de score mais baixo, mas não com penaizações

Link do amigo para SA: https://machinelearningmastery.com/simulated-annealing-from-scratch-in-python/
Link do amigo para HC: https://machinelearningmastery.com/stochastic-hill-climbing-in-python-from-scratch/

Temos 2 opções para aqui.

• Criar um algoritmo que siga uma heurística e que devolva mais do que 1 solução. Neste caso iria criar uma solução válida e nos últimos passos modificava-a para criar as outras soluções
• Criar uma solução e aplicar mutações nessa solução para criar soluções válidas. Não estou muto inclinado para este lado, visto que as mutações só dão cócó

Pegar no algoritmo Scala 1/2 e escolher as soluções que não têm o melhor score para gerar as outras soluções

• Pensar em adaptação de initial_solution para ser mais rápido a criar as populações
• Multithreading

Necessário implementar o algoritmo roubado do outro grupo de amiguinhos e da primeira solução do kaggle, esta é a versão simplificada

Coisas a melhorar neste algortitmo:
- Em Shipment, Drone pode ficar com espaço livre, já que só tem em conta 1 order (e.g. ultimo item da order)
- Só aceita caminhos _ -> WH -> Order.

-------------------------------------
Greedy:
Termina quando não há mais orders ou não é possível fazer shipments (falta de produtos maybe)
  Para cada Drone:
    BestShipment()


BestShipment():

Para Cada Order que não esteja completa:
  Faz para cada warehouse:
    new Shipment()
Escolhe shipment com melhor score
shipment.execute()


Shipment():

Para cada produto da order:
  busca quantidade disponivel de produto
  append a lista
criada lista de produtos que esse WH tem da Order
Da lista de produtos criada, vai adicionando a drone até não caber mais, so mais pesado para o mais leve (possível aplicar knapsack aqui)
Score()


Score():
percent = carga_drone / carga_order 
turns   = Soma das 2 distâncias mais 1's por pick up's e drop's
score   = percent / turns

Shipment.execute():
- remove produtos do armazém
- remove produtos da orders
- atualiza posição do drone
- adiciona shipment ao drone
- adiciona turnos ao drone

Acho que os shipments não precisam de ser uma class necessáriamente, podem ser uma estrutura de dados apenas usada lá no meio. Se implementarmos a parte 2 é que pode dar jeito passar para classe

• pyplot
• mathplotlib

4 DataSets

• mother_of_all_warehouses
• busy_day
• redundancy
• demo (maybe not)

A apontar:

• Tempo de execução
• número de soluções (?)

Algoritmos a testar

• initial_solution (naive_solution)
• greedy_solution
• SA
  • Ver com números de iterações diferentes
  • Ver com números de tentativas diferentes
  • Cooling Function
• HC
  • Só ver com iterações
• GA
  • Tamanhos de Populações diferentes
  • Números de iterações
  • Mutation rate

Para além da criação de populações referenciada em #8, temos de tratar dos passos restantes:

• Population (#8)
• Crossover
• Mutations

Não esquecer o nosso amigo dos tutoriais: https://machinelearningmastery.com/simple-genetic-algorithm-from-scratch-in-python/

• Rejeitar soluções com valores muito baixos
• tentar combinações de mutações diferentes
• GRAFICOS

https://we.tl/t-ZNiItSSglW

A partir do código acima comentado podemos fazer a segunda parte do algoritmo.
O tempo de execução aumenta substancialmente, mas as soluções terão sempre melhor pontuação que o algoritmo simplificado

Falar comigo para ter a explicação do algoritmo antes de tentar entender sozinho pelos comentários (aproveitar tempo)

Kaggle:

• https://www.kaggle.com/lyxthe/1st-place-solution
• https://github.com/miraan/google-hash-code-qualification-round

Info de Scala:

• :: & ::: - https://www.scala-lang.org/api/current/scala/collection/immutable/List.html#:::[B%3E:A](prefix:List[B]):List[B]
• head e tail - https://www.tutorialspoint.com/scala/scala_lists.htm
• flatmap - https://www.geeksforgeeks.org/scala-flatmap-method/
• foldleft - https://www.credera.com/insights/mastering-scala-folding