[Avida-SVN] r3430 - in development/source: actions main tools
dk at myxo.css.msu.edu
dk at myxo.css.msu.edu
Tue Sep 29 13:26:22 PDT 2009
Author: dk
Date: 2009-09-29 16:26:21 -0400 (Tue, 29 Sep 2009)
New Revision: 3430
Modified:
development/source/actions/PopulationActions.cc
development/source/main/cAvidaConfig.h
development/source/main/cOrgMessagePredicate.h
development/source/main/cPopulation.cc
development/source/main/nGeometry.h
development/source/tools/cTopology.h
Log:
merging data distribution actions, etc.
Modified: development/source/actions/PopulationActions.cc
===================================================================
--- development/source/actions/PopulationActions.cc 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/actions/PopulationActions.cc 2009-09-29 20:26:21 UTC (rev 3430)
@@ -1926,23 +1926,43 @@
typedef std::vector<int> CellIDList;
typedef std::map<int, std::set<int> > DataMap;
- cAssignRandomCellData(cWorld* world, const cString& args) : cAction(world, args) { }
-
+ //! Constructor.
+ cAssignRandomCellData(cWorld* world, const cString& args) : cAction(world, args), _num_cells(0) {
+ if(args.GetSize()) {
+ cString largs(args);
+ _num_cells = largs.PopWord().AsInt();
+ }
+ }
+
+ //! Destructor.
virtual ~cAssignRandomCellData() { }
- static const cString GetDescription() { return "No Arguments"; }
-
+ //! Description of this event; only possible argument is the number of cells whose data is to be set.
+ static const cString GetDescription() { return "Arguments: [num_cells=deme_size]"; }
+
+ //! Process this event, setting the requested number of cell's data to a random value.
virtual void Process(cAvidaContext& ctx) {
- deme_to_id.clear();
- for(int i=0; i<m_world->GetPopulation().GetNumDemes(); ++i) {
+ for(int i=0; i<m_world->GetPopulation().GetNumDemes(); ++i) {
cDeme& deme = m_world->GetPopulation().GetDeme(i);
- for(int j=0; j<deme.GetSize(); ++j) {
+ zero_cell_data(deme);
+ if((_num_cells == 0) || (_num_cells >= deme.GetSize())) {
// Assign random data to each cell:
- int d = m_world->GetRandom().GetInt(INT_MAX);
- deme.GetCell(j).SetCellData(d);
- // Save that data by deme in the map:
- deme_to_id[deme.GetID()].insert(d);
- }
+ for(int j=0; j<deme.GetSize(); ++j) {
+ int d = m_world->GetRandom().GetInt(INT_MAX);
+ deme.GetCell(j).SetCellData(d);
+ // Save that data by deme in the map:
+ deme_to_id[deme.GetID()].insert(d);
+ }
+ } else {
+ // Assign random data to exactly num_cells cells, with replacement:
+ for(int j=0; j<_num_cells; ++j) {
+ int cell = m_world->GetRandom().GetInt(deme.GetSize());
+ int d = m_world->GetRandom().GetInt(INT_MAX);
+ deme.GetCell(cell).SetCellData(d);
+ // Save that data by deme in the map:
+ deme_to_id[deme.GetID()].insert(d);
+ }
+ }
}
}
@@ -2002,7 +2022,15 @@
}
protected:
+ virtual void zero_cell_data(cDeme& deme) {
+ deme_to_id[deme.GetID()].clear();
+ for(int j=0; j<deme.GetSize(); ++j) {
+ deme.GetCell(j).SetCellData(0);
+ }
+ }
+
static std::map<int, std::set<int> > deme_to_id; //!< Map of deme ID -> set of all cell data in that deme.
+ int _num_cells; //!< The number of cells in each deme whose cell-data is to be set.
};
//! Definition for static data.
@@ -2133,6 +2161,82 @@
};
+/*! This class rewards for data distribution among organisms in a deme.
+
+ Specifically, "data" injected into a single cell-data field in the deme should eventually
+ be readable from another cell in the same deme.
+
+ For injecting data, we use the AssignRandomCellData event (num_cells=1), and we use opinions
+ to determine when data has reached another cell.
+
+ This action does not examine efficiency of distributing data.
+ */
+class cActionDistributeData : public cAbstractCompeteDemes {
+public:
+ cActionDistributeData(cWorld* world, const cString& args) : cAbstractCompeteDemes(world, args) {
+ world->GetStats().AddMessagePredicate(&m_message_counter);
+ }
+
+ //! Destructor.
+ virtual ~cActionDistributeData() { }
+
+ static const cString GetDescription() { return "No arguments."; }
+
+ //! Calculate the current fitness of this deme.
+ virtual double Fitness(cDeme& deme) {
+ return pow((double)received_data(deme) + 1.0, 2.0);
+ }
+
+protected:
+ //! Return how many organisms have received the data, and then set their opinion correctly.
+ unsigned int received_data(const cDeme& deme) {
+ // What is the data we're trying to distribute in this deme?
+ int data = *cAssignRandomCellData::GetDataInDeme(deme).begin();
+
+ // How many organisms in this deme are reflecting that piece of data?
+ unsigned int count=0;
+ for(int i=0; i<deme.GetSize(); ++i) {
+ cOrganism* org = deme.GetOrganism(i);
+ if((org != 0) && org->HasOpinion() && (org->GetOpinion().first==data)) {
+ ++count;
+ }
+ }
+ return count;
+ }
+
+ cOrgMessagePred_CountDemeMessages m_message_counter;
+};
+
+
+class cActionDistributeDataEfficiently : public cActionDistributeData {
+public:
+ cActionDistributeDataEfficiently(cWorld* world, const cString& args) : cActionDistributeData(world, args) {
+ }
+
+ //! Destructor.
+ virtual ~cActionDistributeDataEfficiently() { }
+
+ static const cString GetDescription() { return "No arguments."; }
+
+ //! Calculate the current fitness of this deme.
+ virtual double Fitness(cDeme& deme) {
+ // First, get the number that have received the data (and set their opinion):
+ unsigned int received = received_data(deme);
+
+ // If not everyone has the data yet, we're done:
+ if(received < (unsigned int)deme.GetSize()) {
+ return pow((double)received + 1.0, 2.0);
+ }
+
+ // Now, reward for reducing the number of messages that were used:
+ // The size of the deme is the theoretical minimum number of messages that could be used.
+ double size = deme.GetSize() * 1000; // Scaled by 1000 (arbitrary) to get the fraction > 1.0.
+ double msg_count = m_message_counter.GetMessageCount(deme);
+ return pow(received + 1.0 + size / msg_count, 2.0);
+ }
+};
+
+
/*! This class contains methods that are useful for consensus-related problems.
*/
class ConsensusSupport {
@@ -3901,6 +4005,8 @@
action_lib->Register<cAbstractCompeteDemes_AttackKillAndEnergyConserve>("CompeteDemes_AttackKillAndEnergyConserve");
action_lib->Register<cAssignRandomCellData>("AssignRandomCellData");
+ action_lib->Register<cActionDistributeData>("DistributeData");
+ action_lib->Register<cActionDistributeDataEfficiently>("DistributeDataEfficiently");
action_lib->Register<cActionCompeteDemesByNetwork>("CompeteDemesByNetwork");
action_lib->Register<cActionIteratedConsensus>("IteratedConsensus");
action_lib->Register<cActionCountOpinions>("CountOpinions");
Modified: development/source/main/cAvidaConfig.h
===================================================================
--- development/source/main/cAvidaConfig.h 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/main/cAvidaConfig.h 2009-09-29 20:26:21 UTC (rev 3430)
@@ -282,6 +282,9 @@
CONFIG_ADD_VAR(WORLD_Y, int, 60, "Height of the Avida world");
CONFIG_ADD_VAR(WORLD_Z, int, 1, "Depth of the Avida world");
CONFIG_ADD_VAR(WORLD_GEOMETRY, int, 2, "1 = Bounded Grid\n2 = Torus\n3 = Clique\n4 = Hexagonal grid\n5 = Lattice");
+ CONFIG_ADD_VAR(SCALE_FREE_M, int, 3, "Number of connections to add per cell when using a scale-free geometry.");
+ CONFIG_ADD_VAR(SCALE_FREE_ALPHA, double, 1.0, "Attachment power (1=linear).");
+ CONFIG_ADD_VAR(SCALE_FREE_ZERO_APPEAL, double, 0.0, "Appeal of cells with zero connections.");
CONFIG_ADD_VAR(RANDOM_SEED, int, 0, "Random number seed (0 for based on time)");
CONFIG_ADD_VAR(HARDWARE_TYPE, int, 0, "0 = Original CPUs\n1 = New SMT CPUs\n2 = Transitional SMT\n3 = Experimental CPU\n4 = Gene Expression CPU");
CONFIG_ADD_VAR(SPECULATIVE, bool, 1, "Enable speculative execution");
Modified: development/source/main/cOrgMessagePredicate.h
===================================================================
--- development/source/main/cOrgMessagePredicate.h 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/main/cOrgMessagePredicate.h 2009-09-29 20:26:21 UTC (rev 3430)
@@ -35,8 +35,25 @@
#include <functional>
#include <set>
#include <vector>
+#include <numeric>
+/*! An STL-compatible adaptable binary function to do fun things with maps. */
+template <typename InputIterator, typename BinaryFunction>
+struct apply2nd {
+ typedef typename InputIterator::value_type::second_type first_argument_type;
+ typedef typename InputIterator::value_type second_argument_type;
+ typedef typename BinaryFunction::result_type result_type;
+
+ apply2nd() : _op(BinaryFunction()) { }
+
+ result_type operator()(first_argument_type& x, second_argument_type& y) {
+ return _op(x, y.second);
+ }
+
+ BinaryFunction _op;
+};
+
/*! \brief An STL-compatible predicate on cOrgMessages. The intent here is to
provide a straightforward way to track arbitrary messages *wherever* they appear
in the population. The most utility can be had from message predicates if they're
@@ -54,6 +71,49 @@
};
+struct cOrgMessagePred_CountDemeMessages : public cOrgMessagePredicate {
+ typedef std::map<int, int> MessageCounts; //!< Typedef to track messages sent per-deme.
+
+ cOrgMessagePred_CountDemeMessages() { }
+ ~cOrgMessagePred_CountDemeMessages() { }
+
+ virtual bool operator()(const cOrgMessage& msg) {
+ // Make sure we're not running in the test cpu (is that even possible here?):
+ cDeme* deme = msg.GetSender()->GetOrgInterface().GetDeme();
+ if(deme == 0) { return false; }
+
+ // Now, we're just keeping a count of the messages being sent in each deme.
+ ++m_msg_counts[deme->GetID()];
+ return true;
+ }
+
+ virtual void Print(int update, std::ostream& out) {
+ out << update << " COUNT " <<
+ std::accumulate(m_msg_counts.begin(), m_msg_counts.end(), 0, apply2nd<MessageCounts::iterator, plus<int> >()) << " ";
+ for(MessageCounts::iterator i=m_msg_counts.begin(); i!=m_msg_counts.end(); ++i) {
+ out << " " << i->second;
+ }
+ out << std::endl;
+ }
+
+ virtual void Reset() {
+ m_msg_counts.clear();
+ }
+
+ // What do these do, and why are they in the base struct?
+ virtual bool PreviouslySatisfied() { return false; }
+ virtual cString GetName() { return "cOrgMessagePred_CountDemeMessages"; }
+ virtual void UpdateStats(cStats& stats) { }
+ virtual cDemeCellEvent* GetEvent() { return NULL; }
+
+ int GetMessageCount(const cDeme& deme) {
+ return m_msg_counts[deme.GetID()];
+ }
+
+ MessageCounts m_msg_counts; //!< Map of deme ID to message counts.
+};
+
+
/*! A predicate that tracks all sent messages. */
struct cOrgMessagePred_AllData : public cOrgMessagePredicate
{
Modified: development/source/main/cPopulation.cc
===================================================================
--- development/source/main/cPopulation.cc 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/main/cPopulation.cc 2009-09-29 20:26:21 UTC (rev 3430)
@@ -119,6 +119,9 @@
case nGeometry::HEX: { cout << "Geometry: Hex" << endl; break; }
case nGeometry::LATTICE: { cout << "Geometry: Lattice" << endl; break; }
case nGeometry::PARTIAL: { cout << "Geometry: Partial" << endl; break; }
+ case nGeometry::RANDOM_CONNECTED: { cout << "Geometry: Random connected" << endl; break; }
+ case nGeometry::SCALE_FREE: { cout << "Geometry: Scale-free" << endl; break; }
+
default:
cout << "Unknown geometry!" << endl;
assert(false);
@@ -212,6 +215,16 @@
case nGeometry::LATTICE:
build_lattice(&cell_array.begin()[i], &cell_array.begin()[i+deme_size], deme_size_x, deme_size_y, world_z);
break;
+ case nGeometry::RANDOM_CONNECTED:
+ build_random_connected_network(&cell_array.begin()[i], &cell_array.begin()[i+deme_size], deme_size_x, deme_size_y, m_world->GetRandom());
+ break;
+ case nGeometry::SCALE_FREE:
+ build_scale_free(&cell_array.begin()[i], &cell_array.begin()[i+deme_size],
+ world->GetConfig().SCALE_FREE_M.Get(),
+ world->GetConfig().SCALE_FREE_ALPHA.Get(),
+ world->GetConfig().SCALE_FREE_ZERO_APPEAL.Get(),
+ m_world->GetRandom());
+ break;
default:
assert(false);
}
Modified: development/source/main/nGeometry.h
===================================================================
--- development/source/main/nGeometry.h 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/main/nGeometry.h 2009-09-29 20:26:21 UTC (rev 3430)
@@ -34,8 +34,10 @@
TORUS,
CLIQUE,
HEX,
- PARTIAL,
- LATTICE
+ PARTIAL,
+ LATTICE,
+ RANDOM_CONNECTED,
+ SCALE_FREE
};
}
Modified: development/source/tools/cTopology.h
===================================================================
--- development/source/tools/cTopology.h 2009-09-29 18:35:36 UTC (rev 3429)
+++ development/source/tools/cTopology.h 2009-09-29 20:26:21 UTC (rev 3430)
@@ -178,4 +178,198 @@
}
}
+
+/*
+ Builds a random connected network topology for organisms to communicate through.
+
+ */
+template< typename InputIterator >
+void build_random_connected_network(InputIterator begin, InputIterator end, unsigned int x_size, unsigned int y_size, cRandom& rng) {
+
+ // keep track of boundaries for this deme:
+ int offset = begin->GetID();
+ int demeSize = x_size * y_size;
+
+ // keep track of cells that have been connected already:
+ std::set<int> connected_Cells;
+
+ InputIterator i, j, random_Connected_Cell;
+
+
+
+ for(i = begin; i != end; ++i) {
+ // select a random cell in this deme to connect to:
+ int targetCellID;
+ do {
+ targetCellID = rng.GetInt(0, demeSize);
+ } while((targetCellID + offset) == i->GetID());
+
+ j = &begin[targetCellID];
+
+ // verify no connection exists between i and j:
+ if(i->ConnectionList().FindPtr(j) == NULL) {
+ // create bidirectional connections:
+ i->ConnectionList().Push(j);
+ j->ConnectionList().Push(i);
+
+ // check if either i or j is connected to the
+ // main graph:
+ if(connected_Cells.count(i->GetID()) == 0 && connected_Cells.count(j->GetID()) == 0) {
+ // neither i nor j is connected to the main graph
+
+ // check if main network is empty:
+ if(connected_Cells.empty()) {
+ connected_Cells.insert(i->GetID());
+ connected_Cells.insert(j->GetID());
+ } else {
+ // pick some random cell that is connected:
+ int randomIndex = rng.GetInt(0, connected_Cells.size());
+ int counter = 0;
+ int idValue = 0;
+ set<int>::iterator pos;
+ for(pos = connected_Cells.begin(); pos != connected_Cells.end(); ++pos) {
+ if(counter == randomIndex) {
+ idValue = *pos;
+ break;
+ } else {
+ counter++;
+ }
+ }
+
+ // retrieve the actual cell:
+ random_Connected_Cell = &begin[idValue-offset];
+
+ // randomly select i or j to connect with main network:
+ int zeroOrOne = rng.GetInt(0,2);
+
+ if(zeroOrOne) {
+ // connect i to main network:
+ i->ConnectionList().Push(random_Connected_Cell);
+ random_Connected_Cell->ConnectionList().Push(i);
+ } else {
+ // connect j to main network:
+ j->ConnectionList().Push(random_Connected_Cell);
+ random_Connected_Cell->ConnectionList().Push(j);
+ }
+
+ // add both cells to the main network:
+ // don't care about duplicates...
+ connected_Cells.insert(i->GetID());
+ connected_Cells.insert(j->GetID());
+ }
+
+ } else {
+ connected_Cells.insert(i->GetID());
+ connected_Cells.insert(j->GetID());
+ }
+ }
+ }
+
+
+ // the code above ensures that we have *at the least* a random connected
+ // bidirectional network.
+ // sprinkle additional edges between the cells:
+
+ // we are going to add random extra edges... note demeSize bound is arbitrary.
+ int extraEdges = rng.GetInt(0, demeSize);
+ int a, b;
+
+ for(int n = 0; n < extraEdges; ++n) {
+ // must select two random cells from the network:
+ a = rng.GetInt(0,demeSize);
+ b = rng.GetInt(0,demeSize);
+
+ while(a == b)
+ b = rng.GetInt(0,demeSize);
+
+ i = &begin[a];
+ j = &begin[b];
+
+ // check for existing connection between the two:
+ if(i->ConnectionList().FindPtr(j) == NULL) {
+ i->ConnectionList().Push(j);
+ j->ConnectionList().Push(i);
+ }
+ }
+}
+
+
+//! Helper function to connect two cells.
+template <typename InputIterator>
+void connect(InputIterator u, InputIterator v) {
+ assert(u != v);
+ u->ConnectionList().Push(v);
+ v->ConnectionList().Push(u);
+}
+
+//! Helper function to test if two cells are already connected.
+template <typename InputIterator>
+bool edge(InputIterator u, InputIterator v) {
+ assert(u != v);
+ return u->ConnectionList().FindPtr(v) || v->ConnectionList().FindPtr(u);
+}
+
+
+/*! Builds a scale-free network from the given range of cells.
+
+ This function is an implementation of the Barab\'asi-Albert "preferential attachment"
+ algorithm for iteratively constructing a scale-free network.
+
+ If we think of the population as a graph G, where cells are vertices and connections
+ are edges, then |E(G)| is the number of edges in the graph and d(u \in V(G)) is the
+ degree of a vertex in that graph, the algorithm for preferential attachment is defined as:
+
+ Input:
+ m = number of edges to be added for each new vertex
+ alpha = "power," the degree to which vertices with large numbers of edges are weighted.
+ zero_appeal = offset to prefer vertices with 0 edges
+
+ Initialization:
+ G = a graph, where all nodes have degree >= 1
+
+ foreach vertex u to be added to G:
+ foreach vertex v \in G != u, where !e(u,v), and until m edges are added:
+ connect u-v with probability: (d(v)/|E(G)|)^alpha + zero_appeal
+ */
+template <typename InputIterator>
+void build_scale_free(InputIterator begin, InputIterator end, int m, double alpha, double zero_appeal, cRandom& rng) {
+ assert(begin != end);
+ assert(&begin[1] != end); // at least two vertices.
+ // Connect the first and second cells:
+ connect(&begin[0], &begin[1]);
+ // And initialize the edge and vertex counts:
+ int edge_count=1;
+ int vertex_count=2;
+
+ // Now, for each new vertex (that is, vertices 2+):
+ for(InputIterator u=&begin[2]; u!=end; ++u, ++vertex_count) {
+ // Figure out how many edges we can add:
+ int to_add = std::min(vertex_count, m);
+ int added=0;
+ // Loop through all the vertices currently in the graph:
+ InputIterator v=begin;
+ while(added < to_add) {
+ // If we haven't already connected u and v:
+ if(!edge(u, v)) {
+ // Connect them with P = (d(v)/|E(G)|)^alpha + zero_appeal:
+ double p_edge = (double)v->ConnectionList().GetSize() / edge_count;
+ p_edge = pow(p_edge, alpha) + zero_appeal;
+ // Protect against negative and over-large probabilities:
+ assert(p_edge >= 0.0);
+ p_edge = std::min(p_edge, 1.0);
+ // Probabilistically connect u and v:
+ if(rng.P(p_edge)) {
+ connect(u, v);
+ ++edge_count;
+ ++added;
+ }
+ }
+ // Loop back around to the beginning - note that u is the current end, 'cause
+ // building this graph is an iterative process.
+ if(++v == u) { v = begin; }
+ }
+ }
+}
+
+
#endif
More information about the Avida-cvs
mailing list