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