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