pop.cpp

TSP问题的一个类库 有源代码和stl

/* 
   travelsalesman by Kai Schutte ([e-mail])
   started Feb 8th 2000, file: pop.cpp
   personal research for evolutionary computation (IEEE Spectrum Magazine, Feb '00)
   http://www.webpatterns.net/
*/

/*
  Copyright (C) 2000 Kai Schutte
  
  This program is free software; you can redistribute it and/or
  modify it under the terms of the GNU General Public License
  as published by the Free Software Foundation; either version 2
  of the License, or (at your option) any later version.
  
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.
  
  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*/

#include "pop.h"
#include <stdlib.h>
#include <iostream.h>
#include <sys/time.h>
#include <unistd.h>
#include "../include/list"

inline bool compd(const ccity* s1, const ccity* s2) {
  return (s1->distance < s2->distance);
}

cpop::cpop(cmap* city_map) {
  m = city_map;
}

cpop::~cpop() {
  for (list<ccity*>::iterator i=sol.begin(); i!=sol.end(); i++)
    delete (*i);
}

void cpop::build(int end_count) {
  int alive = 0;
  while (alive < end_count) {
    ccity* cs = new ccity(m);
    cs->create_rand_sol();
    sol.push_back(cs);
    alive++;
  }
}


void cpop::rebuild(int end_count) {
  list<ccity*> old(sol);
  int survivors = sol.size();
  int to_vary = end_count - survivors;
  list<ccity*>::iterator iter = old.begin();
  while (to_vary) {
    ccity* cs = new ccity(m);
    cs->copy(*(*iter));
    cs->create_vari_sol();
    sol.push_back(cs);
    iter++;
    if (iter == old.end())
      iter = old.begin();
    to_vary--;
  }
}

void cpop::kill_off(int to_survive) {
  for (list<ccity*>::iterator i=sol.begin(); i!=sol.end(); i++)
    (*i)->calc_distances();
  sol.sort(compd);
  list<ccity*>::iterator iter=sol.begin();
  for (int t=0; t<to_survive; t++)
    iter++;
  int size = sol.size() - to_survive;
  while (size) {
    delete (*iter);
    iter = sol.erase(iter);
    size--;
  }
}

float cpop::publish(int generation) {
  while (!table.empty()) {
    row *destroy = table.front();
    delete destroy->solution;
    delete destroy;
    table.pop_front();
  }
  for (list<ccity*>::iterator i=sol.begin(); i!=sol.end(); i++) {
    struct row *crow = new row;
    crow->generation = generation;
    crow->total_distance = (*i)->distance;
    crow->solution = new list<int>((*i)->sol);
    table.push_back(crow);
  }
  return sol.front()->distance;
}

void cpop::output_pub() {
  ofstream file;
  file.open("pub.out", ios::out);
  for (list<row*>::iterator i=table.begin(); i!=table.end(); i++) {
    file << (*i)->generation << " " << (*i)->total_distance << " ";
    for (list<int>::iterator l=(*i)->solution->begin(); l !=(*i)->solution->end(); l++) {
      file << (*l) << " ";
    }
    file << endl;
  }
  file.close();
}