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