Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


fuzzy_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_FUZZY_MACHINE_H)
54 #define LIBEVOCOSM_FUZZY_MACHINE_H
55 
56 // Standard C++ Library
57 #include <cstddef>
58 #include <stack>
59 #include <stdexcept>
60 #ifdef DEBUG
61 #include <iostream>
62 #include <iomanip>
63 #endif
64 using namespace std;
65 
66 // libevocosm
67 #include "evocommon.h"
68 #include "machine_tools.h"
69 
70 namespace libevocosm
71 {
73 
86  template <size_t InSize, size_t OutSize>
87  class fuzzy_machine : protected globals, protected machine_tools
88  {
89  public:
91  struct tranout_t
92  {
95 
98 
100  tranout_t(double * state_weights, size_t num_states, double * output_weights)
101  : m_new_state(state_weights, num_states),
102  m_output(output_weights, OutSize)
103  {
104  // nada
105  }
106 
108  tranout_t(const tranout_t & source)
109  : m_new_state(source.m_new_state),
110  m_output(source.m_output)
111  {
112  // nada
113  }
114 
116  tranout_t & operator = (const tranout_t & source)
117  {
118  m_new_state = source.m_new_state;
119  m_output = source.m_output;
120  return *this;
121  }
122  };
123 
125 
135  fuzzy_machine(size_t a_size,
136  double a_output_base,
137  double a_output_range,
138  double a_state_base,
139  double a_state_range);
140 
142 
146  fuzzy_machine(size_t a_size);
147 
149 
154  fuzzy_machine(const fuzzy_machine<InSize,OutSize> & a_parent1, const fuzzy_machine<InSize,OutSize> & a_parent2);
155 
157 
162 
164 
168  virtual ~fuzzy_machine();
169 
170  // Assignment
176  fuzzy_machine & operator = (const fuzzy_machine<InSize,OutSize> & a_source);
177 
179 
191  void mutate(double a_rate);
192 
194 
200  static void set_mutation_weight(mutation_id a_type, double a_weight);
201 
203 
209  size_t transition(size_t a_input);
210 
212 
215  void reset();
216 
218 
222  size_t size() const;
223 
225 
231  const tranout_t & get_transition(size_t a_state, size_t a_input) const;
232 
234 
238  size_t num_input_states() const;
239 
241 
245  size_t num_output_states() const;
246 
248 
252  size_t init_state() const;
253 
255 
259  size_t current_state() const;
260 
262 
273  {
274  return m_state_table;
275  }
276 
277  #ifdef DEBUG
278  void dump(const char * description, ostream & a_stream = cerr) const;
279  #endif
280 
281  private:
282  // release resources
283  void release();
284 
285  // deep copy
286  void deep_copy(const fuzzy_machine<InSize,OutSize> & a_source);
287 
288  protected:
291 
293  size_t m_size;
294 
296  size_t m_init_state;
297 
300 
303 
306 
308  double m_state_base;
309 
312 
315  };
316 
317  // Static initializer
318  template <size_t InSize, size_t OutSize>
320 
321  // release resources
322  template <size_t InSize, size_t OutSize>
324  {
325  for (size_t s = 0; s < m_size; ++s)
326  {
327  for (size_t i = 0; i < InSize; ++i)
328  delete m_state_table[s][i];
329 
330  delete [] m_state_table[s];
331  }
332 
333  delete [] m_state_table;
334  }
335 
336  // deep copy
337  template <size_t InSize, size_t OutSize>
338  void fuzzy_machine<InSize,OutSize>::deep_copy(const fuzzy_machine<InSize,OutSize> & a_source)
339  {
340  // allocate state table
341  m_state_table = new tranout_t ** [m_size];
342 
343  for (size_t s = 0; s < m_size; ++s)
344  {
345  // allocate an array corresponding to inputs
346  m_state_table[s] = new tranout_t * [InSize];
347 
348  // set transition values
349  for (size_t i = 0; i < InSize; ++i)
350  m_state_table[s][i] = new tranout_t(*(a_source.m_state_table[s][i]));
351  }
352  }
353 
354  // Creation constructor
355  template <size_t InSize, size_t OutSize>
357  double a_output_base,
358  double a_output_range,
359  double a_state_base,
360  double a_state_range)
361  : m_state_table(NULL),
362  m_size(a_size),
363  m_init_state(0),
364  m_current_state(0),
365  m_output_base(a_output_base),
366  m_output_range(a_output_range),
367  m_state_base(a_state_base),
368  m_state_range(a_state_range)
369  {
370  // verify parameters
371  if (m_size < 2)
372  throw std::runtime_error("invalid fuzzy_machine creation parameters");
373 
374  // allocate state table
375  m_state_table = new tranout_t ** [m_size];
376 
377  // tables of weights for roulette wheels
378  double * output_weights = new double[OutSize];
379  double * state_weights = new double[m_size];
380 
381  for (size_t s = 0; s < m_size; ++s)
382  {
383  // allocate an array corresponding to inputs
384  m_state_table[s] = new tranout_t * [InSize];
385 
386  for (size_t i = 0; i < InSize; ++i)
387  {
388  // define weights
389  size_t n;
390 
391  for (n = 0; n < OutSize; ++n)
392  output_weights[n] = g_random.get_real() * a_output_range + a_output_base;
393 
394  for (n = 0; n < m_size; ++n)
395  state_weights[n] = g_random.get_real() * a_state_range + a_state_base;
396 
397  // set transition values
398  m_state_table[s][i] = new tranout_t(state_weights,m_size,output_weights);
399  }
400  }
401 
402  delete [] output_weights;
403  delete [] state_weights;
404 
405  // set initial state and start there
406  m_init_state = rand_index(m_size);
408  }
409 
410  // Creation constructor
411  template <size_t InSize, size_t OutSize>
413  : m_state_table(NULL),
414  m_size(a_size),
415  m_init_state(0),
416  m_current_state(0),
417  m_output_base(1.0),
418  m_output_range(100.0),
419  m_state_base(1.0),
420  m_state_range(100.0)
421  {
422  // verify parameters
423  if (m_size < 2)
424  throw std::runtime_error("invalid fuzzy_machine creation parameters");
425 
426  // allocate state table
427  m_state_table = new tranout_t ** [m_size];
428 
429  // tables of weights for roulette wheels
430  double * output_weights = new double[OutSize];
431  double * state_weights = new double[m_size];
432 
433  for (size_t s = 0; s < m_size; ++s)
434  {
435  // allocate an array corresponding to inputs
436  m_state_table[s] = new tranout_t * [InSize];
437 
438  for (size_t i = 0; i < InSize; ++i)
439  {
440  // define weights
441  size_t n;
442 
443  for (n = 0; n < OutSize; ++n)
444  output_weights[n] = 1.0;
445 
446  output_weights[rand_index(OutSize)] = 100.0;
447 
448  for (n = 0; n < m_size; ++n)
449  state_weights[n] = 1.0;
450 
451  state_weights[rand_index(m_size)] = 100.0;
452 
453  // set transition values
454  m_state_table[s][i] = new tranout_t(state_weights,m_size,output_weights);
455  }
456  }
457 
458  delete [] output_weights;
459  delete [] state_weights;
460 
461  // set initial state and start there
462  m_init_state = rand_index(m_size);
464  }
465 
466  // Construct via bisexual crossover
467  template <size_t InSize, size_t OutSize>
469  : m_state_table(NULL),
470  m_size(a_parent1.m_size),
471  m_init_state(0),
472  m_current_state(0),
473  m_output_base(a_parent1.m_output_base),
474  m_output_range(a_parent1.m_output_range),
475  m_state_base(a_parent1.m_state_base),
476  m_state_range(a_parent1.m_state_range)
477  {
478  #ifdef DEBUG
479  cerr << "\n<< crossover operation >>\n";
480  a_parent1.dump("PARENT1");
481  a_parent2.dump("PARENT2");
482  #endif
483 
484  // copy first parent
485  deep_copy(a_parent1);
486 
487  // don't do anything else if fsms differ is size
488  if ((a_parent1.m_size != a_parent2.m_size) || (&a_parent1 == &a_parent2))
489  return;
490 
491  // pick a crossover point
492  size_t x = rand_index(m_size);
493 
494  #ifdef DEBUG
495  cerr << "crossover at " << x << "\n";
496  #endif
497 
498  for (size_t n = x; n < m_size; ++n)
499  {
500  // set transition values
501  for (size_t i = 0; i < InSize; ++i)
502  {
503  delete m_state_table[n][i];
504  m_state_table[n][i] = new tranout_t(*a_parent2.m_state_table[n][i]);
505  }
506  }
507 
508  // randomize the initial state (looks like mom and dad but may act like either one!)
509  if (g_random.get_real() < 0.5)
510  m_init_state = a_parent1.m_init_state;
511  else
512  m_init_state = a_parent2.m_init_state;
513 
514  // reset for start
516 
517  #ifdef DEBUG
518  dump("CHILD");
519  #endif
520  }
521 
522  // Copy constructor
523  template <size_t InSize, size_t OutSize>
525  : m_state_table(NULL),
526  m_size(a_source.m_size),
527  m_init_state(a_source.m_init_state),
528  m_current_state(a_source.m_current_state),
529  m_output_base(a_source.m_output_base),
530  m_output_range(a_source.m_output_range),
531  m_state_base(a_source.m_state_base),
532  m_state_range(a_source.m_state_range)
533  {
534  // copy first parent
535  deep_copy(a_source);
536  }
537 
538  // Virtual destructor
539  template <size_t InSize, size_t OutSize>
541  {
542  release();
543  }
544 
545  // Assignment
546  template <size_t InSize, size_t OutSize>
548  {
549  // release resources
550  release();
551 
552  // set values
553  m_init_state = a_source.m_init_state;
554  m_current_state = a_source.m_current_state;
555  m_size = a_source.m_size;
556  m_output_base = a_source.m_output_base;
557  m_output_range = a_source.m_output_range;
558  m_state_base = a_source.m_state_base;
559  m_state_range = a_source.m_state_range;
560 
561  // copy source
562  deep_copy(a_source);
563 
564  return *this;
565  }
566 
568  template <size_t InSize, size_t OutSize>
570  {
571  g_selector.set_weight(a_type,a_weight);
572  }
573 
574  // Mutation
575  template <size_t InSize, size_t OutSize>
577  {
578  // the number of chances for mutation is based on the number of states in the machine;
579  // larger machines thus encounter more mutations
580  #ifdef DEBUG
581  cerr << "\n<< mutation operation >>\n";
582  dump("BEFORE");
583  #endif
584 
585  for (size_t n = 0; n < m_size; ++n)
586  {
587  if (g_random.get_real() < a_rate)
588  {
589  // pick a mutation
590  switch (g_selector.get_index())
591  {
592  case MUTATE_OUTPUT_SYMBOL:
593  {
594  // mutate output symbol
595  size_t state = rand_index(m_size);
596  size_t input = rand_index(InSize);
597  size_t index = rand_index(OutSize);
598 
599  #ifdef DEBUG
600  cerr << "MUTATE_OUTPUT_SYMBOL, state " << state << ", input " << input << ", index " << index << "\n";
601  #endif
602 
603  double new_weight = m_output_base + m_output_range * g_random.get_real();
604  m_state_table[state][input]->m_output.set_weight(index,new_weight);
605  break;
606  }
607  case MUTATE_TRANSITION:
608  {
609  // mutate state transition
610  size_t state = rand_index(m_size);
611  size_t input = rand_index(InSize);
612  size_t index = rand_index(m_size);
613 
614  #ifdef DEBUG
615  cerr << "MUTATE_TRANSITION, state " << state << ", input " << input << ", index " << index << "\n";
616  #endif
617 
618  double new_weight = m_state_base + m_state_range * g_random.get_real();
619  m_state_table[state][input]->m_new_state.set_weight(index,new_weight);
620  break;
621  }
622  case MUTATE_REPLACE_STATE:
623  {
624  // select mutated state
625  size_t state = rand_index(m_size);
626 
627  #ifdef DEBUG
628  cerr << "REPLACE_STATE, state " << state << "\n";
629  #endif
630 
631  // allocate an array corresponding to inputs
632  delete [] m_state_table[state];
633  m_state_table[state] = new tranout_t * [InSize];
634 
635  // tables of weights for roulette wheels
636  double * output_weights = new double[OutSize];
637  double * state_weights = new double[m_size];
638 
639  for (size_t i = 0; i < InSize; ++i)
640  {
641  // define weights
642  size_t n;
643 
644  for (n = 0; n < OutSize; ++n)
645  output_weights[n] = 1.0;
646 
647  output_weights[rand_index(OutSize)] = 100.0;
648 
649  for (n = 0; n < m_size; ++n)
650  state_weights[n] = 1.0;
651 
652  state_weights[rand_index(m_size)] = 100.0;
653 
654  // set transition values
655  m_state_table[state][i] = new tranout_t(state_weights,m_size,output_weights);
656  }
657 
658  delete [] output_weights;
659  delete [] state_weights;
660 
661  break;
662  }
663  case MUTATE_SWAP_STATES:
664  {
665  // swap two states (by swapping pointers)
666  size_t state1 = rand_index(m_size);
667  size_t state2;
668 
669  do
670  state2 = static_cast<size_t>(rand_index(m_size));
671  while (state2 == state1);
672 
673  #ifdef DEBUG
674  cerr << "MUTATE_SWAP_STATES, " << state1 << " with " << state2 << "\n";
675  #endif
676 
677  for (size_t i = 0; i < InSize; ++i)
678  {
679  tranout_t * temp = m_state_table[state1][i];
680  m_state_table[state1][i] = m_state_table[state2][i];
681  m_state_table[state2][i] = temp;
682  }
683 
684  break;
685  }
686  case MUTATE_INIT_STATE:
687  {
688  // change initial state
689  #ifdef DEBUG
690  cerr << "MUTATE_INIT_STATE\n";
691  #endif
692  m_init_state = rand_index(m_size);
693  break;
694  }
695  #ifdef DEBUG
696  default:
697  cerr << "UNKNOWN MUTATION!\n";
698  #endif
699  }
700  }
701  }
702 
703  // reset current state because init state may have changed
704 
705  m_current_state = m_init_state;
706  #ifdef DEBUG
707  dump("AFTER");
708  #endif
709  }
710 
711  // Cause state transition
712  template <size_t InSize, size_t OutSize>
713  inline size_t fuzzy_machine<InSize,OutSize>::transition(size_t a_input)
714  {
715  // get output symbol for given input for current state
716  size_t output = m_state_table[m_current_state][a_input]->m_output.get_index();
717 
718  // change to new state
719  m_current_state = m_state_table[m_current_state][a_input]->m_new_state.get_index();
720 
721  // return output symbol
722  return output;
723  }
724 
725  // Reset to start-up state
726  template <size_t InSize, size_t OutSize>
728  {
729  m_current_state = m_init_state;
730  }
731 
732  // Get size
733  template <size_t InSize, size_t OutSize>
735  {
736  return m_size;
737  }
738 
739  // Get a copy of the internal table
740  template <size_t InSize, size_t OutSize>
741  inline const typename fuzzy_machine<InSize,OutSize>::tranout_t & fuzzy_machine<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
742  {
743  return *m_state_table[a_state][a_input];
744  }
745 
746  // Get number of input states
747  template <size_t InSize, size_t OutSize>
749  {
750  return InSize;
751  }
752 
753  // Get number of output states
754  template <size_t InSize, size_t OutSize>
756  {
757  return OutSize;
758  }
759 
760  // Get initial state
761  template <size_t InSize, size_t OutSize>
763  {
764  return m_init_state;
765  }
766 
767  // Get current state
768  template <size_t InSize, size_t OutSize>
770  {
771  return m_current_state;
772  }
773 
774  #ifdef DEBUG
775  template <size_t InSize, size_t OutSize>
776  void fuzzy_machine<InSize,OutSize>::dump(const char * description, ostream & a_stream) const
777  {
778  a_stream << "----------\nDumping machine " << description << " (" << hex << this
779  << ")\ninitial state = " << m_init_state
780  << "\ncurrent state = " << m_current_state << "\n\n";
781 
782  for (size_t s = 0; s < m_size; ++s)
783  {
784  a_stream << "state " << s;
785 
786  for (size_t i = 0; i < InSize; ++i)
787  {
788  size_t n;
789 
790  a_stream << "\n output weights:";
791 
792  for (n = 0; n < OutSize; ++n)
793  a_stream << " " << m_state_table[s][i]->m_output.get_weight(n);
794 
795  a_stream << "\n state weights:";
796 
797  for (n = 0; n < m_size; ++n)
798  a_stream << " " << m_state_table[s][i]->m_new_state.get_weight(n);
799 
800  a_stream << endl;
801  }
802  }
803 
804  a_stream << "----------" << endl;
805  }
806  #endif
807 };
808 
809 #endif
Wraps a roulette wheel for selecting mutations.
Definition: machine_tools.h:95
double m_output_base
base value for output weights
Definition: fuzzy_machine.h:302
size_t init_state() const
Get initial state.
Definition: fuzzy_machine.h:762
fuzzy_machine(size_t a_size, double a_output_base, double a_output_range, double a_state_base, double a_state_range)
Creation constructor.
Definition: fuzzy_machine.h:356
roulette_wheel m_new_state
The state to be transitioned to.
Definition: fuzzy_machine.h:94
mutation_id
Types of mutation supported.
Definition: machine_tools.h:69
tranout_t *** m_state_table
State table (the machine definition)
Definition: fuzzy_machine.h:290
A set of common tools for finite state machines.
Definition: machine_tools.h:65
tranout_t(double *state_weights, size_t num_states, double *output_weights)
Creation Constructor.
Definition: fuzzy_machine.h:100
size_t num_output_states() const
Get number of output states.
Definition: fuzzy_machine.h:755
double m_state_range
range for state weights
Definition: fuzzy_machine.h:311
tranout_t(const tranout_t &source)
Copy constructor.
Definition: fuzzy_machine.h:108
static void set_mutation_weight(mutation_id a_type, double a_weight)
Set a mutation weight.
Definition: fuzzy_machine.h:569
Defines a transition and output state pair.
Definition: fuzzy_machine.h:91
A toolkit and framework for implementing evolutionary algorithms.
Definition: analyzer.h:60
static mutation_selector g_selector
Global mutation selector.
Definition: fuzzy_machine.h:314
size_t size() const
Get size.
Definition: fuzzy_machine.h:734
fuzzy_machine & operator=(const fuzzy_machine< InSize, OutSize > &a_source)
Definition: fuzzy_machine.h:547
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 simulated roulette wheel for weighted selection.
Definition: roulette.h:89
size_t m_size
Number of states.
Definition: fuzzy_machine.h:293
size_t num_input_states() const
Get number of input states.
Definition: fuzzy_machine.h:748
double m_state_base
base value for state weights
Definition: fuzzy_machine.h:308
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 transition(size_t a_input)
Cause state transition.
Definition: fuzzy_machine.h:713
roulette_wheel m_output
The output value.
Definition: fuzzy_machine.h:97
double m_output_range
range for output weights
Definition: fuzzy_machine.h:305
void mutate(double a_rate)
Mutation.
Definition: fuzzy_machine.h:576
void reset()
Reset to start-up state.
Definition: fuzzy_machine.h:727
double get_real()
get the next value in the range [0,1)
Definition: evocommon.h:106
virtual ~fuzzy_machine()
Virtual destructor.
Definition: fuzzy_machine.h:540
A finite state machine.
Definition: fuzzy_machine.h:87
size_t current_state() const
Get current state.
Definition: fuzzy_machine.h:769
size_t m_init_state
Initial state.
Definition: fuzzy_machine.h:296
tranout_t *** state_table()
Get current transition table.
Definition: fuzzy_machine.h:272
size_t m_current_state
Current state.
Definition: fuzzy_machine.h:299
const tranout_t & get_transition(size_t a_state, size_t a_input) const
Get a transition from the internal state table.
Definition: fuzzy_machine.h:741

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