[Avida-SVN] r1536 - in branches/dkdev/source: main tools
dknoester at myxo.css.msu.edu
dknoester at myxo.css.msu.edu
Thu May 10 06:28:55 PDT 2007
Author: dknoester
Date: 2007-05-10 09:28:55 -0400 (Thu, 10 May 2007)
New Revision: 1536
Modified:
branches/dkdev/source/main/cPopulation.cc
branches/dkdev/source/tools/cTopology.h
Log:
Another day, another network fitness function.
Modified: branches/dkdev/source/main/cPopulation.cc
===================================================================
--- branches/dkdev/source/main/cPopulation.cc 2007-05-09 14:07:59 UTC (rev 1535)
+++ branches/dkdev/source/main/cPopulation.cc 2007-05-10 13:28:55 UTC (rev 1536)
@@ -805,6 +805,9 @@
for (int deme_id = 0; deme_id < num_demes; deme_id++) {
cDeme & source_deme = deme_array[deme_id];
+ // Doesn't make sense to try and replicate a deme that *has no organisms*.
+ if(source_deme.IsEmpty()) continue;
+
// Test this deme to determine if it should be replicated. If not,
// continue on to the next deme.
switch (rep_trigger) {
@@ -850,37 +853,9 @@
// This number is geometry-dependent. This should be abstracted
// out into a topology management thingy. And we need an easy way to
// specify group tasks (for merit).
- int max_edges=0;
- switch(m_world->GetConfig().WORLD_GEOMETRY.Get()) {
- case nGeometry::GRID: {
- const int interior_nodes = (world_x-2) * (world_y/num_demes - 2);
- const int exterior_nodes = source_deme.GetSize() - interior_nodes;
- // Each interior node has 8 edges.
- max_edges += interior_nodes * 8;
- // Each external node (except for corners) has 5 edges.
- max_edges += (exterior_nodes-4) * 5;
- // Each corner has 3 edges.
- max_edges += 12;
- // And now we've counted each edge twice.
- max_edges /= 2;
- break;
- }
- case nGeometry::TORUS: {
- // Each node has 8 edges; avoid double-counting.
- max_edges = source_deme.GetSize()*4;
- break;
- }
- case nGeometry::CLIQUE: {
- // Euler's formula.
- max_edges = source_deme.GetSize()*(source_deme.GetSize()-1)/2;
- break;
- }
- default: {
- assert(false);
- break;
- }
- }
-
+ int max_edges = max_connections(m_world->GetConfig().WORLD_GEOMETRY.Get(),
+ source_deme.GetHeight(),
+ source_deme.GetWidth());
source_germline.UpdateMerit(pow(f*(max_edges - boost::num_edges(network) + 1), 2));
}
break;
@@ -908,84 +883,70 @@
std::vector<int> components(boost::num_vertices(network));
int num_components = boost::connected_components(network, &components[0]);
if(num_components > 1) continue;
-
- // 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);
-
- // Record that it worked.
- m_world->GetStats().ConnectedTopology(source_deme, mean_lsp);
-
// 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();
-
- // Worst-case mean lsp == 3/4 of a single path.
- double max_lsp = world_x * world_y/num_demes * 0.75;
+ if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() && m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
+ // Source germline.
+ cGermline& source_germline = source_deme.GetGermline();
+
+ unsigned int max_edges = max_connections(m_world->GetConfig().WORLD_GEOMETRY.Get(),
+ source_deme.GetHeight(),
+ source_deme.GetWidth());
- // Quick hack: max# of edges.
- int max_edges=0;
- switch(m_world->GetConfig().WORLD_GEOMETRY.Get()) {
- case nGeometry::GRID: {
- const int interior_nodes = (world_x-2) * (world_y/num_demes - 2);
- const int exterior_nodes = source_deme.GetSize() - interior_nodes;
- // Each interior node has 8 edges.
- max_edges += interior_nodes * 8;
- // Each external node (except for corners) has 5 edges.
- max_edges += (exterior_nodes-4) * 5;
- // Each corner has 3 edges.
- max_edges += 12;
- // And now we've counted each edge twice.
- max_edges /= 2;
- break;
- }
- case nGeometry::TORUS: {
- // Each node has 8 edges; avoid double-counting.
- max_edges = source_deme.GetSize()*4;
- break;
+ 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));
}
- case nGeometry::CLIQUE: {
- // Euler's formula.
- max_edges = source_deme.GetSize()*(source_deme.GetSize()-1)/2;
- break;
+
+ // 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());
}
- default: {
- assert(false);
- break;
- }
- }
+ double mean_lsp = (double)sum_lsp / boost::num_vertices(network);
+
+ // Worst-case mean lsp == 3/4 of a single path.
+ double max_lsp = world_x * world_y/num_demes * 0.75;
- // 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));
+ source_germline.UpdateMerit(pow(max_edges - boost::num_edges(network)+1, 2)
+ + pow(max_lsp - mean_lsp + 1, 2));
+
+ // 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;
}
@@ -995,9 +956,6 @@
continue;
}
- // Doesn't make sense to try and replicate a deme that *has no organisms*.
- if(source_deme.IsEmpty()) continue;
-
// -- If we made it this far, we should replicate this deme --
cRandom& random = m_world->GetRandom();
Modified: branches/dkdev/source/tools/cTopology.h
===================================================================
--- branches/dkdev/source/tools/cTopology.h 2007-05-09 14:07:59 UTC (rev 1535)
+++ branches/dkdev/source/tools/cTopology.h 2007-05-10 13:28:55 UTC (rev 1536)
@@ -7,8 +7,13 @@
topology out of a given range of cells. In every case, the range of cells is
specified by a begin/end iterator pair.
*/
+#ifndef _TOPOLOGY_H_
+#define _TOPOLOGY_H_
+#include "functions.h"
+#include "nGeometry.h"
+
/*! Builds a torus topology out of the cells betwen the iterators.
In a torus, each cell is connected to up to 8 neighbors (including diagonals),
and connections DO wrap around the logical edges of the torus.
@@ -86,3 +91,41 @@
}
}
}
+
+
+/*! Calculates the maximum number of connections in a given region and geometry. */
+int max_connections(int geometry, unsigned int rowSize, unsigned int colSize) {
+ int edge_count=0;
+ switch(geometry) {
+ case nGeometry::GRID: {
+ const int interior_nodes = (colSize-2) * (rowSize-2);
+ const int exterior_nodes = colSize * rowSize - interior_nodes;
+ // Each interior node has 8 edges.
+ edge_count += interior_nodes * 8;
+ // Each external node (except for corners) has 5 edges.
+ edge_count += (exterior_nodes-4) * 5;
+ // Each corner has 3 edges.
+ edge_count += 12;
+ // And now we've counted each edge twice.
+ edge_count /= 2;
+ break;
+ }
+ case nGeometry::TORUS: {
+ // Each node has 8 edges; avoid double-counting.
+ edge_count = rowSize * colSize * 4;
+ break;
+ }
+ case nGeometry::CLIQUE: {
+ // Euler's formula.
+ edge_count = (rowSize*colSize)*(rowSize*colSize-1)/2;
+ break;
+ }
+ default: {
+ assert(false);
+ break;
+ }
+ }
+ return edge_count;
+}
+
+#endif
More information about the Avida-cvs
mailing list