aoo_v2_notes.md

AAO V2 NOTES

In this Notebook

Local Search
2 Opt Swap
3 Opt Swap
Variable Neighborhood Search
Ant Colony
Simulated Annealing
Genetic Algorithm
Greedy Randomized Adaptive Search Procedure
Traveling Salesman Problem
Vehicle Routing Problem (TSP Extended)
Uncapacitated Facility Location Problem
Cutting and packing problem
Knapsack problem (Bagpack)

Simulated Annealing

current_solution ← generate_initial_solution()
best_solution ← current_solution
temperature ← initial_temperature

WHILE temperature > final_temperature:
  neighbor ← generate_neighbor(current_solution)  // small random change
  Δcost ← cost(neighbor) - cost(current_solution)

  IF Δcost < 0 THEN:
    current_solution ← neighbor  // accept better solution
  ELSE IF random(0,1) < exp(-Δcost / temperature) THEN:
    current_solution ← neighbor  // accept worse solution probabilistically
  END IF

  IF cost(current_solution) < cost(best_solution) THEN:
    best_solution ← current_solution
  END IF

  temperature ← update_temperature(temperature)  // e.g., temperature *= alpha
END WHILE

RETURN best_solution

Variable Neighborhood Search (VNS)

initial_solution ← generate a feasible solution
best_solution ← initial_solution

WHILE iteration < max_iterations:
  k ← 1

  WHILE k ≤ k_max:
    shaken_solution ← shake(best_solution, neighborhood_structure_k)  // diversification
    local_optimum ← localSearch(shaken_solution)  // intensification

    IF local_optimum is better than best_solution THEN:
      best_solution ← local_optimum
      k ← 1  // restart with first neighborhood
    ELSE:
      k ← k + 1  // move to next neighborhood
    END IF
  END WHILE

  iteration += 1
END WHILE

RETURN best_solution

Genetic Algorithm

initial_population ← generate a diverse set of feasible solutions
reference_set ← select best and diverse solutions from initial_population

WHILE iteration < max_iterations:
  subsets ← select parent pairs from reference_set // e.g., tournament or roulette selection
  new_solutions ← empty set

  FOR each subset in subsets:
    offspring ← crossover(subset)  // structured mix of parents
    mutated_offspring ← mutate(offspring)  // random variation
    improved_solution ← localSearch(mutated_offspring)  // optional refinement
    
    new_solutions.push(improved_solution)
  END FOR

  FOR each solution in new_solutions do:
    IF solution is better than worst in reference_set OR adds diversity then:
      reference_set.add(solution)
    END IF
  END FOR

  iteration += 1
END WHILE

RETURN reference_set

Tabu Search

current_solution ← initial feasible solution
best_solution ← current_solution
tabu_list ← empty list

WHILE iteration < max_iterations:
  neighborhood ← generate all neighbor solutions of current_solution
  best_candidate ← null
  best_candidate_cost ← ∞
  
  FOR each neighbor in neighborhood:
    move ← operation from current_solution to neighbor (e.g., open/close/swap a facility)
    IF move not in tabu_list or neighbor is better than best_solution then
      IF cost(neighbor) < best_candidate_cost then
        best_candidate ← neighbor
        best_candidate_move ← move
        best_candidate_cost ← cost(neighbor)
      END IF
    END IF
  END IF

  current_solution ← best_candidate

  IF cost(current_solution) < cost(best_solution) then
    best_solution ← current_solution
  END IF

  PUSH best_candidate_move to tabu_list
  
  IF size(tabu_list) > tabu_tenure then
    tabu_list.shift() // remove oldest move from tabu_list
  END IF

  iteration += 1
END WHILE

RETURN best_solution

Scatter Search

// The set object can only store unique values

initial_population ← generate a diverse set of feasible solutions
reference_set ← select best and diverse solutions from initial_population

