simple_machine.h

/*
    Evocosm is a C++ framework for implementing evolutionary algorithms.

    Copyright 2011 Scott Robert Ladd. All rights reserved.

    Evocosm is user-supported open source software. Its continued development is dependent
    on financial support from the community. You can provide funding by visiting the Evocosm
    website at:

        http://www.coyotegulch.com

    You may license Evocosm in one of two fashions:

    1) Simplified BSD License (FreeBSD License)

    Redistribution and use in source and binary forms, with or without modification, are
    permitted provided that the following conditions are met:

    1.  Redistributions of source code must retain the above copyright notice, this list of
        conditions and the following disclaimer.

    2.  Redistributions in binary form must reproduce the above copyright notice, this list
        of conditions and the following disclaimer in the documentation and/or other materials
        provided with the distribution.

    THIS SOFTWARE IS PROVIDED BY SCOTT ROBERT LADD ``AS IS'' AND ANY EXPRESS OR IMPLIED
    WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
    FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SCOTT ROBERT LADD OR
    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
    SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
    ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
    ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    The views and conclusions contained in the software and documentation are those of the
    authors and should not be interpreted as representing official policies, either expressed
    or implied, of Scott Robert Ladd.

    2) Closed-Source Proprietary License

    If your project is a closed-source or proprietary project, the Simplified BSD License may
    not be appropriate or desirable. In such cases, contact the Evocosm copyright holder to
    arrange your purchase of an appropriate license.

    The author can be contacted at:

          scott.ladd@coyotegulch.com
          scott.ladd@gmail.com
          http:www.coyotegulch.com
*/

#if !defined(LIBEVOCOSM_SIMPLE_FSM_H)
#define LIBEVOCOSM_SIMPLE_FSM_H

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

// libevocosm
#include "evocommon.h"
#include "machine_tools.h"

namespace libevocosm
{

    template <size_t InSize, size_t OutSize>
    class simple_machine : protected globals, protected machine_tools
    {
    public:
        struct tranout_t
        {
            size_t m_new_state;

            size_t m_output;
        };


        simple_machine(size_t a_size);


        simple_machine(const simple_machine<InSize,OutSize> & a_parent1, const simple_machine<InSize,OutSize> & a_parent2);


        simple_machine(const simple_machine<InSize,OutSize> & a_source);


        virtual ~simple_machine();

        //  Assignment
        simple_machine & operator = (const simple_machine<InSize,OutSize> & a_source);


        void mutate(double a_rate);


        static void set_mutation_weight(mutation_id a_type, double a_weight);


        size_t transition(size_t a_input);


        void reset();


        size_t size() const;


        const tranout_t & get_transition(size_t a_state, size_t a_input) const;


        size_t num_input_states() const;


        size_t num_output_states() const;


        size_t init_state() const;


        size_t current_state() const;

    private:
        // release resources
        void release();

        // deep copy
        void deep_copy(const simple_machine<InSize,OutSize> & a_source);

    protected:
        tranout_t ** m_state_table;

        size_t m_init_state;

        size_t m_current_state;

        size_t m_size;

        static mutation_selector g_selector;
    };

    //  Static initializer
    template <size_t InSize, size_t OutSize>
    typename simple_machine<InSize,OutSize>::mutation_selector simple_machine<InSize,OutSize>::g_selector;

    // release resources
    template <size_t InSize, size_t OutSize>
    void simple_machine<InSize,OutSize>::release()
    {
        for (size_t s = 0; s < m_size; ++s)
            delete [] m_state_table[s];

        delete [] m_state_table;
    }

    // deep copy
    template <size_t InSize, size_t OutSize>
    void simple_machine<InSize,OutSize>::deep_copy(const simple_machine<InSize,OutSize> & a_source)
    {
        // allocate state table
        m_state_table = new tranout_t * [m_size];

        for (size_t s = 0; s < m_size; ++s)
        {
            // allocate an array corresponding to inputs
            m_state_table[s] = new tranout_t [InSize];

            // set transition values
            for (size_t i = 0; i < InSize; ++i)
            {
                m_state_table[s][i].m_new_state = a_source.m_state_table[s][i].m_new_state;
                m_state_table[s][i].m_output    = a_source.m_state_table[s][i].m_output;
            }
        }
    }

