Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


state_machine.h
00001 /*
00002     Evocosm is a C++ framework for implementing evolutionary algorithms.
00003 
00004     Copyright 2011 Scott Robert Ladd. All rights reserved.
00005 
00006     Evocosm is user-supported open source software. Its continued development is dependent
00007     on financial support from the community. You can provide funding by visiting the Evocosm
00008     website at:
00009 
00010         http://www.coyotegulch.com
00011 
00012     You may license Evocosm in one of two fashions:
00013 
00014     1) Simplified BSD License (FreeBSD License)
00015 
00016     Redistribution and use in source and binary forms, with or without modification, are
00017     permitted provided that the following conditions are met:
00018 
00019     1.  Redistributions of source code must retain the above copyright notice, this list of
00020         conditions and the following disclaimer.
00021 
00022     2.  Redistributions in binary form must reproduce the above copyright notice, this list
00023         of conditions and the following disclaimer in the documentation and/or other materials
00024         provided with the distribution.
00025 
00026     THIS SOFTWARE IS PROVIDED BY SCOTT ROBERT LADD ``AS IS'' AND ANY EXPRESS OR IMPLIED
00027     WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
00028     FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SCOTT ROBERT LADD OR
00029     CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
00030     CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
00031     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
00032     ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00033     NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
00034     ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00035 
00036     The views and conclusions contained in the software and documentation are those of the
00037     authors and should not be interpreted as representing official policies, either expressed
00038     or implied, of Scott Robert Ladd.
00039 
00040     2) Closed-Source Proprietary License
00041 
00042     If your project is a closed-source or proprietary project, the Simplified BSD License may
00043     not be appropriate or desirable. In such cases, contact the Evocosm copyright holder to
00044     arrange your purchase of an appropriate license.
00045 
00046     The author can be contacted at:
00047 
00048           scott.ladd@coyotegulch.com
00049           scott.ladd@gmail.com
00050           http:www.coyotegulch.com
00051 */
00052 
00053 #if !defined(LIBEVOCOSM_FSM_H)
00054 #define LIBEVOCOSM_FSM_H
00055 
00056 // Standard C++ Library
00057 #include <cstddef>
00058 #include <vector>
00059 #include <map>
00060 #include <stack>
00061 #include <stdexcept>
00062 using namespace std;
00063 
00064 // libevocosm
00065 #include "evocommon.h"
00066 #include "roulette.h"
00067 #include "machine_tools.h"
00068 
00069 namespace libevocosm
00070 {
00072 
00086     template <typename InputT, typename OutputT>
00087     class state_machine : protected globals, protected fsm_tools
00088     {
00089     public:
00091         typedef InputT  t_input;
00092 
00094         typedef OutputT t_output;
00095 
00097         typedef typename std::pair<t_output, size_t> t_transition;
00098 
00100         typedef typename std::map<t_input, t_transition> t_input_map;
00101 
00103         typedef typename std::vector<t_input_map> t_state_table;
00104 
00106 
00113         state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
00114 
00116 
00125         state_machine(const state_machine<InputT,OutputT> & a_parent1, const state_machine<InputT,OutputT> & a_parent2);
00126 
00128 
00132         state_machine(const state_machine<InputT,OutputT> & a_source);
00133 
00135 
00139         virtual ~state_machine();
00140 
00141         //  Assignment
00146         state_machine & operator = (const state_machine<InputT,OutputT> & a_source);
00147 
00149 
00164         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);
00165 
00167 
00172         t_output transition(const state_machine<InputT,OutputT>::t_input & a_input);
00173 
00175 
00178         void reset();
00179 
00181 
00186         t_state_table get_table() const;
00187 
00189 
00193         size_t get_init_state() const;
00194 
00196 
00200         size_t get_current_state() const;
00201 
00202     protected:
00204         t_state_table m_state_table;
00205 
00207         size_t m_size;
00208 
00210         size_t m_init_state;
00211 
00213         size_t m_current_state;
00214 
00216         static mutation_selector g_default_selector;
00217 
00218     private:
00219         // create a state map
00220         t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
00221     };
00222 
00223     //  Static initializer
00224     template <typename InputT, typename OutputT>
00225     typename state_machine<InputT,OutputT>::mutation_selector state_machine<InputT,OutputT>::g_default_selector;
00226 
00227     //  Creation constructor
00228     template <typename InputT, typename OutputT>
00229     state_machine<InputT,OutputT>::state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
00230       : m_state_table(),
00231         m_init_state(0),
00232         m_current_state(0),
00233         m_size(a_size)
00234     {
00235         // verify parameters
00236         if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1))
00237             throw std::runtime_error("invalid state_machine creation parameters");
00238 
00239         for (size_t n = 0; n < m_size; ++n)
00240         {
00241             // add input map to state table
00242             m_state_table.push_back(create_input_map(a_inputs,a_outputs));
00243         }
00244 
00245         // set initial state and start there
00246         m_init_state = rand_index(m_size);
00247         m_current_state = m_init_state;
00248     }
00249 
00250     //  Construct via bisexual crossover
00251     template <typename InputT, typename OutputT>
00252     state_machine<InputT,OutputT>::state_machine(const state_machine<InputT,OutputT> & a_parent1, const state_machine<InputT,OutputT> & a_parent2)
00253       : m_state_table(a_parent1.m_state_table),
00254         m_init_state(0),
00255         m_current_state(0),
00256         m_size(0)
00257     {
00258         size_t n;
00259 
00260         // don't do anything else if fsms differ is size
00261         if (a_parent1.m_size != a_parent2.m_size)
00262             return;
00263 
00264         // replace states from those in second parent 50/50 chance
00265         for (size_t n = 0; n < m_size; ++n)
00266         {
00267             if (g_random.get_real() > 0.5)
00268                 m_state_table[n] = a_parent2.m_state_table[n];
00269         }
00270 
00271         // calculate the size
00272         m_size = m_state_table.size();
00273 
00274         // randomize the initial state (looks like mom and dad but may act like either one!)
00275         if (g_random.get_real() < 0.5)
00276             m_init_state = a_parent1.m_init_state;
00277         else
00278             m_init_state = a_parent2.m_init_state;
00279 
00280         // reset for start
00281         m_current_state = m_init_state;
00282     }
00283 
00284     //  Copy constructor
00285     template <typename InputT, typename OutputT>
00286     state_machine<InputT,OutputT>::state_machine(const state_machine<InputT,OutputT> & a_source)
00287       : m_state_table(a_source.m_state_table),
00288         m_init_state(a_source.m_init_state),
00289         m_current_state(a_source.m_current_state),
00290         m_size(a_source.m_size)
00291     {
00292         // nada
00293     }
00294 
00295     //  Virtual destructor
00296     template <typename InputT, typename OutputT>
00297     state_machine<InputT,OutputT>::~state_machine()
00298     {
00299         // nada
00300     }
00301 
00302     //  Assignment
00303     template <typename InputT, typename OutputT>
00304     state_machine<InputT,OutputT> & state_machine<InputT,OutputT>::operator = (const state_machine<InputT,OutputT> & a_source)
00305     {
00306         if (this != &a_source)
00307         {
00308             m_state_table   = a_source.m_state_table;
00309             m_init_state    = a_source.m_init_state;
00310             m_current_state = a_source.m_current_state;
00311             m_size          = a_source.m_size;
00312         }
00313 
00314         return *this;
00315     }
00316 
00317     //  Mutation
00318     template <typename InputT, typename OutputT>
00319     void state_machine<InputT,OutputT>::mutate(double a_rate,
00320                                      const std::vector<t_input> & a_inputs,
00321                                      const std::vector<t_output> & a_outputs,
00322                                      mutation_selector & a_selector)
00323     {
00324         if (g_random.get_real() < a_rate)
00325         {
00326             // pick a mutation
00327             switch (a_selector.get_index())
00328             {
00329                 case MUTATE_OUTPUT_SYMBOL:
00330                 {
00331                     // mutate output symbol
00332                     size_t state  = rand_index(m_size);
00333                     size_t input  = rand_index(a_inputs.size());
00334                     size_t output = rand_index(a_outputs.size());
00335                     m_state_table[state][a_inputs[input]].first = a_outputs[output];
00336                     break;
00337                 }
00338                 case MUTATE_TRANSITION:
00339                 {
00340                     // mutate state transition
00341                     size_t state  = rand_index(m_size);
00342                     size_t input  = rand_index(a_inputs.size());
00343                     size_t new_state = rand_index(m_size);
00344                     m_state_table[state][a_inputs[input]].second = new_state;
00345                     break;
00346                 }
00347                 case MUTATE_REPLACE_STATE:
00348                 {
00349                     // select state
00350                     size_t state  = rand_index(m_size);
00351                     m_state_table[state] = create_input_map(a_inputs,a_outputs);
00352                 }
00353                 case MUTATE_SWAP_STATES:
00354                 {
00355                     // swap two states
00356                     size_t state1 = rand_index(m_size);
00357                     size_t state2;
00358 
00359                     do
00360                         state2 = rand_index(m_size);
00361                     while (state2 == state1);
00362 
00363                     t_input_map temp = m_state_table[state1];
00364                     m_state_table[state1] = m_state_table[state2];
00365                     m_state_table[state2] = temp;
00366                     break;
00367                 }
00368                 case MUTATE_INIT_STATE:
00369                 {
00370                     // change initial state
00371                     m_init_state  = rand_index(m_size);
00372                     break;
00373                 }
00374             }
00375         }
00376 
00377         // reset current state because init state may have changed
00378         m_current_state = m_init_state;
00379     }
00380 
00381     //  Cause state transition
00382     template <typename InputT, typename OutputT>
00383     typename state_machine<InputT,OutputT>::t_output state_machine<InputT,OutputT>::transition(const state_machine<InputT,OutputT>::t_input & a_input)
00384     {
00385         // get transition state
00386         t_transition & trans = m_state_table[m_current_state][a_input];
00387 
00388         // change to new state
00389         m_current_state = trans.second;
00390 
00391         // return output symbol
00392         return trans.first;
00393     }
00394 
00395     //  Reset to start-up state
00396     template <typename InputT, typename OutputT>
00397     inline void state_machine<InputT,OutputT>::reset()
00398     {
00399         m_current_state = m_init_state;
00400     }
00401 
00402     //  Get a copy of the internal table
00403     template <typename InputT, typename OutputT>
00404     inline typename state_machine<InputT,OutputT>::t_state_table state_machine<InputT,OutputT>::get_table() const
00405     {
00406         return m_state_table;
00407     }
00408 
00409     //  Get initial state
00410     template <typename InputT, typename OutputT>
00411     inline size_t state_machine<InputT,OutputT>::get_init_state() const
00412     {
00413         return m_init_state;
00414     }
00415 
00416     //  Get current state
00417     template <typename InputT, typename OutputT>
00418     inline size_t state_machine<InputT,OutputT>::get_current_state() const
00419     {
00420         return m_current_state;
00421     }
00422 
00423     // create a state map
00424     template <typename InputT, typename OutputT>
00425     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)
00426     {
00427         // maximum output index
00428         size_t max_output = a_outputs.size();
00429 
00430         // create an input map for this state
00431         t_input_map input_map;
00432 
00433         // for each input, define an output and a state transition
00434         for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input)
00435         {
00436             // pick a random output symbol and new state
00437             t_output out_symbol = a_outputs[rand_index(max_output)];
00438             size_t   new_state  = rand_index(m_size);
00439 
00440             // add transition data to map
00441             input_map[*input] = std::make_pair(out_symbol,new_state);
00442         }
00443 
00444         return input_map;
00445     }
00446 };
00447 
00448 #endif

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