faif
HillClimbing.hpp
1 #ifndef HILL_CLIMBING_HPP
2 #define HILL_CLIMBING_HPP
3 
4 #if defined(_MSC_VER) && (_MSC_VER >= 1400)
5 //msvc10.0 warnings for concepts
6 #pragma warning(disable:4510)
7 #pragma warning(disable:4610)
8 #endif
9 
10 #include <boost/concept_check.hpp>
11 
12 #include "Node.hpp"
13 #include "Space.hpp"
14 
15 namespace faif {
16  namespace search {
17 
18  /** \brief the policy class for HillClimbing, check all neighbours */
19  template<typename Space> struct NextNodeCheckAll {
20 
21  typedef typename Space::Individual Individual;
22  typedef typename Individual::PNode PNode;
23 
24  /** \brief next node as the better neighbour */
25  static PNode nextNode(const PNode& initial) {
26  //the fitness is required
27  BOOST_CONCEPT_ASSERT((SpaceConcept<Space>));
28  //the methods to create tree-like structures are required
29  BOOST_CONCEPT_ASSERT((NodeWithChildrenConcept<Individual>));
30 
31  typedef typename Space::Fitness Fitness;
32  Fitness best_fitness = Space::fitness(*initial);
33 
34  PNode best_neighbour;
35 
36  typedef typename Individual::Children Children;
37  Children ch = initial->getChildren();
38  for( typename Children::const_iterator it = ch.begin(); it != ch.end(); ++it ) {
39  const PNode neighbour = *it;
40  Fitness neighbour_fitness = Space::fitness(*neighbour);
41  if (best_fitness < neighbour_fitness) {
42  best_neighbour = neighbour;
43  best_fitness = neighbour_fitness;
44  }
45  }
46  return best_neighbour;
47  }
48  };
49 
50  /** \brief the hill climbing algorithm. Search the neighbour for the better solution
51  */
52  template<typename Space,
53  template <typename> class NextNodeStrategy = NextNodeCheckAll >
54  class HillClimbing {
55  public:
56  typedef typename Space::Individual Individual;
57  typedef typename Individual::PNode PNode;
58  typedef typename Space::Fitness Fitness;
59 
60  HillClimbing() { }
61 
62  /** \brief the hill climbing algorithm - until stop repeat searching all adjacent nodes. */
63  PNode solve(const PNode& initial) {
64  //the fitness is required
65  BOOST_CONCEPT_ASSERT((SpaceConcept<Space>));
66  //the methods to create tree-like structures are required
67  BOOST_CONCEPT_ASSERT((NodeWithChildrenConcept<Individual>));
68 
69  typename Individual::PNode current = initial;
70  typename Individual::PNode best_neighbour = current;
71  do {
72  current = best_neighbour;
73  best_neighbour = NextNodeStrategy<Space>::nextNode(current);
74  }
75  while( best_neighbour != 0L );
76  return current;
77  }
78  };
79 
80  } //namespace search
81 } //namespace faif
82 
83 
84 #endif // HILL_CLIMBING_HPP
Definition: Chain.h:17
the concept for node with children
Definition: Node.hpp:44
PNode solve(const PNode &initial)
the hill climbing algorithm - until stop repeat searching all adjacent nodes.
Definition: HillClimbing.hpp:63
the hill climbing algorithm. Search the neighbour for the better solution
Definition: HillClimbing.hpp:54
static PNode nextNode(const PNode &initial)
next node as the better neighbour
Definition: HillClimbing.hpp:25
the typedef-s for space, where the fitness is defined as double
Definition: Space.hpp:25
the concept for space with fitness
Definition: Space.hpp:33
the policy class for HillClimbing, check all neighbours
Definition: HillClimbing.hpp:19