Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


fsm.h

00001 //---------------------------------------------------------------------
00002 //  Algorithmic Conjurings @ http://www.coyotegulch.com
00003 //  Evocosm -- An Object-Oriented Framework for Evolutionary Algorithms
00004 //
00005 //  fsm.h
00006 //---------------------------------------------------------------------
00007 //
00008 //  Copyright 1996, 1999, 2002, 2003, 2004, 2005 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 <vector>
00041 #include <map>
00042 #include <stack>
00043 #include <stdexcept>
00044 using namespace std;
00045 
00046 // libevocosm
00047 #include "evocommon.h"
00048 #include "roulette.h"
00049 #include "fsm_tools.h"
00050 
00051 namespace libevocosm
00052 {
00054 
00068     template <typename InputT, typename OutputT>
00069     class fsm : protected globals, protected fsm_tools
00070     {
00071     public:
00073         typedef InputT  t_input;
00074 
00076         typedef OutputT t_output;
00077 
00079         typedef typename std::pair<t_output, size_t> t_transition;
00080 
00082         typedef typename std::map<t_input, t_transition> t_input_map;
00083 
00085         typedef typename std::vector<t_input_map> t_state_table;
00086 
00088 
00095         fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
00096 
00098 
00107         fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2);
00108 
00110 
00114         fsm(const fsm<InputT,OutputT> & a_source);
00115 
00117 
00121         virtual ~fsm();
00122 
00123         //  Assignment
00128         fsm & operator = (const fsm<InputT,OutputT> & a_source);
00129 
00131 
00146         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);
00147         
00149 
00154         t_output transition(const fsm<InputT,OutputT>::t_input & a_input);
00155 
00157 
00160         void reset();
00161 
00163 
00168         t_state_table get_table() const;
00169 
00171 
00175         size_t get_init_state() const;
00176 
00178 
00182         size_t get_current_state() const;
00183 
00184     protected:
00186         t_state_table m_state_table;
00187 
00189         size_t m_size;
00190 
00192         size_t m_init_state;
00193 
00195         size_t m_current_state;
00196 
00198         static mutation_selector g_default_selector;
00199         
00200     private:
00201         // create a state map
00202         t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
00203     };
00204 
00205     //  Static initializer
00206     template <typename InputT, typename OutputT>
00207     typename fsm<InputT,OutputT>::mutation_selector fsm<InputT,OutputT>::g_default_selector;
00208 
00209     //  Creation constructor
00210     template <typename InputT, typename OutputT>
00211     fsm<InputT,OutputT>::fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
00212       : m_state_table(),
00213         m_init_state(0),
00214         m_current_state(0),
00215         m_size(a_size)
00216     {
00217         // verify parameters
00218         if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1))
00219             throw std::runtime_error("invalid fsm creation parameters");
00220 
00221         for (size_t n = 0; n < m_size; ++n)
00222         {
00223             // add input map to state table
00224             m_state_table.push_back(create_input_map(a_inputs,a_outputs));
00225         }
00226 
00227         // set initial state and start there
00228         m_init_state = g_random.get_rand_index(m_size);
00229         m_current_state = m_init_state;
00230     }
00231 
00232     //  Construct via bisexual crossover
00233     template <typename InputT, typename OutputT>
00234     fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2)
00235       : m_state_table(a_parent1.m_state_table),
00236         m_init_state(0),
00237         m_current_state(0),
00238         m_size(0)
00239     {
00240         size_t n;
00241 
00242         // don't do anything else if fsms differ is size
00243         if (a_parent1.m_size != a_parent2.m_size)
00244             return;
00245 
00246         // replace states from those in second parent 50/50 chance
00247         for (size_t n = 0; n < m_size; ++n)
00248         {
00249             if (g_random.get_rand_real2() > 0.5)
00250                 m_state_table[n] = a_parent2.m_state_table[n];
00251         }
00252 
00253         // calculate the size
00254         m_size = m_state_table.size();
00255 
00256         // randomize the initial state (looks like mom and dad but may act like either one!)
00257         if (g_random.get_rand_real2() < 0.5)
00258             m_init_state = a_parent1.m_init_state;
00259         else
00260             m_init_state = a_parent2.m_init_state;
00261 
00262         // reset for start
00263         m_current_state = m_init_state;
00264     }
00265 
00266     //  Copy constructor
00267     template <typename InputT, typename OutputT>
00268     fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_source)
00269       : m_state_table(a_source.m_state_table),
00270         m_init_state(a_source.m_init_state),
00271         m_current_state(a_source.m_current_state),
00272         m_size(a_source.m_size)
00273     {
00274         // nada
00275     }
00276 
00277     //  Virtual destructor
00278     template <typename InputT, typename OutputT>
00279     fsm<InputT,OutputT>::~fsm()
00280     {
00281         // nada
00282     }
00283 
00284     //  Assignment
00285     template <typename InputT, typename OutputT>
00286     fsm<InputT,OutputT> & fsm<InputT,OutputT>::operator = (const fsm<InputT,OutputT> & a_source)
00287     {
00288         if (this != &a_source)
00289         {
00290             m_state_table   = a_source.m_state_table;
00291             m_init_state    = a_source.m_init_state;
00292             m_current_state = a_source.m_current_state;
00293             m_size          = a_source.m_size;
00294         }
00295 
00296         return *this;
00297     }
00298 
00299     //  Mutation
00300     template <typename InputT, typename OutputT>
00301     void fsm<InputT,OutputT>::mutate(double a_rate, 
00302                                      const std::vector<t_input> & a_inputs,
00303                                      const std::vector<t_output> & a_outputs,
00304                                      mutation_selector & a_selector)
00305     {
00306         if (g_random.get_rand_real2() < a_rate)
00307         {
00308             // pick a mutation
00309             switch (a_selector.get_index())
00310             {
00311                 case MUTATE_OUTPUT_SYMBOL:
00312                 {
00313                     // mutate output symbol
00314                     size_t state  = g_random.get_rand_index(m_size);
00315                     size_t input  = g_random.get_rand_index(a_inputs.size());
00316                     size_t output = g_random.get_rand_index(a_outputs.size());
00317                     m_state_table[state][a_inputs[input]].first = a_outputs[output];
00318                     break;
00319                 }    
00320                 case MUTATE_TRANSITION:
00321                 {
00322                     // mutate state transition
00323                     size_t state  = g_random.get_rand_index(m_size);
00324                     size_t input  = g_random.get_rand_index(a_inputs.size());
00325                     size_t new_state = g_random.get_rand_index(m_size);
00326                     m_state_table[state][a_inputs[input]].second = new_state;
00327                     break;
00328                 }
00329                 case MUTATE_REPLACE_STATE:
00330                 {
00331                     // select state
00332                     size_t state  = g_random.get_rand_index(m_size);
00333                     m_state_table[state] = create_input_map(a_inputs,a_outputs);
00334                 }
00335                 case MUTATE_SWAP_STATES:
00336                 {
00337                     // swap two states
00338                     size_t state1 = g_random.get_rand_index(m_size);
00339                     size_t state2;
00340         
00341                     do
00342                         state2 = g_random.get_rand_index(m_size);
00343                     while (state2 == state1);
00344         
00345                     t_input_map temp = m_state_table[state1];
00346                     m_state_table[state1] = m_state_table[state2];
00347                     m_state_table[state2] = temp;
00348                     break;
00349                 }    
00350                 case MUTATE_INIT_STATE:
00351                 {
00352                     // change initial state
00353                     m_init_state  = g_random.get_rand_index(m_size);
00354                     break;
00355                 }
00356             }
00357         }
00358         
00359         // reset current state because init state may have changed
00360         m_current_state = m_init_state;
00361     }
00362 
00363     //  Cause state transition
00364     template <typename InputT, typename OutputT>
00365     typename fsm<InputT,OutputT>::t_output fsm<InputT,OutputT>::transition(const fsm<InputT,OutputT>::t_input & a_input)
00366     {
00367         // get transition state
00368         t_transition & trans = m_state_table[m_current_state][a_input];
00369 
00370         // change to new state
00371         m_current_state = trans.second;
00372 
00373         // return output symbol
00374         return trans.first;
00375     }
00376 
00377     //  Reset to start-up state
00378     template <typename InputT, typename OutputT>
00379     inline void fsm<InputT,OutputT>::reset()
00380     {
00381         m_current_state = m_init_state;
00382     }
00383 
00384     //  Get a copy of the internal table
00385     template <typename InputT, typename OutputT>
00386     inline typename fsm<InputT,OutputT>::t_state_table fsm<InputT,OutputT>::get_table() const
00387     {
00388         return m_state_table;
00389     }
00390 
00391     //  Get initial state
00392     template <typename InputT, typename OutputT>
00393     inline size_t fsm<InputT,OutputT>::get_init_state() const
00394     {
00395         return m_init_state;
00396     }
00397 
00398     //  Get current state
00399     template <typename InputT, typename OutputT>
00400     inline size_t fsm<InputT,OutputT>::get_current_state() const
00401     {
00402         return m_current_state;
00403     }
00404 
00405     // create a state map
00406     template <typename InputT, typename OutputT>
00407     typename fsm<InputT,OutputT>::t_input_map fsm<InputT,OutputT>::create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
00408     {
00409         // maximum output index
00410         size_t max_output = a_outputs.size();
00411 
00412         // create an input map for this state
00413         t_input_map input_map;
00414 
00415         // for each input, define an output and a state transition
00416         for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input)
00417         {
00418             // pick a random output symbol and new state
00419             t_output out_symbol = a_outputs[g_random.get_rand_index(max_output)];
00420             size_t   new_state  = g_random.get_rand_index(m_size);
00421 
00422             // add transition data to map
00423             input_map[*input] = std::make_pair(out_symbol,new_state);
00424         }
00425 
00426         return input_map;
00427     }
00428 };
00429 
00430 #endif

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