You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
Alexis Pereda caf2a692f9
thesis version
2 years ago
bench/graspels thesis version 2 years ago
celero thesis version 2 years ago
data thesis version 2 years ago
examples thesis version 2 years ago
inc thesis version 2 years ago
results thesis version 2 years ago
rtbenchmarks thesis version 2 years ago
scripts thesis version 2 years ago
src thesis version 2 years ago
.gitignore thesis version 2 years ago
CMakeLists.txt thesis version 2 years ago
LICENSE thesis version 2 years ago
README.md thesis version 2 years ago

README.md

About

ROSA (in french "Recherche Opérationnelle grâce aux Squelettes Algorithmiques", i.e. Operational Research with Algorithmic Skeletons). It relies on alsk for the algorithmic skeletons. This is part of the work done for my Ph.D. thesis.

Brief

The main algorithm implemented and presented is GRASP×ELS. This metaheuristic can be represented as below:

When implemented as an algorithmic skeleton, its representation becomes this tree:

Obtained using the following source code.

For the internal ELS:

template<typename InitLS, typename Mutate, typename LS, typename InnerSelect, typename OuterSelect>
using SkelElsStruct =
S<alsk::Serial,
  InitLS,           // LSI
  S<IterSel,
    S<FarmSel,
      S<Serial,
        Mutate, LS  // M then LS
      >,
      InnerSelect   // Sel3
    >,
    OuterSelect     // Sel2
  >
>;

template<typename Solution>
using SkelElsLinks =
L<Serial, R<1>(Solution const&),
  Solution(P<0>),
  L<IterSel, Solution(R<0> const&),
    L<FarmSel, Solution(Solution),
      L<Serial, R<1>(P<0>),
        Solution(P<0>, RNG&),
        Solution(R<0> const&)
      >,
      Solution(Solution const&, Solution const&)
    >,
    Solution(Solution const&, Solution const&)
  >
>;

template<
  typename Solution,
  typename InitLS, typename Mutate, typename LS, typename InnerSelect, typename OuterSelect
>
using SkelEls = BuildSkeleton<SkelElsStruct, SkelElsLinks>::skeleton<
  Pack<InitLS, Mutate, LS, InnerSelect, OuterSelect>,
  Pack<Solution>
>;

For the GRASP:

template<typename CH, typename LS, typename Select>
using SkelGraspStructure =
S<FarmSel,
  S<Serial, CH, LS>,
  Select              // Sel1
>;

template<typename Problem, typename Solution>
using SkelGraspLinks =
L<FarmSel, Solution(Problem const&),
  L<Serial, R<1>(P<0>),
    Solution(P<0>, RNG),
    Solution(R<0>)
  >,
  Solution(Solution, Solution)
>;

template<typename Problem, typename Solution, typename CH, typename LS, typename Select>
using SkelGrasp = BuildSkeleton<SkelGraspStructure, SkelGraspLinks>::skeleton<
  Pack<CH, LS, Select>,
  Pack<Problem, Solution>
>;

Then the GRASP×ELS can be constructed:

// All arguments are defined types or functions, see full source code
using ELS = SkelEls<
  tsp::Solution,
  Descent,
  Move2Opt, Descent,
  FN(selectMin)
>;

using GRASPxELS = SkelGrasp<
  tsp::Problem, tsp::Solution,
  RGreedy<tsp::Solution>, ELS,
  FN(selectMin)
>;

Performances

The measures shown below are from using the GRASPxELS algorithm to solve an instance of TSP with 194 nodes. Various execution policies are used:

  • "hw_seq": handwritten sequential implementation;
  • "hw_par": handwritten parallel implementation;
  • "sk_seq": skeleton without parallelisation;
  • "sk_firstlevel": skeleton with parallelisation of the first level;
  • "sk_staticpool": skeleton with parallelisation using a thread pool with static task distribution;
  • "sk_dynamicpool": skeleton with parallelisation using a classical thread pool with dynamic task distribution;
  • "sk_thread": skeleton with parallelisation using dynamically created threads.

For an execution with only one allotted core, meaning that there is no parallelisation done, we obtain the data below. Note that this data set do not use the legend shown above. All subsequent images use it.

For parallel executions, measures give the following data.

With 24 iterations for the outmost parallel loop:

With only 4 iterations for the outmost parallel loop:

Organisation

Main directories:

  • src: sources;
  • src/rosa: the library sources;
  • rtbenchmarks: scripts for compile-time/run-time benchmarking;
  • results: results presented in the thesis, obtained using mentioned scripts and codes.

Usage

To produce the Makefile and build the project:

mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make