近年来，分布式数据库的应用变得更加广泛，但分布式数据库中的多连接查询优化问题却没有得到很好的解决。随着分布式数据库的规模不断增大，多连接查询优化问题越来越深地影响着数据查询的效率，而传统的优化技术在解决多连接查询优化问题上显得无能为力。本文研究的主要内容是根据分布式数据库多连接查询优化的特点，对基于任意连接树编码的遗传算法进行改进，给每一棵树型染色体串的叶结点附一个值，为计算染色体串的适应度函数提供了方便；同时提出一种新的变异算子，这个变异算子很好地解决了交叉算子产生新个体能力不足的问题。然后，我们通过试验得到了一组遗传算法参数的最佳值，并用这组参数值进行多连接查询优化。在最后的试验中表明，改进的遗传算法对分布式数据库多连接查询优化有很好的效果，优化后的查询代价大大降低了。