00001 #include <cmath>
00002 #include <iostream>
00003 #include <string>
00004 #include <fstream>
00005 #include <ecf/ECF.h>
00006 #include "TSPEvalOp.h"
00007
00008
00009 void TSPEvalOp::registerParameters(StateP state)
00010 {
00011 state->getRegistry()->registerEntry("tsp.infile", (voidP) (new std::string), ECF::STRING);
00012 }
00013
00014
00015 bool TSPEvalOp::initialize(StateP state)
00016 {
00017 if(!state->getRegistry()->isModified("tsp.infile")) {
00018 state->getLogger()->log(1, "Error: no input file defined for TSP! (parameter 'tsp.infile'");
00019 return false;
00020 }
00021
00022 voidP sptr = state->getRegistry()->getEntry("tsp.infile");
00023 std::string filePath = *((std::string*) sptr.get());
00024
00025 std::ifstream iFile(filePath.c_str());
00026 std::string line;
00027 if(!iFile.is_open()) {
00028 state->getLogger()->log(1, "Error: can't open input file " + filePath);
00029 return false;
00030 }
00031
00032
00033 do {
00034 getline(iFile,line);
00035 }while(line.find("DIMENSION",0) == std::string::npos);
00036 std::stringstream ss(line.substr(line.find(":") + 1));
00037 ss >> dimension;
00038
00039
00040 state->getRegistry()->modifyEntry("Permutation.size", (voidP) new uint(dimension));
00041
00042
00043 state->getPopulation()->initialize(state);
00044
00045
00046 do {
00047 getline(iFile,line);
00048 }while(line.find("EDGE_WEIGHT_TYPE",0) == std::string::npos);
00049 std::stringstream ss_type(line.substr(line.find(":") + 1));
00050 string dataType;
00051 ss_type >> dataType;
00052
00053 if(dataType == "EUC_2D") {
00054
00055
00056 do {
00057 getline(iFile,line);
00058 }while(line.find("NODE_COORD_SECTION",0) == std::string::npos);
00059
00060 coordinates.resize(dimension);
00061 for(int i = 0; i < dimension; i++) {
00062 coordinates[i].resize(2);
00063 double datum;
00064 iFile >> datum;
00065 iFile >> coordinates[i][0];
00066 iFile >> coordinates[i][1];
00067 }
00068
00069 weights.resize(dimension);
00070 for(int i = 0; i < dimension; i++) {
00071 weights[i].resize(dimension);
00072 for(int j = 0; j < dimension; j++) {
00073 double diffX = coordinates[i][0] - coordinates[j][0];
00074 double diffY = coordinates[i][1] - coordinates[j][1];
00075 weights[i][j] = (int) (0.5 + sqrt(1. * diffX * diffX + diffY * diffY));
00076 }
00077 }
00078 return true;
00079
00080 } else if (dataType == "EXPLICIT") {
00081 do {
00082 getline(iFile,line);
00083 }while(line.find("EDGE_WEIGHT_FORMAT",0) == std::string::npos);
00084 std::stringstream ss_format(line.substr(line.find(":") + 1));
00085 string dataFormat;
00086 ss_format >> dataFormat;
00087 if(dataFormat == "FULL_MATRIX") {
00088
00089 do {
00090 getline(iFile,line);
00091 }while(line.find("EDGE_WEIGHT_SECTION",0) == std::string::npos);
00092
00093 weights.resize(dimension);
00094 for(int i = 0; i < dimension; i++) {
00095 weights[i].resize(dimension);
00096 for(int j = 0; j < dimension; j++) {
00097 iFile >> weights[i][j];
00098 }
00099 }
00100 return true;
00101 }
00102
00103 }
00104
00105
00106
00107 state->getLogger()->log(1, "TSP initializer: can't recognize TSP data in " + filePath
00108 + "\n(supported TSP instances: \n\t- type \"EDGE_WEIGHT_TYPE: EUC_2D\" \n\t- type \"EDGE_WEIGHT_TYPE: EXPLICIT\" with "
00109 + "\"EDGE_WEIGHT_FORMAT: FULL_MATRIX\")");
00110 return false;
00111 }
00112
00113
00114 FitnessP TSPEvalOp::evaluate(IndividualP individual)
00115 {
00116
00117 FitnessP fitness (new FitnessMin);
00118
00119
00120 Permutation::Permutation* perm = (Permutation::Permutation*) individual->getGenotype().get();
00121
00122
00123
00124 int fitnessV = 0;
00125
00126 uint size = (uint) perm->variables.size();
00127 for(uint i = 0; i < size - 1; i++){
00128
00129 fitnessV += weights[perm->variables[i]][perm->variables[i + 1]];
00130 }
00131 fitnessV += weights[perm->variables[0]][perm->variables[dimension - 1]];
00132
00133 fitness->setValue(fitnessV);
00134 return fitness;
00135 }