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 // simple_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 <stack> 00041 #include <stdexcept> 00042 using namespace std; 00043 00044 // libevocosm 00045 #include "evocommon.h" 00046 #include "fsm_tools.h" 00047 00048 namespace libevocosm 00049 { 00051 00059 template <size_t InSize, size_t OutSize> 00060 class simple_fsm : protected globals, protected fsm_tools 00061 { 00062 public: 00064 struct tranout_t 00065 { 00067 size_t m_new_state; 00068 00070 size_t m_output; 00071 }; 00072 00074 00078 simple_fsm(size_t a_size); 00079 00081 00086 simple_fsm(const simple_fsm<InSize,OutSize> & a_parent1, const simple_fsm<InSize,OutSize> & a_parent2); 00087 00089 00093 simple_fsm(const simple_fsm<InSize,OutSize> & a_source); 00094 00096 00100 virtual ~simple_fsm(); 00101 00102 // Assignment 00108 simple_fsm & operator = (const simple_fsm<InSize,OutSize> & a_source); 00109 00111 00123 void mutate(double a_rate); 00124 00126 00132 static void set_mutation_weight(mutation_id a_type, double a_weight); 00133 00135 00141 size_t transition(size_t a_input); 00142 00144 00147 void reset(); 00148 00150 00154 size_t size() const; 00155 00157 00163 const tranout_t & get_transition(size_t a_state, size_t a_input) const; 00164 00166 00170 size_t num_input_states() const; 00171 00173 00177 size_t num_output_states() const; 00178 00180 00184 size_t init_state() const; 00185 00187 00191 size_t current_state() const; 00192 00193 private: 00194 // release resources 00195 void release(); 00196 00197 // deep copy 00198 void deep_copy(const simple_fsm<InSize,OutSize> & a_source); 00199 00200 protected: 00202 tranout_t ** m_state_table; 00203 00205 size_t m_init_state; 00206 00208 size_t m_current_state; 00209 00211 size_t m_size; 00212 00214 static mutation_selector g_selector; 00215 }; 00216 00217 // Static initializer 00218 template <size_t InSize, size_t OutSize> 00219 typename simple_fsm<InSize,OutSize>::mutation_selector simple_fsm<InSize,OutSize>::g_selector; 00220 00221 // release resources 00222 template <size_t InSize, size_t OutSize> 00223 void simple_fsm<InSize,OutSize>::release() 00224 { 00225 for (size_t s = 0; s < m_size; ++s) 00226 delete [] m_state_table[s]; 00227 00228 delete [] m_state_table; 00229 } 00230 00231 // deep copy 00232 template <size_t InSize, size_t OutSize> 00233 void simple_fsm<InSize,OutSize>::deep_copy(const simple_fsm<InSize,OutSize> & a_source) 00234 { 00235 // allocate state table 00236 m_state_table = new tranout_t * [m_size]; 00237 00238 for (size_t s = 0; s < m_size; ++s) 00239 { 00240 // allocate an array corresponding to inputs 00241 m_state_table[s] = new tranout_t [InSize]; 00242 00243 // set transition values 00244 for (size_t i = 0; i < InSize; ++i) 00245 { 00246 m_state_table[s][i].m_new_state = a_source.m_state_table[s][i].m_new_state; 00247 m_state_table[s][i].m_output = a_source.m_state_table[s][i].m_output; 00248 } 00249 } 00250 } 00251 00252 // Creation constructor 00253 template <size_t InSize, size_t OutSize> 00254 simple_fsm<InSize,OutSize>::simple_fsm(size_t a_size) 00255 : m_state_table(NULL), 00256 m_init_state(0), 00257 m_current_state(0), 00258 m_size(a_size) 00259 { 00260 // verify parameters 00261 if (m_size < 2) 00262 throw std::runtime_error("invalid simple_fsm creation parameters"); 00263 00264 // allocate state table 00265 m_state_table = new tranout_t * [m_size]; 00266 00267 for (size_t s = 0; s < m_size; ++s) 00268 { 00269 // allocate an array corresponding to inputs 00270 m_state_table[s] = new tranout_t [InSize]; 00271 00272 // set transition values 00273 for (size_t i = 0; i < InSize; ++i) 00274 { 00275 m_state_table[s][i].m_new_state = rand_index(m_size); 00276 m_state_table[s][i].m_output = rand_index(OutSize); 00277 } 00278 } 00279 00280 // set initial state and start there 00281 m_init_state = rand_index(m_size); 00282 m_current_state = m_init_state; 00283 } 00284 00285 // Construct via bisexual crossover 00286 template <size_t InSize, size_t OutSize> 00287 simple_fsm<InSize,OutSize>::simple_fsm(const simple_fsm<InSize,OutSize> & a_parent1, const simple_fsm<InSize,OutSize> & a_parent2) 00288 : m_state_table(NULL), 00289 m_init_state(0), 00290 m_current_state(0), 00291 m_size(a_parent1.m_size) 00292 { 00293 // copy first parent 00294 deep_copy(a_parent1); 00295 00296 // don't do anything else if fsms differ is size 00297 if (a_parent1.m_size != a_parent2.m_size) 00298 return; 00299 00300 // replace states from those in second parent 50/50 chance 00301 size_t x = rand_index(m_size); 00302 00303 for (size_t n = x; n < m_size; ++n) 00304 { 00305 // set transition values 00306 for (size_t i = 0; i < InSize; ++i) 00307 { 00308 m_state_table[n][i].m_new_state = a_parent2.m_state_table[n][i].m_new_state; 00309 m_state_table[n][i].m_output = a_parent2.m_state_table[n][i].m_output; 00310 } 00311 } 00312 00313 // randomize the initial state (looks like mom and dad but may act like either one!) 00314 if (g_random.get_real() < 0.5) 00315 m_init_state = a_parent1.m_init_state; 00316 else 00317 m_init_state = a_parent2.m_init_state; 00318 00319 // reset for start 00320 m_current_state = m_init_state; 00321 } 00322 00323 // Copy constructor 00324 template <size_t InSize, size_t OutSize> 00325 simple_fsm<InSize,OutSize>::simple_fsm(const simple_fsm<InSize,OutSize> & a_source) 00326 : m_state_table(NULL), 00327 m_init_state(a_source.m_init_state), 00328 m_current_state(a_source.m_current_state), 00329 m_size(a_source.m_size) 00330 { 00331 // copy first parent 00332 deep_copy(a_source); 00333 } 00334 00335 // Virtual destructor 00336 template <size_t InSize, size_t OutSize> 00337 simple_fsm<InSize,OutSize>::~simple_fsm() 00338 { 00339 release(); 00340 } 00341 00342 // Assignment 00343 template <size_t InSize, size_t OutSize> 00344 simple_fsm<InSize,OutSize> & simple_fsm<InSize,OutSize>::operator = (const simple_fsm<InSize,OutSize> & a_source) 00345 { 00346 // release resources 00347 release(); 00348 00349 // set values 00350 m_init_state = a_source.m_init_state; 00351 m_current_state = a_source.m_current_state; 00352 m_size = a_source.m_size; 00353 00354 // copy source 00355 deep_copy(a_source); 00356 00357 return *this; 00358 } 00359 00361 template <size_t InSize, size_t OutSize> 00362 inline void simple_fsm<InSize,OutSize>::set_mutation_weight(mutation_id a_type, double a_weight) 00363 { 00364 g_selector.set_weight(a_type,a_weight); 00365 } 00366 00367 // Mutation 00368 template <size_t InSize, size_t OutSize> 00369 void simple_fsm<InSize,OutSize>::mutate(double a_rate) 00370 { 00371 // the number of chances for mutation is based on the number of states in the machine; 00372 // larger machines thus encounter more mutations 00373 for (size_t n = 0; n < m_size; ++n) 00374 { 00375 if (g_random.get_real() < a_rate) 00376 { 00377 // pick a mutation 00378 switch (g_selector.get_index()) 00379 { 00380 case MUTATE_OUTPUT_SYMBOL: 00381 { 00382 // mutate output symbol 00383 size_t state = rand_index(m_size); 00384 size_t input = rand_index(InSize); 00385 00386 size_t choice; 00387 00388 do 00389 { 00390 choice = rand_index(OutSize); 00391 } 00392 while (m_state_table[state][input].m_output == choice); 00393 00394 m_state_table[state][input].m_output = choice; 00395 break; 00396 } 00397 case MUTATE_TRANSITION: 00398 { 00399 // mutate state transition 00400 size_t state = rand_index(m_size); 00401 size_t input = rand_index(InSize); 00402 00403 size_t choice; 00404 00405 do 00406 { 00407 choice = rand_index(m_size); 00408 } 00409 while (m_state_table[state][input].m_new_state == choice); 00410 00411 m_state_table[state][input].m_new_state = choice; 00412 break; 00413 } 00414 case MUTATE_REPLACE_STATE: 00415 { 00416 // mutate state transition 00417 size_t state = rand_index(m_size); 00418 00419 // allocate an array corresponding to inputs 00420 delete [] m_state_table[state]; 00421 m_state_table[state] = new tranout_t [InSize]; 00422 00423 // set transition values 00424 for (size_t i = 0; i < InSize; ++i) 00425 { 00426 m_state_table[state][i].m_new_state = rand_index(m_size); 00427 m_state_table[state][i].m_output = rand_index(OutSize); 00428 } 00429 00430 break; 00431 } 00432 case MUTATE_SWAP_STATES: 00433 { 00434 // swap two states (by swapping pointers) 00435 size_t state1 = rand_index(m_size); 00436 size_t state2; 00437 00438 do 00439 state2 = rand_index(m_size); 00440 while (state2 == state1); 00441 00442 for (size_t i = 0; i < InSize; ++i) 00443 { 00444 tranout_t temp = m_state_table[state1][i]; 00445 m_state_table[state1][i] = m_state_table[state2][i]; 00446 m_state_table[state2][i] = temp; 00447 } 00448 00449 break; 00450 } 00451 case MUTATE_INIT_STATE: 00452 { 00453 // change initial state 00454 size_t choice; 00455 00456 do 00457 { 00458 choice = rand_index(m_size); 00459 } 00460 while (m_init_state == choice); 00461 00462 m_init_state = choice; 00463 00464 break; 00465 } 00466 } 00467 } 00468 } 00469 00470 // reset current state because init state may have changed 00471 m_current_state = m_init_state; 00472 } 00473 00474 // Cause state transition 00475 template <size_t InSize, size_t OutSize> 00476 inline size_t simple_fsm<InSize,OutSize>::transition(size_t a_input) 00477 { 00478 // get output symbol for given input for current state 00479 size_t output = m_state_table[m_current_state][a_input].m_output; 00480 00481 // change to new state 00482 m_current_state = m_state_table[m_current_state][a_input].m_new_state; 00483 00484 // return output symbol 00485 return output; 00486 } 00487 00488 // Reset to start-up state 00489 template <size_t InSize, size_t OutSize> 00490 inline void simple_fsm<InSize,OutSize>::reset() 00491 { 00492 m_current_state = m_init_state; 00493 } 00494 00495 // Get size 00496 template <size_t InSize, size_t OutSize> 00497 inline size_t simple_fsm<InSize,OutSize>::size() const 00498 { 00499 return m_size; 00500 } 00501 00502 // Get a copy of the internal table 00503 template <size_t InSize, size_t OutSize> 00504 inline const typename simple_fsm<InSize,OutSize>::tranout_t & simple_fsm<InSize,OutSize>::get_transition(size_t a_state, size_t a_input) const 00505 { 00506 return m_state_table[a_state][a_input]; 00507 } 00508 00509 // Get number of input states 00510 template <size_t InSize, size_t OutSize> 00511 inline size_t simple_fsm<InSize,OutSize>::num_input_states() const 00512 { 00513 return InSize; 00514 } 00515 00516 // Get number of output states 00517 template <size_t InSize, size_t OutSize> 00518 inline size_t simple_fsm<InSize,OutSize>::num_output_states() const 00519 { 00520 return OutSize; 00521 } 00522 00523 // Get initial state 00524 template <size_t InSize, size_t OutSize> 00525 inline size_t simple_fsm<InSize,OutSize>::init_state() const 00526 { 00527 return m_init_state; 00528 } 00529 00530 // Get current state 00531 template <size_t InSize, size_t OutSize> 00532 inline size_t simple_fsm<InSize,OutSize>::current_state() const 00533 { 00534 return m_current_state; 00535 } 00536 }; 00537 00538 #endif
© 1996-2005 Scott Robert Ladd. All rights reserved.
HTML documentation generated by Dimitri van Heesch's excellent Doxygen tool.