Develop a first prototype of the variable neighborhood search (VNS) algorithm

[ajnebro]

The first step in the development of a VNS algorithm to solve MSA problems is to start with a version able of dealing with simple binary (e.g., OneMax) problems.

TO-DO

• [x] Initialize algorithm class
  • [x] VNS()
    • [x] shake()
    • [x] generateNeighbourhoods()
    • [x] generateInitialSolution()
    • [x] stoppingCondition
    • [x] fitness()
• [x] Write examples
• [x] Initialize tests class
  • [x] Define tests

[olegbrz]

Trajectory-based metaheuristics

A trajectory-based metaheuristic iteratively improves a single solution and forms a search trajectory in the solution space. Examples of trajectory-based metaheuristics include Simulated Annealing (SA), Tabu Search (TS), Iterated Local Search (ILS) and Guided Local Search (GLS)

Source: A new cooperative framework for parallel trajectory-based metaheuristics

Introduction to VNS

Variable neighborhood search (VNS) is a recent metaheuristic for solving combinatorial and global optimization problems whose basic idea is systematic change of neighborhood within a local search. In this survey paper we present basic rules of VNS and some of its extensions. Moreover, applications are briefly summarized. They comprise heuristic solution of a variety of optimization problems, ways to accelerate exact algorithms and to analyze heuristic solution processes, as well as computer-assisted discovery of conjectures in graph theory.

Source: VARIABLE NEIGHBORHOOD SEARCH Pierre Hansen, Nenad Mladenović

Pseudocode

def VNS():
    define_neighbourhood_strutures N_k (k=1,...,k_max)
    generateInitialSolution s ∈ S
    while (!stoppingCondition):
        k = 1
        while (k <= k_max):
            s' = shake(s), s' ∈ N_k(s)
            if (fitness(s'') < fitness(s)):
                s = s''
                k = 1
            else:
                k = k + 1

TO-DO

• [ ] VNS()
  • [ ] shake()
  • [x] generateInitialSolution()
  • [x] stoppingCondition
  • [x] fitness()