1 /*
2 * Open BEAGLE
3 * Copyright (C) 2001-2007 by Christian Gagne and Marc Parizeau
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18 *
19 * Contact:
20 * Laboratoire de Vision et Systemes Numeriques
21 * Departement de genie electrique et de genie informatique
22 * Universite Laval, Quebec, Canada, G1K 7P4
23 * http://vision.gel.ulaval.ca
24 *
25 */
26
27 /*!
28 * \file TSPEvalOp.cpp
29 * \brief Implementation of the class TSPEvalOp.
30 * \author Christian Gagne
31 * \author Marc Parizeau
32 * $Revision: 1.5.2.1 $
33 * $Date: 2007/05/09 01:51:23 $
34 */
35
36 #include "beagle/GA.hpp"
37 #include "TSPEvalOp.hpp"
38
39 #include <cmath>
40
41 #define BEAGLE_TSP_PROBLEMSIZE 25
42
43
44 using namespace Beagle;
45
46 /*!
47 * \brief Construct the individual evaluation operator for the TSP problem.
48 */
TSPEvalOp()49 TSPEvalOp::TSPEvalOp() :
50 EvaluationOp("TSPEvalOp")
51 { }
52
53
54 /*!
55 * \brief Evaluate the fitness of the given individual.
56 * \param inIndividual Current individual to evaluate.
57 * \param ioContext Evolutionary context.
58 * \return Handle to the fitness value of the individual.
59 */
evaluate(Individual & inIndividual,Context & ioContext)60 Fitness::Handle TSPEvalOp::evaluate(Individual& inIndividual, Context& ioContext)
61 {
62 Beagle_AssertM(inIndividual.size() == 1);
63 GA::IntegerVector::Handle lPath = castHandleT<GA::IntegerVector>(inIndividual[0]);
64 const unsigned int lRootIndex = mDistancesMatrix->getRows()-1;
65 double lTripDistance = (*mDistancesMatrix)(lRootIndex,(*lPath)[0]);
66 for(unsigned int i=1; i<lPath->size(); ++i) {
67 lTripDistance += (*mDistancesMatrix)((*lPath)[i-1],(*lPath)[i]);
68 }
69 lTripDistance += (*mDistancesMatrix)((*lPath)[lPath->size()-1],lRootIndex);
70 return new FitnessSimpleMin(float(lTripDistance));
71 }
72
73
74 /*!
75 * \brief Initialize the TSP evaluation operator.
76 * \param ioSystem Evolutionary system.
77 */
initialize(Beagle::System & ioSystem)78 void TSPEvalOp::initialize(Beagle::System& ioSystem)
79 {
80 Beagle::EvaluationOp::initialize(ioSystem);
81
82 if(ioSystem.getRegister().isRegistered("ts.graph.distances")) {
83 mDistancesMatrix = castHandleT<Matrix>(ioSystem.getRegister().getEntry("ts.graph.distances"));
84 } else {
85 mDistancesMatrix = new Matrix(0,0);
86 Beagle::string lLongDescrip("Distances between graph's nodes (the towns by analogy). ");
87 lLongDescrip += "If the matrix value is not specified, it will be randomly generated ";
88 lLongDescrip += "at the initialization time.";
89 Register::Description lDescription(
90 "TSP distances matrix",
91 "Matrix",
92 "",
93 lLongDescrip
94 );
95 ioSystem.getRegister().addEntry("ts.graph.distances", mDistancesMatrix, lDescription);
96 }
97
98 if(ioSystem.getRegister().isRegistered("ga.init.vectorsize")) {
99 mIntVectorSize = castHandleT<UInt>(ioSystem.getRegister()["ga.init.vectorsize"]);
100 } else {
101 mIntVectorSize = new UInt(0);
102 Register::Description lDescription(
103 "Initial integer vectors sizes",
104 "UInt",
105 "0",
106 "Integer vector size of initialized individuals."
107 );
108 ioSystem.getRegister().addEntry("ga.init.vectorsize", mIntVectorSize, lDescription);
109 }
110 }
111
112
113 /*!
114 * \brief Post-initialize the TSP evaluation operator.
115 * \param ioSystem Evolutionary system.
116 */
postInit(Beagle::System & ioSystem)117 void TSPEvalOp::postInit(Beagle::System& ioSystem)
118 {
119 Beagle::EvaluationOp::postInit(ioSystem);
120
121 if((mDistancesMatrix->getRows()==0) || (mDistancesMatrix->getCols()==0)) {
122 // Generating randomly the TSP graph to solve.
123 std::vector< std::pair<double,double> > lNodePosition(BEAGLE_TSP_PROBLEMSIZE);
124 for(unsigned int i=0; i<BEAGLE_TSP_PROBLEMSIZE; ++i) {
125 lNodePosition[i].first = ioSystem.getRandomizer().rollUniform(0.0, 10.0);
126 lNodePosition[i].second = ioSystem.getRandomizer().rollUniform(0.0, 10.0);
127 }
128 // Computing distance (simply Euclidean distances) between the nodes.
129 mDistancesMatrix->resize(BEAGLE_TSP_PROBLEMSIZE,BEAGLE_TSP_PROBLEMSIZE);
130 for(unsigned int i=0; i<BEAGLE_TSP_PROBLEMSIZE; ++i) {
131 for(unsigned int j=(i+1); j<BEAGLE_TSP_PROBLEMSIZE; ++j) {
132 double lDistance = ((lNodePosition[j].first-lNodePosition[i].first) *
133 (lNodePosition[j].first-lNodePosition[i].first)) +
134 ((lNodePosition[j].second-lNodePosition[i].second) *
135 (lNodePosition[j].second-lNodePosition[i].second));
136 lDistance = std::sqrt(lDistance);
137 lDistance += ioSystem.getRandomizer().rollGaussian(0.0, 0.5); // Add some noise
138 (*mDistancesMatrix)(i,j) = (*mDistancesMatrix)(j,i) = lDistance;
139 }
140 }
141 for(unsigned int i=0; i<BEAGLE_TSP_PROBLEMSIZE; ++i) (*mDistancesMatrix)(i,i) = 0.0;
142 }
143 else if(mDistancesMatrix->getRows() != mDistancesMatrix->getCols()) {
144 std::ostringstream lOSS;
145 lOSS << "Distances matrix of TSP evaluation operator (registered as ";
146 lOSS << "'ts.graph.distances' parameter) must be square!";
147 throw Beagle_RunTimeExceptionM(lOSS.str().c_str());
148 }
149
150 mIntVectorSize->getWrappedValue() = (mDistancesMatrix->getRows()-1);
151
152 Beagle_LogInfoM(
153 ioSystem.getLogger(),
154 "evaluation", "TSPEvalOp",
155 Beagle::string("Distances matrix used in TSP problem: ")+mDistancesMatrix->serialize()
156 );
157 }
158
159
160