直接分析基因池遗传算法的种群动力系统相当复杂，对其进行Walsh变换，并证明新的动力系统与原系统G是拓扑共轭的，通过分析找出参数搜索空间规模与基因池遗传算法种群动力系统不动点的解析关系，并且分析各不动点的稳定性．

1.相关符号及定义说明

定义1 遗传算法通常采用二进制编码，一般是按照一定精度要求从参数空间选取均匀分布的N个点作为参数搜索空间。当N满足时，用长度为的二进制串恰好能够表示所有参数搜索空间中的点，N越大越大，反之亦然。因此，可以用来表征参数搜索空间内所有包含的点的多少，称为参数搜索空间规模。

定义2 “大海捞针”函数（needle-in-a-haystack fitness function）以一定长度的二进制串为自变量，函数形式为

。

定义3 种群分布向量x为联结平衡的，当且仅当：，对任意成立。

定义4 采用基因池重组的遗传算法称为基因池遗传算法。

2.基因池遗传算法的种群动力系统G与其经Walsh变换后的拓扑等价系统

定义5 在遗传算法中，用映射U刻画变异操作，用映射F刻画选择操作，用映射M刻画重组操作，记G(x)=U。，（）；G(x)就可以刻画整个遗传操作。可见G(x)是到的映射，又由动力系统的定义可判断G是的离散动力系统，称G为种群动力系统。

Th1 如果种群分布向量x是联结平衡的，那么对任意，有。

引理1 如果，则有对所有成立。

引理2 映射是到的同胚。

证明：任取，存在映射，且。根据的定义，是在映射W(x)下的值域，因而映射是满射；又有定义可知存在W(x)存在逆映射；因而是一一映射。由此可知：W是到的同胚。

证毕。

引理3 由定义4中关于基因池重组的描述和定理1，对任意

这是基因池重组操作的映射在Walsh变换下的表示。

引理4 对任意

这是刻画选择操作的映射在Walsh变换下的表示。

引理5 对任意，这是刻画变异操作的映射在Walsh变换下的表示。

引理6 见参考文献4，刻画整个操作的映射在Walsh变换下的表示。

引理7 令，则是上的离散动力系统。

由上引理可以证明Wash 变换后的系统与原系统是拓扑共轭的。

Th2 动力系统G和是拓扑同胚的，并且是拓扑共轭的。

由于G和是拓扑共轭的，可知G和有拓扑等价的结构和轨迹，且在相同的时刻达到不动点，不动点的个数和稳定情况也相同；即可以通过研究动力系统在不同条件下的不动点及其稳定性来推知G在相应条件下的不动点及稳定性情况。

3.决定不动点情况的动力方程

将“大海捞针”函数带入引理6的第2个式子中，在根据不动点满足，即可得到如下结论。

Th3 对于无限种群基因池遗传算法，当适应度函数是“大海捞针”函数时，若是动力系统的不动点，当且仅当

成立。

推论1 若是动力系统的不动点，则其分量是等值的。

4.参数搜索空间规模与基因池遗传算法的种群动力系统稳定性的关系

根据Th3和推论1，通过进一步分析来刻画参数搜索空间规模与动力系统的不动点之间的变化关系。

Th4 令，则参数搜索空间规模与动力系统的不动点的关系可用如下公式刻画

                      （1）

证明：由推论1可知的各分量具有等值性，可以统一用变量代替。有Th1，的其余分量的值都可以表示成的函数，进而表示成的函数。因此，决定着所有分量的值，所以和一一对应。综上，可以用与的关系式刻画与的关系。

用代替带入Th3的式中，整理可得

                 （2）

求解方程并表示为为因变量并以为自变量的函数，即可得关系式（1）。     证毕。

定义6 由于与存在一一对应关系，也把称为的不动点，并将方程（2）称为的不动点的等价方程。

由于动力系统与G是拓扑共轭的，其不动点与x也是一一对应的，所以刻画与的不动点关系的式（1），也等同刻画了与G的不动点之间的关系。由于动力系统G描述的是基因池遗传算法的动力学特性，因此从式（1）可以看出参数搜索空间规模的变换对基因池遗传算法稳定性产生的影响。

根据引理1可知的绝对值小于1；又从式（1）可知，当的取值范围是[-1,0)时，的取值范围超出实数范围；因此时有意义的取值范围是[0,1]。

5.动力系统的不动点的稳定性分析

如果函数是可微的，那么它在不动点x处的一阶偏导数是一个阶的雅可比矩阵J，矩阵J的元素定义为。则当J的特征根的模的最大值小于1时，x就是g的一个渐进稳定的不动点。通过讨论映射在的雅可比矩阵的特征根模的最大值，说明不动点的稳定性。由于的值完全取决于分量，所以这里表示，进而变成一个维的雅可比矩阵。

引理8 不动点处，对任意且，雅可比矩阵的元素满足如下式子

进一步，当时上式中的偏导数非负，即雅可比矩阵的元素非负。

引理9 若阶方阵A的对角线元素等于d，其余元素等于e，则方阵A有1个特征值等于，其余个特征值均等于d－e。

定义7 设，，可定义

               （3）

如果d，e>0，则。由引理8，9和定义7可推知如下定理。

Th5 ；且时特征根之模的最大值是。

根据上述结论，给出不动点的判别标准和参数搜索空间规模以及峰值高度参数a对不动点稳定性的影响情况。

Th6 当时，动力系统的不动点的稳定性由决定，当<1时，不动点是稳定的；当>1时，不动点是不稳定的；当＝1时情况不定。另外，参数搜索空间规模的增大会破坏不动点的稳定性；参数a的增大会加快不动点的稳定性。

设定参数，a的值并将式（1）带入（3），即得各不动点的稳定性判别式。