Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


simple_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_SIMPLE_FSM_H)
54 #define LIBEVOCOSM_SIMPLE_FSM_H
55 
56 // Standard C++ Library
57 #include <cstddef>
58 #include <stack>
59 #include <stdexcept>
60 using namespace std;
61 
62 // libevocosm
63 #include "evocommon.h"
64 #include "machine_tools.h"
65 
66 namespace libevocosm
67 {
69 
77  template <size_t InSize, size_t OutSize>
78  class simple_machine : protected globals, protected machine_tools
79  {
80  public:
82  struct tranout_t
83  {
85  size_t m_new_state;
86 
88  size_t m_output;
89  };
90 
92 
96  simple_machine(size_t a_size);
97 
99 
105 
107 
112 
114 
118  virtual ~simple_machine();
119 
120  // Assignment
126  simple_machine & operator = (const simple_machine<InSize,OutSize> & a_source);
127 
129 
141  void mutate(double a_rate);
142 
144 
150  static void set_mutation_weight(mutation_id a_type, double a_weight);
151 
153 
159  size_t transition(size_t a_input);
160 
162 
165  void reset();
166 
168 
172  size_t size() const;
173 
175 
181  const tranout_t & get_transition(size_t a_state, size_t a_input) const;
182 
184 
188  size_t num_input_states() const;
189 
191 
195  size_t num_output_states() const;
196 
198 
202  size_t init_state() const;
203 
205 
209  size_t current_state() const;
210 
211  private:
212  // release resources
213  void release();
214 
215  // deep copy
216  void deep_copy(const simple_machine<InSize,OutSize> & a_source);
217 
218  protected:
221 
223  size_t m_init_state;
224 
227 
229  size_t m_size;
230 
232  static mutation_selector g_selector;
233  };
234 
235  // Static initializer
236  template <size_t InSize, size_t OutSize>
238 
239  // release resources
240  template <size_t InSize, size_t OutSize>
242  {
243  for (size_t s = 0; s < m_size; ++s)
244  delete [] m_state_table[s];
245 
246  delete [] m_state_table;
247  }
248 
249  // deep copy
250  template <size_t InSize, size_t OutSize>
251  void simple_machine<InSize,OutSize>::deep_copy(const simple_machine<InSize,OutSize> & a_source)
252  {
253  // allocate state table
254  m_state_table = new tranout_t * [m_size];
255 
256  for (size_t s = 0; s < m_size; ++s)
257  {
258  // allocate an array corresponding to inputs
259  m_state_table[s] = new tranout_t [InSize];
260 
261  // set transition values
262  for (size_t i = 0; i < InSize; ++i)
263  {
264  m_state_table[s][i].m_new_state = a_source.m_state_table[s][i].m_new_state;
265  m_state_table[s][i].m_output = a_source.m_state_table[s][i].m_output;
266  }
267  }
268  }
269 
270  // Creation constructor
271  template <size_t InSize, size_t OutSize>
273  : m_state_table(NULL),
274  m_init_state(0),
275  m_current_state(0),
276  m_size(a_size)
277  {
278  // verify parameters
279  if (m_size < 2)
280  throw std::runtime_error("invalid simple_machine creation parameters");
281 
282  // allocate state table
283  m_state_table = new tranout_t * [m_size];
284 
285  for (size_t s = 0; s < m_size; ++s)
286  {
287  // allocate an array corresponding to inputs
288  m_state_table[s] = new tranout_t [InSize];
289 
290  // set transition values
291  for (size_t i = 0; i < InSize; ++i)
292  {
293  m_state_table[s][i].m_new_state = rand_index(m_size);
294  m_state_table[s][i].m_output = rand_index(OutSize);
295  }
296  }
297 
298  // set initial state and start there
299  m_init_state = rand_index(m_size);
301  }
302 
303  // Construct via bisexual crossover
304  template <size_t InSize, size_t OutSize>
306  : m_state_table(NULL),
307  m_init_state(0),
308  m_current_state(0),
309  m_size(a_parent1.m_size)
310  {
311  // copy first parent
312  deep_copy(a_parent1);
313 
314  // don't do anything else if fsms differ is size
315  if (a_parent1.m_size != a_parent2.m_size)
316  return;
317 
318  // replace states from those in second parent 50/50 chance
319  size_t x = rand_index(m_size);
320 
321  for (size_t n = x; n < m_size; ++n)
322  {
323  // set transition values
324  for (size_t i = 0; i < InSize; ++i)
325  {
326  m_state_table[n][i].m_new_state = a_parent2.m_state_table[n][i].m_new_state;
327  m_state_table[n][i].m_output = a_parent2.m_state_table[n][i].m_output;
328  }
329  }
330 
331  // randomize the initial state (looks like mom and dad but may act like either one!)
332  if (g_random.get_real() < 0.5)
333  m_init_state = a_parent1.m_init_state;
334  else
335  m_init_state = a_parent2.m_init_state;
336 
337  // reset for start
339  }
340 
341  // Copy constructor
342  template <size_t InSize, size_t OutSize>
344  : m_state_table(NULL),
345  m_init_state(a_source.m_init_state),
346  m_current_state(a_source.m_current_state),
347  m_size(a_source.m_size)
348  {
349  // copy first parent
350  deep_copy(a_source);
351  }
352 
353  // Virtual destructor
354  template <size_t InSize, size_t OutSize>
356  {
357  release();
358  }
359 
360  // Assignment
361  template <size_t InSize, size_t OutSize>
363  {
364  // release resources
365  release();
366 
367  // set values
368  m_init_state = a_source.m_init_state;
369  m_current_state = a_source.m_current_state;
370  m_size = a_source.m_size;
371 
372  // copy source
373  deep_copy(a_source);
374 
375  return *this;
376  }
377 
379  template <size_t InSize, size_t OutSize>
381  {
382  g_selector.set_weight(a_type,a_weight);
383  }
384 
385  // Mutation
386  template <size_t InSize, size_t OutSize>
388  {
389  // the number of chances for mutation is based on the number of states in the machine;
390  // larger machines thus encounter more mutations
391  for (size_t n = 0; n < m_size; ++n)
392  {
393  if (g_random.get_real() < a_rate)
394  {
395  // pick a mutation
396  switch (g_selector.get_index())
397  {
398  case MUTATE_OUTPUT_SYMBOL:
399  {
400  // mutate output symbol
401  size_t state = rand_index(m_size);
402  size_t input = rand_index(InSize);
403 
404  size_t choice;
405 
406  do
407  {
408  choice = rand_index(OutSize);
409  }
410  while (m_state_table[state][input].m_output == choice);
411 
412  m_state_table[state][input].m_output = choice;
413  break;
414  }
415  case MUTATE_TRANSITION:
416  {
417  // mutate state transition
418  size_t state = rand_index(m_size);
419  size_t input = rand_index(InSize);
420 
421  size_t choice;
422 
423  do
424  {
425  choice = rand_index(m_size);
426  }
427  while (m_state_table[state][input].m_new_state == choice);
428 
429  m_state_table[state][input].m_new_state = choice;
430  break;
431  }
432  case MUTATE_REPLACE_STATE:
433  {
434  // mutate state transition
435  size_t state = rand_index(m_size);
436 
437  // allocate an array corresponding to inputs
438  delete [] m_state_table[state];
439  m_state_table[state] = new tranout_t [InSize];
440 
441  // set transition values
442  for (size_t i = 0; i < InSize; ++i)
443  {
444  m_state_table[state][i].m_new_state = rand_index(m_size);
445  m_state_table[state][i].m_output = rand_index(OutSize);
446  }
447 
448  break;
449  }
450  case MUTATE_SWAP_STATES:
451  {
452  // swap two states (by swapping pointers)
453  size_t state1 = rand_index(m_size);
454  size_t state2;
455 
456  do
457  state2 = rand_index(m_size);
458  while (state2 == state1);
459 
460  for (size_t i = 0; i < InSize; ++i)
461  {
462  tranout_t temp = m_state_table[state1][i];
463  m_state_table[state1][i] = m_state_table[state2][i];
464  m_state_table[state2][i] = temp;
465  }
466 
467  break;
468  }
469  case MUTATE_INIT_STATE:
470  {
471  // change initial state
472  size_t choice;
473 
474  do
475  {
476  choice = rand_index(m_size);
477  }
478  while (m_init_state == choice);
479 
480  m_init_state = choice;
481 
482  break;
483  }
484  }
485  }
486  }
487 
488  // reset current state because init state may have changed
489  m_current_state = m_init_state;
490  }
491 
492  // Cause state transition
493  template <size_t InSize, size_t OutSize>
494  inline size_t simple_machine<InSize,OutSize>::transition(size_t a_input)
495  {
496  // get output symbol for given input for current state
497  size_t output = m_state_table[m_current_state][a_input].m_output;
498 
499  // change to new state
500  m_current_state = m_state_table[m_current_state][a_input].m_new_state;
501 
502  // return output symbol
503  return output;
504  }
505 
506  // Reset to start-up state
507  template <size_t InSize, size_t OutSize>
509  {
510  m_current_state = m_init_state;
511  }
512 
513  // Get size
514  template <size_t InSize, size_t OutSize>
516  {
517  return m_size;
518  }
519 
520  // Get a copy of the internal table
521  template <size_t InSize, size_t OutSize>
522  inline const typename simple_machine<InSize,OutSize>::tranout_t & simple_machine<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
523  {
524  return m_state_table[a_state][a_input];
525  }
526 
527  // Get number of input states
528  template <size_t InSize, size_t OutSize>
530  {
531  return InSize;
532  }
533 
534  // Get number of output states
535  template <size_t InSize, size_t OutSize>
537  {
538  return OutSize;
539  }
540 
541  // Get initial state
542  template <size_t InSize, size_t OutSize>
544  {
545  return m_init_state;
546  }
547 
548  // Get current state
549  template <size_t InSize, size_t OutSize>
551  {
552  return m_current_state;
553  }
554 };
555 
556 #endif
Wraps a roulette wheel for selecting mutations.
Definition: machine_tools.h:95
size_t size() const
Get size.
Definition: simple_machine.h:515
Defines a transition and output state pair.
Definition: simple_machine.h:82
size_t num_output_states() const
Get number of output states.
Definition: simple_machine.h:536
mutation_id
Types of mutation supported.
Definition: machine_tools.h:69
static void set_mutation_weight(mutation_id a_type, double a_weight)
Set a mutation weight.
Definition: simple_machine.h:380
A set of common tools for finite state machines.
Definition: machine_tools.h:65
size_t m_output
The output value.
Definition: simple_machine.h:88
static mutation_selector g_selector
Global mutation selector.
Definition: simple_machine.h:232
simple_machine & operator=(const simple_machine< InSize, OutSize > &a_source)
Definition: simple_machine.h:362
tranout_t ** m_state_table
State table (the machine definition)
Definition: simple_machine.h:220
A toolkit and framework for implementing evolutionary algorithms.
Definition: analyzer.h:60
simple_machine(size_t a_size)
Creation constructor.
Definition: simple_machine.h:272
void reset()
Reset to start-up state.
Definition: simple_machine.h:508
Elements shared by all classes in Evocosm.
Definition: evocommon.h:117
size_t current_state() const
Get current state.
Definition: simple_machine.h:550
static prng g_random
A shared random number generator.
Definition: evocommon.h:127
size_t m_current_state
Current state.
Definition: simple_machine.h:226
const tranout_t & get_transition(size_t a_state, size_t a_input) const
Get a transition from the internal state table.
Definition: simple_machine.h:522
size_t m_new_state
The state to be transitioned to.
Definition: simple_machine.h:85
size_t init_state() const
Get initial state.
Definition: simple_machine.h:543
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: simple_machine.h:223
void mutate(double a_rate)
Mutation.
Definition: simple_machine.h:387
size_t num_input_states() const
Get number of input states.
Definition: simple_machine.h:529
double get_real()
get the next value in the range [0,1)
Definition: evocommon.h:106
size_t m_size
Number of states.
Definition: simple_machine.h:229
size_t transition(size_t a_input)
Cause state transition.
Definition: simple_machine.h:494
virtual ~simple_machine()
Virtual destructor.
Definition: simple_machine.h:355
A simple finite state machine with integer-indexed states.
Definition: simple_machine.h:78

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