全局收敛性

定义7.1：设｛ξm｝是概率空间的一个随机向量序列，若∃一个随机向量ξ使得

假设（A）：

（1）问题（1）的可行域D是Rn中一个有界闭集；

（2）f（x）在［L，U］⊃D上连续；

（3）至少存在一个全局极小点x＊使对∀δ＞0，集合D∩｛x：｜‖x－x＊‖＜δ｝的Lebesgue测度大于0。

其中，f＊＝min ｛f（x）：x∈D｝＝｛f（x＊）：x＊∈S｝，于是，种群P（k）可分为两种状态：

S1：若P（k）中至少有一点属于Q1，则称P（k）处于状态S1；

S2：若P（k）中所有点都不属于Q1，则称P（k）处于状态S2。

定理7.1：设pij（i，j＝1，2）表示P（k）处于状态Si，而P（k＋1）处于状态Sj的概率，则在假设（A）下有：

（a）对任一个处于状态S1的P（k），必有p11＝1

（b）对任一个处于状态S2的P（k），存在一个常数c∈（0，1），使p22＜c。

证明：从算法7.1选择方法知，若P（k）∈S1，则P（k＋1）∈S1，∴（a）成立；∵S≠Φ，对满足假设（A）中（3）的∀x＊∈S，∵f（x）在D上连续，∴∃γ＞0，使得，当x∈D∩

注意到p21表示P（k）处于状态S2而P（k＋1）处于状态S1的概率，由式（7－3）及式（7－5）可知

记c＝1－P1（x），于是，由式（7－6）知，

0＜c＜1，由p21＋p22＝1及式（7－7），c的定义知，p22＝1－p21≤1－P1（x）＝c

于是，结论（b）成立。

定理7.2：设｛P（k）｝是由算法产生的种群序列，且P（0）中至少有一点属于D，用x＊（k）记P（k）中最好的点，即x＊（k）＝argmin ｛f（x）：x∈P（k）∩D｝，则在假设（A）下，

即算法1以概率1收敛到全局最优解。

证明：对∀ε＞0，记pk＝p ｛f（x＊（k））－f（x＊）≥ε｝，则

由定理7.1知，