Created by Scott Robert Ladd at Coyote Gulch Productions.
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_FSM_H) 00054 #define LIBEVOCOSM_FSM_H 00055 00056 // Standard C++ Library 00057 #include <cstddef> 00058 #include <vector> 00059 #include <map> 00060 #include <stack> 00061 #include <stdexcept> 00062 using namespace std; 00063 00064 // libevocosm 00065 #include "evocommon.h" 00066 #include "roulette.h" 00067 #include "machine_tools.h" 00068 00069 namespace libevocosm 00070 { 00072 00086 template <typename InputT, typename OutputT> 00087 class state_machine : protected globals, protected fsm_tools 00088 { 00089 public: 00091 typedef InputT t_input; 00092 00094 typedef OutputT t_output; 00095 00097 typedef typename std::pair<t_output, size_t> t_transition; 00098 00100 typedef typename std::map<t_input, t_transition> t_input_map; 00101 00103 typedef typename std::vector<t_input_map> t_state_table; 00104 00106 00113 state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs); 00114 00116 00125 state_machine(const state_machine<InputT,OutputT> & a_parent1, const state_machine<InputT,OutputT> & a_parent2); 00126 00128 00132 state_machine(const state_machine<InputT,OutputT> & a_source); 00133 00135 00139 virtual ~state_machine(); 00140 00141 // Assignment 00146 state_machine & operator = (const state_machine<InputT,OutputT> & a_source); 00147 00149 00164 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); 00165 00167 00172 t_output transition(const state_machine<InputT,OutputT>::t_input & a_input); 00173 00175 00178 void reset(); 00179 00181 00186 t_state_table get_table() const; 00187 00189 00193 size_t get_init_state() const; 00194 00196 00200 size_t get_current_state() const; 00201 00202 protected: 00204 t_state_table m_state_table; 00205 00207 size_t m_size; 00208 00210 size_t m_init_state; 00211 00213 size_t m_current_state; 00214 00216 static mutation_selector g_default_selector; 00217 00218 private: 00219 // create a state map 00220 t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs); 00221 }; 00222 00223 // Static initializer 00224 template <typename InputT, typename OutputT> 00225 typename state_machine<InputT,OutputT>::mutation_selector state_machine<InputT,OutputT>::g_default_selector; 00226 00227 // Creation constructor 00228 template <typename InputT, typename OutputT> 00229 state_machine<InputT,OutputT>::state_machine(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs) 00230 : m_state_table(), 00231 m_init_state(0), 00232 m_current_state(0), 00233 m_size(a_size) 00234 { 00235 // verify parameters 00236 if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1)) 00237 throw std::runtime_error("invalid state_machine creation parameters"); 00238 00239 for (size_t n = 0; n < m_size; ++n) 00240 { 00241 // add input map to state table 00242 m_state_table.push_back(create_input_map(a_inputs,a_outputs)); 00243 } 00244 00245 // set initial state and start there 00246 m_init_state = rand_index(m_size); 00247 m_current_state = m_init_state; 00248 } 00249 00250 // Construct via bisexual crossover 00251 template <typename InputT, typename OutputT> 00252 state_machine<InputT,OutputT>::state_machine(const state_machine<InputT,OutputT> & a_parent1, const state_machine<InputT,OutputT> & a_parent2) 00253 : m_state_table(a_parent1.m_state_table), 00254 m_init_state(0), 00255 m_current_state(0), 00256 m_size(0) 00257 { 00258 size_t n; 00259 00260 // don't do anything else if fsms differ is size 00261 if (a_parent1.m_size != a_parent2.m_size) 00262 return; 00263 00264 // replace states from those in second parent 50/50 chance 00265 for (size_t n = 0; n < m_size; ++n) 00266 { 00267 if (g_random.get_real() > 0.5) 00268 m_state_table[n] = a_parent2.m_state_table[n]; 00269 } 00270 00271 // calculate the size 00272 m_size = m_state_table.size(); 00273 00274 // randomize the initial state (looks like mom and dad but may act like either one!) 00275 if (g_random.get_real() < 0.5) 00276 m_init_state = a_parent1.m_init_state; 00277 else 00278 m_init_state = a_parent2.m_init_state; 00279 00280 // reset for start 00281 m_current_state = m_init_state; 00282 } 00283 00284 // Copy constructor 00285 template <typename InputT, typename OutputT> 00286 state_machine<InputT,OutputT>::state_machine(const state_machine<InputT,OutputT> & a_source) 00287 : m_state_table(a_source.m_state_table), 00288 m_init_state(a_source.m_init_state), 00289 m_current_state(a_source.m_current_state), 00290 m_size(a_source.m_size) 00291 { 00292 // nada 00293 } 00294 00295 // Virtual destructor 00296 template <typename InputT, typename OutputT> 00297 state_machine<InputT,OutputT>::~state_machine() 00298 { 00299 // nada 00300 } 00301 00302 // Assignment 00303 template <typename InputT, typename OutputT> 00304 state_machine<InputT,OutputT> & state_machine<InputT,OutputT>::operator = (const state_machine<InputT,OutputT> & a_source) 00305 { 00306 if (this != &a_source) 00307 { 00308 m_state_table = a_source.m_state_table; 00309 m_init_state = a_source.m_init_state; 00310 m_current_state = a_source.m_current_state; 00311 m_size = a_source.m_size; 00312 } 00313 00314 return *this; 00315 } 00316 00317 // Mutation 00318 template <typename InputT, typename OutputT> 00319 void state_machine<InputT,OutputT>::mutate(double a_rate, 00320 const std::vector<t_input> & a_inputs, 00321 const std::vector<t_output> & a_outputs, 00322 mutation_selector & a_selector) 00323 { 00324 if (g_random.get_real() < a_rate) 00325 { 00326 // pick a mutation 00327 switch (a_selector.get_index()) 00328 { 00329 case MUTATE_OUTPUT_SYMBOL: 00330 { 00331 // mutate output symbol 00332 size_t state = rand_index(m_size); 00333 size_t input = rand_index(a_inputs.size()); 00334 size_t output = rand_index(a_outputs.size()); 00335 m_state_table[state][a_inputs[input]].first = a_outputs[output]; 00336 break; 00337 } 00338 case MUTATE_TRANSITION: 00339 { 00340 // mutate state transition 00341 size_t state = rand_index(m_size); 00342 size_t input = rand_index(a_inputs.size()); 00343 size_t new_state = rand_index(m_size); 00344 m_state_table[state][a_inputs[input]].second = new_state; 00345 break; 00346 } 00347 case MUTATE_REPLACE_STATE: 00348 { 00349 // select state 00350 size_t state = rand_index(m_size); 00351 m_state_table[state] = create_input_map(a_inputs,a_outputs); 00352 } 00353 case MUTATE_SWAP_STATES: 00354 { 00355 // swap two states 00356 size_t state1 = rand_index(m_size); 00357 size_t state2; 00358 00359 do 00360 state2 = rand_index(m_size); 00361 while (state2 == state1); 00362 00363 t_input_map temp = m_state_table[state1]; 00364 m_state_table[state1] = m_state_table[state2]; 00365 m_state_table[state2] = temp; 00366 break; 00367 } 00368 case MUTATE_INIT_STATE: 00369 { 00370 // change initial state 00371 m_init_state = rand_index(m_size); 00372 break; 00373 } 00374 } 00375 } 00376 00377 // reset current state because init state may have changed 00378 m_current_state = m_init_state; 00379 } 00380 00381 // Cause state transition 00382 template <typename InputT, typename OutputT> 00383 typename state_machine<InputT,OutputT>::t_output state_machine<InputT,OutputT>::transition(const state_machine<InputT,OutputT>::t_input & a_input) 00384 { 00385 // get transition state 00386 t_transition & trans = m_state_table[m_current_state][a_input]; 00387 00388 // change to new state 00389 m_current_state = trans.second; 00390 00391 // return output symbol 00392 return trans.first; 00393 } 00394 00395 // Reset to start-up state 00396 template <typename InputT, typename OutputT> 00397 inline void state_machine<InputT,OutputT>::reset() 00398 { 00399 m_current_state = m_init_state; 00400 } 00401 00402 // Get a copy of the internal table 00403 template <typename InputT, typename OutputT> 00404 inline typename state_machine<InputT,OutputT>::t_state_table state_machine<InputT,OutputT>::get_table() const 00405 { 00406 return m_state_table; 00407 } 00408 00409 // Get initial state 00410 template <typename InputT, typename OutputT> 00411 inline size_t state_machine<InputT,OutputT>::get_init_state() const 00412 { 00413 return m_init_state; 00414 } 00415 00416 // Get current state 00417 template <typename InputT, typename OutputT> 00418 inline size_t state_machine<InputT,OutputT>::get_current_state() const 00419 { 00420 return m_current_state; 00421 } 00422 00423 // create a state map 00424 template <typename InputT, typename OutputT> 00425 typename state_machine<InputT,OutputT>::t_input_map state_machine<InputT,OutputT>::create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs) 00426 { 00427 // maximum output index 00428 size_t max_output = a_outputs.size(); 00429 00430 // create an input map for this state 00431 t_input_map input_map; 00432 00433 // for each input, define an output and a state transition 00434 for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input) 00435 { 00436 // pick a random output symbol and new state 00437 t_output out_symbol = a_outputs[rand_index(max_output)]; 00438 size_t new_state = rand_index(m_size); 00439 00440 // add transition data to map 00441 input_map[*input] = std::make_pair(out_symbol,new_state); 00442 } 00443 00444 return input_map; 00445 } 00446 }; 00447 00448 #endif
© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.