Evocosm - A C++ Framework for Evolutionary Computing

Main Index

Created by Scott Robert Ladd at Coyote Gulch Productions.


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

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