Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


state_machine.h
1 /*
2  Evocosm is a C++ framework for implementing evolutionary algorithms.
3 
4  Copyright 2011 Scott Robert Ladd. All rights reserved.
5 
6  Evocosm is user-supported open source software. Its continued development is dependent
7  on financial support from the community. You can provide funding by visiting the Evocosm
8  website at:
9 
10  http://www.coyotegulch.com
11 
12  You may license Evocosm in one of two fashions:
13 
14  1) Simplified BSD License (FreeBSD License)
15 
16  Redistribution and use in source and binary forms, with or without modification, are
17  permitted provided that the following conditions are met:
18 
19  1. Redistributions of source code must retain the above copyright notice, this list of
20  conditions and the following disclaimer.
21 
22  2. Redistributions in binary form must reproduce the above copyright notice, this list
23  of conditions and the following disclaimer in the documentation and/or other materials
24  provided with the distribution.
25 
26  THIS SOFTWARE IS PROVIDED BY SCOTT ROBERT LADD ``AS IS'' AND ANY EXPRESS OR IMPLIED
27  WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
28  FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SCOTT ROBERT LADD OR
29  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30  CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
31  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
32  ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
33  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
34  ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 
36  The views and conclusions contained in the software and documentation are those of the
37  authors and should not be interpreted as representing official policies, either expressed
38  or implied, of Scott Robert Ladd.
39 
40  2) Closed-Source Proprietary License
41 
42  If your project is a closed-source or proprietary project, the Simplified BSD License may
43  not be appropriate or desirable. In such cases, contact the Evocosm copyright holder to
44  arrange your purchase of an appropriate license.
45 
46  The author can be contacted at:
47 
48  scott.ladd@coyotegulch.com
49  scott.ladd@gmail.com
50  http:www.coyotegulch.com
51 */
52 
53 #if !defined(LIBEVOCOSM_FSM_H)
54 #define LIBEVOCOSM_FSM_H
55 
56 // Standard C++ Library
57 #include <cstddef>
58 #include <vector>
59 #include <map>
60 #include <stack>
61 #include <stdexcept>
62 using namespace std;
63 
64 // libevocosm
65 #include "evocommon.h"
66 #include "roulette.h"
67 #include "machine_tools.h"
68 
69 namespace libevocosm
70 {
72 
86  template <typename InputT, typename OutputT>
87  class state_machine : protected globals, protected fsm_tools
88  {
89  public:
91  typedef InputT t_input;
92 
94  typedef OutputT t_output;
95 
97  typedef typename std::pair<t_output, size_t> t_transition;
98 
100  typedef typename std::map<t_input, t_transition> t_input_map;
101 
103  typedef typename std::vector<t_input_map> t_state_table;
104 
106 
113  state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
114 
116 
125  state_machine(const state_machine<InputT,OutputT> & a_parent1, const state_machine<InputT,OutputT> & a_parent2);
126 
128 
133 
135 
139  virtual ~state_machine();
140 
141  // Assignment
146  state_machine & operator = (const state_machine<InputT,OutputT> & a_source);
147 
149 
164  void mutate(double a_rate, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs, mutation_selector & a_selector = g_default_selector);
165 
167 
172  t_output transition(const state_machine<InputT,OutputT>::t_input & a_input);
173 
175 
178  void reset();
179 
181 
186  t_state_table get_table() const;
187 
189 
193  size_t get_init_state() const;
194 
196 
200  size_t get_current_state() const;
201 
202  protected:
204  t_state_table m_state_table;
205 
207  size_t m_size;
208 
210  size_t m_init_state;
211 
214 
216  static mutation_selector g_default_selector;
217 
218  private:
219  // create a state map
220  t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
221  };
222 
223  // Static initializer
224  template <typename InputT, typename OutputT>
226 
227  // Creation constructor
228  template <typename InputT, typename OutputT>
229  state_machine<InputT,OutputT>::state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
230  : m_state_table(),
231  m_init_state(0),
232  m_current_state(0),
233  m_size(a_size)
234  {
235  // verify parameters
236  if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1))
237  throw std::runtime_error("invalid state_machine creation parameters");
238 
239  for (size_t n = 0; n < m_size; ++n)
240  {
241  // add input map to state table
242  m_state_table.push_back(create_input_map(a_inputs,a_outputs));
243  }
244 
245  // set initial state and start there
246  m_init_state = rand_index(m_size);
248  }
249 
250  // Construct via bisexual crossover
251  template <typename InputT, typename OutputT>
253  : m_state_table(a_parent1.m_state_table),
254  m_init_state(0),
255  m_current_state(0),
256  m_size(0)
257  {
258  size_t n;
259 
260  // don't do anything else if fsms differ is size
261  if (a_parent1.m_size != a_parent2.m_size)
262  return;
263 
264  // replace states from those in second parent 50/50 chance
265  for (size_t n = 0; n < m_size; ++n)
266  {
267  if (g_random.get_real() > 0.5)
268  m_state_table[n] = a_parent2.m_state_table[n];
269  }
270 
271  // calculate the size
272  m_size = m_state_table.size();
273 
274  // randomize the initial state (looks like mom and dad but may act like either one!)
275  if (g_random.get_real() < 0.5)
276  m_init_state = a_parent1.m_init_state;
277  else
278  m_init_state = a_parent2.m_init_state;
279 
280  // reset for start
282  }
283 
284  // Copy constructor
285  template <typename InputT, typename OutputT>
287  : m_state_table(a_source.m_state_table),
288  m_init_state(a_source.m_init_state),
289  m_current_state(a_source.m_current_state),
290  m_size(a_source.m_size)
291  {
292  // nada
293  }
294 
295  // Virtual destructor
296  template <typename InputT, typename OutputT>
298  {
299  // nada
300  }
301 
302  // Assignment
303  template <typename InputT, typename OutputT>
305  {
306  if (this != &a_source)
307  {
308  m_state_table = a_source.m_state_table;
309  m_init_state = a_source.m_init_state;
310  m_current_state = a_source.m_current_state;
311  m_size = a_source.m_size;
312  }
313 
314  return *this;
315  }
316 
317  // Mutation
318  template <typename InputT, typename OutputT>
320  const std::vector<t_input> & a_inputs,
321  const std::vector<t_output> & a_outputs,
322  mutation_selector & a_selector)
323  {
324  if (g_random.get_real() < a_rate)
325  {
326  // pick a mutation
327  switch (a_selector.get_index())
328  {
329  case MUTATE_OUTPUT_SYMBOL:
330  {
331  // mutate output symbol
332  size_t state = rand_index(m_size);
333  size_t input = rand_index(a_inputs.size());
334  size_t output = rand_index(a_outputs.size());
335  m_state_table[state][a_inputs[input]].first = a_outputs[output];
336  break;
337  }
338  case MUTATE_TRANSITION:
339  {
340  // mutate state transition
341  size_t state = rand_index(m_size);
342  size_t input = rand_index(a_inputs.size());
343  size_t new_state = rand_index(m_size);
344  m_state_table[state][a_inputs[input]].second = new_state;
345  break;
346  }
347  case MUTATE_REPLACE_STATE:
348  {
349  // select state
350  size_t state = rand_index(m_size);
351  m_state_table[state] = create_input_map(a_inputs,a_outputs);
352  }
353  case MUTATE_SWAP_STATES:
354  {
355  // swap two states
356  size_t state1 = rand_index(m_size);
357  size_t state2;
358 
359  do
360  state2 = rand_index(m_size);
361  while (state2 == state1);
362 
363  t_input_map temp = m_state_table[state1];
364  m_state_table[state1] = m_state_table[state2];
365  m_state_table[state2] = temp;
366  break;
367  }
368  case MUTATE_INIT_STATE:
369  {
370  // change initial state
371  m_init_state = rand_index(m_size);
372  break;
373  }
374  }
375  }
376 
377  // reset current state because init state may have changed
378  m_current_state = m_init_state;
379  }
380 
381  // Cause state transition
382  template <typename InputT, typename OutputT>
384  {
385  // get transition state
386  t_transition & trans = m_state_table[m_current_state][a_input];
387 
388  // change to new state
389  m_current_state = trans.second;
390 
391  // return output symbol
392  return trans.first;
393  }
394 
395  // Reset to start-up state
396  template <typename InputT, typename OutputT>
398  {
399  m_current_state = m_init_state;
400  }
401 
402  // Get a copy of the internal table
403  template <typename InputT, typename OutputT>
405  {
406  return m_state_table;
407  }
408 
409  // Get initial state
410  template <typename InputT, typename OutputT>
412  {
413  return m_init_state;
414  }
415 
416  // Get current state
417  template <typename InputT, typename OutputT>
419  {
420  return m_current_state;
421  }
422 
423  // create a state map
424  template <typename InputT, typename OutputT>
425  typename state_machine<InputT,OutputT>::t_input_map state_machine<InputT,OutputT>::create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
426  {
427  // maximum output index
428  size_t max_output = a_outputs.size();
429 
430  // create an input map for this state
431  t_input_map input_map;
432 
433  // for each input, define an output and a state transition
434  for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input)
435  {
436  // pick a random output symbol and new state
437  t_output out_symbol = a_outputs[rand_index(max_output)];
438  size_t new_state = rand_index(m_size);
439 
440  // add transition data to map
441  input_map[*input] = std::make_pair(out_symbol,new_state);
442  }
443 
444  return input_map;
445  }
446 };
447 
448 #endif
size_t get_init_state() const
Get initial state.
Definition: state_machine.h:411
InputT t_input
Exported input type.
Definition: state_machine.h:91
static mutation_selector g_default_selector
A static, default mutation selector.
Definition: state_machine.h:216
t_output transition(const state_machine< InputT, OutputT >::t_input &a_input)
Cause state transition.
Definition: state_machine.h:383
size_t m_current_state
Current state.
Definition: state_machine.h:213
void mutate(double a_rate, const std::vector< t_input > &a_inputs, const std::vector< t_output > &a_outputs, mutation_selector &a_selector=g_default_selector)
Mutation.
Definition: state_machine.h:319
t_state_table get_table() const
Get a copy of the internal table.
Definition: state_machine.h:404
OutputT t_output
Exported output type.
Definition: state_machine.h:94
virtual ~state_machine()
Virtual destructor.
Definition: state_machine.h:297
size_t get_current_state() const
Get current state.
Definition: state_machine.h:418
A toolkit and framework for implementing evolutionary algorithms.
Definition: analyzer.h:60
std::pair< t_output, size_t > t_transition
Type of a transition.
Definition: state_machine.h:97
size_t m_size
Number of states.
Definition: state_machine.h:207
state_machine & operator=(const state_machine< InputT, OutputT > &a_source)
Definition: state_machine.h:304
Elements shared by all classes in Evocosm.
Definition: evocommon.h:117
static prng g_random
A shared random number generator.
Definition: evocommon.h:127
A finite state machine.
Definition: state_machine.h:87
static size_t rand_index(size_t n)
Static function to allow use of g_random function pointer in random_shuffle.
Definition: evocommon.h:121
size_t m_init_state
Initial state.
Definition: state_machine.h:210
double get_real()
get the next value in the range [0,1)
Definition: evocommon.h:106
t_state_table m_state_table
State table (the machine definition)
Definition: state_machine.h:204
void reset()
Reset to start-up state.
Definition: state_machine.h:397
state_machine(size_t a_size, const std::vector< t_input > &a_inputs, const std::vector< t_output > &a_outputs)
Creation constructor.
Definition: state_machine.h:229
std::vector< t_input_map > t_state_table
State table (the machine)
Definition: state_machine.h:103
std::map< t_input, t_transition > t_input_map
Mapping inputs to outputs and state transitions.
Definition: state_machine.h:100

© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.