Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


fuzzy_machine.h

00001 //---------------------------------------------------------------------
00002 //  Algorithmic Conjurings @ http://www.coyotegulch.com
00003 //  Evocosm -- An Object-Oriented Framework for Evolutionary Algorithms
00004 //
00005 //  fuzzy_machine.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_FUZZY_MACHINE_H)
00036 #define LIBEVOCOSM_FUZZY_MACHINE_H
00037 
00038 // Standard C++ Library
00039 #include <cstddef>
00040 #include <stack>
00041 #include <stdexcept>
00042 #ifdef DEBUG
00043 #include <iostream>
00044 #include <iomanip>
00045 #endif
00046 using namespace std;
00047 
00048 // libevocosm
00049 #include "evocommon.h"
00050 #include "fsm_tools.h"
00051 
00052 namespace libevocosm
00053 {
00055 
00068     template <size_t InSize, size_t OutSize>
00069     class fuzzy_machine : protected globals, protected fsm_tools
00070     {
00071     public:
00073         struct tranout_t
00074         {
00076             roulette_wheel m_new_state;
00077             
00079             roulette_wheel m_output;
00080             
00082             tranout_t(double * state_weights, size_t num_states, double * output_weights)
00083               : m_new_state(state_weights, num_states),
00084                 m_output(output_weights, OutSize)
00085             {
00086                 // nada
00087             }
00088             
00090             tranout_t(const tranout_t & source)
00091               : m_new_state(source.m_new_state),
00092                 m_output(source.m_output)
00093             {
00094                 // nada
00095             }
00096             
00098             tranout_t & operator = (const tranout_t & source)
00099             {
00100                 m_new_state = source.m_new_state;
00101                 m_output    = source.m_output;
00102                 return *this;
00103             }
00104         };
00105 
00107 
00117         fuzzy_machine(size_t a_size,
00118                       double a_output_base,
00119                       double a_output_range,
00120                       double a_state_base,
00121                       double a_state_range);
00122 
00124 
00128         fuzzy_machine(size_t a_size);
00129 
00131 
00136         fuzzy_machine(const fuzzy_machine<InSize,OutSize> & a_parent1, const fuzzy_machine<InSize,OutSize> & a_parent2);
00137 
00139 
00143         fuzzy_machine(const fuzzy_machine<InSize,OutSize> & a_source);
00144 
00146 
00150         virtual ~fuzzy_machine();
00151 
00152         //  Assignment
00158         fuzzy_machine & operator = (const fuzzy_machine<InSize,OutSize> & a_source);
00159 
00161 
00173         void mutate(double a_rate);
00174         
00176 
00182         static void set_mutation_weight(mutation_id a_type, double a_weight);
00183         
00185 
00191         size_t transition(size_t a_input);
00192 
00194 
00197         void reset();
00198 
00200 
00204         size_t size() const;
00205 
00207 
00213         const tranout_t & get_transition(size_t a_state, size_t a_input) const;
00214         
00216 
00220         size_t num_input_states() const;
00221 
00223 
00227         size_t num_output_states() const;
00228         
00230 
00234         size_t init_state() const;
00235 
00237 
00241         size_t current_state() const;
00242         
00244 
00254         tranout_t *** state_table()
00255         {
00256             return m_state_table;
00257         }
00258 
00259         #ifdef DEBUG
00260         void dump(const char * description, ostream & a_stream = cerr) const;
00261         #endif
00262 
00263     private:
00264         // release resources
00265         void release();
00266 
00267         // deep copy
00268         void deep_copy(const fuzzy_machine<InSize,OutSize> & a_source);
00269 
00270     protected:
00272         tranout_t *** m_state_table;
00273 
00275         size_t m_size;
00276 
00278         size_t m_init_state;
00279 
00281         size_t m_current_state;
00282 
00284         double m_output_base;
00285         
00287         double m_output_range;
00288         
00290         double m_state_base;
00291         
00293         double m_state_range;
00294         
00296         static mutation_selector g_selector;
00297     };
00298 
00299     //  Static initializer
00300     template <size_t InSize, size_t OutSize>
00301     typename fuzzy_machine<InSize,OutSize>::mutation_selector fuzzy_machine<InSize,OutSize>::g_selector;
00302 
00303     // release resources
00304     template <size_t InSize, size_t OutSize>
00305     void fuzzy_machine<InSize,OutSize>::release()
00306     {
00307         for (size_t s = 0; s < m_size; ++s)
00308         {
00309             for (size_t i = 0; i < InSize; ++i)
00310                 delete m_state_table[s][i];
00311             
00312             delete [] m_state_table[s];
00313         }
00314 
00315         delete [] m_state_table;
00316     }
00317 
00318     // deep copy
00319     template <size_t InSize, size_t OutSize>
00320     void fuzzy_machine<InSize,OutSize>::deep_copy(const fuzzy_machine<InSize,OutSize> & a_source)
00321     {
00322         // allocate state table
00323         m_state_table = new tranout_t ** [m_size];
00324 
00325         for (size_t s = 0; s < m_size; ++s)
00326         {
00327             // allocate an array corresponding to inputs
00328             m_state_table[s] = new tranout_t * [InSize];
00329 
00330             // set transition values
00331             for (size_t i = 0; i < InSize; ++i)
00332                 m_state_table[s][i] = new tranout_t(*(a_source.m_state_table[s][i]));
00333         }
00334     }
00335 
00336     //  Creation constructor
00337     template <size_t InSize, size_t OutSize>
00338     fuzzy_machine<InSize,OutSize>::fuzzy_machine(size_t a_size,
00339                                                  double a_output_base,
00340                                                  double a_output_range,
00341                                                  double a_state_base,
00342                                                  double a_state_range)
00343       : m_state_table(NULL),
00344         m_size(a_size),
00345         m_init_state(0),
00346         m_current_state(0),
00347         m_output_base(a_output_base),
00348         m_output_range(a_output_range),
00349         m_state_base(a_state_base),
00350         m_state_range(a_state_range)
00351     {
00352         // verify parameters
00353         if (m_size < 2)
00354             throw std::runtime_error("invalid fuzzy_machine creation parameters");
00355 
00356         // allocate state table
00357         m_state_table = new tranout_t ** [m_size];
00358 
00359         // tables of weights for roulette wheels
00360         double * output_weights = new double[OutSize];
00361         double * state_weights  = new double[m_size];
00362         
00363         for (size_t s = 0; s < m_size; ++s)
00364         {
00365             // allocate an array corresponding to inputs
00366             m_state_table[s] = new tranout_t * [InSize];
00367 
00368             for (size_t i = 0; i < InSize; ++i)
00369             {
00370                 // define weights
00371                 size_t n; 
00372 
00373                 for (n = 0; n < OutSize; ++n)
00374                     output_weights[n] = g_random.get_rand_real2() * a_output_range + a_output_base;
00375 
00376                 for (n = 0; n < m_size; ++n)
00377                     state_weights[n] = g_random.get_rand_real2() * a_state_range + a_state_base;
00378 
00379                 // set transition values
00380                 m_state_table[s][i] = new tranout_t(state_weights,m_size,output_weights);
00381             }
00382         }
00383             
00384         delete [] output_weights;
00385         delete [] state_weights;
00386 
00387         // set initial state and start there
00388         m_init_state    = g_random.get_rand_index(m_size);
00389         m_current_state = m_init_state;
00390     }
00391 
00392     //  Creation constructor
00393     template <size_t InSize, size_t OutSize>
00394     fuzzy_machine<InSize,OutSize>::fuzzy_machine(size_t a_size)
00395       : m_state_table(NULL),
00396         m_size(a_size),
00397         m_init_state(0),
00398         m_current_state(0),
00399         m_output_base(1.0),
00400         m_output_range(100.0),
00401         m_state_base(1.0),
00402         m_state_range(100.0)
00403     {
00404         // verify parameters
00405         if (m_size < 2)
00406             throw std::runtime_error("invalid fuzzy_machine creation parameters");
00407 
00408         // allocate state table
00409         m_state_table = new tranout_t ** [m_size];
00410 
00411         // tables of weights for roulette wheels
00412         double * output_weights = new double[OutSize];
00413         double * state_weights  = new double[m_size];
00414         
00415         for (size_t s = 0; s < m_size; ++s)
00416         {
00417             // allocate an array corresponding to inputs
00418             m_state_table[s] = new tranout_t * [InSize];
00419 
00420             for (size_t i = 0; i < InSize; ++i)
00421             {
00422                 // define weights
00423                 size_t n; 
00424 
00425                 for (n = 0; n < OutSize; ++n)
00426                     output_weights[n] = 1.0; 
00427                 
00428                 output_weights[g_random.get_rand_index(OutSize)] = 100.0;
00429 
00430                 for (n = 0; n < m_size; ++n)
00431                     state_weights[n] = 1.0;
00432                 
00433                 state_weights[g_random.get_rand_index(m_size)] = 100.0;
00434 
00435                 // set transition values
00436                 m_state_table[s][i] = new tranout_t(state_weights,m_size,output_weights);
00437             }
00438         }
00439             
00440         delete [] output_weights;
00441         delete [] state_weights;
00442 
00443         // set initial state and start there
00444         m_init_state = g_random.get_rand_index(m_size);
00445         m_current_state = m_init_state;
00446     }
00447 
00448     // Construct via bisexual crossover
00449     template <size_t InSize, size_t OutSize>
00450     fuzzy_machine<InSize,OutSize>::fuzzy_machine(const fuzzy_machine<InSize,OutSize> & a_parent1, const fuzzy_machine<InSize,OutSize> & a_parent2)
00451       : m_state_table(NULL),
00452         m_size(a_parent1.m_size),
00453         m_init_state(0),
00454         m_current_state(0),
00455         m_output_base(a_parent1.m_output_base),
00456         m_output_range(a_parent1.m_output_range),
00457         m_state_base(a_parent1.m_state_base),
00458         m_state_range(a_parent1.m_state_range)
00459     {
00460         #ifdef DEBUG
00461         cerr << "\n<< crossover operation >>\n";
00462         a_parent1.dump("PARENT1");
00463         a_parent2.dump("PARENT2");
00464         #endif
00465 
00466         // copy first parent
00467         deep_copy(a_parent1);
00468 
00469         // don't do anything else if fsms differ is size
00470         if ((a_parent1.m_size != a_parent2.m_size) || (&a_parent1 == &a_parent2))
00471             return;
00472 
00473         // pick a crossover point
00474         size_t x = g_random.get_rand_index(m_size);
00475         
00476         #ifdef DEBUG
00477         cerr << "crossover at " << x << "\n";
00478         #endif
00479                 
00480         for (size_t n = x; n < m_size; ++n)
00481         {
00482             // set transition values
00483             for (size_t i = 0; i < InSize; ++i)
00484             {
00485                 delete m_state_table[n][i];
00486                 m_state_table[n][i] = new tranout_t(*a_parent2.m_state_table[n][i]);
00487             }
00488         }
00489 
00490         // randomize the initial state (looks like mom and dad but may act like either one!)
00491         if (g_random.get_rand_real2() < 0.5)
00492             m_init_state = a_parent1.m_init_state;
00493         else
00494             m_init_state = a_parent2.m_init_state;
00495 
00496         // reset for start
00497         m_current_state = m_init_state;
00498         
00499         #ifdef DEBUG
00500         dump("CHILD");
00501         #endif
00502     }
00503 
00504     //  Copy constructor
00505     template <size_t InSize, size_t OutSize>
00506     fuzzy_machine<InSize,OutSize>::fuzzy_machine(const fuzzy_machine<InSize,OutSize> & a_source)
00507       : m_state_table(NULL),
00508         m_size(a_source.m_size),
00509         m_init_state(a_source.m_init_state),
00510         m_current_state(a_source.m_current_state),
00511         m_output_base(a_source.m_output_base),
00512         m_output_range(a_source.m_output_range),
00513         m_state_base(a_source.m_state_base),
00514         m_state_range(a_source.m_state_range)
00515     {
00516         // copy first parent
00517         deep_copy(a_source);
00518     }
00519 
00520     //  Virtual destructor
00521     template <size_t InSize, size_t OutSize>
00522     fuzzy_machine<InSize,OutSize>::~fuzzy_machine()
00523     {
00524         release();
00525     }
00526 
00527     //  Assignment
00528     template <size_t InSize, size_t OutSize>
00529     fuzzy_machine<InSize,OutSize> & fuzzy_machine<InSize,OutSize>::operator = (const fuzzy_machine<InSize,OutSize> & a_source)
00530     {
00531         // release resources
00532         release();
00533 
00534         // set values
00535         m_init_state    = a_source.m_init_state;
00536         m_current_state = a_source.m_current_state;
00537         m_size          = a_source.m_size;
00538         m_output_base   = a_source.m_output_base;
00539         m_output_range  = a_source.m_output_range;
00540         m_state_base    = a_source.m_state_base;
00541         m_state_range   = a_source.m_state_range;
00542 
00543         // copy source
00544         deep_copy(a_source);
00545 
00546         return *this;
00547     }
00548 
00550     template <size_t InSize, size_t OutSize>
00551     inline void fuzzy_machine<InSize,OutSize>::set_mutation_weight(mutation_id a_type, double a_weight)
00552     {
00553         g_selector.set_weight(a_type,a_weight);
00554     }
00555     
00556     //  Mutation
00557     template <size_t InSize, size_t OutSize>
00558     void fuzzy_machine<InSize,OutSize>::mutate(double a_rate)
00559     {
00560         // the number of chances for mutation is based on the number of states in the machine;
00561         // larger machines thus encounter more mutations
00562         #ifdef DEBUG
00563         cerr << "\n<< mutation operation >>\n";
00564         dump("BEFORE");
00565         #endif
00566 
00567         for (size_t n = 0; n < m_size; ++n)
00568         {
00569             if (g_random.get_rand_real2() < a_rate)
00570             {
00571                 // pick a mutation
00572                 switch (g_selector.get_index())
00573                 {
00574                     case MUTATE_OUTPUT_SYMBOL:
00575                     {
00576                         // mutate output symbol
00577                         size_t state  = g_random.get_rand_index(m_size);
00578                         size_t input  = g_random.get_rand_index(InSize);
00579                         size_t index  = g_random.get_rand_index(OutSize);
00580 
00581                         #ifdef DEBUG
00582                         cerr << "MUTATE_OUTPUT_SYMBOL, state " << state << ", input " << input << ", index " << index << "\n";
00583                         #endif
00584                         
00585                         double new_weight = m_output_base + m_output_range * g_random.get_rand_real3();
00586                         m_state_table[state][input]->m_output.set_weight(index,new_weight);
00587                         break;
00588                     }    
00589                     case MUTATE_TRANSITION:
00590                     {
00591                         // mutate state transition
00592                         size_t state  = g_random.get_rand_index(m_size);
00593                         size_t input  = g_random.get_rand_index(InSize);
00594                         size_t index  = g_random.get_rand_index(m_size);
00595 
00596                         #ifdef DEBUG
00597                         cerr << "MUTATE_TRANSITION, state " << state << ", input " << input << ", index " << index << "\n";
00598                         #endif
00599                         
00600                         double new_weight = m_state_base + m_state_range * g_random.get_rand_real3();
00601                         m_state_table[state][input]->m_new_state.set_weight(index,new_weight);
00602                         break;
00603                     }
00604                     case MUTATE_REPLACE_STATE:
00605                     {
00606                         // select mutated state
00607                         size_t state  = g_random.get_rand_index(m_size);
00608 
00609                         #ifdef DEBUG
00610                         cerr << "REPLACE_STATE, state " << state << "\n";
00611                         #endif
00612                         
00613                         // allocate an array corresponding to inputs
00614                         delete [] m_state_table[state];
00615                         m_state_table[state] = new tranout_t * [InSize];
00616 
00617                         // tables of weights for roulette wheels
00618                         double * output_weights = new double[OutSize];
00619                         double * state_weights  = new double[m_size];
00620 
00621                         for (size_t i = 0; i < InSize; ++i)
00622                         {
00623                             // define weights
00624                             size_t n; 
00625 
00626                             for (n = 0; n < OutSize; ++n)
00627                                 output_weights[n] = 1.0; 
00628 
00629                             output_weights[g_random.get_rand_index(OutSize)] = 100.0;
00630 
00631                             for (n = 0; n < m_size; ++n)
00632                                 state_weights[n] = 1.0;
00633 
00634                             state_weights[g_random.get_rand_index(m_size)] = 100.0;
00635 
00636                             // set transition values
00637                             m_state_table[state][i] = new tranout_t(state_weights,m_size,output_weights);
00638                         }
00639 
00640                         delete [] output_weights;
00641                         delete [] state_weights;
00642 
00643                         break;                        
00644                     }
00645                     case MUTATE_SWAP_STATES:
00646                     {
00647                         // swap two states (by swapping pointers)
00648                         size_t state1 = g_random.get_rand_index(m_size);
00649                         size_t state2;
00650             
00651                         do
00652                             state2 = static_cast<size_t>(g_random.get_rand_index(m_size));
00653                         while (state2 == state1);
00654                         
00655                         #ifdef DEBUG
00656                         cerr << "MUTATE_SWAP_STATES, " << state1 << " with " << state2 << "\n";
00657                         #endif
00658             
00659                         for (size_t i = 0; i < InSize; ++i)
00660                         {
00661                             tranout_t * temp         = m_state_table[state1][i];
00662                             m_state_table[state1][i] = m_state_table[state2][i];
00663                             m_state_table[state2][i] = temp;
00664                         }
00665 
00666                         break;
00667                     }    
00668                     case MUTATE_INIT_STATE:
00669                     {
00670                         // change initial state
00671                         #ifdef DEBUG
00672                         cerr << "MUTATE_INIT_STATE\n";
00673                         #endif
00674                         m_init_state  = g_random.get_rand_index(m_size);
00675                         break;
00676                     }
00677                     #ifdef DEBUG
00678                     default:
00679                         cerr << "UNKNOWN MUTATION!\n";
00680                     #endif
00681                 }
00682             }
00683         }
00684         
00685         // reset current state because init state may have changed
00686         
00687         m_current_state = m_init_state;
00688         #ifdef DEBUG
00689         dump("AFTER");
00690         #endif
00691     }
00692 
00693     //  Cause state transition
00694     template <size_t InSize, size_t OutSize>
00695     inline size_t fuzzy_machine<InSize,OutSize>::transition(size_t a_input)
00696     {
00697         // get output symbol for given input for current state
00698         size_t output = m_state_table[m_current_state][a_input]->m_output.get_index();
00699 
00700         // change to new state
00701         m_current_state = m_state_table[m_current_state][a_input]->m_new_state.get_index();
00702 
00703         // return output symbol
00704         return output;
00705     }
00706 
00707     //  Reset to start-up state
00708     template <size_t InSize, size_t OutSize>
00709     inline void fuzzy_machine<InSize,OutSize>::reset()
00710     {
00711         m_current_state = m_init_state;
00712     }
00713 
00714     // Get size
00715     template <size_t InSize, size_t OutSize>
00716     inline size_t fuzzy_machine<InSize,OutSize>::size() const
00717     {
00718         return m_size;
00719     }
00720 
00721     //  Get a copy of the internal table
00722     template <size_t InSize, size_t OutSize>
00723     inline const typename fuzzy_machine<InSize,OutSize>::tranout_t & fuzzy_machine<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const
00724     {
00725         return *m_state_table[a_state][a_input];
00726     }
00727 
00728     // Get number of input states
00729     template <size_t InSize, size_t OutSize>
00730     inline size_t fuzzy_machine<InSize,OutSize>::num_input_states() const
00731     {
00732         return InSize;
00733     }
00734 
00735     // Get number of output states
00736     template <size_t InSize, size_t OutSize>
00737     inline size_t fuzzy_machine<InSize,OutSize>::num_output_states() const
00738     {
00739         return OutSize;
00740     }
00741         
00742     //  Get initial state
00743     template <size_t InSize, size_t OutSize>
00744     inline size_t fuzzy_machine<InSize,OutSize>::init_state() const
00745     {
00746         return m_init_state;
00747     }
00748 
00749     //  Get current state
00750     template <size_t InSize, size_t OutSize>
00751     inline size_t fuzzy_machine<InSize,OutSize>::current_state() const
00752     {
00753         return m_current_state;
00754     }
00755     
00756     #ifdef DEBUG
00757     template <size_t InSize, size_t OutSize>
00758     void fuzzy_machine<InSize,OutSize>::dump(const char * description, ostream & a_stream) const
00759     {
00760         a_stream << "----------\nDumping machine " << description << " (" << hex << this
00761                  << ")\ninitial state = " << m_init_state
00762                  << "\ncurrent state = " << m_current_state << "\n\n";
00763         
00764         for (size_t s = 0; s < m_size; ++s)
00765         {
00766             a_stream << "state " << s;
00767             
00768             for (size_t i = 0; i < InSize; ++i)
00769             {
00770                 size_t n;
00771                 
00772                 a_stream << "\n  output weights:";
00773                 
00774                 for (n = 0; n < OutSize; ++n)
00775                     a_stream << " " << m_state_table[s][i]->m_output.get_weight(n);
00776 
00777                 a_stream << "\n  state  weights:";
00778                 
00779                 for (n = 0; n < m_size; ++n)
00780                     a_stream << " " << m_state_table[s][i]->m_new_state.get_weight(n);
00781                 
00782                 a_stream << endl;
00783             }
00784         }
00785         
00786         a_stream << "----------" << endl;
00787     }
00788     #endif    
00789 };
00790 
00791 #endif

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