WHILE iteration < max_iterations:
  subsets ← generate all or a subset of pairs/combinations from reference_set
  new_solutions ← empty set
  
  FOR each subset in subsets:
    combined_colution ← combine(subset)  // typically linear combination or structured mix (crossover)
    improved_solution ← localSearch(combined_colution) or 2optSwap(combined_colution)
    
    new_solutions.push(improved_solution)
  END FOR

  FOR each solution in new_solutions do:
    IF solution is better than worst in reference_set OR adds diversity then:
      reference_set = solution
    END IF
  END FOR

  iteration += 1
END WHILE

RETURN reference_set

Considere o Problema de Localização de Instalações sem Restrições de Capacidade, bem conhecido por UFLP (Uncapacitated Facility Location Problem)

a. Descreva a vizinhança clássica, mais utilizada em algoritmos heurísticos para o UFLP.

A vizinhança clássica no UFLP envolve modificar o conjunto de instalações abertas. As operações mais comuns são:

1. open: adicionar uma instalação atualmente fechada;
2. clone: remover uma instalação atualmente aberta;
3. swap: fechar uma instalação aberta e abrir uma fechada simultaneamente.

Cada movimento gera uma nova solução ao redistribuir os clientes às instalações disponíveis, recalculando o custo total. Essa vizinhança é eficiente por permitir ajustes pontuais na solução com impacto direto no custo.

b. Descreva sucintamente uma possível aplicação de Tabu Search ao UFLP.

O Uncapacitated Facility Location Problem (UFLP) consiste em decidir quais instalações (facilities) abrir para atender a uma série de clientes, minimizando o custo total de abertura das instalações e transporte, sem restrição de capacidade.

Uma abordagem possível é iniciar com uma solução viável, por exemplo, atribuindo cada cliente à instalação mais próxima (nearest neighbor), e selecionando um subconjunto de instalações iniciais abertas.

Em seguida, aplica-se o Tabu Search para explorar a vizinhança da solução atual através de movimentos como: open, close, swap.

Para evitar ciclos, movimentos inversos recentes são colocados em uma lista tabu. O critérios de aspiração pode permitir a reversão de movimentos tabu se melhorarem significativamente a solução.

Considere o Problema do Caixeiro Viajante (TSP – Traveling Salesman Problem)

a. Descreva a vizinhança clássica, mais utilizada em algoritmos heurísticos para o TSP.

A vizinhança clássica mais utilizada no TSP é baseada na operação de 2-opt.

1. Selecionar dois arcos (i, i+1) e (j, j+1) da rota atual;
2. Remover esses arcos e reconectar as extremidades invertendo a subrota entre os pontos i+1 e j.

Essa modificação gera uma nova solução ao reordenar parte do percurso, com potencial para reduzir a distância total. Outras vizinhanças populares incluem 3-opt (remoção e reconexão de 3 arcos) e swap de vértices.

b. Descreva sucintamente uma possível aplicação de Tabu Search ao TSP.

O TSP (Traveling Salesman Problem) é um problema clássico de otimização combinatória que consiste em: dado um conjunto de 𝑛 cidades e as distâncias entre cada par de cidades, o objetivo é encontrar a permutação das cidades que minimize o custo total do percurso fechado (circuito Hamiltoniano).

O Tabu Search aplica-se ao TSP partindo de uma solução inicial (nearest neighbor) e explorando sua vizinhança com movimentos como 2-opt (troca de dois arcos para eliminar cruzamentos).

A cada iteração:

1. Gera-se um conjunto de soluções vizinhas;
2. Escolhe-se a melhor, mesmo que não melhore o custo, desde que o movimento realizado (ex.: troca entre dois pares de vértices) não esteja na lista tabu;
3. A lista tabu armazena movimentos recentes por um número fixo de iterações, evitando retrocessos (ciclos);
4. Um critério de aspiração permite aceitar um movimento tabu se ele resultar em uma solução melhor que a melhor conhecida.