Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


simple_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_SIMPLE_FSM_H)
00054 #define LIBEVOCOSM_SIMPLE_FSM_H
00055 
00056 // Standard C++ Library
00057 #include <cstddef>
00058 #include <stack>
00059 #include <stdexcept>
00060 using namespace std;
00061 
00062 // libevocosm
00063 #include "evocommon.h"
00064 #include "machine_tools.h"
00065 
00066 namespace libevocosm
00067 {
00069 
00077     template <size_t InSize, size_t OutSize>
00078     class simple_machine : protected globals, protected machine_tools
00079     {
00080     public:
00082         struct tranout_t
00083         {
00085             size_t m_new_state;
00086 
00088             size_t m_output;
00089         };
00090 
00092 
00096         simple_machine(size_t a_size);
00097 
00099 
00104         simple_machine(const simple_machine<InSize,OutSize> & a_parent1, const simple_machine<InSize,OutSize> & a_parent2);
00105 
00107 
00111         simple_machine(const simple_machine<InSize,OutSize> & a_source);
00112 
00114 
00118         virtual ~simple_machine();
00119 
00120         //  Assignment
00126         simple_machine & operator = (const simple_machine<InSize,OutSize> & a_source);
00127 
00129 
00141         void mutate(double a_rate);
00142 
00144 
00150         static void set_mutation_weight(mutation_id a_type, double a_weight);
00151 
00153 
00159         size_t transition(size_t a_input);
00160 
00162 
00165         void reset();
00166 
00168 
00172         size_t size() const;
00173 
00175 
00181         const tranout_t & get_transition(size_t a_state, size_t a_input) const;
00182 
00184 
00188         size_t num_input_states() const;
00189 
00191 
00195         size_t num_output_states() const;
00196 
00198 
00202         size_t init_state() const;
00203 
00205 
00209         size_t current_state() const;
00210 
00211     private:
00212         // release resources
00213         void release();
00214 
00215         // deep copy
00216         void deep_copy(const simple_machine<InSize,OutSize> & a_source);
00217 
00218     protected:
00220         tranout_t ** m_state_table;
00221 
00223         size_t m_init_state;
00224 
00226         size_t m_current_state;
00227 
00229         size_t m_size;
00230 
00232         static mutation_selector g_selector;
00233     };
00234 
00235     //  Static initializer
00236     template <size_t InSize, size_t OutSize>
00237     typename simple_machine<InSize,OutSize>::mutation_selector simple_machine<InSize,OutSize>::g_selector;
00238 
00239     // release resources
00240     template <size_t InSize, size_t OutSize>
00241     void simple_machine<InSize,OutSize>::release()
00242     {
00243         for (size_t s = 0; s < m_size; ++s)
00244             delete [] m_state_table[s];
00245 
00246         delete [] m_state_table;
00247     }
00248 
00249     // deep copy
00250     template <size_t InSize, size_t OutSize>
00251     void simple_machine<InSize,OutSize>::deep_copy(const simple_machine<InSize,OutSize> & a_source)
00252     {
00253         // allocate state table
00254         m_state_table = new tranout_t * [m_size];
00255 
00256         for (size_t s = 0; s < m_size; ++s)
00257         {
00258             // allocate an array corresponding to inputs
00259             m_state_table[s] = new tranout_t [InSize];
00260 
00261             // set transition values
00262             for (size_t i = 0; i < InSize; ++i)
00263             {
00264                 m_state_table[s][i].m_new_state = a_source.m_state_table[s][i].m_new_state;
00265                 m_state_table[s][i].m_output    = a_source.m_state_table[s][i].m_output;
00266             }
00267         }
00268     }
00269 
00270     //  Creation constructor
00271     template <size_t InSize, size_t OutSize>
00272     simple_machine<InSize,OutSize>::simple_machine(size_t a_size)
00273       : m_state_table(NULL),
00274         m_init_state(0),
00275         m_current_state(0),
00276         m_size(a_size)
00277     {
00278         // verify parameters
00279         if (m_size < 2)
00280             throw std::runtime_error("invalid simple_machine creation parameters");
00281 
00282         // allocate state table
00283         m_state_table = new tranout_t * [m_size];
00284 
00285         for (size_t s = 0; s < m_size; ++s)
00286         {
00287             // allocate an array corresponding to inputs
00288             m_state_table[s] = new tranout_t [InSize];
00289 
00290             // set transition values
00291             for (size_t i = 0; i < InSize; ++i)
00292             {
00293                 m_state_table[s][i].m_new_state = rand_index(m_size);
00294                 m_state_table[s][i].m_output    = rand_index(OutSize);
00295             }
00296         }
00297 
00298         // set initial state and start there
00299         m_init_state = rand_index(m_size);
00300         m_current_state = m_init_state;
00301     }
00302 
00303     // Construct via bisexual crossover
00304     template <size_t InSize, size_t OutSize>
00305     simple_machine<InSize,OutSize>::simple_machine(const simple_machine<InSize,OutSize> & a_parent1, const simple_machine<InSize,OutSize> & a_parent2)
00306       : m_state_table(NULL),
00307         m_init_state(0),
00308         m_current_state(0),
00309         m_size(a_parent1.m_size)
00310     {
00311         // copy first parent
00312         deep_copy(a_parent1);
00313 
00314         // don't do anything else if fsms differ is size
00315         if (a_parent1.m_size != a_parent2.m_size)
00316             return;
00317 
00318         // replace states from those in second parent 50/50 chance
00319         size_t x = rand_index(m_size);
00320 
00321         for (size_t n = x; n < m_size; ++n)
00322         {
00323             // set transition values
00324             for (size_t i = 0; i < InSize; ++i)
00325             {
00326                 m_state_table[n][i].m_new_state = a_parent2.m_state_table[n][i].m_new_state;
00327                 m_state_table[n][i].m_output    = a_parent2.m_state_table[n][i].m_output;
00328             }
00329         }
00330 
00331         // randomize the initial state (looks like mom and dad but may act like either one!)
00332         if (g_random.get_real() < 0.5)
00333             m_init_state = a_parent1.m_init_state;
00334         else
00335             m_init_state = a_parent2.m_init_state;
00336 
00337         // reset for start
00338         m_current_state = m_init_state;
00339     }
00340 
00341     //  Copy constructor
00342     template <size_t InSize, size_t OutSize>
00343     simple_machine<InSize,OutSize>::simple_machine(const simple_machine<InSize,OutSize> & a_source)
00344       : m_state_table(NULL),
00345         m_init_state(a_source.m_init_state),
00346         m_current_state(a_source.m_current_state),
00347         m_size(a_source.m_size)
00348     {
00349         // copy first parent
00350         deep_copy(a_source);
00351     }
00352 
00353     //  Virtual destructor
00354     template <size_t InSize, size_t OutSize>
00355     simple_machine<InSize,OutSize>::~simple_machine()
00356     {
00357         release();
00358     }
00359 
00360     //  Assignment
00361     template <size_t InSize, size_t OutSize>
00362     simple_machine<InSize,OutSize> & simple_machine<InSize,OutSize>::operator = (const simple_machine<InSize,OutSize> & a_source)
00363     {
00364         // release resources
00365         release();
00366 
00367         // set values
00368         m_init_state    = a_source.m_init_state;
00369         m_current_state = a_source.m_current_state;
00370         m_size          = a_source.m_size;
00371 
00372         // copy source
00373         deep_copy(a_source);
00374 
00375         return *this;
00376     }
00377 
00379     template <size_t InSize, size_t OutSize>
00380     inline void simple_machine<InSize,OutSize>::set_mutation_weight(mutation_id a_type, double a_weight)
00381     {
00382         g_selector.set_weight(a_type,a_weight);
00383     }
00384 
00385     //  Mutation
00386     template <size_t InSize, size_t OutSize>
00387     void simple_machine<InSize,OutSize>::mutate(double a_rate)
00388     {
00389         // the number of chances for mutation is based on the number of states in the machine;
00390         // larger machines thus encounter more mutations
00391         for (size_t n = 0; n < m_size; ++n)
00392         {
00393             if (g_random.get_real() < a_rate)
00394             {
00395                 // pick a mutation
00396                 switch (g_selector.get_index())
00397                 {
00398                     case MUTATE_OUTPUT_SYMBOL:
00399                     {
00400                         // mutate output symbol
00401                         size_t state  = rand_index(m_size);
00402                         size_t input  = rand_index(InSize);
00403 
00404                         size_t choice;
00405 
00406                         do
00407                         {
00408                             choice = rand_index(OutSize);
00409                         }
00410                         while (m_state_table[state][input].m_output == choice);
00411 
00412                         m_state_table[state][input].m_output = choice;
00413                         break;
00414                     }
00415                     case MUTATE_TRANSITION:
00416                     {
00417                         // mutate state transition
00418                         size_t state  = rand_index(m_size);
00419                         size_t input  = rand_index(InSize);
00420 
00421                         size_t choice;
00422 
00423                         do
00424                         {
00425                             choice = rand_index(m_size);
00426                         }
00427                         while (m_state_table[state][input].m_new_state == choice);
00428 
00429                         m_state_table[state][input].m_new_state = choice;
00430                         break;
00431                     }
00432                     case MUTATE_REPLACE_STATE:
00433                     {
00434                         // mutate state transition
00435                         size_t state  = rand_index(m_size);
00436 
00437                         // allocate an array corresponding to inputs
00438                         delete [] m_state_table[state];
00439                         m_state_table[state] = new tranout_t [InSize];
00440 
00441                         // set transition values
00442                         for (size_t i = 0; i < InSize; ++i)
00443                         {
00444                             m_state_table[state][i].m_new_state = rand_index(m_size);
00445                             m_state_table[state][i].m_output    = rand_index(OutSize);
00446                         }
00447 
00448                         break;
00449                     }
00450                     case MUTATE_SWAP_STATES:
00451                     {
00452                         // swap two states (by swapping pointers)
00453                         size_t state1 = rand_index(m_size);
00454                         size_t state2;
00455 
00456                         do
00457                             state2 = rand_index(m_size);
00458                         while (state2 == state1);
00459 
00460                         for (size_t i = 0; i < InSize; ++i)
00461                         {
00462                             tranout_t temp = m_state_table[state1][i];
00463                             m_state_table[state1][i] = m_state_table[state2][i];
00464                             m_state_table[state2][i] = temp;
00465                         }
00466 
00467                         break;
00468                     }
00469                     case MUTATE_INIT_STATE:
00470                     {
00471                         // change initial state
00472                         size_t choice;
00473 
00474                         do
00475                         {
00476                             choice = rand_index(m_size);
00477                         }
00478                         while (m_init_state == choice);
00479 
00480                         m_init_state  = choice;
00481 
00482                         break;
00483                     }
00484                 }
00485             }
00486         }
00487 
00488         // reset current state because init state may have changed
00489         m_current_state = m_init_state;
00490     }
00491 
00492     //  Cause state transition
00493     template <size_t InSize, size_t OutSize>
00494     inline size_t simple_machine<InSize,OutSize>::transition(size_t a_input)
00495     {
00496         // get output symbol for given input for current state
00497         size_t output = m_state_table[m_current_state][a_input].m_output;
00498 
00499         // change to new state
00500         m_current_state = m_state_table[m_current_state][a_input].m_new_state;
00501 
00502         // return output symbol
00503         return output;
00504     }
00505 
00506     //  Reset to start-up state
00507     template <size_t InSize, size_t OutSize>
00508     inline void simple_machine<InSize,OutSize>::reset()
00509     {
00510         m_current_state = m_init_state;
00511     }
00512 
00513     // Get size
00514     template <size_t InSize, size_t OutSize>
00515     inline size_t simple_machine<InSize,OutSize>::size() const
00516     {
00517         return m_size;
00518     }
00519 
00520     //  Get a copy of the internal table
00521     template <size_t InSize, size_t OutSize>
00522     inline const typename simple_machine<InSize,OutSize>::tranout_t & simple_machine<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
00523     {
00524         return m_state_table[a_state][a_input];
00525     }
00526 
00527     // Get number of input states
00528     template <size_t InSize, size_t OutSize>
00529     inline size_t simple_machine<InSize,OutSize>::num_input_states() const
00530     {
00531         return InSize;
00532     }
00533 
00534     // Get number of output states
00535     template <size_t InSize, size_t OutSize>
00536     inline size_t simple_machine<InSize,OutSize>::num_output_states() const
00537     {
00538         return OutSize;
00539     }
00540 
00541     //  Get initial state
00542     template <size_t InSize, size_t OutSize>
00543     inline size_t simple_machine<InSize,OutSize>::init_state() const
00544     {
00545         return m_init_state;
00546     }
00547 
00548     //  Get current state
00549     template <size_t InSize, size_t OutSize>
00550     inline size_t simple_machine<InSize,OutSize>::current_state() const
00551     {
00552         return m_current_state;
00553     }
00554 };
00555 
00556 #endif

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