[Avida-SVN] r1653 - in branches/dkdev: Avida.xcodeproj source/actions source/cpu source/main source/tools
dknoester at myxo.css.msu.edu
dknoester at myxo.css.msu.edu
Wed Jun 6 19:24:12 PDT 2007
Author: dknoester
Date: 2007-06-06 22:24:12 -0400 (Wed, 06 Jun 2007)
New Revision: 1653
Added:
branches/dkdev/source/tools/cTopology.cc
Modified:
branches/dkdev/Avida.xcodeproj/project.pbxproj
branches/dkdev/source/actions/PopulationActions.cc
branches/dkdev/source/actions/PrintActions.cc
branches/dkdev/source/cpu/cHardwareCPU.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
branches/dkdev/source/tools/CMakeLists.txt
branches/dkdev/source/tools/cTopology.h
Log:
Updated stat outputting, added new ReplicateDemes method for connecting two random cells.
Modified: branches/dkdev/Avida.xcodeproj/project.pbxproj
===================================================================
--- branches/dkdev/Avida.xcodeproj/project.pbxproj 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/Avida.xcodeproj/project.pbxproj 2007-06-07 02:24:12 UTC (rev 1653)
@@ -7,6 +7,7 @@
objects = {
/* Begin PBXBuildFile section */
+ 428C60240C17978C000212E2 /* cTopology.cc in Sources */ = {isa = PBXBuildFile; fileRef = 428C60230C17978C000212E2 /* cTopology.cc */; };
7005A70609BA0FA90007E16E /* cTestCPUInterface.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7005A70209BA0FA90007E16E /* cTestCPUInterface.cc */; };
7005A70809BA0FA90007E16E /* cTestCPUInterface.cc in Sources */ = {isa = PBXBuildFile; fileRef = 7005A70209BA0FA90007E16E /* cTestCPUInterface.cc */; };
700E2996085A1F6000CF158A /* avida in CopyFiles */ = {isa = PBXBuildFile; fileRef = DCC3164D07626CF3008F7A48 /* avida */; };
@@ -294,6 +295,7 @@
/* End PBXCopyFilesBuildPhase section */
/* Begin PBXFileReference section */
+ 428C60230C17978C000212E2 /* cTopology.cc */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = cTopology.cc; sourceTree = "<group>"; };
7005A70109BA0FA90007E16E /* cTestCPUInterface.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = cTestCPUInterface.h; sourceTree = "<group>"; };
7005A70209BA0FA90007E16E /* cTestCPUInterface.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = cTestCPUInterface.cc; sourceTree = "<group>"; };
7005A70909BA0FBE0007E16E /* cOrgInterface.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = cOrgInterface.h; sourceTree = "<group>"; };
@@ -1413,6 +1415,7 @@
70B08B9008FB2E6B00FC65FE /* cTools.cc */,
70B08B9108FB2E6B00FC65FE /* cWeightedIndex.cc */,
E08178B90B3DCB9600B474B6 /* cTopology.h */,
+ 428C60230C17978C000212E2 /* cTopology.cc */,
70B08B8008FB2E5500FC65FE /* cTools.h */,
70B08B8108FB2E5500FC65FE /* cUInt.h */,
70B08B8208FB2E5500FC65FE /* cWeightedIndex.h */,
@@ -1898,6 +1901,7 @@
708BF2FE0AB65DC700A923BF /* cEventList.cc in Sources */,
E03F28DC0B8A2840009966B8 /* cDeme.cc in Sources */,
E0F61B210BA33F5D00B53C23 /* cGermline.cc in Sources */,
+ 428C60240C17978C000212E2 /* cTopology.cc in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -1950,7 +1954,7 @@
suppress,
);
PRODUCT_NAME = avida;
- USER_HEADER_SEARCH_PATHS = "source/main source/cpu";
+ USER_HEADER_SEARCH_PATHS = "source//";
};
name = Development;
};
Modified: branches/dkdev/source/actions/PopulationActions.cc
===================================================================
--- branches/dkdev/source/actions/PopulationActions.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/actions/PopulationActions.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -889,12 +889,14 @@
cString in_trigger("full_deme");
if (largs.GetSize()) in_trigger = largs.PopWord();
- if (in_trigger == "all") m_rep_trigger = 0;
+ if (in_trigger == "any") m_rep_trigger = 0;
else if (in_trigger == "full_deme") m_rep_trigger = 1;
else if (in_trigger == "corners") m_rep_trigger = 2;
- else if (in_trigger == "topo-connected") m_rep_trigger = 3;
- else if (in_trigger == "deme-age") m_rep_trigger = 4;
- else if (in_trigger == "min-diameter") m_rep_trigger = 5;
+ 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 {
cString err("Unknown replication trigger '");
err += in_trigger;
Modified: branches/dkdev/source/actions/PrintActions.cc
===================================================================
--- branches/dkdev/source/actions/PrintActions.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/actions/PrintActions.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -65,7 +65,9 @@
STATS_OUT_FILE(PrintGenotypeMap, genotype_map.m );
STATS_OUT_FILE(PrintMarketData, market.dat );
STATS_OUT_FILE(PrintTopologyData, topology.dat);
+STATS_OUT_FILE(PrintDemeData, deme.dat);
+
#define POP_OUT_FILE(METHOD, DEFAULT) /* 1 */ \
class cAction ## METHOD : public cAction { /* 2 */ \
private: /* 3 */ \
@@ -1453,8 +1455,28 @@
};
+class cActionPrintLastTopology : public cAction
+{
+public:
+ cActionPrintLastTopology(cWorld* world, const cString& args) : cAction(world, args) { }
+ static const cString GetDescription() { return "No arguments."; }
+ void Process(cAvidaContext& ctx) {
+ m_world->GetStats().PrintLastTopology();
+ }
+};
+class cActionPrintLastGermline : public cAction
+{
+public:
+ cActionPrintLastGermline(cWorld* world, const cString& args) : cAction(world, args) { }
+ static const cString GetDescription() { return "No arguments."; }
+ void Process(cAvidaContext& ctx) {
+ m_world->GetStats().PrintLastGermline();
+ }
+};
+
+
void RegisterPrintActions(cActionLibrary* action_lib)
{
// Stats Out Files
@@ -1519,7 +1541,11 @@
// Topology
action_lib->Register<cActionPrintTopologyData>("PrintTopologyData");
+ action_lib->Register<cActionPrintDemeData>("PrintDemeData");
+ action_lib->Register<cActionPrintLastTopology>("PrintLastTopology");
+ action_lib->Register<cActionPrintLastGermline>("PrintLastGermline");
+
// @DMB - The following actions are DEPRECATED aliases - These will be removed in 2.7.
action_lib->Register<cActionPrintAverageData>("print_average_data");
action_lib->Register<cActionPrintErrorData>("print_error_data");
Modified: branches/dkdev/source/cpu/cHardwareCPU.cc
===================================================================
--- branches/dkdev/source/cpu/cHardwareCPU.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/cpu/cHardwareCPU.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -3533,10 +3533,7 @@
if(organism->GetCellID()==-1) return false;
cPopulationCell& cell = m_world->GetPopulation().GetCell(organism->GetCellID());
cDeme& deme = m_world->GetPopulation().GetDeme(cell.GetDemeID());
-
- // Rate-limiting link construction.
- if(!deme.CreateLink()) return false;
-
+
cDeme::Network& network = deme.GetNetwork();
cDeme::CellVertexMap& cvMap = deme.GetCellVertexMap();
@@ -3571,9 +3568,14 @@
network))).first;
}
- // Finally, add the edge. We're done.
- boost::add_edge(u->second, v->second, network);
- return true;
+ // Rate-limiting link construction.
+ //if(deme.CreateLink()) {
+ // Finally, add the edge. We're done.
+ boost::add_edge(u->second, v->second, network);
+ return true;
+ //}
+
+ //return false;
}
Modified: branches/dkdev/source/main/cDeme.cc
===================================================================
--- branches/dkdev/source/main/cDeme.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/main/cDeme.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -7,7 +7,11 @@
*/
#include "cDeme.h"
+#include "cWorld.h"
+#include "cTopology.h"
+#include <boost/graph/connected_components.hpp>
+
cDeme::cDeme()
: width(0)
, birth_count(0)
@@ -20,9 +24,15 @@
{
}
-void cDeme::Setup(const tArray<int> & in_cells, int in_width)
+void cDeme::Setup(const tArray<int> & in_cells, int in_width, cWorld* world)
{
+ _world = world;
cell_ids = in_cells;
+ _cellsToLink = std::make_pair(_world->GetRandom().GetInt(cell_ids.GetSize()),
+ _world->GetRandom().GetInt(cell_ids.GetSize()));
+ while(_cellsToLink.second == _cellsToLink.first) {
+ _cellsToLink.second = _world->GetRandom().GetInt(cell_ids.GetSize());
+ }
birth_count = 0;
org_count = 0;
@@ -75,3 +85,21 @@
// cGermline's copy ctor.
_germline = germline;
}
+
+
+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;
+
+ // Do we have a connected graph?
+ std::vector<int> components(boost::num_vertices(network));
+ int num_components = boost::connected_components(network, &components[0]);
+ return num_components == 1;
+}
+
+
+int max_edges(cDeme& deme) {
+ return cTopology::max_connections(deme.GetWorld()->GetConfig().WORLD_GEOMETRY.Get(), deme.GetHeight(), deme.GetWidth());
+}
Modified: branches/dkdev/source/main/cDeme.h
===================================================================
--- branches/dkdev/source/main/cDeme.h 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/main/cDeme.h 2007-06-07 02:24:12 UTC (rev 1653)
@@ -24,6 +24,9 @@
#include "cGermline.h"
+class cWorld;
+
+
class cDeme {
public:
//! The internal vertex properties.
@@ -44,7 +47,7 @@
cDeme();
~cDeme();
- void Setup(const tArray<int> & in_cells, int in_width=-1);
+ void Setup(const tArray<int> & in_cells, int in_width, cWorld* world);
int GetSize() const { return cell_ids.GetSize(); }
int GetCellID(int pos) const { return cell_ids[pos]; }
@@ -61,6 +64,8 @@
int GetOrgCount() const { return org_count; }
void IncOrgCount() { org_count++; }
void DecOrgCount() { org_count--; }
+
+ cWorld* GetWorld() { return _world; }
bool IsEmpty() const { return org_count == 0; }
bool IsFull() const { return org_count == cell_ids.GetSize(); }
@@ -73,7 +78,9 @@
bool IsCellID(int cell_id) { return false; }
//! Returns true if a link may be created in this deme.
bool CreateLink();
-
+ //! Returns a boolean for whether two cells, selected at random, are linked.
+ std::pair<int,int> GetCellsToLink() { return _cellsToLink; }
+
// -= Germline =-
cGermline& GetGermline() { return _germline; }
void ReplaceGermline(const cGermline& germline);
@@ -93,7 +100,9 @@
cGermline _germline; //!< The germline for this deme, if used.
int _age; //!< How old this deme is, in updates.
+ cWorld* _world; //!< Pointer to the world.
int _links; //!< The number of links currently available to members of this deme.
+ std::pair<int, int> _cellsToLink; //! The ids of cells that should be linked.
};
@@ -114,4 +123,10 @@
Distance distance;
};
+
+//! Returns a boolean for whether the passed-in deme's network is connected.
+bool network_is_connected(cDeme& deme);
+//! Returns the maximum number of edges that this deme's network can have.
+int max_edges(cDeme& deme);
+
#endif
Modified: branches/dkdev/source/main/cPopulation.cc
===================================================================
--- branches/dkdev/source/main/cPopulation.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/main/cPopulation.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -102,7 +102,7 @@
deme_cells[offset] = cell_id;
cell_array[cell_id].SetDemeID(deme_id);
}
- deme_array[deme_id].Setup(deme_cells, deme_size_x);
+ deme_array[deme_id].Setup(deme_cells, deme_size_x, m_world);
}
@@ -115,18 +115,18 @@
// We're cheating here; we're using the random access nature of an iterator
// to index beyond the end of the cell_array.
case nGeometry::GRID: {
- build_grid(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
- deme_size_x, deme_size_y);
+ cTopology::build_grid(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
+ deme_size_x, deme_size_y);
break;
}
case nGeometry::TORUS: {
- build_torus(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
- deme_size_x, deme_size_y);
+ cTopology::build_torus(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
+ deme_size_x, deme_size_y);
break;
}
case nGeometry::CLIQUE: {
- build_clique(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
- deme_size_x, deme_size_y);
+ cTopology::build_clique(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
+ deme_size_x, deme_size_y);
break;
}
default: {
@@ -803,7 +803,8 @@
// Loop through all candidate demes...
for (int deme_id = 0; deme_id < num_demes; deme_id++) {
- cDeme & source_deme = deme_array[deme_id];
+ cDeme& source_deme = deme_array[deme_id];
+ double source_germline_merit = 0.0;
// Doesn't make sense to try and replicate a deme that *has no organisms*.
if(source_deme.IsEmpty()) continue;
@@ -811,168 +812,223 @@
// Test this deme to determine if it should be replicated. If not,
// continue on to the next deme.
switch (rep_trigger) {
- case 0: // CASE: Replicate all non-empty demes...
- // If this deme is empt, continue looping...
- if (source_deme.IsEmpty()) continue;
+ case 0: {
+ // Replicate non-empty demes.
+ if(source_deme.IsEmpty()) continue;
break;
- case 1: // Replicate all full demes...
- if (source_deme.IsFull() == false) continue;
+ }
+ case 1: {
+ // Replicate full demes.
+ if(source_deme.IsFull() == false) continue;
break;
- case 2: // Replicate all demes with the corners filled in.
- {
+ }
+ case 2: {
+ // Replicate all demes with the corners filled in.
// The first and last IDs represent the two corners.
const int id1 = source_deme.GetCellID(0);
const int id2 = source_deme.GetCellID(source_deme.GetSize() - 1);
if (cell_array[id1].IsOccupied() == false ||
- cell_array[id2].IsOccupied() == false) continue;
+ cell_array[id2].IsOccupied() == false) continue;
+ break;
}
- break;
- case 3: {
- // Checks to see if the topology that has been built by this deme:
- // 1) Contains a vertex for all cells in the deme.
- // 2) Is completely connected.
- cDeme::Network& network = source_deme.GetNetwork();
- if(boost::num_vertices(network) != (unsigned int)source_deme.GetSize()) continue;
- std::vector<int> components(boost::num_vertices(network));
- int num_components = boost::connected_components(network, &components[0]);
- if(num_components > 1) continue;
-
- // Hm, ok, well we now have connected deme. We should really do some
- // stats tracking now.
- m_world->GetStats().ConnectedTopology(source_deme);
-
- // 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()) {
- // This is just a hack to see if this approach will work; if so, it
- // definitely needs refactoring.
- cGermline& source_germline = source_deme.GetGermline();
- const double f=1.0;
-
- // Need to calculate the maximum number of edges in the deme.
- // 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 = 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;
- }
- case 4: {
- // Replicates old demes.
+ case 3: {
+ // Replicate old demes.
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());
+ break;
}
case 5: {
- // 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.
+ // 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);
+ 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());
+
+ // 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));
+ }
- // Do we have all the vertices?
- if(boost::num_vertices(network) != (unsigned int)source_deme.GetSize()) continue;
-
- // Do we have a connected graph?
- std::vector<int> components(boost::num_vertices(network));
- int num_components = boost::connected_components(network, &components[0]);
- if(num_components > 1) continue;
+ // 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;
+ }
+ case 7: {
+ // 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);
- // 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();
+ 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;
+ }
- 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,
- // );
- }
+ // 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 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:
cerr << "ERROR: Invalid replication trigger " << rep_trigger
<< " in cPopulation::ReplicateDemes()" << endl;
continue;
}
- // -- If we made it this far, we should replicate this deme --
+ // -- If we made it this far, we should replicate this deme. --
+
+ // Check to see if we should update the source deme's germline merit.
+ if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() && m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
+ source_deme.GetGermline().UpdateMerit(source_germline_merit);
+ }
+ m_world->GetStats().DemeReplication(source_deme);
cRandom& random = m_world->GetRandom();
// Choose a random target deme to replicate to, and kill all the organisms
Modified: branches/dkdev/source/main/cStats.cc
===================================================================
--- branches/dkdev/source/main/cStats.cc 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/main/cStats.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -17,6 +17,7 @@
#include "cWorld.h"
#include "cWorldDriver.h"
#include "cGenome.h"
+#include "cPopulation.h"
#include <float.h>
#include <math.h>
@@ -92,6 +93,8 @@
, num_sold(0)
, num_used(0)
, num_own_used(0)
+ , _topo_connected(0)
+ , _deme_repl_count(0)
{
task_cur_count.Resize( m_world->GetNumTasks() );
task_last_count.Resize( m_world->GetNumTasks() );
@@ -855,17 +858,54 @@
}
-void cStats::ConnectedTopology(cDeme& deme, double meanlsp) {
- cDeme::Network& network = deme.GetNetwork();
- ++m_topo_numReplications;
- m_topo_numEdges.Add(boost::num_edges(network));
- m_topo_meanLsp.Add(meanlsp);
- m_topo_lastNetwork = network;
- m_topo_germline = deme.GetGermline();
+//
+// Here lie deme and topology stats.
+//
+void cStats::Topology(cDeme::Network& network) {
+ _topo_edges.Add(boost::num_edges(network));
+ _topo_last_network = network;
}
-// Need to fix the vertices to contain the cell position.
+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);
+}
+
+
+void cStats::TopologyReplication(cDeme::Network& network) {
+ _topo_edges_repl.Add(boost::num_edges(network));
+}
+
+
+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");
+ df.Write(_topo_edges_repl.Average(), "mean edges in networks that caused replication");
+ df.Write(_topo_connected, "count of connected networks");
+ df.Write(_topo_meanlsp.Average(), "mean mean longest shortest-path");
+ df.Write(_topo_maxlsp.Average(), "mean max longest shortest-path");
+ df.Write(_topo_maxlsp_frac.Average(), "mean (mean lsp / max lsp)");
+ df.Endl();
+
+ _topo_connected = 0;
+ _topo_edges.Clear();
+ _topo_edges_repl.Clear();
+ _topo_meanlsp.Clear();
+ _topo_maxlsp.Clear();
+ _topo_maxlsp_frac.Clear();
+}
+
+
struct topo_vertex_writer {
topo_vertex_writer(cDeme::Network& network) : _network(network) { }
@@ -878,32 +918,56 @@
};
-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(m_topo_numReplications, "Number of deme replications.");
- df.Write(m_topo_numEdges.Average(), "Avg. number of edges on deme replication.");
- df.Write(m_topo_meanLsp.Average(), "Avg. longest shortest-path.");
- m_topo_numReplications = 0;
- m_topo_numEdges.Clear();
- m_topo_meanLsp.Clear();
- df.Endl();
-
- if(boost::num_vertices(m_topo_lastNetwork) > 0) {
+void cStats::PrintLastTopology() {
+ if(boost::num_vertices(_topo_last_network) > 0) {
std::stringstream filename;
filename << "./data/topo-" << GetUpdate() << ".dot";
std::ofstream outfile(filename.str().c_str());
- boost::write_graphviz(outfile, m_topo_lastNetwork, topo_vertex_writer(m_topo_lastNetwork));
+ boost::write_graphviz(outfile, _topo_last_network, topo_vertex_writer(_topo_last_network));
outfile.close();
}
+}
- if(m_topo_germline.Size() > 0) {
+
+void cStats::PrintLastGermline() {
+ assert(m_world->GetConfig().DEMES_USE_GERMLINE.Get());
+ if(_deme_last_germline.Size() > 0) {
std::stringstream filename;
filename << "./data/germ-" << GetUpdate() << ".genome";
std::ofstream outfile(filename.str().c_str());
- outfile << m_topo_germline.GetLatest().AsString() << std::endl;
+ outfile << _deme_last_germline.GetLatest().AsString() << std::endl;
outfile.close();
}
}
+
+
+void cStats::DemeReplication(cDeme& deme) {
+ // Common deme statistics.
+ ++_deme_repl_count;
+ _deme_age.Add(deme.GetAge());
+
+ // Germline-specific statistics.
+ if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() && m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
+ _deme_last_germline = deme.GetGermline();
+ _deme_merit.Add(deme.GetGermline().GetMerit().GetDouble());
+ }
+}
+
+
+void cStats::PrintDemeData(const cString& filename) {
+ cDataFile& df = m_world->GetDataFile(filename);
+ df.WriteComment("Deme replication data");
+ df.WriteTimeStamp();
+ df.Write(GetUpdate(), "update");
+ df.Write(_deme_repl_count, "replication count");
+ df.Write(std::min(_deme_repl_count/(double)m_world->GetPopulation().GetNumDemes(), 1.0), "replication probability");
+ df.Write(_deme_age.Average(), "mean age of replicated demes");
+ if(m_world->GetConfig().DEMES_USE_GERMLINE.Get() && m_world->GetConfig().DEMES_HAVE_MERIT.Get()) {
+ df.Write(_deme_merit.Average(), "mean merit of replicated demes");
+ }
+ df.Endl();
+
+ _deme_repl_count = 0;
+ _deme_merit.Clear();
+ _deme_age.Clear();
+}
Modified: branches/dkdev/source/main/cStats.h
===================================================================
--- branches/dkdev/source/main/cStats.h 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/main/cStats.h 2007-06-07 02:24:12 UTC (rev 1653)
@@ -202,12 +202,19 @@
int num_used;
int num_own_used;
- int m_topo_numReplications; //!< Number of deme replications since the last stats output.
- cDoubleSum m_topo_numEdges; //!< Average number of edges per deme upon replication.
- cDoubleSum m_topo_meanLsp; //!< Mean longest shortest-path in the network.
- cDeme::Network m_topo_lastNetwork; //!< The network resulting from the last replication.
- cGermline m_topo_germline; //!< The germline that built the network above.
+ 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.
+ 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
@@ -552,8 +559,17 @@
void PrintMarketData(const cString& filename);
// Topology
- void ConnectedTopology(cDeme& deme, double meanlsp=0.0);
+ void Topology(cDeme::Network& network);
+ void TopologyConnected(cDeme::Network& network);
+ void TopologyLSP(double meanlsp, double maxlsp);
+ void TopologyReplication(cDeme::Network& network);
void PrintTopologyData(const cString& filename);
+ void PrintLastTopology();
+
+ // Demes
+ void DemeReplication(cDeme& deme);
+ void PrintDemeData(const cString& filename);
+ void PrintLastGermline();
};
Modified: branches/dkdev/source/tools/CMakeLists.txt
===================================================================
--- branches/dkdev/source/tools/CMakeLists.txt 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/tools/CMakeLists.txt 2007-06-07 02:24:12 UTC (rev 1653)
@@ -30,6 +30,7 @@
cStringUtil.cc
cThread.cc
cTools.cc
+ cTopology.cc
cWeightedIndex.cc
cCycleCheck.cc
)
Added: branches/dkdev/source/tools/cTopology.cc
===================================================================
--- branches/dkdev/source/tools/cTopology.cc (rev 0)
+++ branches/dkdev/source/tools/cTopology.cc 2007-06-07 02:24:12 UTC (rev 1653)
@@ -0,0 +1,63 @@
+#include <algorithm>
+#include <cmath>
+
+#include "cTopology.h"
+#include "nGeometry.h"
+
+/*! Calculates the maximum number of connections in a given region and geometry. */
+int cTopology::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;
+}
+
+
+/*! Calculates the minimal diameter in a given region and geometry.
+Technically, this is the minimal mean longest shortest-path, over all cells. */
+int cTopology::min_diameter(int geometry, unsigned int rowSize, unsigned int colSize) {
+ switch(geometry) {
+ case nGeometry::GRID: {
+ return std::max(rowSize, colSize) - 1;
+ }
+ case nGeometry::TORUS: {
+ // Not sure about this... no time...
+ //return ceil(std::max(rowSize, colSize) / 2);
+ assert(false);
+ }
+ case nGeometry::CLIQUE: {
+ return 1;
+ }
+ default: {
+ assert(false);
+ break;
+ }
+ }
+}
Modified: branches/dkdev/source/tools/cTopology.h
===================================================================
--- branches/dkdev/source/tools/cTopology.h 2007-06-06 19:14:49 UTC (rev 1652)
+++ branches/dkdev/source/tools/cTopology.h 2007-06-07 02:24:12 UTC (rev 1653)
@@ -10,13 +10,10 @@
#ifndef _TOPOLOGY_H_
#define _TOPOLOGY_H_
-#include <algorithm>
-#include <cmath>
-
#include "functions.h"
-#include "nGeometry.h"
-
+namespace cTopology {
+
/*! 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.
@@ -97,62 +94,14 @@
/*! 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;
-}
+int max_connections(int geometry, unsigned int rowSize, unsigned int colSize);
/*! Calculates the minimal diameter in a given region and geometry.
Technically, this is the minimal mean longest shortest-path, over all cells. */
-int min_diameter(int geometry, unsigned int rowSize, unsigned int colSize) {
- switch(geometry) {
- case nGeometry::GRID: {
- return std::max(rowSize, colSize) - 1;
- }
- case nGeometry::TORUS: {
- // Not sure about this... no time...
- //return ceil(std::max(rowSize, colSize) / 2);
- assert(false);
- }
- case nGeometry::CLIQUE: {
- return 1;
- }
- default: {
- assert(false);
- break;
- }
- }
-}
+int min_diameter(int geometry, unsigned int rowSize, unsigned int colSize);
+} // namespace cTopology
+
#endif
More information about the Avida-cvs
mailing list