Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


simple_fsm.h

00001 //---------------------------------------------------------------------
00002 //  Algorithmic Conjurings @ http://www.coyotegulch.com
00003 //  Evocosm -- An Object-Oriented Framework for Evolutionary Algorithms
00004 //
00005 //  simple_fsm.h
00006 //---------------------------------------------------------------------
00007 //
00008 //  Copyright 1996, 1999, 2002, 2003, 2004, 2005, 2006, 2007 Scott Robert Ladd
00009 //
00010 //  This program is free software; you can redistribute it and/or modify
00011 //  it under the terms of the GNU General Public License as published by
00012 //  the Free Software Foundation; either version 2 of the License, or
00013 //  (at your option) any later version.
00014 //
00015 //  This program is distributed in the hope that it will be useful,
00016 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 //  GNU General Public License for more details.
00019 //
00020 //  You should have received a copy of the GNU General Public License
00021 //  along with this program; if not, write to the
00022 //      Free Software Foundation, Inc.
00023 //      59 Temple Place - Suite 330
00024 //      Boston, MA 02111-1307, USA.
00025 //
00026 //-----------------------------------------------------------------------
00027 //
00028 //  For more information on this software package, please visit
00029 //  Scott's web site, Coyote Gulch Productions, at:
00030 //
00031 //      http://www.coyotegulch.com
00032 //
00033 //-----------------------------------------------------------------------
00034 
00035 #if !defined(LIBEVOCOSM_FSM_H)
00036 #define LIBEVOCOSM_FSM_H
00037 
00038 // Standard C++ Library
00039 #include <cstddef>
00040 #include <stack>
00041 #include <stdexcept>
00042 using namespace std;
00043 
00044 // libevocosm
00045 #include "evocommon.h"
00046 #include "fsm_tools.h"
00047 
00048 namespace libevocosm
00049 {
00051 
00059     template <size_t InSize, size_t OutSize>
00060     class simple_fsm : protected globals, protected fsm_tools
00061     {
00062     public:
00064         struct tranout_t
00065         {
00067             size_t m_new_state;
00068 
00070             size_t m_output;
00071         };
00072 
00074 
00078         simple_fsm(size_t a_size);
00079 
00081 
00086         simple_fsm(const simple_fsm<InSize,OutSize> & a_parent1, const simple_fsm<InSize,OutSize> & a_parent2);
00087 
00089 
00093         simple_fsm(const simple_fsm<InSize,OutSize> & a_source);
00094 
00096 
00100         virtual ~simple_fsm();
00101 
00102         //  Assignment
00108         simple_fsm & operator = (const simple_fsm<InSize,OutSize> & a_source);
00109 
00111 
00123         void mutate(double a_rate);
00124 
00126 
00132         static void set_mutation_weight(mutation_id a_type, double a_weight);
00133 
00135 
00141         size_t transition(size_t a_input);
00142 
00144 
00147         void reset();
00148 
00150 
00154         size_t size() const;
00155 
00157 
00163         const tranout_t & get_transition(size_t a_state, size_t a_input) const;
00164 
00166 
00170         size_t num_input_states() const;
00171 
00173 
00177         size_t num_output_states() const;
00178 
00180 
00184         size_t init_state() const;
00185 
00187 
00191         size_t current_state() const;
00192 
00193     private:
00194         // release resources
00195         void release();
00196 
00197         // deep copy
00198         void deep_copy(const simple_fsm<InSize,OutSize> & a_source);
00199 
00200     protected:
00202         tranout_t ** m_state_table;
00203 
00205         size_t m_init_state;
00206 
00208         size_t m_current_state;
00209 
00211         size_t m_size;
00212 
00214         static mutation_selector g_selector;
00215     };
00216 
00217     //  Static initializer
00218     template <size_t InSize, size_t OutSize>
00219     typename simple_fsm<InSize,OutSize>::mutation_selector simple_fsm<InSize,OutSize>::g_selector;
00220 
00221     // release resources
00222     template <size_t InSize, size_t OutSize>
00223     void simple_fsm<InSize,OutSize>::release()
00224     {
00225         for (size_t s = 0; s < m_size; ++s)
00226             delete [] m_state_table[s];
00227 
00228         delete [] m_state_table;
00229     }
00230 
00231     // deep copy
00232     template <size_t InSize, size_t OutSize>
00233     void simple_fsm<InSize,OutSize>::deep_copy(const simple_fsm<InSize,OutSize> & a_source)
00234     {
00235         // allocate state table
00236         m_state_table = new tranout_t * [m_size];
00237 
00238         for (size_t s = 0; s < m_size; ++s)
00239         {
00240             // allocate an array corresponding to inputs
00241             m_state_table[s] = new tranout_t [InSize];
00242 
00243             // set transition values
00244             for (size_t i = 0; i < InSize; ++i)
00245             {
00246                 m_state_table[s][i].m_new_state = a_source.m_state_table[s][i].m_new_state;
00247                 m_state_table[s][i].m_output    = a_source.m_state_table[s][i].m_output;
00248             }
00249         }
00250     }
00251 
00252     //  Creation constructor
00253     template <size_t InSize, size_t OutSize>
00254     simple_fsm<InSize,OutSize>::simple_fsm(size_t a_size)
00255       : m_state_table(NULL),
00256         m_init_state(0),
00257         m_current_state(0),
00258         m_size(a_size)
00259     {
00260         // verify parameters
00261         if (m_size < 2)
00262             throw std::runtime_error("invalid simple_fsm creation parameters");
00263 
00264         // allocate state table
00265         m_state_table = new tranout_t * [m_size];
00266 
00267         for (size_t s = 0; s < m_size; ++s)
00268         {
00269             // allocate an array corresponding to inputs
00270             m_state_table[s] = new tranout_t [InSize];
00271 
00272             // set transition values
00273             for (size_t i = 0; i < InSize; ++i)
00274             {
00275                 m_state_table[s][i].m_new_state = rand_index(m_size);
00276                 m_state_table[s][i].m_output    = rand_index(OutSize);
00277             }
00278         }
00279 
00280         // set initial state and start there
00281         m_init_state = rand_index(m_size);
00282         m_current_state = m_init_state;
00283     }
00284 
00285     // Construct via bisexual crossover
00286     template <size_t InSize, size_t OutSize>
00287     simple_fsm<InSize,OutSize>::simple_fsm(const simple_fsm<InSize,OutSize> & a_parent1, const simple_fsm<InSize,OutSize> & a_parent2)
00288       : m_state_table(NULL),
00289         m_init_state(0),
00290         m_current_state(0),
00291         m_size(a_parent1.m_size)
00292     {
00293         // copy first parent
00294         deep_copy(a_parent1);
00295 
00296         // don't do anything else if fsms differ is size
00297         if (a_parent1.m_size != a_parent2.m_size)
00298             return;
00299 
00300         // replace states from those in second parent 50/50 chance
00301         size_t x = rand_index(m_size);
00302 
00303         for (size_t n = x; n < m_size; ++n)
00304         {
00305             // set transition values
00306             for (size_t i = 0; i < InSize; ++i)
00307             {
00308                 m_state_table[n][i].m_new_state = a_parent2.m_state_table[n][i].m_new_state;
00309                 m_state_table[n][i].m_output    = a_parent2.m_state_table[n][i].m_output;
00310             }
00311         }
00312 
00313         // randomize the initial state (looks like mom and dad but may act like either one!)
00314         if (g_random.get_real() < 0.5)
00315             m_init_state = a_parent1.m_init_state;
00316         else
00317             m_init_state = a_parent2.m_init_state;
00318 
00319         // reset for start
00320         m_current_state = m_init_state;
00321     }
00322 
00323     //  Copy constructor
00324     template <size_t InSize, size_t OutSize>
00325     simple_fsm<InSize,OutSize>::simple_fsm(const simple_fsm<InSize,OutSize> & a_source)
00326       : m_state_table(NULL),
00327         m_init_state(a_source.m_init_state),
00328         m_current_state(a_source.m_current_state),
00329         m_size(a_source.m_size)
00330     {
00331         // copy first parent
00332         deep_copy(a_source);
00333     }
00334 
00335     //  Virtual destructor
00336     template <size_t InSize, size_t OutSize>
00337     simple_fsm<InSize,OutSize>::~simple_fsm()
00338     {
00339         release();
00340     }
00341 
00342     //  Assignment
00343     template <size_t InSize, size_t OutSize>
00344     simple_fsm<InSize,OutSize> & simple_fsm<InSize,OutSize>::operator = (const simple_fsm<InSize,OutSize> & a_source)
00345     {
00346         // release resources
00347         release();
00348 
00349         // set values
00350         m_init_state    = a_source.m_init_state;
00351         m_current_state = a_source.m_current_state;
00352         m_size          = a_source.m_size;
00353 
00354         // copy source
00355         deep_copy(a_source);
00356 
00357         return *this;
00358     }
00359 
00361     template <size_t InSize, size_t OutSize>
00362     inline void simple_fsm<InSize,OutSize>::set_mutation_weight(mutation_id a_type, double a_weight)
00363     {
00364         g_selector.set_weight(a_type,a_weight);
00365     }
00366 
00367     //  Mutation
00368     template <size_t InSize, size_t OutSize>
00369     void simple_fsm<InSize,OutSize>::mutate(double a_rate)
00370     {
00371         // the number of chances for mutation is based on the number of states in the machine;
00372         // larger machines thus encounter more mutations
00373         for (size_t n = 0; n < m_size; ++n)
00374         {
00375             if (g_random.get_real() < a_rate)
00376             {
00377                 // pick a mutation
00378                 switch (g_selector.get_index())
00379                 {
00380                     case MUTATE_OUTPUT_SYMBOL:
00381                     {
00382                         // mutate output symbol
00383                         size_t state  = rand_index(m_size);
00384                         size_t input  = rand_index(InSize);
00385 
00386                         size_t choice;
00387 
00388                         do
00389                         {
00390                             choice = rand_index(OutSize);
00391                         }
00392                         while (m_state_table[state][input].m_output == choice);
00393 
00394                         m_state_table[state][input].m_output = choice;
00395                         break;
00396                     }
00397                     case MUTATE_TRANSITION:
00398                     {
00399                         // mutate state transition
00400                         size_t state  = rand_index(m_size);
00401                         size_t input  = rand_index(InSize);
00402 
00403                         size_t choice;
00404 
00405                         do
00406                         {
00407                             choice = rand_index(m_size);
00408                         }
00409                         while (m_state_table[state][input].m_new_state == choice);
00410 
00411                         m_state_table[state][input].m_new_state = choice;
00412                         break;
00413                     }
00414                     case MUTATE_REPLACE_STATE:
00415                     {
00416                         // mutate state transition
00417                         size_t state  = rand_index(m_size);
00418 
00419                         // allocate an array corresponding to inputs
00420                         delete [] m_state_table[state];
00421                         m_state_table[state] = new tranout_t [InSize];
00422 
00423                         // set transition values
00424                         for (size_t i = 0; i < InSize; ++i)
00425                         {
00426                             m_state_table[state][i].m_new_state = rand_index(m_size);
00427                             m_state_table[state][i].m_output    = rand_index(OutSize);
00428                         }
00429 
00430                         break;
00431                     }
00432                     case MUTATE_SWAP_STATES:
00433                     {
00434                         // swap two states (by swapping pointers)
00435                         size_t state1 = rand_index(m_size);
00436                         size_t state2;
00437 
00438                         do
00439                             state2 = rand_index(m_size);
00440                         while (state2 == state1);
00441 
00442                         for (size_t i = 0; i < InSize; ++i)
00443                         {
00444                             tranout_t temp = m_state_table[state1][i];
00445                             m_state_table[state1][i] = m_state_table[state2][i];
00446                             m_state_table[state2][i] = temp;
00447                         }
00448 
00449                         break;
00450                     }
00451                     case MUTATE_INIT_STATE:
00452                     {
00453                         // change initial state
00454                         size_t choice;
00455 
00456                         do
00457                         {
00458                             choice = rand_index(m_size);
00459                         }
00460                         while (m_init_state == choice);
00461 
00462                         m_init_state  = choice;
00463 
00464                         break;
00465                     }
00466                 }
00467             }
00468         }
00469 
00470         // reset current state because init state may have changed
00471         m_current_state = m_init_state;
00472     }
00473 
00474     //  Cause state transition
00475     template <size_t InSize, size_t OutSize>
00476     inline size_t simple_fsm<InSize,OutSize>::transition(size_t a_input)
00477     {
00478         // get output symbol for given input for current state
00479         size_t output = m_state_table[m_current_state][a_input].m_output;
00480 
00481         // change to new state
00482         m_current_state = m_state_table[m_current_state][a_input].m_new_state;
00483 
00484         // return output symbol
00485         return output;
00486     }
00487 
00488     //  Reset to start-up state
00489     template <size_t InSize, size_t OutSize>
00490     inline void simple_fsm<InSize,OutSize>::reset()
00491     {
00492         m_current_state = m_init_state;
00493     }
00494 
00495     // Get size
00496     template <size_t InSize, size_t OutSize>
00497     inline size_t simple_fsm<InSize,OutSize>::size() const
00498     {
00499         return m_size;
00500     }
00501 
00502     //  Get a copy of the internal table
00503     template <size_t InSize, size_t OutSize>
00504     inline const typename simple_fsm<InSize,OutSize>::tranout_t & simple_fsm<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
00505     {
00506         return m_state_table[a_state][a_input];
00507     }
00508 
00509     // Get number of input states
00510     template <size_t InSize, size_t OutSize>
00511     inline size_t simple_fsm<InSize,OutSize>::num_input_states() const
00512     {
00513         return InSize;
00514     }
00515 
00516     // Get number of output states
00517     template <size_t InSize, size_t OutSize>
00518     inline size_t simple_fsm<InSize,OutSize>::num_output_states() const
00519     {
00520         return OutSize;
00521     }
00522 
00523     //  Get initial state
00524     template <size_t InSize, size_t OutSize>
00525     inline size_t simple_fsm<InSize,OutSize>::init_state() const
00526     {
00527         return m_init_state;
00528     }
00529 
00530     //  Get current state
00531     template <size_t InSize, size_t OutSize>
00532     inline size_t simple_fsm<InSize,OutSize>::current_state() const
00533     {
00534         return m_current_state;
00535     }
00536 };
00537 
00538 #endif

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