Created by Scott Robert Ladd at Coyote Gulch Productions.
00001 //--------------------------------------------------------------------- 00002 // Algorithmic Conjurings @ http://www.coyotegulch.com 00003 // Evocosm -- An Object-Oriented Framework for Evolutionary Algorithms 00004 // 00005 // fsm.h 00006 //--------------------------------------------------------------------- 00007 // 00008 // Copyright 1996, 1999, 2002, 2003, 2004, 2005, 2006, 2007 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_FSM_H) 00036 #define LIBEVOCOSM_FSM_H 00037 00038 // Standard C++ Library 00039 #include <cstddef> 00040 #include <vector> 00041 #include <map> 00042 #include <stack> 00043 #include <stdexcept> 00044 using namespace std; 00045 00046 // libevocosm 00047 #include "evocommon.h" 00048 #include "roulette.h" 00049 #include "fsm_tools.h" 00050 00051 namespace libevocosm 00052 { 00054 00068 template <typename InputT, typename OutputT> 00069 class fsm : protected globals, protected fsm_tools 00070 { 00071 public: 00073 typedef InputT t_input; 00074 00076 typedef OutputT t_output; 00077 00079 typedef typename std::pair<t_output, size_t> t_transition; 00080 00082 typedef typename std::map<t_input, t_transition> t_input_map; 00083 00085 typedef typename std::vector<t_input_map> t_state_table; 00086 00088 00095 fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs); 00096 00098 00107 fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2); 00108 00110 00114 fsm(const fsm<InputT,OutputT> & a_source); 00115 00117 00121 virtual ~fsm(); 00122 00123 // Assignment 00128 fsm & operator = (const fsm<InputT,OutputT> & a_source); 00129 00131 00146 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); 00147 00149 00154 t_output transition(const fsm<InputT,OutputT>::t_input & a_input); 00155 00157 00160 void reset(); 00161 00163 00168 t_state_table get_table() const; 00169 00171 00175 size_t get_init_state() const; 00176 00178 00182 size_t get_current_state() const; 00183 00184 protected: 00186 t_state_table m_state_table; 00187 00189 size_t m_size; 00190 00192 size_t m_init_state; 00193 00195 size_t m_current_state; 00196 00198 static mutation_selector g_default_selector; 00199 00200 private: 00201 // create a state map 00202 t_input_map create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs); 00203 }; 00204 00205 // Static initializer 00206 template <typename InputT, typename OutputT> 00207 typename fsm<InputT,OutputT>::mutation_selector fsm<InputT,OutputT>::g_default_selector; 00208 00209 // Creation constructor 00210 template <typename InputT, typename OutputT> 00211 fsm<InputT,OutputT>::fsm(size_t a_size, const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs) 00212 : m_state_table(), 00213 m_init_state(0), 00214 m_current_state(0), 00215 m_size(a_size) 00216 { 00217 // verify parameters 00218 if ((a_size < 2) || (a_inputs.size() < 1) || (a_outputs.size() < 1)) 00219 throw std::runtime_error("invalid fsm creation parameters"); 00220 00221 for (size_t n = 0; n < m_size; ++n) 00222 { 00223 // add input map to state table 00224 m_state_table.push_back(create_input_map(a_inputs,a_outputs)); 00225 } 00226 00227 // set initial state and start there 00228 m_init_state = rand_index(m_size); 00229 m_current_state = m_init_state; 00230 } 00231 00232 // Construct via bisexual crossover 00233 template <typename InputT, typename OutputT> 00234 fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_parent1, const fsm<InputT,OutputT> & a_parent2) 00235 : m_state_table(a_parent1.m_state_table), 00236 m_init_state(0), 00237 m_current_state(0), 00238 m_size(0) 00239 { 00240 size_t n; 00241 00242 // don't do anything else if fsms differ is size 00243 if (a_parent1.m_size != a_parent2.m_size) 00244 return; 00245 00246 // replace states from those in second parent 50/50 chance 00247 for (size_t n = 0; n < m_size; ++n) 00248 { 00249 if (g_random.get_real() > 0.5) 00250 m_state_table[n] = a_parent2.m_state_table[n]; 00251 } 00252 00253 // calculate the size 00254 m_size = m_state_table.size(); 00255 00256 // randomize the initial state (looks like mom and dad but may act like either one!) 00257 if (g_random.get_real() < 0.5) 00258 m_init_state = a_parent1.m_init_state; 00259 else 00260 m_init_state = a_parent2.m_init_state; 00261 00262 // reset for start 00263 m_current_state = m_init_state; 00264 } 00265 00266 // Copy constructor 00267 template <typename InputT, typename OutputT> 00268 fsm<InputT,OutputT>::fsm(const fsm<InputT,OutputT> & a_source) 00269 : m_state_table(a_source.m_state_table), 00270 m_init_state(a_source.m_init_state), 00271 m_current_state(a_source.m_current_state), 00272 m_size(a_source.m_size) 00273 { 00274 // nada 00275 } 00276 00277 // Virtual destructor 00278 template <typename InputT, typename OutputT> 00279 fsm<InputT,OutputT>::~fsm() 00280 { 00281 // nada 00282 } 00283 00284 // Assignment 00285 template <typename InputT, typename OutputT> 00286 fsm<InputT,OutputT> & fsm<InputT,OutputT>::operator = (const fsm<InputT,OutputT> & a_source) 00287 { 00288 if (this != &a_source) 00289 { 00290 m_state_table = a_source.m_state_table; 00291 m_init_state = a_source.m_init_state; 00292 m_current_state = a_source.m_current_state; 00293 m_size = a_source.m_size; 00294 } 00295 00296 return *this; 00297 } 00298 00299 // Mutation 00300 template <typename InputT, typename OutputT> 00301 void fsm<InputT,OutputT>::mutate(double a_rate, 00302 const std::vector<t_input> & a_inputs, 00303 const std::vector<t_output> & a_outputs, 00304 mutation_selector & a_selector) 00305 { 00306 if (g_random.get_real() < a_rate) 00307 { 00308 // pick a mutation 00309 switch (a_selector.get_index()) 00310 { 00311 case MUTATE_OUTPUT_SYMBOL: 00312 { 00313 // mutate output symbol 00314 size_t state = rand_index(m_size); 00315 size_t input = rand_index(a_inputs.size()); 00316 size_t output = rand_index(a_outputs.size()); 00317 m_state_table[state][a_inputs[input]].first = a_outputs[output]; 00318 break; 00319 } 00320 case MUTATE_TRANSITION: 00321 { 00322 // mutate state transition 00323 size_t state = rand_index(m_size); 00324 size_t input = rand_index(a_inputs.size()); 00325 size_t new_state = rand_index(m_size); 00326 m_state_table[state][a_inputs[input]].second = new_state; 00327 break; 00328 } 00329 case MUTATE_REPLACE_STATE: 00330 { 00331 // select state 00332 size_t state = rand_index(m_size); 00333 m_state_table[state] = create_input_map(a_inputs,a_outputs); 00334 } 00335 case MUTATE_SWAP_STATES: 00336 { 00337 // swap two states 00338 size_t state1 = rand_index(m_size); 00339 size_t state2; 00340 00341 do 00342 state2 = rand_index(m_size); 00343 while (state2 == state1); 00344 00345 t_input_map temp = m_state_table[state1]; 00346 m_state_table[state1] = m_state_table[state2]; 00347 m_state_table[state2] = temp; 00348 break; 00349 } 00350 case MUTATE_INIT_STATE: 00351 { 00352 // change initial state 00353 m_init_state = rand_index(m_size); 00354 break; 00355 } 00356 } 00357 } 00358 00359 // reset current state because init state may have changed 00360 m_current_state = m_init_state; 00361 } 00362 00363 // Cause state transition 00364 template <typename InputT, typename OutputT> 00365 typename fsm<InputT,OutputT>::t_output fsm<InputT,OutputT>::transition(const fsm<InputT,OutputT>::t_input & a_input) 00366 { 00367 // get transition state 00368 t_transition & trans = m_state_table[m_current_state][a_input]; 00369 00370 // change to new state 00371 m_current_state = trans.second; 00372 00373 // return output symbol 00374 return trans.first; 00375 } 00376 00377 // Reset to start-up state 00378 template <typename InputT, typename OutputT> 00379 inline void fsm<InputT,OutputT>::reset() 00380 { 00381 m_current_state = m_init_state; 00382 } 00383 00384 // Get a copy of the internal table 00385 template <typename InputT, typename OutputT> 00386 inline typename fsm<InputT,OutputT>::t_state_table fsm<InputT,OutputT>::get_table() const 00387 { 00388 return m_state_table; 00389 } 00390 00391 // Get initial state 00392 template <typename InputT, typename OutputT> 00393 inline size_t fsm<InputT,OutputT>::get_init_state() const 00394 { 00395 return m_init_state; 00396 } 00397 00398 // Get current state 00399 template <typename InputT, typename OutputT> 00400 inline size_t fsm<InputT,OutputT>::get_current_state() const 00401 { 00402 return m_current_state; 00403 } 00404 00405 // create a state map 00406 template <typename InputT, typename OutputT> 00407 typename fsm<InputT,OutputT>::t_input_map fsm<InputT,OutputT>::create_input_map(const std::vector<t_input> & a_inputs, const std::vector<t_output> & a_outputs) 00408 { 00409 // maximum output index 00410 size_t max_output = a_outputs.size(); 00411 00412 // create an input map for this state 00413 t_input_map input_map; 00414 00415 // for each input, define an output and a state transition 00416 for (typename std::vector<t_input>::const_iterator input = a_inputs.begin(); input != a_inputs.end(); ++input) 00417 { 00418 // pick a random output symbol and new state 00419 t_output out_symbol = a_outputs[rand_index(max_output)]; 00420 size_t new_state = rand_index(m_size); 00421 00422 // add transition data to map 00423 input_map[*input] = std::make_pair(out_symbol,new_state); 00424 } 00425 00426 return input_map; 00427 } 00428 }; 00429 00430 #endif
© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.