fsm.h

//---------------------------------------------------------------------
//  Algorithmic Conjurings @ http://www.coyotegulch.com
//  Evocosm -- An Object-Oriented Framework for Evolutionary Algorithms
//
//  fsm.h
//---------------------------------------------------------------------
//
//  Copyright 1996, 1999, 2002, 2003, 2004, 2005, 2006, 2007 Scott Robert Ladd
//
//  This program is free software; you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation; either version 2 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the
//      Free Software Foundation, Inc.
//      59 Temple Place - Suite 330
//      Boston, MA 02111-1307, USA.
//
//-----------------------------------------------------------------------
//
//  For more information on this software package, please visit
//  Scott's web site, Coyote Gulch Productions, at:
//
//      http://www.coyotegulch.com
//
//-----------------------------------------------------------------------

#if !defined(LIBEVOCOSM_FSM_H)
#define LIBEVOCOSM_FSM_H

// Standard C++ Library
#include <cstddef>
#include <vector>
#include <map>
#include <stack>
#include <stdexcept>
using namespace std;

// libevocosm
#include "evocommon.h"
#include "roulette.h"
#include "fsm_tools.h"

namespace libevocosm
{

    template <typename InputT, typename OutputT>
    class fsm : protected globals, protected fsm_tools
    {
    public:
        typedef InputT  t_input;

        typedef OutputT t_output;

        typedef typename std::pair<t_output, size_t> t_transition;

        typedef typename std::map<t_input, t_transition> t_input_map;

        typedef typename std::vector<t_input_map> t_state_table;


        fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);


        fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2);


        fsm(const fsm<InputT,OutputT> & a_source);


        virtual ~fsm();

        //  Assignment
        fsm & operator = (const fsm<InputT,OutputT> & a_source);


        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);


        t_output transition(const fsm<InputT,OutputT>::t_input & a_input);


        void reset();


        t_state_table get_table() const;


        size_t get_init_state() const;


        size_t get_current_state() const;

    protected:
        t_state_table m_state_table;

        size_t m_size;

        size_t m_init_state;

        size_t m_current_state;

        static mutation_selector g_default_selector;

    private:
        // create a state map
        t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs);
    };

    //  Static initializer
    template <typename InputT, typename OutputT>
    typename fsm<InputT,OutputT>::mutation_selector fsm<InputT,OutputT>::g_default_selector;

    //  Creation constructor
    template <typename InputT, typename OutputT>
    fsm<InputT,OutputT>::fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs)
      : m_state_table(),
        m_init_state(0),
        m_current_state(0),
        m_size(a_size)
    {
        // verify parameters
        if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1))
            throw std::runtime_error("invalid fsm creation parameters");

        for (size_t n = 0; n < m_size; ++n)
        {
            // add input map to state table
            m_state_table.push_back(create_input_map(a_inputs,a_outputs));
        }

        // set initial state and start there
        m_init_state = rand_index(m_size);
        m_current_state = m_init_state;
    }

    //  Construct via bisexual crossover
    template <typename InputT, typename OutputT>
    fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2)
      : m_state_table(a_parent1.m_state_table),
        m_init_state(0),
        m_current_state(0),
        m_size(0)
    {
        size_t n;

        // don't do anything else if fsms differ is size
        if (a_parent1.m_size != a_parent2.m_size)
            return;

        // replace states from those in second parent 50/50 chance
        for (size_t n = 0; n < m_size; ++n)
        {
            if (g_random.get_real() > 0.5)
                m_state_table[n] = a_parent2.m_state_table[n];
        }

        // calculate the size
        m_size = m_state_table.size();

        // randomize the initial state (looks like mom and dad but may act like either one!)
        if (g_random.get_real() < 0.5)
            m_init_state = a_parent1.m_init_state;
        else
            m_init_state = a_parent2.m_init_state;

        // reset for start
        m_current_state = m_init_state;
    }

    //  Copy constructor
    template <typename InputT, typename OutputT>
    fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_source)
      : m_state_table(a_source.m_state_table),
        m_init_state(a_source.m_init_state),
        m_current_state(a_source.m_current_state),
        m_size(a_source.m_size)
    {
        // nada
    }

    //  Virtual destructor
    template <typename InputT, typename OutputT>
    fsm<InputT,OutputT>::~fsm()
    {
        // nada
    }

    //  Assignment
    template <typename InputT, typename OutputT>
    fsm<InputT,OutputT> & fsm<InputT,OutputT>::operator = (const fsm<InputT,OutputT> & a_source)
    {
        if (this != &a_source)
        {
            m_state_table   = a_source.m_state_table;
            m_init_state    = a_source.m_init_state;
            m_current_state = a_source.m_current_state;
            m_size          = a_source.m_size;
        }

        return *this;
    }

    //  Mutation
    template <typename InputT, typename OutputT>
    void fsm<InputT,OutputT>::mutate(double a_rate,
                                     const std::vector<t_input> & a_inputs,
                                     const std::vector<t_output> & a_outputs,
                                     mutation_selector & a_selector)
    {
        if (g_random.get_real() < a_rate)
        {
            // pick a mutation
            switch (a_selector.get_index())
            {
                case MUTATE_OUTPUT_SYMBOL:
                {
                    // mutate output symbol
                    size_t state  = rand_index(m_size);
                    size_t input  = rand_index(a_inputs.size());
                    size_t output = rand_index(a_outputs.size());
                    m_state_table[state][a_inputs[input]].first = a_outputs[output];
                    break;
                }
                case MUTATE_TRANSITION:
                {
                    // mutate state transition
                    size_t state  = rand_index(m_size);
                    size_t input  = rand_index(a_inputs.size());
                    size_t new_state = rand_index(m_size);
                    m_state_table[state][a_inputs[input]].second = new_state;
                    break;
                }
                case MUTATE_REPLACE_STATE:
                {
                    // select state
                    size_t state  = rand_index(m_size);
                    m_state_table[state] = create_input_map(a_inputs,a_outputs);
                }
                case MUTATE_SWAP_STATES:
                {
                    // swap two states
                    size_t state1 = rand_index(m_size);
                    size_t state2;

                    do
                        state2 = rand_index(m_size);
                    while (state2 == state1);

                    t_input_map temp = m_state_table[state1];
                    m_state_table[state1] = m_state_table[state2];
                    m_state_table[state2] = temp;
                    break;
                }
                case MUTATE_INIT_STATE:
                {
                    // change initial state
                    m_init_state  = rand_index(m_size);
                    break;
                }
            }
        }

        // reset current state because init state may have changed
        m_current_state = m_init_state;
    }

    //  Cause state transition
    template <typename InputT, typename OutputT>
    typename fsm<InputT,OutputT>::t_output fsm<InputT,OutputT>::transition(const fsm<InputT,OutputT>::t_input & a_input)
    {
        // get transition state
        t_transition & trans = m_state_table[m_current_state][a_input];

        // change to new state
        m_current_state = trans.second;

        // return output symbol
        return trans.first;
    }

    //  Reset to start-up state
    template <typename InputT, typename OutputT>
    inline void fsm<InputT,OutputT>::reset()
    {
        m_current_state = m_init_state;
    }

    //  Get a copy of the internal table
    template <typename InputT, typename OutputT>
    inline typename fsm<InputT,OutputT>::t_state_table fsm<InputT,OutputT>::get_table() const
    {
        return m_state_table;
    }

    //  Get initial state
    template <typename InputT, typename OutputT>
    inline size_t fsm<InputT,OutputT>::get_init_state() const
    {
        return m_init_state;
    }

    //  Get current state
    template <typename InputT, typename OutputT>
    inline size_t fsm<InputT,OutputT>::get_current_state() const
    {
        return m_current_state;
    }

    // create a state map
    template <typename InputT, typename OutputT>
    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)
    {
        // maximum output index
        size_t max_output = a_outputs.size();

        // create an input map for this state
        t_input_map input_map;

        // for each input, define an output and a state transition
        for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input)
        {
            // pick a random output symbol and new state
            t_output out_symbol = a_outputs[rand_index(max_output)];
            size_t   new_state  = rand_index(m_size);

            // add transition data to map
            input_map[*input] = std::make_pair(out_symbol,new_state);
        }

        return input_map;
    }
};

#endif