    //  Creation constructor
    template <size_t InSize, size_t OutSize>
    simple_machine<InSize,OutSize>::simple_machine(size_t a_size)
      : m_state_table(NULL),
        m_init_state(0),
        m_current_state(0),
        m_size(a_size)
    {
        // verify parameters
        if (m_size < 2)
            throw std::runtime_error("invalid simple_machine creation parameters");

        // allocate state table
        m_state_table = new tranout_t * [m_size];

        for (size_t s = 0; s < m_size; ++s)
        {
            // allocate an array corresponding to inputs
            m_state_table[s] = new tranout_t [InSize];

            // set transition values
            for (size_t i = 0; i < InSize; ++i)
            {
                m_state_table[s][i].m_new_state = rand_index(m_size);
                m_state_table[s][i].m_output    = rand_index(OutSize);
            }
        }

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

    // Construct via bisexual crossover
    template <size_t InSize, size_t OutSize>
    simple_machine<InSize,OutSize>::simple_machine(const simple_machine<InSize,OutSize> & a_parent1, const simple_machine<InSize,OutSize> & a_parent2)
      : m_state_table(NULL),
        m_init_state(0),
        m_current_state(0),
        m_size(a_parent1.m_size)
    {
        // copy first parent
        deep_copy(a_parent1);

        // 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
        size_t x = rand_index(m_size);

        for (size_t n = x; n < m_size; ++n)
        {
            // set transition values
            for (size_t i = 0; i < InSize; ++i)
            {
                m_state_table[n][i].m_new_state = a_parent2.m_state_table[n][i].m_new_state;
                m_state_table[n][i].m_output    = a_parent2.m_state_table[n][i].m_output;
            }
        }

        // 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 <size_t InSize, size_t OutSize>
    simple_machine<InSize,OutSize>::simple_machine(const simple_machine<InSize,OutSize> & a_source)
      : m_state_table(NULL),
        m_init_state(a_source.m_init_state),
        m_current_state(a_source.m_current_state),
        m_size(a_source.m_size)
    {
        // copy first parent
        deep_copy(a_source);
    }

    //  Virtual destructor
    template <size_t InSize, size_t OutSize>
    simple_machine<InSize,OutSize>::~simple_machine()
    {
        release();
    }

    //  Assignment
    template <size_t InSize, size_t OutSize>
    simple_machine<InSize,OutSize> & simple_machine<InSize,OutSize>::operator = (const simple_machine<InSize,OutSize> & a_source)
    {
        // release resources
        release();

        // set values
        m_init_state    = a_source.m_init_state;
        m_current_state = a_source.m_current_state;
        m_size          = a_source.m_size;

        // copy source
        deep_copy(a_source);

        return *this;
    }

    template <size_t InSize, size_t OutSize>
    inline void simple_machine<InSize,OutSize>::set_mutation_weight(mutation_id a_type, double a_weight)
    {
        g_selector.set_weight(a_type,a_weight);
    }

    //  Mutation
    template <size_t InSize, size_t OutSize>
    void simple_machine<InSize,OutSize>::mutate(double a_rate)
    {
        // the number of chances for mutation is based on the number of states in the machine;
        // larger machines thus encounter more mutations
        for (size_t n = 0; n < m_size; ++n)
        {
            if (g_random.get_real() < a_rate)
            {
                // pick a mutation
                switch (g_selector.get_index())
                {
                    case MUTATE_OUTPUT_SYMBOL:
                    {
                        // mutate output symbol
                        size_t state  = rand_index(m_size);
                        size_t input  = rand_index(InSize);

                        size_t choice;

                        do
                        {
                            choice = rand_index(OutSize);
                        }
                        while (m_state_table[state][input].m_output == choice);

                        m_state_table[state][input].m_output = choice;
                        break;
                    }
                    case MUTATE_TRANSITION:
                    {
                        // mutate state transition
                        size_t state  = rand_index(m_size);
                        size_t input  = rand_index(InSize);

                        size_t choice;

                        do
                        {
                            choice = rand_index(m_size);
                        }
                        while (m_state_table[state][input].m_new_state == choice);

                        m_state_table[state][input].m_new_state = choice;
                        break;
                    }
                    case MUTATE_REPLACE_STATE:
                    {
                        // mutate state transition
                        size_t state  = rand_index(m_size);

                        // allocate an array corresponding to inputs
                        delete [] m_state_table[state];
                        m_state_table[state] = new tranout_t [InSize];

                        // set transition values
                        for (size_t i = 0; i < InSize; ++i)
                        {
                            m_state_table[state][i].m_new_state = rand_index(m_size);
                            m_state_table[state][i].m_output    = rand_index(OutSize);
                        }

                        break;
                    }
                    case MUTATE_SWAP_STATES:
                    {
                        // swap two states (by swapping pointers)
                        size_t state1 = rand_index(m_size);
                        size_t state2;

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

                        for (size_t i = 0; i < InSize; ++i)
                        {
                            tranout_t temp = m_state_table[state1][i];
                            m_state_table[state1][i] = m_state_table[state2][i];
                            m_state_table[state2][i] = temp;
                        }

                        break;
                    }
                    case MUTATE_INIT_STATE:
                    {
                        // change initial state
                        size_t choice;

                        do
                        {
                            choice = rand_index(m_size);
                        }
                        while (m_init_state == choice);

                        m_init_state  = choice;

                        break;
                    }
                }
            }
        }

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

    //  Cause state transition
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::transition(size_t a_input)
    {
        // get output symbol for given input for current state
        size_t output = m_state_table[m_current_state][a_input].m_output;

        // change to new state
        m_current_state = m_state_table[m_current_state][a_input].m_new_state;

        // return output symbol
        return output;
    }

    //  Reset to start-up state
    template <size_t InSize, size_t OutSize>
    inline void simple_machine<InSize,OutSize>::reset()
    {
        m_current_state = m_init_state;
    }

    // Get size
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::size() const
    {
        return m_size;
    }

    //  Get a copy of the internal table
    template <size_t InSize, size_t OutSize>
    inline const typename simple_machine<InSize,OutSize>::tranout_t & simple_machine<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
    {
        return m_state_table[a_state][a_input];
    }

    // Get number of input states
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::num_input_states() const
    {
        return InSize;
    }

    // Get number of output states
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::num_output_states() const
    {
        return OutSize;
    }

    //  Get initial state
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::init_state() const
    {
        return m_init_state;
    }

    //  Get current state
    template <size_t InSize, size_t OutSize>
    inline size_t simple_machine<InSize,OutSize>::current_state() const
    {
        return m_current_state;
    }
};

#endif