1 // METSlib source file - model.hh -*- C++ -*-
2 //
3 /*
4 * Software License Agreement (BSD License)
5 *
6 * Copyright (c) 2006-2012, Mirko Maischberger <mirko.maischberger@gmail.com>
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer in the documentation and/or other materials provided
18 * with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
23 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
24 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
26 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
28 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
30 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
31 * POSSIBILITY OF SUCH DAMAGE.
32 *
33 */
34
35 #ifndef METS_MODEL_HH_
36 #define METS_MODEL_HH_
37
38 namespace mets {
39
40 /// @brief Type of the objective/cost function.
41 ///
42 /// You should be able to change this to "int" for your uses
43 /// to improve performance if it suffice, no guarantee.
44 ///
45 using gol_type = double;
46
47 /// @brief Exception risen when some algorithm has no more moves to
48 /// make.
49 class no_moves_error
50 : public std::runtime_error
51 {
52 public:
no_moves_error()53 no_moves_error()
54 : std::runtime_error("There are no more available moves.") {}
no_moves_error(const std::string message)55 no_moves_error(const std::string message)
56 : std::runtime_error(message) {}
57 };
58
59 /// @brief A sequence function object useful as an STL generator.
60 ///
61 /// Returns start, start+1, ...
62 ///
63 class sequence
64 {
65 public:
66 /// @brief A sequence class starting at start.
sequence(int start=0)67 sequence(int start = 0)
68 : value_m(start)
69 { }
70 /// @brief Subscript operator. Each call increments the value of
71 /// the sequence.
operator ()()72 int operator()()
73 { return value_m++; }
74 protected:
75 int value_m;
76 };
77
78 /// @brief An interface for prototype objects.
79 class clonable {
80 public:
81 virtual
~clonable()82 ~clonable() {};
83 virtual clonable*
84 clone() const = 0;
85 };
86
87 /// @brief An interface for hashable objects.
88 class hashable {
89 public:
90 virtual
~hashable()91 ~hashable() {};
92 virtual std::size_t
93 hash() const = 0;
94 };
95
96 /// @brief An interface for copyable objects.
97 class copyable {
98 public:
99 virtual
~copyable()100 ~copyable() {};
101 virtual void
102 copy_from(const copyable&) = 0;
103 };
104
105 /// @brief An interface for printable objects.
106 class printable {
107 public:
108 virtual
~printable()109 ~printable() {}
110 virtual void
print(std::ostream &) const111 print(std::ostream& /*os*/) const { };
112 };
113
114 /// @defgroup model Model
115 /// @{
116
117 /// @brief interface of a feasible solution space to be searched
118 /// with tabu search.
119 ///
120 /// Note that "feasible" is not intended w.r.t. the constraint of
121 /// the problem but only regarding the space we want the local
122 /// search to explore. From time to time allowing solutions to
123 /// explore unfeasible regions is non only allowed, but encouraged
124 /// to improve tabu search performances. In those cases the
125 /// objective function should probably account for unfeasibility
126 /// with a penalty term.
127 ///
128 /// This is the most generic solution type and is useful only if you
129 /// implement your own solution recorder and
130 /// max-noimprove. Otherwise you might want to derive from an
131 /// evaluable_solution or from a permutation_problem class,
132 /// depending on your problem type.
133 ///
134 class feasible_solution
135 {
136 public:
137 /// @brief Virtual dtor.
138 virtual
~feasible_solution()139 ~feasible_solution()
140 { }
141
142 };
143
144
145 /// @brief A copyable and evaluable solution implementation,
146 ///
147 /// All you need, if you implement your own mets::solution_recorder,
148 /// is to derive from the almost empty
149 /// mets::feasible_solution. However, if you want to use the
150 /// provided mets::best_ever_recorder you need to derive from this
151 /// class (that also defines an interface to copy and evaluate a
152 /// solution).
153 ///
154 /// @see mets::best_ever_recorder
155 class evaluable_solution : public feasible_solution,
156 public copyable
157 {
158 public:
159 /// @brief Cost function to be minimized.
160 ///
161 /// The cost function is the target that the search algorithm
162 /// tries to minimize.
163 ///
164 /// You must implement this for your problem.
165 ///
166 virtual gol_type
167 cost_function() const = 0;
168 };
169
170 /// @brief An abstract permutation problem.
171 ///
172 /// The permutation problem provides a skeleton to rapidly prototype
173 /// permutation problems (such as Assignment problem, Quadratic AP,
174 /// TSP, and so on). The skeleton holds a pi_m variable that, at
175 /// each step, contains a permutation of the numbers in [0..n-1].
176 ///
177 /// A few operators are provided to randomly choose a solution, to
178 /// perturbate a solution with some random swaps and to simply swap
179 /// two items in the list.
180 ///
181 /// @see mets::swap_elements
182 class permutation_problem: public evaluable_solution
183 {
184 public:
185
186 /// @brief Unimplemented.
187 permutation_problem();
188
189 /// @brief Inizialize pi_m = {0, 1, 2, ..., n-1}.
permutation_problem(int n)190 permutation_problem(int n) : pi_m(n), cost_m(0.0)
191 { std::generate(pi_m.begin(), pi_m.end(), sequence(0)); }
192
193 /// @brief Copy from another permutation problem, if you introduce
194 /// new member variables remember to override this and to call
195 /// permutation_problem::copy_from in the overriding code.
196 ///
197 /// @param other the problem to copy from
198 void copy_from(const copyable& other);
199
200 /// @brief: Compute cost of the whole solution.
201 ///
202 /// You will need to override this one.
203 virtual gol_type
204 compute_cost() const = 0;
205
206 /// @brief: Evaluate a swap.
207 ///
208 /// Implement this method to evaluate the change in the cost
209 /// function after the swap (without actually modifying the
210 /// solution). The method should return the difference in cost
211 /// between the current position and the position after the swap
212 /// (negative if decreasing and positive otherwise).
213 ///
214 /// To obtain maximal performance from the algorithm it is
215 /// essential, whenever possible, to only compute the cost update
216 /// and not the whole cost function.
217 virtual gol_type
218 evaluate_swap(int i, int j) const = 0;
219
220 /// @brief The size of the problem.
221 /// Do not override unless you know what you are doing.
222 std::size_t
size() const223 size() const
224 { return pi_m.size(); }
225
226 /// @brief Returns the cost of the current solution. The default
227 /// implementation provided returns the protected
228 /// mets::permutation_problem::cost_m member variable. Do not
229 /// override unless you know what you are doing.
cost_function() const230 gol_type cost_function() const
231 { return cost_m; }
232
233 /// @brief Updates the cost with the one computed by the subclass.
234 /// Do not override unless you know what you are doing.
235 void
update_cost()236 update_cost()
237 { cost_m = compute_cost(); }
238
239 /// @brief: Apply a swap and update the cost.
240 /// Do not override unless you know what you are doing.
241 void
apply_swap(int i,int j)242 apply_swap(int i, int j)
243 { cost_m += evaluate_swap(i,j); std::swap(pi_m[i], pi_m[j]); }
244
245
246 protected:
247 std::vector<int> pi_m;
248 gol_type cost_m;
249 template<typename random_generator>
250 friend void random_shuffle(permutation_problem& p, random_generator& rng);
251 };
252
253
254 /// @brief Shuffle a permutation problem (generates a random starting point).
255 ///
256 /// @see mets::permutation_problem
257 template<typename random_generator>
random_shuffle(permutation_problem & p,random_generator & rng)258 void random_shuffle(permutation_problem& p, random_generator& rng)
259 {
260 #if defined (METSLIB_TR1_BOOST)
261 boost::uniform_int<std::size_t> unigen;
262 boost::variate_generator<random_generator&,
263 boost::uniform_int<std::size_t> >gen(rng, unigen);
264 #elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
265 std::uniform_int<std::size_t> unigen;
266 std::variate_generator<random_generator&,
267 std::uniform_int<std::size_t> >gen(rng, unigen);
268 #else
269 std::tr1::uniform_int<std::size_t> unigen;
270 std::tr1::variate_generator<random_generator&,
271 std::tr1::uniform_int<std::size_t> >gen(rng, unigen);
272 #endif
273 std::shuffle(p.pi_m.begin(), p.pi_m.end(), gen);
274 p.update_cost();
275 }
276
277 /// @brief Perturbate a problem with n swap moves.
278 ///
279 /// @see mets::permutation_problem
280 template<typename random_generator>
perturbate(permutation_problem & p,unsigned int n,random_generator & rng)281 void perturbate(permutation_problem& p, unsigned int n, random_generator& rng)
282 {
283 #if defined (METSLIB_TR1_BOOST)
284 boost::uniform_int<> int_range;
285 #elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
286 std::uniform_int<> int_range;
287 #else
288 std::tr1::uniform_int<> int_range;
289 #endif
290 for(unsigned int ii=0; ii!=n;++ii)
291 {
292 int p1 = int_range(rng, p.size());
293 int p2 = int_range(rng, p.size());
294 while(p1 == p2)
295 p2 = int_range(rng, p.size());
296 p.apply_swap(p1, p2);
297 }
298 }
299
300 /// @brief Move to be operated on a feasible solution.
301 ///
302 /// You must implement this (one or more types are allowed) for your
303 /// problem.
304 ///
305 /// You must provide an apply as well as an evaluate method.
306 ///
307 /// NOTE: this interface changed from 0.4.x to 0.5.x. The change was
308 /// needed to provide a more general interface.
309 class move
310 {
311 public:
312
313 virtual
~move()314 ~move()
315 { };
316
317 ///
318 /// @brief Evaluate the cost after the move.
319 ///
320 /// What if we make this move? Local searches can be speed up by a
321 /// substantial amount if we are able to efficiently evaluate the
322 /// cost of the neighboring solutions without actually changing
323 /// the solution.
324 virtual gol_type
325 evaluate(const feasible_solution& sol) const = 0;
326
327 ///
328 /// @brief Operates this move on sol.
329 ///
330 /// This should actually change the solution.
331 virtual void
332 apply(feasible_solution& sol) const = 0;
333
334
335 };
336
337 /// @brief A Mana Move is a move that can be automatically made tabu
338 /// by the mets::simple_tabu_list.
339 ///
340 /// If you implement this class you can use the
341 /// mets::simple_tabu_list as a ready to use tabu list.
342 ///
343 /// You must implement a clone() method, provide an hash funciton
344 /// and provide a operator==() method that is responsible to find if
345 /// a move is equal to another.
346 ///
347 /// NOTE: If the desired behaviour is to declare tabu the *opposite*
348 /// of the last made move you can achieve that behavioud override
349 /// the opposite_of() method as well.
350 ///
351 class mana_move :
352 public move,
353 public clonable,
354 public hashable
355 {
356 public:
357
358 /// @brief Create and return a new move that is the reverse of
359 /// this one
360 ///
361 /// By default this just calls "clone". If this method is not
362 /// overridden the mets::simple_tabu_list declares tabu the last
363 /// made move. Reimplementing this method it is possibile to
364 /// actually declare as tabu the opposite of the last made move
365 /// (if we moved a to b we can declare tabu moving b to a).
366 virtual mana_move*
opposite_of() const367 opposite_of() const
368 { return static_cast<mana_move*>(clone()); }
369
370 /// @brief Tell if this move equals another w.r.t. the tabu list
371 /// management (for mets::simple_tabu_list)
372 virtual bool
373 operator==(const mana_move& other) const = 0;
374
375 };
376
377 template<typename rndgen> class swap_neighborhood; // fw decl
378
379 /// @brief A mets::mana_move that swaps two elements in a
380 /// mets::permutation_problem.
381 ///
382 /// Each instance swaps two specific objects.
383 ///
384 /// @see mets::permutation_problem, mets::mana_move
385 ///
386 class swap_elements : public mets::mana_move
387 {
388 public:
389
390 /// @brief A move that swaps from and to.
swap_elements(int from,int to)391 swap_elements(int from, int to)
392 : p1(std::min(from,to)), p2(std::max(from,to))
393 { }
394
395 /// @brief Virtual method that applies the move on a point
396 gol_type
evaluate(const mets::feasible_solution & s) const397 evaluate(const mets::feasible_solution& s) const
398 { const permutation_problem& sol =
399 static_cast<const permutation_problem&>(s);
400 return sol.cost_function() + sol.evaluate_swap(p1, p2); }
401
402 /// @brief Virtual method that applies the move on a point
403 void
apply(mets::feasible_solution & s) const404 apply(mets::feasible_solution& s) const
405 { permutation_problem& sol = static_cast<permutation_problem&>(s);
406 sol.apply_swap(p1, p2); }
407
408 /// @brief Clones this move (so that the tabu list can store it)
409 clonable*
clone() const410 clone() const
411 { return new swap_elements(p1, p2); }
412
413 /// @brief An hash function used by the tabu list (the hash value is
414 /// used to insert the move in an hash set).
415 std::size_t
hash() const416 hash() const
417 { return (p1)<<16^(p2); }
418
419 /// @brief Comparison operator used to tell if this move is equal to
420 /// a move in the simple tabu list move set.
421 bool
422 operator==(const mets::mana_move& o) const;
423
424 /// @brief Modify this swap move.
change(int from,int to)425 void change(int from, int to)
426 { p1 = std::min(from,to); p2 = std::max(from,to); }
427
428 protected:
429 int p1; ///< the first element to swap
430 int p2; ///< the second element to swap
431
432 template <typename>
433 friend class swap_neighborhood;
434 };
435
436 /// @brief A mets::mana_move that swaps a subsequence of elements in
437 /// a mets::permutation_problem.
438 ///
439 /// @see mets::permutation_problem, mets::mana_move
440 ///
441 class invert_subsequence : public mets::mana_move
442 {
443 public:
444
445 /// @brief A move that swaps from and to.
invert_subsequence(int from,int to)446 invert_subsequence(int from, int to)
447 : p1(from), p2(to)
448 { }
449
450 /// @brief Virtual method that applies the move on a point
451 gol_type
452 evaluate(const mets::feasible_solution& s) const;
453
454 /// @brief Virtual method that applies the move on a point
455 void
456 apply(mets::feasible_solution& s) const;
457
458 clonable*
clone() const459 clone() const
460 { return new invert_subsequence(p1, p2); }
461
462 /// @brief An hash function used by the tabu list (the hash value is
463 /// used to insert the move in an hash set).
464 std::size_t
hash() const465 hash() const
466 { return (p1)<<16^(p2); }
467
468 /// @brief Comparison operator used to tell if this move is equal to
469 /// a move in the tabu list.
470 bool
471 operator==(const mets::mana_move& o) const;
472
change(int from,int to)473 void change(int from, int to)
474 { p1 = from; p2 = to; }
475
476 protected:
477 int p1; ///< the first element to swap
478 int p2; ///< the second element to swap
479
480 // template <typename>
481 // friend class invert_full_neighborhood;
482 };
483
484 /// @brief A neighborhood generator.
485 ///
486 /// This is a sample implementation of the neighborhood exploration
487 /// concept. You can still derive from this class and implement the
488 /// refresh method, but, since version 0.5.x you don't need to.
489 ///
490 /// To implement your own move manager you should simply adhere to
491 /// the following concept:
492 ///
493 /// provide an iterator, and size_type types, a begin() and end()
494 /// method returning iterators to a move collection. The switch to a
495 /// template based move_manager was made so that you can use any
496 /// iterator type that you want. This allows, between other things,
497 /// to implement intelligent iterators that dynamically return
498 /// moves.
499 ///
500 /// The move manager can represent both Variable and Constant
501 /// Neighborhoods.
502 ///
503 /// To make a constant neighborhood put moves in the moves_m queue
504 /// in the constructor and implement an empty <code>void
505 /// refresh(feasible_solution&)</code> method.
506 ///
507 class move_manager
508 {
509 public:
510 ///
511 /// @brief Initialize the move manager with an empty list of moves
move_manager()512 move_manager()
513 : moves_m()
514 { }
515
516 /// @brief Virtual destructor
~move_manager()517 virtual ~move_manager()
518 { }
519
520 /// @brief Selects a different set of moves at each iteration.
521 virtual void
522 refresh(mets::feasible_solution& s) = 0;
523
524 /// @brief Iterator type to iterate over moves of the neighborhood
525 using iterator = std::deque<move *>::iterator;
526
527 /// @brief Size type
528 using size_type = std::deque<move *>::size_type;
529
530 /// @brief Begin iterator of available moves queue.
begin()531 iterator begin()
532 { return moves_m.begin(); }
533
534 /// @brief End iterator of available moves queue.
end()535 iterator end()
536 { return moves_m.end(); }
537
538 /// @brief Size of the neighborhood.
size() const539 size_type size() const
540 { return moves_m.size(); }
541
542 protected:
543 std::deque<move*> moves_m; ///< The moves queue
544 move_manager(const move_manager&);
545 };
546
547
548 /// @brief Generates a stochastic subset of the neighborhood.
549 #if defined (METSLIB_TR1_BOOST)
550 template<typename random_generator = boost::minstd_rand0>
551 #elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
552 template<typename random_generator = std::minstd_rand0>
553 #else
554 template<typename random_generator = std::tr1::minstd_rand0>
555 #endif
556 class swap_neighborhood : public mets::move_manager
557 {
558 public:
559 /// @brief A neighborhood exploration strategy for mets::swap_elements.
560 ///
561 /// This strategy selects *moves* random swaps
562 ///
563 /// @param r a random number generator (e.g. an instance of
564 /// std::tr1::minstd_rand0 or std::tr1::mt19936)
565 ///
566 /// @param moves the number of swaps to add to the exploration
567 ///
568 swap_neighborhood(random_generator& r,
569 unsigned int moves);
570
571 /// @brief Dtor.
572 ~swap_neighborhood();
573
574 /// @brief Selects a different set of moves at each iteration.
575 void refresh(mets::feasible_solution& s);
576
577 protected:
578 random_generator& rng;
579
580 #if defined (METSLIB_TR1_BOOST)
581 boost::uniform_int<> int_range;
582 #elif defined (METSLIB_HAVE_UNORDERED_MAP) && !defined (METSLIB_TR1_MIXED_NAMESPACE)
583 std::uniform_int<> int_range;
584 #else
585 std::tr1::uniform_int<> int_range;
586 #endif
587 unsigned int n;
588
589 void randomize_move(swap_elements& m, unsigned int size);
590 };
591
592 //________________________________________________________________________
593 template<typename random_generator>
594 mets::swap_neighborhood< random_generator
swap_neighborhood(random_generator & r,unsigned int moves)595 >::swap_neighborhood(random_generator& r,
596 unsigned int moves)
597 : mets::move_manager(), rng(r), int_range(0), n(moves)
598 {
599 // n simple moves
600 for(unsigned int ii = 0; ii != n; ++ii)
601 moves_m.push_back(new swap_elements(0,0));
602 }
603
604 template<typename random_generator>
~swap_neighborhood()605 mets::swap_neighborhood<random_generator>::~swap_neighborhood()
606 {
607 // delete all moves
608 for(iterator ii = begin(); ii != end(); ++ii)
609 delete (*ii);
610 }
611
612 template<typename random_generator>
613 void
refresh(mets::feasible_solution & s)614 mets::swap_neighborhood<random_generator>::refresh(mets::feasible_solution& s)
615 {
616 permutation_problem& sol = dynamic_cast<permutation_problem&>(s);
617 iterator ii = begin();
618
619 // the first n are simple qap_moveS
620 for(unsigned int cnt = 0; cnt != n; ++cnt)
621 {
622 swap_elements* m = static_cast<swap_elements*>(*ii);
623 randomize_move(*m, sol.size());
624 ++ii;
625 }
626
627 }
628
629 template<typename random_generator>
630 void
631 mets::swap_neighborhood<random_generator
randomize_move(swap_elements & m,unsigned int size)632 >::randomize_move(swap_elements& m, unsigned int size)
633 {
634 int p1 = int_range(rng, size);
635 int p2 = int_range(rng, size);
636 while(p1 == p2)
637 p2 = int_range(rng, size);
638 // we are friend, so we know how to handle the nuts&bolts of
639 // swap_elements
640 m.p1 = std::min(p1,p2);
641 m.p2 = std::max(p1,p2);
642 }
643
644 /// @brief Generates a the full swap neighborhood.
645 class swap_full_neighborhood : public mets::move_manager
646 {
647 public:
648 /// @brief A neighborhood exploration strategy for mets::swap_elements.
649 ///
650 /// This strategy selects *moves* random swaps.
651 ///
652 /// @param size the size of the problem
swap_full_neighborhood(int size)653 swap_full_neighborhood(int size) : move_manager()
654 {
655 for(int ii(0); ii!=size-1; ++ii)
656 for(int jj(ii+1); jj!=size; ++jj)
657 moves_m.push_back(new swap_elements(ii,jj));
658 }
659
660 /// @brief Dtor.
~swap_full_neighborhood()661 ~swap_full_neighborhood() {
662 for(move_manager::iterator it = moves_m.begin();
663 it != moves_m.end(); ++it)
664 delete *it;
665 }
666
667 /// @brief Use the same set set of moves at each iteration.
refresh(mets::feasible_solution &)668 void refresh(mets::feasible_solution& /*s*/) { }
669
670 };
671
672
673 /// @brief Generates a the full subsequence inversion neighborhood.
674 class invert_full_neighborhood : public mets::move_manager
675 {
676 public:
invert_full_neighborhood(int size)677 invert_full_neighborhood(int size) : move_manager()
678 {
679 for(int ii(0); ii!=size; ++ii)
680 for(int jj(0); jj!=size; ++jj)
681 if(ii != jj)
682 moves_m.push_back(new invert_subsequence(ii,jj));
683 }
684
685 /// @brief Dtor.
~invert_full_neighborhood()686 ~invert_full_neighborhood() {
687 for(std::deque<move*>::iterator it = moves_m.begin();
688 it != moves_m.end(); ++it)
689 delete *it;
690 }
691
692 /// @brief This is a static neighborhood
693 void
refresh(mets::feasible_solution &)694 refresh(mets::feasible_solution& /*s*/)
695 { }
696
697 };
698
699 /// @}
700
701 /// @brief Functor class to allow hash_set of moves (used by tabu list)
702 class mana_move_hash
703 {
704 public:
operator ()(mana_move const * mov) const705 std::size_t operator()(mana_move const* mov) const
706 {return mov->hash();}
707 };
708
709 /// @brief Functor class to allow hash_set of moves (used by tabu list)
710 template<typename Tp>
711 struct dereferenced_equal_to
712 {
operator ()mets::dereferenced_equal_to713 bool operator()(const Tp l,
714 const Tp r) const
715 { return l->operator==(*r); }
716 };
717
718 }
719
720 //________________________________________________________________________
721 inline void
copy_from(const mets::copyable & other)722 mets::permutation_problem::copy_from(const mets::copyable& other)
723 {
724 const mets::permutation_problem& o =
725 dynamic_cast<const mets::permutation_problem&>(other);
726 pi_m = o.pi_m;
727 cost_m = o.cost_m;
728 }
729
730 //________________________________________________________________________
731 inline bool
operator ==(const mets::mana_move & o) const732 mets::swap_elements::operator==(const mets::mana_move& o) const
733 {
734 try {
735 const mets::swap_elements& other =
736 dynamic_cast<const mets::swap_elements&>(o);
737 return (this->p1 == other.p1 && this->p2 == other.p2);
738 } catch (std::bad_cast& e) {
739 return false;
740 }
741 }
742
743 //________________________________________________________________________
744
745 inline void
apply(mets::feasible_solution & s) const746 mets::invert_subsequence::apply(mets::feasible_solution& s) const
747 {
748 mets::permutation_problem& sol =
749 static_cast<mets::permutation_problem&>(s);
750 int size = static_cast<int>(sol.size());
751 int top = p1 < p2 ? (p2-p1+1) : (size+p2-p1+1);
752 for(int ii(0); ii!=top/2; ++ii)
753 {
754 int from = (p1+ii)%size;
755 int to = (size+p2-ii)%size;
756 assert(from >= 0 && from < size);
757 assert(to >= 0 && to < size);
758 sol.apply_swap(from, to);
759 }
760 }
761
762 inline mets::gol_type
evaluate(const mets::feasible_solution & s) const763 mets::invert_subsequence::evaluate(const mets::feasible_solution& s) const
764 {
765 const mets::permutation_problem& sol =
766 static_cast<const mets::permutation_problem&>(s);
767 int size = static_cast<int>(sol.size());
768 int top = p1 < p2 ? (p2-p1+1) : (size+p2-p1+1);
769 mets::gol_type eval = 0.0;
770 for(int ii(0); ii!=top/2; ++ii)
771 {
772 int from = (p1+ii)%size;
773 int to = (size+p2-ii)%size;
774 assert(from >= 0 && from < size);
775 assert(to >= 0 && to < size);
776 eval += sol.evaluate_swap(from, to);
777 }
778 return eval;
779 }
780
781 inline bool
operator ==(const mets::mana_move & o) const782 mets::invert_subsequence::operator==(const mets::mana_move& o) const
783 {
784 try {
785 const mets::invert_subsequence& other =
786 dynamic_cast<const mets::invert_subsequence&>(o);
787 return (this->p1 == other.p1 && this->p2 == other.p2);
788 } catch (std::bad_cast& e) {
789 return false;
790 }
791 }
792
793 #endif
794