[Avida-SVN] r1899 - in branches/dkdev/source: actions main
dknoester at myxo.css.msu.edu
dknoester at myxo.css.msu.edu
Tue Aug 7 12:33:22 PDT 2007
Author: dknoester
Date: 2007-08-07 15:33:22 -0400 (Tue, 07 Aug 2007)
New Revision: 1899
Modified:
branches/dkdev/source/actions/PopulationActions.cc
branches/dkdev/source/main/cDeme.cc
branches/dkdev/source/main/cDeme.h
branches/dkdev/source/main/cPopulation.cc
branches/dkdev/source/main/cStats.cc
branches/dkdev/source/main/cStats.h
Log:
refactored the topology fitness functions, s/lsp/cpl.
Modified: branches/dkdev/source/actions/PopulationActions.cc
===================================================================
--- branches/dkdev/source/actions/PopulationActions.cc 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/actions/PopulationActions.cc 2007-08-07 19:33:22 UTC (rev 1899)
@@ -895,12 +895,17 @@
else if (in_trigger == "deme-age") m_rep_trigger = 3;
else if (in_trigger == "topo-connected") m_rep_trigger = 4;
else if (in_trigger == "topo-edge-merit") m_rep_trigger = 5;
- else if (in_trigger == "topo-meanlsp-merit") m_rep_trigger = 6;
- else if (in_trigger == "topo-2cells-edge-merit") m_rep_trigger = 7;
- else if (in_trigger == "topo-2cells-path-merit") m_rep_trigger = 8;
- else if (in_trigger == "message-collection") m_rep_trigger = 9;
- else if (in_trigger == "clustering-coefficient") m_rep_trigger = 10;
- else if (in_trigger == "characteristic-path-length") m_rep_trigger = 11;
+ else if (in_trigger == "topo-inverse-edge-merit") m_rep_trigger = 6;
+ else if (in_trigger == "topo-diameter-merit") m_rep_trigger = 7;
+ else if (in_trigger == "topo-inverse-diameter-merit") m_rep_trigger = 8;
+ else if (in_trigger == "topo-cpl-merit") m_rep_trigger = 9;
+ else if (in_trigger == "topo-inverse-cpl-merit") m_rep_trigger = 10;
+ else if (in_trigger == "topo-clustering-coeff-merit") m_rep_trigger = 11;
+ else if (in_trigger == "topo-inverse-clustering-coeff-merit") m_rep_trigger = 12;
+ else if (in_trigger == "topo-target-clustering-coeff-merit") m_rep_trigger = 13;
+// else if (in_trigger == "topo-2cells-edge-merit") m_rep_trigger = 7;
+// else if (in_trigger == "topo-2cells-path-merit") m_rep_trigger = 8;
+// else if (in_trigger == "message-collection") m_rep_trigger = 9;
else {
cString err("Unknown replication trigger '");
err += in_trigger;
Modified: branches/dkdev/source/main/cDeme.cc
===================================================================
--- branches/dkdev/source/main/cDeme.cc 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/main/cDeme.cc 2007-08-07 19:33:22 UTC (rev 1899)
@@ -12,7 +12,7 @@
#include "cTopology.h"
#include "cWorld.h"
-
+#include <numeric>
#include <boost/graph/connected_components.hpp>
cDeme::cDeme()
@@ -118,12 +118,7 @@
}
-bool network_is_connected(cDeme& deme) {
- cDeme::Network& network = deme.GetNetwork();
-
- // Do we have all the vertices?
- if(boost::num_vertices(network) != (unsigned int)deme.GetSize()) return false;
-
+bool network_is_connected(cDeme::Network& network) {
// Do we have a connected graph?
std::vector<int> components(boost::num_vertices(network));
int num_components = boost::connected_components(network, &components[0]);
@@ -161,3 +156,83 @@
// Now, if the distance from src to dst is 0, we know there is no path.
return dv[dst] != 0;
}
+
+
+// Calculate the distances between each pair of nodes; 0 == not connected.
+cDeme::DistanceMatrix all_pairs_distances(cDeme::Network& network) {
+ cDeme::DistanceMatrix distance_matrix(boost::num_vertices(network),
+ cDeme::DistanceVector(boost::num_vertices(network), 0));
+ for(cDeme::SizeType i=0; i<boost::num_vertices(network); ++i) {
+ DistanceVisitor<cDeme::SizeType*> visitor(&distance_matrix[i][0]);
+ cDeme::Network::vertex_descriptor src = boost::vertices(network).first[i];
+ boost::breadth_first_search(network, src, boost::visitor(visitor));
+ }
+
+ return distance_matrix;
+}
+
+
+/*! Calculate the characteristic path length of the deme's network. CPL is the
+mean distance between all pairs of vertices. */
+double characteristic_path_length(cDeme::Network& network) {
+ cDeme::DistanceMatrix distance_matrix = all_pairs_distances(network);
+
+ // Mean path length from v to v'.
+ double cpl_sum=0.0;
+ for(cDeme::SizeType i=0; i<boost::num_vertices(network); ++i) {
+ cpl_sum += std::accumulate(distance_matrix[i].begin(), distance_matrix[i].end(), 0.0) / (boost::num_vertices(network)-1);
+ }
+
+ return cpl_sum / boost::num_vertices(network);
+}
+
+
+unsigned int diameter(cDeme::Network& network) {
+ cDeme::DistanceMatrix distance_matrix = all_pairs_distances(network);
+
+ // Mean path length from v to v'.
+ cDeme::DistanceVector max_distances;
+ for(cDeme::SizeType i=0; i<boost::num_vertices(network); ++i) {
+ max_distances.push_back(*std::max_element(distance_matrix[i].begin(), distance_matrix[i].end()));
+ }
+
+ return *std::max_element(max_distances.begin(), max_distances.end());
+}
+
+
+double clustering_coefficient(cDeme::Network& network) {
+ // For each vertex in the graph, calculate the number of edges between vertices in the neighborhood.
+ cDeme::Network::vertex_iterator vi, vi_end;
+ std::vector<double> cluster_coeffs;
+ for(tie(vi,vi_end)=vertices(network); vi!=vi_end; ++vi) {
+ // Get the list of vertices which are in the neighborhood of vi.
+ typedef cDeme::Network::adjacency_iterator adjacency_iterator;
+ std::pair<adjacency_iterator, adjacency_iterator> adjacent = boost::adjacent_vertices(*vi, network);
+ typedef std::set<cDeme::Network::vertex_descriptor> neighborhood;
+ neighborhood neighbors;
+ for(; adjacent.first!=adjacent.second; ++adjacent.first) {
+ neighbors.insert(*adjacent.first);
+ }
+
+ if(neighbors.size() > 1) {
+ // Now, count the edges between vertices in the neighborhood.
+ unsigned int neighborhood_edge_count=0;
+ for(neighborhood::iterator i=neighbors.begin(); i!=neighbors.end(); ++i) {
+ typedef cDeme::Network::out_edge_iterator out_edge_iterator;
+ std::pair<out_edge_iterator,out_edge_iterator> oe = out_edges(*i,network);
+ for(; oe.first!=oe.second; ++oe.first) {
+ if(neighbors.find(target(*oe.first,network))!=neighbors.end()) {
+ ++neighborhood_edge_count;
+ }
+ }
+ }
+ neighborhood_edge_count /= 2;
+ cluster_coeffs.push_back((double)neighborhood_edge_count / (neighbors.size()*(neighbors.size()-1)/2));
+ } else {
+ cluster_coeffs.push_back(1.0);
+ }
+ }
+
+ // Clustering coefficient:
+ return std::accumulate(cluster_coeffs.begin(), cluster_coeffs.end(), 0.0) / cluster_coeffs.size();
+}
Modified: branches/dkdev/source/main/cDeme.h
===================================================================
--- branches/dkdev/source/main/cDeme.h 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/main/cDeme.h 2007-08-07 19:33:22 UTC (rev 1899)
@@ -43,6 +43,14 @@
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS,
vertex_properties> Network;
+ typedef cDeme::Network::vertices_size_type SizeType;
+
+ //! An ease-of-use typedef to support distance calculations.
+ typedef std::vector<SizeType> DistanceVector;
+
+ //! An ease-of-use typedef to support distance matrices.
+ typedef std::vector<DistanceVector> DistanceMatrix;
+
//! A map of cell IDs to vertex descriptors.
typedef std::map<int, Network::vertex_descriptor> CellVertexMap;
@@ -138,10 +146,17 @@
//! Returns a boolean for whether the passed-in deme's network is connected.
-bool network_is_connected(cDeme& deme);
+bool network_is_connected(cDeme::Network& network);
//! Returns the maximum number of edges that this deme's network can have.
int max_edges(cDeme& deme);
//! Returns a boolean for whether the passed-in deme's two randomly selected cells are connected.
bool network_2cells_connected(cDeme& deme);
-
+//! Returns the characteristic path length of the network.
+double characteristic_path_length(cDeme::Network& network);
+//! Returns the diameter of the network.
+unsigned int diameter(cDeme::Network& network);
+//! Returns the clustering coefficient of the network.
+double clustering_coefficient(cDeme::Network& network);
+//! Returns a matrix of all-pairs distances.
+cDeme::DistanceMatrix all_pairs_distances(cDeme::Network& network);
#endif
Modified: branches/dkdev/source/main/cPopulation.cc
===================================================================
--- branches/dkdev/source/main/cPopulation.cc 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/main/cPopulation.cc 2007-08-07 19:33:22 UTC (rev 1899)
@@ -807,6 +807,7 @@
// Loop through all candidate demes...
for (int deme_id = 0; deme_id < num_demes; deme_id++) {
cDeme& source_deme = deme_array[deme_id];
+ cDeme::Network& network = source_deme.GetNetwork();
double source_germline_merit = 0.0;
// Doesn't make sense to try and replicate a deme that *has no organisms*.
@@ -835,356 +836,216 @@
break;
}
case 3: {
- // Replicate old demes.
+ // Replicate old demes (deme-age).
if(source_deme.GetAge() < m_world->GetConfig().MAX_DEME_AGE.Get()) continue;
break;
}
case 4: {
- // Replicate demes that are connected.
- m_world->GetStats().Topology(source_deme.GetNetwork());
- if(!network_is_connected(source_deme)) continue;
- m_world->GetStats().TopologyConnected(source_deme.GetNetwork());
- m_world->GetStats().TopologyReplication(source_deme.GetNetwork());
+ // Replicate demes that are connected (topo-connected).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
break;
}
case 5: {
- // Replicate demes that are connected, and set merit to the inverse of edge count.
- m_world->GetStats().Topology(source_deme.GetNetwork());
- if(!network_is_connected(source_deme)) continue;
- m_world->GetStats().TopologyConnected(source_deme.GetNetwork());
- m_world->GetStats().TopologyReplication(source_deme.GetNetwork());
- source_germline_merit = pow((double)max_edges(source_deme) - boost::num_edges(source_deme.GetNetwork()) + 1, 2);
+ // Replicate demes that are connected, and set merit to the edge count (topo-edge-merit).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
+
+ source_germline_merit = pow((double)boost::num_edges(network), 2);
break;
}
case 6: {
- // Replicate demes that are connected, and set merit to the inverse of mean LSP.
- m_world->GetStats().Topology(source_deme.GetNetwork());
- if(!network_is_connected(source_deme)) continue;
- m_world->GetStats().TopologyConnected(source_deme.GetNetwork());
- m_world->GetStats().TopologyReplication(source_deme.GetNetwork());
+ // Replicate demes that are connected, and set merit to the inverse of edge count (topo-inverse-edge-merit).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
- // Calculate the distances between each pair of nodes.
- cDeme::Network& network = source_deme.GetNetwork();
- typedef cDeme::Network::vertices_size_type size_type;
- typedef std::vector<size_type> DistanceVector;
- std::vector<DistanceVector> distance_matrix(boost::num_vertices(network),
- DistanceVector(boost::num_vertices(network), 0));
- for(size_type i=0; i<boost::num_vertices(network); ++i) {
- DistanceVisitor<size_type*> visitor(&distance_matrix[i][0]);
- cDeme::Network::vertex_descriptor src = boost::vertices(network).first[i];
- boost::breadth_first_search(network, src, boost::visitor(visitor));
- }
-
- // Now calculate the mean longest shortest-path from each node.
- size_type sum_lsp=0;
- for(size_type i=0; i<boost::num_vertices(network); ++i) {
- sum_lsp += *std::max_element(distance_matrix[i].begin(), distance_matrix[i].end());
- }
- double mean_lsp = (double)sum_lsp / boost::num_vertices(network);
- double max_lsp = world_x * world_y/num_demes * 0.75;
- m_world->GetStats().TopologyLSP(mean_lsp, max_lsp);
- source_germline_merit = pow(max_lsp - mean_lsp + 1, 2);
- break;
- }
+ source_germline_merit = pow((double)max_edges(source_deme) - boost::num_edges(network) + 1, 2);
+ break;
+ }
case 7: {
- // Replicate demes that have connected two randomly-selected cells.
- // Merit is the inverse of edge count.
- cDeme::Network& network = source_deme.GetNetwork();
+ // Replicate demes that are connected, and set merit equal to the diameter (topo-diameter-merit).
m_world->GetStats().Topology(network);
-
- cDeme::CellVertexMap& vertex_map = source_deme.GetCellVertexMap();
- std::pair<int,int> cells = source_deme.GetCellsToLink();
-
- // First verify that both of the cells in question are in the network.
- if(vertex_map.find(cells.first)==vertex_map.end()
- || vertex_map.find(cells.second)==vertex_map.end()) {
- continue;
- }
-
- // Ok, they're both in the network. From the src, get the distance to
- // all other vertices.
- typedef cDeme::Network::vertices_size_type size_type;
- typedef std::vector<size_type> DistanceVector;
- DistanceVector dv(boost::num_vertices(network),0);
- DistanceVisitor<size_type*> visitor(&dv[0]);
- cDeme::Network::vertex_descriptor src = vertex_map[cells.first];
- cDeme::Network::vertex_descriptor dst = vertex_map[cells.second];
- boost::breadth_first_search(network, src, boost::visitor(visitor));
-
- // Now, if the distance from src to dst is 0, we know there is no path.
- if(dv[dst]==0) continue;
-
- // We've determined that there is a path; replication will proceed.
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
m_world->GetStats().TopologyReplication(network);
- source_germline_merit = pow((double)(max_edges(source_deme) - boost::num_edges(network)+1), 2);
+
+ source_germline_merit = pow((double)diameter(network), 2);
break;
}
case 8: {
- // Replicate demes that have connected two randomly-selected cells.
- // Merit is the inverse of (max(e(N))-e(N)+1) +
- cDeme::Network& network = source_deme.GetNetwork();
+ // Replicate demes that are connected, and set merit equal to the inverse of their
+ // diameter (topo-inverse-diameter-merit).
m_world->GetStats().Topology(network);
-
- cDeme::CellVertexMap& vertex_map = source_deme.GetCellVertexMap();
- std::pair<int,int> cells = source_deme.GetCellsToLink();
-
- // First verify that both of the cells in question are in the network.
- if(vertex_map.find(cells.first)==vertex_map.end()
- || vertex_map.find(cells.second)==vertex_map.end()) {
- continue;
- }
-
- // We're also going to make sure that the network has a chance to fill up.
- // This is to discourage extra work.
- if(boost::num_vertices(network) < (unsigned)source_deme.GetSize()) {
- continue;
- }
-
- // Ok, they're both in the network. From the src, get the distance to
- // all other vertices.
- typedef cDeme::Network::vertices_size_type size_type;
- typedef std::vector<size_type> DistanceVector;
- DistanceVector dv(boost::num_vertices(network),0);
- DistanceVisitor<size_type*> visitor(&dv[0]);
- cDeme::Network::vertex_descriptor src = vertex_map[cells.first];
- cDeme::Network::vertex_descriptor dst = vertex_map[cells.second];
- boost::breadth_first_search(network, src, boost::visitor(visitor));
-
- // Now, if the distance from src to dst is 0, we know there is no path.
- if(dv[dst]==0) continue;
-
- // We've determined that there is a path; replication will proceed.
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
m_world->GetStats().TopologyReplication(network);
- source_germline_merit = pow((double)boost::num_vertices(network) - 1 - dv[dst], 2);
+
+ // Note: we don't need a +1 here (max diameter is less than num_vertices).
+ source_germline_merit = pow((double)boost::num_vertices(network) - diameter(network), 2);
break;
- }
+ }
case 9: {
- // Replicate demes that have managed to collect all their constituent ids.
- // The merit of the deme is in inverse proportion to the number of messages used.
-
- // Have we collected each id?
- const cDeme::CellCountMap& ccmap = source_deme.GetMessageCollection();
- bool replicate=true;
- for(cDeme::CellCountMap::const_iterator i=ccmap.begin(); i!=ccmap.end(); ++i) {
- replicate = replicate && (i->second>0);
- }
- if(!replicate) continue;
-
- // Merit in inverse proportion to the number of messages used.
- // Merit will be in the range [1,deme size).
- source_germline_merit = pow(1+
- (double)source_deme.GetSize() -
- std::min((int)source_deme.GetMessageCollectionCount(), source_deme.GetSize())
- , 2);
-
+ // Replicate demes that are connected, and set merit to the CPL (topo-cpl-merit)
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
+
+ source_germline_merit = pow(characteristic_path_length(network), 2);
break;
- }
+ }
case 10: {
- // Replicate demes that are connected, with merit based on their clustering coefficient.
- // Clustering coefficient is the number of links between a vertex's neighbors / number of possible links.
- // This case is meant to be used with a completely connection topology, as the number of links between neighbors
- // in other topologies is somewhat problematic.
- m_world->GetStats().Topology(source_deme.GetNetwork());
- if(!network_is_connected(source_deme)) continue;
- m_world->GetStats().TopologyConnected(source_deme.GetNetwork());
- m_world->GetStats().TopologyReplication(source_deme.GetNetwork());
-
- // For each vertex in the graph, calculate the number of edges between vertices in the neighborhood.
- cDeme::Network& network = source_deme.GetNetwork();
- cDeme::Network::vertex_iterator vi, vi_end;
- std::vector<double> cluster_coeffs;
- for(tie(vi,vi_end)=vertices(network); vi!=vi_end; ++vi) {
- // Get the list of vertices which are in the neighborhood of vi.
- typedef cDeme::Network::adjacency_iterator adjacency_iterator;
- std::pair<adjacency_iterator, adjacency_iterator> adjacent = boost::adjacent_vertices(*vi, network);
- typedef std::set<cDeme::Network::vertex_descriptor> neighborhood;
- neighborhood neighbors;
- for(; adjacent.first!=adjacent.second; ++adjacent.first) {
- neighbors.insert(*adjacent.first);
- }
+ // Replicate demes that are connected, and set merit to the inverse of CPL (topo-inverse-cpl-merit)
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
- if(neighbors.size() > 1) {
- // Now, count the edges between vertices in the neighborhood.
- unsigned int neighborhood_edge_count=0;
- for(neighborhood::iterator i=neighbors.begin(); i!=neighbors.end(); ++i) {
- typedef cDeme::Network::out_edge_iterator out_edge_iterator;
- std::pair<out_edge_iterator,out_edge_iterator> oe = out_edges(*i,network);
- for(; oe.first!=oe.second; ++oe.first) {
- if(neighbors.find(target(*oe.first,network))!=neighbors.end()) {
- ++neighborhood_edge_count;
- }
- }
- }
- neighborhood_edge_count /= 2;
- cluster_coeffs.push_back((double)neighborhood_edge_count / (neighbors.size()*(neighbors.size()-1)/2));
- } else {
- cluster_coeffs.push_back(1.0);
- }
- }
-
- // Clustering coefficient:
- double clustering_coeff =
- std::accumulate(cluster_coeffs.begin(), cluster_coeffs.end(), 0.0) / cluster_coeffs.size();
-
- m_world->GetStats().TopologyClusteringCoeff(clustering_coeff);
-
- // Max clustering coefficient is... 1, occuring when all possible edges are present.
- // Let's try 0.5 first, scaled to 0-100.
- clustering_coeff *= 100.0;
- // 057-clustering, 058-clustering2
- //double target_clustering_coeff=50.0;
- // 061-clustering3
- double target_clustering_coeff=25.0;
-
- // What we need here is an exponentially-decreasing function of target to both
- // low and high-range limits.
- clustering_coeff = std::min(100.0, clustering_coeff);
- clustering_coeff = std::max(0.0, clustering_coeff);
- source_germline_merit = pow(100.0-abs(clustering_coeff-target_clustering_coeff)+1, 2);
+ source_germline_merit = pow(0.75*boost::num_vertices(network)
+ - characteristic_path_length(network) + 1, 2);
break;
- }
+ }
case 11: {
- // Replicate demes that are connected, and set merit inversly proportional to the
- // characteristic path length of the network.
- // Replicate demes that are connected, and set merit to the inverse of mean LSP.
- m_world->GetStats().Topology(source_deme.GetNetwork());
- if(!network_is_connected(source_deme)) continue;
- m_world->GetStats().TopologyConnected(source_deme.GetNetwork());
- m_world->GetStats().TopologyReplication(source_deme.GetNetwork());
-
- // Calculate the distances between each pair of nodes.
- cDeme::Network& network = source_deme.GetNetwork();
- typedef cDeme::Network::vertices_size_type size_type;
- typedef std::vector<size_type> DistanceVector;
- std::vector<DistanceVector> distance_matrix(boost::num_vertices(network),
- DistanceVector(boost::num_vertices(network), 0));
- for(size_type i=0; i<boost::num_vertices(network); ++i) {
- DistanceVisitor<size_type*> visitor(&distance_matrix[i][0]);
- cDeme::Network::vertex_descriptor src = boost::vertices(network).first[i];
- boost::breadth_first_search(network, src, boost::visitor(visitor));
- }
-
- // Mean path length from v to v'.
- double vertex_cpl=0.0;
- for(size_type i=0; i<boost::num_vertices(network); ++i) {
- vertex_cpl += std::accumulate(distance_matrix[i].begin(), distance_matrix[i].end(), 0.0) / (boost::num_vertices(network)-1);
- }
-
- // Mean of mean path lengths.
- double cpl = vertex_cpl / boost::num_vertices(network);
- double max_cpl = world_x * world_y/num_demes * 0.75;
-
- m_world->GetStats().TopologyCPL(cpl);
- // 059-cpl, 060-cpl2:
- // source_germline_merit = pow(max_cpl - cpl + 1, 2);
- // 062-cpl3:
- source_germline_merit = pow(cpl, 2);
+ // Replicate demes that are connected, and set merit to the clustering coefficient (topo-clustering-coeff-merit).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
+
+ source_germline_merit = pow(100.0*clustering_coefficient(network) + 1, 2);
break;
}
-//case 5: {
-// // Replicate demes that are connectd, and set merit to f(edge count, diameter).
-//
-// // This flavor of replicate demes rewards for constructing networks with a
-// // small per-node longest shortest-path.
-// //
-// // We check to see if the topology that has been build by this deme:
-// // 1) Contains all vertices.
-// // 2) Is connected.
-// // 3) Has one component.
-// // 4) And then rewards the deme based on how close it is to having the minimum average diameter.
-// cDeme::Network& network = source_deme.GetNetwork();
-// m_world->GetStats().Topology(network);
-//
-// if(!network_is_connected(network)) continue;
-// m_world->GetStats().ConnectedTopology(network);
-//
-//
-// // Check to see if we need to update the deme's merit.
-// if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() && m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
-// // Source germline.
-// cGermline& source_germline = source_deme.GetGermline();
-//
-// const int max_edges = max_connections(m_world->GetConfig().WORLD_GEOMETRY.Get(),
-// source_deme.GetHeight(),
-// source_deme.GetWidth());
-//
-// const int min_lsp = min_diameter(m_world->GetConfig().WORLD_GEOMETRY.Get(),
-// source_deme.GetHeight(),
-// source_deme.GetWidth());
-//
-// // if(boost::num_edges(network)>=(boost::num_vertices(network))) {
-// // // Not yet a minimal network.
-// // source_germline.UpdateMerit(pow(max_edges - boost::num_edges(network)+1, 2));
-// // m_world->GetStats().ConnectedTopology(source_deme, 0);
-// //
-// // } else {
-// // It is a minimal network.
-//
-// // Calculate the shortest distances between all vertices.
-// typedef cDeme::Network::vertices_size_type size_type;
-// typedef std::vector<size_type> DistanceVector;
-// std::vector<DistanceVector> distance_matrix(boost::num_vertices(network),
-// DistanceVector(boost::num_vertices(network), 0));
-// for(size_type i=0; i<boost::num_vertices(network); ++i) {
-// DistanceVisitor<size_type*> visitor(&distance_matrix[i][0]);
-// cDeme::Network::vertex_descriptor src = boost::vertices(network).first[i];
-// boost::breadth_first_search(network, src, boost::visitor(visitor));
-// }
-//
-// // Now calculate the mean longest shortest-path from each node.
-// size_type sum_lsp=0;
-// for(size_type i=0; i<boost::num_vertices(network); ++i) {
-// sum_lsp += *std::max_element(distance_matrix[i].begin(), distance_matrix[i].end());
-// }
-// double mean_lsp = (double)sum_lsp / boost::num_vertices(network);
-// double max_lsp = world_x * world_y/num_demes * 0.75;
-//
-// // Have we found the minimal lsp?
-// // if(min_lsp != (int)mean_lsp) {
-// // // Not a min LSP network.
-// source_germline.UpdateMerit(pow(max_lsp - mean_lsp + 1, 2));
-// // } else {
-// // // A min LSP network.
-// // source_germline.UpdateMerit(pow((double)(max_edges - boost::num_edges(network)+1), 2)
-// // + pow((double)(max_lsp - mean_lsp + 1), 2));
-// // source_germline.UpdateMerit(pow((max_lsp-mean_lsp)/(max_lsp-min_lsp), 2)
-// // + pow((max_edges-boost::num_edges(network))
-// // / (max_edges-boost::num_vertices(network)-1), 2)
-// // + 1);
-// // }
-//
-// m_world->GetStats().ConnectedTopology(source_deme, mean_lsp);
-//
-//
-// // Now, update this deme's merit.
-// // This particular calculation doesn't work well; it rewards small diameter and small number of edges equally.
-// // The end result is a network that favors low edge count, with little bias towards diameter.
-// //source_germline.UpdateMerit(pow(max_lsp - mean_lsp + 1, 2) // This is for mean lsp.
-// // + pow(max_edges - boost::num_edges(network) + 1, 2));
-// //
-// // This one however, is perhaps better. We reward low diameter the most, scaled by the maximum possible
-// // number of edges. Then, we reduce this number by the actual number of edges, and square it.
-// // This fitness function is the opposite of the above. Here, low diameter is favored, resulting in nearly
-// // full networks.
-// //source_germline.UpdateMerit(pow((max_lsp - mean_lsp + 1) * max_edges - boost::num_edges(network), 2));
-// //
-// // Let's try to balance these out a bit. We're looking for a network that has both low diameter
-// // and few edges.
-// //source_germline.UpdateMerit(pow((max_lsp-mean_lsp+1)*(max_edges-boost::num_edges(network)+1),2));
-// //
-// // That didn't work either. Let's try normalizing and scaling.
-// //source_germline.UpdateMerit(pow(
-// // (max_lsp-mean_lsp)/max_lsp
-// // + (max_edges-boost::num_edges(network))/max_edges
-// // + 1,
-// // );
-// }
-// break;
-//}
- default:
+ case 12: {
+ // Replicate demes that are connected, and set merit to the inverse of the clustering coefficient
+ // (topo-inverse-clustering-coeff-merit).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
+
+ source_germline_merit = pow(100.0 - 100.0*clustering_coefficient(network) + 1, 2);
+ break;
+ }
+ case 13: {
+ // Replicate demes that are connected, and set the merit based on the proximity to a specified
+ // clustering coefficient (topo-target-clustering-coeff-merit).
+ m_world->GetStats().Topology(network);
+ if(boost::num_vertices(network) < (unsigned int)source_deme.GetSize()) continue;
+ if(!network_is_connected(network)) continue;
+ m_world->GetStats().TopologyReplication(network);
+
+ double coeff = clustering_coefficient(network);
+ double target_coeff = 0.5;
+
+ // Want to reward for absolute "closeness" to target.
+ // matlab: x=0:0.001:1; target=0.5; plot(x, (power(1/100,abs(target-x))*100).^2)
+ source_germline_merit = pow(pow(0.01, abs(target_coeff - coeff))*100, 2);
+ break;
+ }
+// case 8: {
+// // Replicate demes that have connected two randomly-selected cells.
+// // Merit is the inverse of edge count.
+// cDeme::Network& network = source_deme.GetNetwork();
+// m_world->GetStats().Topology(network);
+//
+// cDeme::CellVertexMap& vertex_map = source_deme.GetCellVertexMap();
+// std::pair<int,int> cells = source_deme.GetCellsToLink();
+//
+// // First verify that both of the cells in question are in the network.
+// if(vertex_map.find(cells.first)==vertex_map.end()
+// || vertex_map.find(cells.second)==vertex_map.end()) {
+// continue;
+// }
+//
+// // Ok, they're both in the network. From the src, get the distance to
+// // all other vertices.
+// typedef cDeme::Network::vertices_size_type size_type;
+// typedef std::vector<size_type> DistanceVector;
+// DistanceVector dv(boost::num_vertices(network),0);
+// DistanceVisitor<size_type*> visitor(&dv[0]);
+// cDeme::Network::vertex_descriptor src = vertex_map[cells.first];
+// cDeme::Network::vertex_descriptor dst = vertex_map[cells.second];
+// boost::breadth_first_search(network, src, boost::visitor(visitor));
+//
+// // Now, if the distance from src to dst is 0, we know there is no path.
+// if(dv[dst]==0) continue;
+//
+// // We've determined that there is a path; replication will proceed.
+// m_world->GetStats().TopologyReplication(network);
+// source_germline_merit = pow((double)(max_edges(source_deme) - boost::num_edges(network)+1), 2);
+// break;
+// }
+// case 8: {
+// // Replicate demes that have connected two randomly-selected cells.
+// // Merit is the inverse of (max(e(N))-e(N)+1) +
+// cDeme::Network& network = source_deme.GetNetwork();
+// m_world->GetStats().Topology(network);
+//
+// cDeme::CellVertexMap& vertex_map = source_deme.GetCellVertexMap();
+// std::pair<int,int> cells = source_deme.GetCellsToLink();
+//
+// // First verify that both of the cells in question are in the network.
+// if(vertex_map.find(cells.first)==vertex_map.end()
+// || vertex_map.find(cells.second)==vertex_map.end()) {
+// continue;
+// }
+//
+// // We're also going to make sure that the network has a chance to fill up.
+// // This is to discourage extra work.
+// if(boost::num_vertices(network) < (unsigned)source_deme.GetSize()) {
+// continue;
+// }
+//
+// // Ok, they're both in the network. From the src, get the distance to
+// // all other vertices.
+// typedef cDeme::Network::vertices_size_type size_type;
+// typedef std::vector<size_type> DistanceVector;
+// DistanceVector dv(boost::num_vertices(network),0);
+// DistanceVisitor<size_type*> visitor(&dv[0]);
+// cDeme::Network::vertex_descriptor src = vertex_map[cells.first];
+// cDeme::Network::vertex_descriptor dst = vertex_map[cells.second];
+// boost::breadth_first_search(network, src, boost::visitor(visitor));
+//
+// // Now, if the distance from src to dst is 0, we know there is no path.
+// if(dv[dst]==0) continue;
+//
+// // We've determined that there is a path; replication will proceed.
+// m_world->GetStats().TopologyReplication(network);
+// source_germline_merit = pow((double)boost::num_vertices(network) - 1 - dv[dst], 2);
+// break;
+// }
+// case 9: {
+// // Replicate demes that have managed to collect all their constituent ids.
+// // The merit of the deme is in inverse proportion to the number of messages used.
+//
+// // Have we collected each id?
+// const cDeme::CellCountMap& ccmap = source_deme.GetMessageCollection();
+// bool replicate=true;
+// for(cDeme::CellCountMap::const_iterator i=ccmap.begin(); i!=ccmap.end(); ++i) {
+// replicate = replicate && (i->second>0);
+// }
+// if(!replicate) continue;
+//
+// // Merit in inverse proportion to the number of messages used.
+// // Merit will be in the range [1,deme size).
+// source_germline_merit = pow(1+
+// (double)source_deme.GetSize() -
+// std::min((int)source_deme.GetMessageCollectionCount(), source_deme.GetSize())
+// , 2);
+//
+// break;
+// }
+ default: {
cerr << "ERROR: Invalid replication trigger " << rep_trigger
<< " in cPopulation::ReplicateDemes()" << endl;
continue;
+ }
}
// -- If we made it this far, we should replicate this deme. --
Modified: branches/dkdev/source/main/cStats.cc
===================================================================
--- branches/dkdev/source/main/cStats.cc 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/main/cStats.cc 2007-08-07 19:33:22 UTC (rev 1899)
@@ -862,62 +862,48 @@
//
// Here lie deme and topology stats.
//
+
+/*! Generic statistics that should be gathered for all networks. */
void cStats::Topology(cDeme::Network& network) {
_topo_edges.Add(boost::num_edges(network));
+ _topo_vertices.Add(boost::num_vertices(network));
_topo_last_network = network;
}
-void cStats::TopologyConnected(cDeme::Network& network) {
- ++_topo_connected;
-}
-
-
-void cStats::TopologyLSP(double meanlsp, double maxlsp) {
- _topo_meanlsp.Add(meanlsp);
- _topo_maxlsp.Add(maxlsp);
- _topo_maxlsp_frac.Add(meanlsp/maxlsp);
-}
-
-
+/*! Statistics that should be gathered only for those networks that cause replication. */
void cStats::TopologyReplication(cDeme::Network& network) {
+ ++_topo_connected;
_topo_edges_repl.Add(boost::num_edges(network));
+ _topo_vertices_repl.Add(boost::num_vertices(network));
+ _topo_clustering_coeff.Add(clustering_coefficient(network));
+ _topo_cpl.Add(characteristic_path_length(network));
+ _topo_diameter.Add(diameter(network));
}
-
-void cStats::TopologyClusteringCoeff(double clustering_coefficient) {
- _topo_clustering_coeff.Add(clustering_coefficient);
-}
-
-
-void cStats::TopologyCPL(double cpl) {
- _topo_cpl.Add(cpl);
-}
-
-
void cStats::PrintTopologyData(const cString& filename) {
cDataFile& df = m_world->GetDataFile(filename);
df.WriteComment( "Topology data\n" );
df.WriteTimeStamp();
- df.Write(GetUpdate(), "update" );
- df.Write(_topo_edges.Average(), "mean edges in all constructed networks [edges]");
- df.Write(_topo_edges_repl.Average(), "mean edges in networks that caused replication [repl_edges]");
- df.Write(_topo_connected, "count of connected networks [conn]");
- df.Write(_topo_meanlsp.Average(), "mean mean longest shortest-path [mean_lsp]");
- df.Write(_topo_maxlsp.Average(), "mean max longest shortest-path [max_lsp]");
- df.Write(_topo_maxlsp_frac.Average(), "mean (mean lsp / max lsp) [lsp_ratio]");
- df.Write(_topo_clustering_coeff.Average(), "mean clustering coefficient [cluster]");
+ df.Write(GetUpdate(), "update [update]" );
+ df.Write(_topo_edges.Average(), "mean edges in all networks [edges]");
+ df.Write(_topo_edges_repl.Average(), "mean edges in all replicated networks [repl_edges]");
+ df.Write(_topo_vertices.Average(), "mean vertices in all networks [vertices]");
+ df.Write(_topo_vertices_repl.Average(), "mean vertices in all replicated networks [repl_vertices]");
+ df.Write(_topo_connected, "count of connected networks [connected]");
+ df.Write(_topo_clustering_coeff.Average(), "mean clustering coefficient [cluster_coeff]");
df.Write(_topo_cpl.Average(), "mean characteristic path length [cpl]");
+ df.Write(_topo_diameter.Average(), "mean diameter [diameter]");
df.Endl();
_topo_connected = 0;
_topo_edges.Clear();
_topo_edges_repl.Clear();
- _topo_meanlsp.Clear();
- _topo_maxlsp.Clear();
- _topo_maxlsp_frac.Clear();
+ _topo_vertices.Clear();
+ _topo_vertices_repl.Clear();
_topo_clustering_coeff.Clear();
_topo_cpl.Clear();
+ _topo_diameter.Clear();
}
@@ -1010,7 +996,7 @@
cDataFile& df = m_world->GetDataFile(filename);
df.WriteComment("Deme replication data");
df.WriteTimeStamp();
- df.Write(GetUpdate(), "update");
+ df.Write(GetUpdate(), "update [update]");
df.Write(_deme_repl_count, "replication count [count]");
df.Write(std::min(_deme_repl_count/(double)m_world->GetPopulation().GetNumDemes(), 1.0),
"replication probability [prob]");
@@ -1030,7 +1016,7 @@
cDataFile& df = m_world->GetDataFile(filename);
df.WriteComment("Message collection stats");
df.WriteTimeStamp();
- df.Write(GetUpdate(), "update");
+ df.Write(GetUpdate(), "update [update]");
cDoubleSum collection_count;
cDoubleSum cell_ids_collected;
@@ -1046,8 +1032,8 @@
cell_ids_collected.Add(ids_collected);
}
- df.Write(collection_count.Average(), "mean collection count (per deme)");
- df.Write(cell_ids_collected.Average(), "mean cell ids collected (per deme)");
+ df.Write(collection_count.Average(), "mean collection count (per deme) [coll_count]");
+ df.Write(cell_ids_collected.Average(), "mean cell ids collected (per deme) [cell_ids]");
df.Endl();
}
Modified: branches/dkdev/source/main/cStats.h
===================================================================
--- branches/dkdev/source/main/cStats.h 2007-08-07 18:22:51 UTC (rev 1898)
+++ branches/dkdev/source/main/cStats.h 2007-08-07 19:33:22 UTC (rev 1899)
@@ -202,22 +202,7 @@
int num_sold;
int num_used;
int num_own_used;
-
- int _topo_connected; //!< Count of connected networks.
- cDoubleSum _topo_edges; //!< Edge count in all networks.
- cDoubleSum _topo_edges_repl; //!< Edge count in networks that cauasd deme replication.
- cDoubleSum _topo_meanlsp; //!< Mean longest shortest-path.
- cDoubleSum _topo_maxlsp; //!< Max longest shortest-path.
- cDoubleSum _topo_maxlsp_frac; //!< Mean LSP / Max LSP.
- cDoubleSum _topo_clustering_coeff; //!< Clustering coefficient.
- cDoubleSum _topo_cpl; //!< Characteristic path length.
- cDeme::Network _topo_last_network; //!< The last constructed network.
-
- int _deme_repl_count; //!< Number of deme replications since the last stats output.
- cDoubleSum _deme_merit; //!< Deme merits, upon replication.
- cDoubleSum _deme_age; //!< Deme ages, upon replication.
- cGermline _deme_last_germline; //!< The last germline to cause a deme replication.
-
+
cStats(); // @not_implemented
cStats(const cStats&); // @not_implemented
cStats& operator=(const cStats&); // @not_implemented
@@ -561,26 +546,50 @@
void PrintGenotypeMap(const cString& filename);
void PrintMarketData(const cString& filename);
- // Topology
+ //
+ // Topology-related statistics.
+ //
+public:
void Topology(cDeme::Network& network);
- void TopologyConnected(cDeme::Network& network);
- void TopologyLSP(double meanlsp, double maxlsp);
void TopologyReplication(cDeme::Network& network);
- void TopologyClusteringCoeff(double clustering_coefficient);
- void TopologyCPL(double cpl);
void PrintTopologyData(const cString& filename);
void PrintLastTopology();
void PrintEachTopology();
- // Demes
+private:
+ int _topo_connected; //!< Count of connected networks.
+ cDoubleSum _topo_edges; //!< Edge count in all networks.
+ cDoubleSum _topo_edges_repl; //!< Edge count in networks that replicated.
+ cDoubleSum _topo_vertices; //!< Vertex count in all networks;
+ cDoubleSum _topo_vertices_repl; //!< Vertex count in networks that replicated.
+ cDoubleSum _topo_clustering_coeff; //!< Clustering coefficient.
+ cDoubleSum _topo_cpl; //!< Characteristic path length.
+ cDoubleSum _topo_diameter; //!< Diameter of the network.
+ cDeme::Network _topo_last_network; //!< The last constructed network.
+
+ //
+ // Deme-related statistics.
+ //
+public:
void DemeReplication(cDeme& deme);
void PrintDemeData(const cString& filename);
void PrintLastGermline();
+private:
+ int _deme_repl_count; //!< Number of deme replications since the last stats output.
+ cDoubleSum _deme_merit; //!< Deme merits, upon replication.
+ cDoubleSum _deme_age; //!< Deme ages, upon replication.
+ cGermline _deme_last_germline; //!< The last germline to cause a deme replication.
- // Satellite
- void PrintCollectionData(const cString& filename);
+ //
+ // Satellite-related statistics.
+ //
+public:
+ void PrintCollectionData(const cString& filename);
+private:
- // Attractor
+ //
+ // Attractor-related statistics.
+ //
public:
struct edge_properties {
edge_properties() : _count(1) { }
More information about the Avida-cvs
mailing list