Wednesday, September 13, 2006


Dependency-tree EDA in C++ online

Just minutes ago I put online the C++ source code of the dependency-tree estimation of distribution algorithm (dtEDA), which is one of the simpler EDAs but it can encode dependencies between problem variables in the form of a dependency tree. The code is not restricted to binary strings (unusual for my code); each symbol in the string can have an arbitrary number of values (specified by a user-defined function). The code also includes bisection for determining the optimal population size for reliable convergence, which is a useful feature for obtaining scalability plots.

The main advantage of using dtEDA instead of more complex EDAs, such as BOA or ECGA, is that dtEDA uses simpler models and it should thus be faster. The disadvantage is that the models are restricted and the user won't get good scalability if the dependencies cannot be effectively encoded as dependency trees (and more complex structures are needed).

The main advantage of using dtEDA instead of simpler EDAs, such as PBIL or UMDA, is that dtEDA is capable of encoding dependencies between the variables and it does not assume that the variables contribute to the objective function independently. The disadvantage is that learning dependency trees is still slower than using the simple univariate distributions where the structure is fixed.

The code is heavily commented and documented (by hand and using Doxygen automatic documentation generation system). I hope you find it useful.

Downloads from MEDAL:

Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?