GSOC 2009 - Improved hBOA by integrating the BBHC and implement the simulated annealing algorithm

From OpenCog
Jump to: navigation, search

Basic Details

Abstract

MOSES is the cognitive plugin of Opencog Framework, and it plays an important role in the Opencog. The hBOA is used to generate the promising programs as optimal algorithm in MOSES. But it is not the optimal one in this context. Therefore, to improving the efficiency of the optimal algorithm in MOSES is very important and meaningful. The BBHC and simulated annealing algorithm are suitable to be integrated into the MOSES. These integration work would make MOSES better and smarter

Contributors

Mentors

Weekly Work Log

Stage I Learning and Reading stage (now to May 17)

before 2009/04/24

  • register the branch of opencog, but blocked by the *bzr push* behind the firewall.
  • solved the bocked problem and push the branch to lp:~xiaohui/opencog/moses.You may find how I fix it in my blog
  • studied the Dr.Moshe's Doctor thesis(CH1)

2009/04/27 to 2009/05/03

  • learned the doxygen ,read the manual of it
  • studied Dr. Pelikan 's book of hBOA (CH1~CH2)
  • read the code of moses/moses.h and documented it in the form of doxygen

2009/05/04 to 2009/05/10

  • studied Dr. Pelikan's book of hBOA(CH3~CH4)
  • studied Dr. Moshe's Doctor's thesis(CH2~CH3)

2009/05/11 to 2009/05/17

  • studied Dr. Pelikan's book of hBOA(CH5~CH8)
  • studied Dr. Moshe's Doctor's thesis(CH4)

Stage II Reading and Coding stage

2009/05/23 to 2009/05/30

  • studied Dr. Moshe's Doctor's thesis(CH5~CH7)
  • studied the Simulated Annealing Algorithm
  • reading the code of moses/field_set.h/cc

2009/06/01 to 2009/06/07

  • studied the moses code by debuging moses-distrunction step by step
  • reading the document about the representation about the continous value

2009/06/08 to 2009/06/14

  • still studied the moses code and got more clear about it.

2009/06/15 to 2009/06/21

  • write the unit test of *sample_from_neighborhood* in the optimization.h
  • studied moses code and add some comments

2009/06/22 to 2009/06/28

  • write the unit test case for *generate_all_in_neighborhood* method in optimization.h
  • modified the *sample_from_neighborhood* and the *generate_all_in_neighborhood* to accept the optional parameter center_instance as an exemplar. The signature of these two functions are as follow:
/**
 * This procedure samples sample_size instances at distance n from the exemplar
 * (i.e., with n non-zero elements in the sequence)
 *
 *@param fs  - deme
 *@param n   - distance
 *@param sample_size  - number of instances to be generated
 *@param out - deme where to store the instances
 *@param center_inst the center instance as the exemplar by given
 */
template<typename Out>
void sample_from_neighborhood(const eda::field_set& fs, int n,
                                 int sample_size, Out out, opencog::RandGen& rng,
                                 const eda::instance & center_inst )
template<typename Out>
void sample_from_neighborhood(const eda::field_set& fs, int n,
                                 int sample_size, Out out, opencog::RandGen& rng)

and

/**
 * Generates instances at distance n from the exemplar
 * (i.e., with n elements changed from 0 from the exemplar)
 * It calls a recursive function vary_n_knobs which varies
 * instance fields one by one (in all possible ways)
 *
 * @param fs  - deme
 * @param n   - distance
 * @param out - deme (where to store the instances)
 * @param cneter_inst - the instance as an exemplar
 */
 template<typename Out>
    void generate_all_in_neighborhood(const eda::field_set& fs, int n, Out out, 
                                      const eda::instance& center_inst )

template<typename Out>
    void generate_all_in_neighborhood(const eda::field_set& fs, int n, Out out)

By adding these two functions , so we could sample the neighborhood using the default instance or the given distance, it is useful for the SA.

2009/06/29 to 2009/07/05

  • add two functions cooling_schedule and accept_probability for the simulated_annealing
  • fixed some bugs

2009/07/06 to 2009/07/12

  • almost blocked these days

2009/07/28 to 2009/08/02

  • implemented the simulated annealing algorithm(ignored the contin and onto type too).

I have tested the performance of SA compare to the iterative hillclimbing of moses-disjuction. on my pc(OS:Debian lenny CPU:AMD Athlon(tm) XP 1900+ 1597.640MHz)

parameters for moses-disjuctioniterative hillclimbing simulated annealing
(seed = 1, arity = 5,maxevals = 10) Number of evals performed: 10
best -9 or(#1 not(#4))
time = 0s
Number of evals performed: 10
best -9 or(#1 not(#4))
time = 0s
(seed = 1, arity = 5,maxevals = 100) Number of evals performed: 100
best -1 true
time = 0s
Number of evals performed: 100
best -3 or(#2 #3 #5)
time = 2s
(seed = 1, arity = 8,maxevals = 100) Number of evals performed: 100
best -63 or(#4 #5)
time = 2s
Number of evals performed: 100
best -63 or(#4 #5)
time = 2s
(seed = 1, arity = 15,maxevals = 100) Number of evals performed: 100
-8191 or(#6 #13)
time = 402s
Number of evals performed: 100
-8191 or(#6 #13)
time = 385s
  • wrote some unit tests for the field_set,and my understanding of field_set, you could find it here

2009/08/03 to 2009/08/09

  • modify the SA implementation for sample one neighborhood every time

The SA implemented last week have many bugs and bad performance, and I rewrite it again and it samples one neighborhood a time. It should need to be modified it to sample many neighborhood at one time, which will improve the performance.

  • add the contin type to the sample_from_neighborhood.

I have add a function called generate_contin_neighborhood to generate one neighborhood one time of the contin instance by the given distance(now ,the distance is equals to 1). I have write the unit test for this function. But it still has a bug,which blocks me at these days. I am trying to fix it as soon as possible.