一种基于KM传染病模型的函数优化方法

摘要

一种基于KM传染病模型的函数优化方法—SIR算法，采用基于KM传染病模型，假设在某个生态系统存在N个生物个体，每个生物个体由n个特征来表征；该生态系统存在一种传染病，且在N个生物个体之间传染，通过传染算子、病态算子、治愈算子、免疫算子和活动算子使生物个体之间相互交换信息：PPI指数高的个体通过病态算子和免疫算子向PPI指数低的个体传递强壮特征的信息，使得PPI指数低的个体能向好的方向生长；传染算子和治愈算子通过使个体获得其它某些个体的平均特征信息，从而降低了该个体陷入局部最优解的概率；活动算子通过使个体的活跃度提高，从而扩大了搜索范围；本算法具有搜索能力强和全局收敛性的特点，为复杂函数优化问题的求解提供了一种方法。

说明书

技术领域

本发明涉及智能优化算法，具体涉及一种基于KM传染病模型的函数优化方法—SIR算法。 

背景技术

考虑一般函数优化问题 

minf(X) 

$>s.t.\left(\begin{array}{c}{g}_i\left(X\right)\ge 0,i=\mathrm{1,2},···,I\\ h_i\left(X\right)=0,i=\mathrm{1,2},···,E\\ X\in H⋐R^n\end{array}\right)---\left(1\right)$>

式中：Rⁿ是n维欧氏空间；X=(x₁，x₂，…，x_n)是一个n维决策向量，变量x_i(i=1，2，…，n)为实数；H为搜索空间，又称解空间；f(X)为目标函数；g_i(X)≥0为第i个约束条件，i=1，2，…，I，I为不等式约束条件个数；h_i(X)=0为第i个等式约束条件，i=1，2，…，E，E为等式约束条件个数。目标函数f(X)和约束条件g_i(X)、h_i(X)不需要特殊的限制条件，传统的基于函数连续性和可导性的数学优化方法无法解决该问题。 

上述优化问题(1)的求解方法是群体智能优化算法，这类算法具有较广泛的适用性。已有的智能优化算法有：(1)遗传算法：该算法1975年由美国芝加哥大学Holland的专著《Adaptation in Natural and Artificial Systems》提出，所采用的技术方案是利用遗传学理论构造个体进化方法，从而对优化问题进行求解；(2)蚁群算法：该算法由Colorni A和Dorigo M等人在文献《Distributed optimization by ant colonies，Proceedings of the1^st Europe Conference on Artificial Life，1991，134～142》中提出，所采用的技术方案是模拟蚂蚁群体觅食行为来进行优化问题的求解；(3)粒子群算法：该算法由Eberhart R和 Kennedy J在文献《New optimizer using particle swarm theory，MHS’95Proceedings of the Sixth International Symposium on Micro Machine and Human Science，IEEE，Piscataway，NJ，USA，1995：38～43》中提出，所采用的技术方案是利用模仿鸟类的群体行为来进行优化问题的求解；(4)鱼群算法：该算法由李晓磊、邵之江和钱积新等人在文献《一种基于动物自治体的寻优棋式：鱼群算法，系统工程理论与实践，2002,22(11):32～38》中提出，所采用的技术方案是利用鱼在水中的觅食、追尾、群聚等行为对优化问题解空间进行搜索，从而获取优化问题的全局最优解；(5)生物地理学算法，该算法2008年由Dan Simon用生物地理学的方法提出，文献为《Simon D.Biogeography-based Optimization[J].IEEE Transactions.Evolutionary Computation，2008，12(6)：702-713》。该算法通过种群在栖息地间的迁移实现了对优化问题最优解的搜索；(6)蝙蝠算法：该算法2010年由Yang X S在文献《A new metaheuristic bat-inspired algorithm，Nature Inspired Cooperative Strategies for Optimization(NICSO2010),Studies in Computational Intelligence 284,Springer-Verlag,Berlin Eidelberg,2010,65-74》中提出，该算法通过模拟蝙蝠回声定位行为而提出的一种新的智能优化算法，它也是一种基于种群的随机搜索寻优算法，蝙蝠个体是蝙蝠算法的基本单元，整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获取最优解。 

与本发明相关的优化算法是免疫算法，该算法由王磊、潘进和焦李成在文献《免疫算法，电子学报，2000，28(7)：74-78》提出。该算法借鉴生命科学中免疫的概念与理论，其核心在于免疫算子的构造，而免疫算子是通过接种疫苗和选择免疫两个步骤来完成的；李茂军，罗安，童调生在文献《工免疫算法及其应用研究，控制理论与应用，2004，21(2)：153-158》中证明了免疫算法具有全局收敛性。 

免疫算法的大部分成果是基于Burnet在文献《The Clonal Selection Theory of Acquired Immunity，Cambridge:Cambridge University Press，1959》提出的克隆选择学说。基于克隆选择原理，De Castro博士在文献《Learning and Optimization Using the Clone Selection Principle[J].IEEE Transactions on Evolutionary Computation,2002,6(3):239-251》中提出了一种克隆选择算法，其核心是采用了比例复制算子和比例变异算子。该算法容易产生多样性差、算法实现过程困难的缺点。Timmis等人同样基于克隆选择机理提出了B-Cell算法，Cutello等人基于CLONALG设计了不同的高频变异操作，提出了用于优化的免疫算法opt-IA。焦李成等人在对免疫选择机理深入研究的基础上，提出了自适应多克隆规划算法、自适应动态克隆算法、免疫优势克隆算法等多种高级免疫克隆选择算法。 

与本发明相关的另一种优化算法是曹先彬，王本年和王煦法在文献《一种病毒进化型遗传算法，小型微型计算机系统，2001，21(1)：59～62》提出的VEGA算法。该算法以遗传算法为基础，从生物病毒机制中抽取出适合改进遗传算法的一些特征，将个体分为病毒个体和宿主个体，两种个体各自有不同的行为，两者之间又通过感染操作而具有一种自然的协同联系，从而大大提高了个体的多样性。 

上述这些算法主要存在如下问题： 

(1)免疫算法中涉及的个体是基因，免疫算子是通过对基因进行疫苗选择和疫苗接种两种操作来构造，免疫算子的构造必须与需要求解的实际优化问题相关，而实际优化问题变化万千，因此免疫算法无法构造出通用的免疫算子； 

(2)免疫算法中只有免疫算子这一个算子，要想扩展出其他算子需要涉及生命科学中非常专业和深奥的免疫理论知识，因而对非生命科学领域的研究 人员来说非常困难； 

(3)免疫算法中的免疫算子单一，当求解许多复杂优化问题，特别说高维优化问题时性能低下； 

(4)VEGA算法的缺陷在于：a)该算法没有考虑个体的免疫能力；b)该算法没有考虑个体染病与治愈之间的状态转换。 

发明内容

为了解决上述现有技术存在的问题，本发明的目的在于提供一种基于KM传染病模型的函数优化方法—SIR算法，本算法具有搜索能力强和全局收敛性的特点，为复杂函数优化问题的求解提供了一种解决方案。 

为了达到上述目的，本发明采用如下技术方案： 

一种基于KM传染病模型的函数优化方法—SIR算法， 

其特征在于：设要解决的函数优化问题为： 

minf(X) 

$>s.t.\left(\begin{array}{c}{g}_i\left(X\right)\ge 0,i=\mathrm{1,2},···,I\\ h_i\left(X\right)=0,i=\mathrm{1,2},···,E\\ X\in H⋐R^n\end{array}\right)---\left(1\right)$>

式中：Rⁿ是n维欧氏空间；X=(x₁，x₂，…，x_n)是一个n维决策向量，变量x_i(i=1，2，…，n)为实数；H为搜索空间，又称解空间；f(X)为目标函数；g_i(X)≥0为第i个约束条件，i=1，2，…，I，I为不等式约束条件个数；h_i(X)=0为第i个等式约束条件，i=1，2，…，E，E为等式约束条件个数。目标函数f(X)和约束条件g_i(X)、h_i(X)不需要特殊的限制条件； 

优化问题的搜索空间与生态系统相对应，该生态系统中一个生物个体对应于优化问题的一个试探解，采用基于KM传染病模型，假设在某个生态系统存在N个生物个体，每个生物个体由n个特征来表征；该生态系统存在一种传染病，且在N个生物个体之间传染，该传染病攻击的是生物个体的部分 特征，生物个体染病后可以被治愈，治愈后的生物个体不会再染病，即获得免疫能力；个体的体质强弱是通过该个体的某些特征的染病、某些特征的治愈与某些特征已获得免疫的情况综合决定的；体质强壮的个体能继续生长，而体质虚弱的生物个体则停止生长； 

通过利用传染算子、病态算子、治愈算子、免疫算子和活动算子使生物个体之间相互交换信息：PPI指数高的个体通过病态算子和免疫算子向PPI指数低的个体传递强壮特征的信息，使得PPI指数低的个体能向好的方向生长；传染算子和治愈算子通过使个体获得其它某些个体的平均特征信息，从而降低了该个体陷入局部最优解的概率；活动算子通过使个体的活跃度提高，从而扩大了搜索范围。 

为了使SIR算法适用于各种优化问题，将优化问题(1)的目标函数改写成下式： 

式中：F_max为非常大的实数，用于对不满足约束条件的试探解进行惩罚。 

KM传染病模型 

早在1927年，Kermack和Mckendrick首先利用动力学的方法来建立传染病的数学模型，这个模型简称为KM模型。这个模型的建立是基于以下三个基本假设(称为KM假设)： 

假设A：生态系统的生物个体的总数量是常数，不因时间变化而改变。 

假设B：易感者由于受传染病的影响，其个体数随时间而变化的变化率与当时易感者的个体数和当时已染病的个体数之积成正比。 

假设C：从染病者类转到消除者(免疫者)类的速度与当时染病者类的个体 数成正比。 

基于上述三个假设，我们把所生态系统的生物个体分成三类： 

S类：易感者(susceptible)类，即在生态系统内所有未染病者的全体，这一类生物个体若与染病者作有效接触，就容易受传染而得病。 

I类：染病者(infective)类，即在这生态系统内已染上传染病而且仍在发病期的个体的全体，这一类个体若与易感者类的个体作有效接触，就容易把疾病传染给易感者。 

R类：消除者(removed)类，即表示因为染病而死亡或病愈有免疫能力的个体的全体，这一类个体不再受染病者的传染而重新得病，也不会把疾病传染给易感者。 

假设生态系统生物个体总数为1个单位，我们以S(t)，I(t)和R(t)分别代表在时期t时在S类、I类和R类个体数的所占的比例。对于该生态系统的任意一个个体来说，S(t)，I(t)和R(t)就表示该个体属于S类、I类和R类的概率，或者说该个体处于S状态、I状态和R状态的概率。所述S状态是指个体未染病的状态，简称易感状态；所述I状态是指个体已感染上传染病的状态，简称已病状态；所述R状态是指个体染病后已痊愈，并已获得免疫的状态，简称免疫状态。 

如果我们把S(t)，I(t)和R(t)看成是某种化学物质的浓度，则KM三假设用化学反应的语言来叙述为 

式中：β和r为正常数。如果我们再假设在所研究的时间区间内没有生物个体 的自然出生与死亡率，则由KM三假设及化学动力学建模方法，即可得到传染病的数学模型，即KM模型为 

$>\left(\begin{array}{c}\frac{\mathrm{dS}}{\mathrm{dt}}=-\mathrm{\beta SI}\\ \frac{\mathrm{dI}}{\mathrm{dt}}=\mathrm{\beta SI}-\mathrm{rI}\\ \frac{\mathrm{dR}}{\mathrm{dt}}=\mathrm{rI}\\ S\left(0\right)=S_0>0,I\left(0\right)=I_0>0,R\left(0\right)\ge 0\end{array}\right)---\left(3\right)$>

式中：参数β称为传染率，β>0；r称为移除率，又称康复率或治愈率，r>0。 

算法场景设计 

本算法假设在某个生态系统存在N个生物个体，用编号表示就是1，2，…，N。每个个体由n个特征来表征，即对个体i来说，其表征特征为(x_i1，x_i2，…，x_in)。该生态系统存在一种传染病，且在N个生物个体之间传染。这种传染病攻击的是生物个体的部分特征。个体染病后可以被治愈，治愈后的个体即获得免疫能力，不可能重新染病。个体的体质强弱是通过该个体某些特征的染病、某些特征的治愈与某些特征已获得免疫的情况综合决定的。体质强壮的个体能继续生长，而体质虚弱的个体则停止生长。将上述场景映射到对优化问题(1)全局最优解的搜索过程中，其含义如下： 

优化问题的搜索空间与生态系统相对应，该生态系统中一个生物个体对应于优化问题的一个试探解，N个生物个体所对应的试探解集就是{X₁，X₂，…，X_N}，X_i=(x_i1，x_i2，…，x_in)，i=1，2，…，N；个体i的一个特征对应于优化问题试探解X_i的一个变量，即个体i的特征j与试探解X_i的变量x_ij相对应。所以个体i的特征数与试探解X_i的变量数相同，都为n。因此，个体i与试探解X_i是等价概念。个体的体质强弱用体质指数PPI(Population Physique Index，PPI)来表示，PPI指数对应于优化问题(1)的目标函数值。好的试探解对应具有较高PPI值的 个体，即体质强壮的生物个体；差的试探解对应具有较低PPI值的个体，即体质虚弱的生物个体。对于优化问题(1)，个体i的PPI指数计算方法为： 

PPI(X_i)=F_max-F(X_i)            (4) 

在时期t，随机产生生态系统的传染率β和治愈率r，采用KM传染病模型计算个体i的易感率S_i(t)、染病率I_i(t)和治愈率R_i(t)。个体i在时期t处于易感即S状态、染病即I状态和免疫即R状态三个状态中的哪个状态，由S_i(t)、I_i(t)和R_i(t)中最大者确定。下列五种情况符合KM模型三个假设，是合法的状态： 

(1)若时期t-1个体i处于S状态，而时期t个体i也处于S状态，则个体i处于S状态，此时采用活动算子来计算个体i的生长状态。 

(2)若时期t-1个体i处于S状态，而时期t个体i却处于I状态，则个体i感染上疾病，即处于I状态，此时采用传染算子来计算个体i的生长状态。 

(3)若时期t-1个体i处于I状态，而时期t个体i也处于I状态，则个体i仍在继续生病，即继续处于I状态，此时采用病态算子来计算个体i的生长状态。 

(4)若时期t-1个体i处于I状态，而时期t个体i却处于R状态，则个体i感染上疾病后被治愈了，从此以后个体i不会再感染上该疾病，即处于R状态，此时采用治愈算子计算个体i的生长状态。 

(5)若时期t-1个体i处于R状态，而时期t个体i仍处于R状态，则个体i已处于R状态，此时采用免疫算子计算个体i的生长状态。 

除上述五种合法情况外，其他情况均为非法情况。在所有非法情况下，个体i仍保持时期t-1时的状态不变，其生长状态也不进行计算和更新。 

由于在任何时期，生态系统的传染率β和治愈率r都是随机的，因此个体i的易感率S_i(t)、染病率I_i(t)和治愈率R_i(t)也是随机的，个体i的生长状态将在S、 I、R三个状态之间随机转换。这种随机转换映射到优化问题的解空间，意味着每个试探解在解空间从一个位置转移到另外一个位置，从而实现了对解空间的随机搜索。 

随机搜索过程中，若时期t个体i的PPI指数高于其时期t-1的PPI指数，则个体i将继续生长，此意味着个体i离全局最优解越来越近。反之，若时期t个体i的PPI指数低于或等于其时期t-1的PPI指数，则个体i将停止生长，但不萎缩，此意味着个体i留在时期t-1所在的位置不动。这种步步不差的随机搜索策略使得该算法具有全局收敛性。 

根据算法场景设计，可构造出SIR算法。 

演化算子设计 

在时期t，生态系统的N个生物个体的状态值为下面给出传染算子、病态算子、治愈算子、免疫算子和活动算子的计算方法。 

(1)传染算子。从已染病的个体中随机挑选L个个体，L≥1，这些个体形成已染病者集合让这L个个体某些特征的平均状态值作为个体i对应特征的状态值，也就是让已染病的个体的特征及其状态值传染给未染病者，使其染病。即 

式中：和分别表示时期t时期t-1个体i中的第j个特征的状态值；E₀是从用其编号表示的特征集合{1，2，…，n}中随机选出一个特征的概率上限；p为特征被选中的实际概率，p=Rand(0,1)，Rand(0，1)表示在[0，1]区间产生一个均匀分布随机数。 

(2)病态算子。当个体i处于患病状态时，总是通过各种办法使其自身的 体质增强，以便使其病能治愈。因此，可从已染病的个体中随机挑选体质好的L个个体，L≥1，即这些个体的PPI指数要高于个体i的PPI指数，这些高PPI指数的个体形成集合让这些个体某些特征的平均状态值作为个体i对应特征的状态值，也就是让体质好的已染病个体的特征及其状态值传给个体i，使其体质增强。即 

式中未说明符合含义同前。 

(3)治愈算子。从病已治愈的个体中随机挑选L个个体，L≥1，这些个体形成病已治愈者集合让这L个个体某些特征的平均状态值作为个体i对应特征的状态值，也就是让已治愈的个体的特征及其状态值传给染病者，使其治愈。即 

式中未说明符合含义同前。 

(4)免疫算子。从已免疫的个体中随机挑选L个体质较个体i更好的个体，L≥1，这些个体形成体质更优的已免疫者集合让这L个个体某些特征的平均状态值作为个体i对应特征的状态值，也就是让体质更优的已免疫的个体的特征及其状态值传给即将获得免疫能力的个体i，使其免疫，相当于将已具有免疫能力的较优个体的血清注入待免疫个体的体内，使其获得免疫能力。即 

(5)活动算子。从标识为S状态的未染病个体中随机挑选L=m_I+m_E个个体形成易感者集合让这L个个体某些特征的状态值之和的差值作为个体i对应特征的状态值。即 

式中：$>\forall k,s\in \{i_1,i_2,···,i_L\},k\ne s\ne i;$>α_k，β_k为常数，0<α_k，β_k<1；m_I和m_E为参与当前计算的个体数，m_I≥2，m_E≥1，m_I>m_E。因个体i的特征的状态值计算没有利用已染病或已免疫的个体的特征，故个体i不会染病也不会获得免疫；采用其它个体特征的状态值之和的差值来计算个体i特征的状态值，可以增加个体i的特征的新旧状态值的差异，以此提升个体i活跃度。 

(6)生长算子。SIR算法通过传染算子、病态算子、治愈算子、免疫算子和活动算子产生新一代个体之后，采用生长算子将新一代个体与相应的前代个体进行比较，将较优者更新成下一代个体中，将较差者不作改变地保留成原状态。对于最小化优化问题(1)，其生长算子可以描述为 

式中：$>V_i^t=(v_{i1}^t,v_{i2}^t,···,v_{\mathrm{in}}^t),$>$>X_i^{t-1}=(x_{i1}^{t-1},x_{i2}^{t-1},···,x_{\mathrm{in}}^{t-1});$>函数和按式(4)计算，此处未进行说明的符号的含义同前。 

一旦新的个体形成之后，SIR算法继续通过传染算子、病态算子、治愈算子、免疫算子和活动算子和生长等算子对个体群不断进行演化直到找到最优解。 

SIR算法通过利用传染算子、病态算子、治愈算子、免疫算子和活动算子来使生物个体之间交换信息。PPI指数高的个体通过病态算子和免疫算子向PPI指数低的个体传递较好特征信息，使得PPI指数低的个体能向好的方向成长；活动算子能使个体的活跃度提高，从而扩大搜索范围；传染算子和治愈算子能使个体获得平均特征信息，从而降低了个体陷入局部最优的概率。 

个体初始化 

假设优化问题搜索空间的维数为n，每个变量的搜索区间为[l_i，u_i]，i=1，2，…，n，则利用正交拉丁方生成算法INIT产生N个初始解的正交表L_N(Nⁿ)的构造算法。 

算法INIT产生N个初始解的正交表L_N(Nⁿ)的构造算法 

步骤1：计算每个变量的离散点y_ij： 

y_ij=l_i+(j-1)(u_i-l_i)/(N-1)，i=1，2，…，n；j=1，2，…，N。 

步骤2：根据正交拉丁方的生成方法计算初始解x_ij： 

x_ij=y_jk,i=1，2，…，N，j=1，2，…，n 

式中：k=(i+j-1)mod N；若k=0，则k=N。 

算法INIT所确定的N个初始解X_i=(x_i1，x_i2，…，x_in)，i=1，2，…，N，具有很好的均衡分散性和整齐可比性。 

所述SIR算法包括如下步骤： 

(1)初始化：a)令时期t=0，按表1初始化本算法中涉及到的所有参数； 

b)按正交拉丁方生成方法INIT确定N个初始个体； 

表1参数的取值方法 

(2)令个体i从1循环到N，重复执行下述步骤(3)～步骤(5)； 

(3)计算$>S_i^t=\mathrm{Rand}\left(\mathrm{0,1}\right),$>$>I_i^t=0.5\mathrm{Rand}\left(\mathrm{0,1}\right),$>$>R_i^t=1-S_i^t-I_i^t;$>其中和分别表示时期t个体i处于易感状态、染病状态和免疫状态的概率；Rand(0，1)表示在[0，1]区间产生一个均匀分布随机数； 

(4)计算个体i的SIR状态：若则若 $>I_i^t=\max (S_i^t,I_i^t,R_i^t),$>则$>{\mathrm{SIR}}_i^t=I;$>若$>R_i^t=\max (S_i^t,I_i^t,R_i^t),$>则$>{\mathrm{SIR}}_i^t=R;$>其中，函数 表示在和三者中取最大者，表示时期t个体i所处 的状态，如若则表示时期t个体i处于易感状态；若则表示时期t个体i处于染病状态；若则表示时期t个体i处于免疫状态； 

(5)令i=i+1，若i≤N，则转上述步骤(3)，否则转步骤(6)； 

(6)执行下列操作： 

(7)令时期t从1循环到G，重复执行下述步骤(8)～步骤(31)，其中G为演化最大代数； 

(8)令个体i从1循环到N，重复执行下述步骤(9)～步骤(28)； 

(9)随机产生β=Rand(0，1)，r=Rand(0，1)； 

(10)利用KM模型式(3)计算$>\left(\begin{array}{c}{S}_i^t=S_i^{t-1}-\beta S_i^{t-1}{I}_i^{t-1}\\ I_i^t=I_i^{t-1}+\beta S_i^{t-1}{I}_i^{t-1}-r{I}_i^{t-1}\\ R_i^t=1-S_i^t-I_i^t\end{array}\right);$>

(11)计算个体i的SIR状态：若则若 $>I_i^t=\max (S_i^t,I_i^t,R_i^t),$>则$>{\mathrm{SIR}}_i^t=I;$>若$>R_i^t=\max (S_i^t,I_i^t,R_i^t),$>则$>{\mathrm{SIR}}_i^t=R;$>

(12)若则令pL=0，pU=pS；其中，pS为状态S出现的概率上限，pL表示概率的下限变量，pU表示概率的上限变量； 

(13)若则令pL=pS，pU=pI；其中，pI为状态I出现的概率上限； 

(14)若则令pL=pS，pU=pR；其中，pR为状态R出现的概率上限； 

(15)令个体的特征j从1循环到n，重复执行下述步骤(16)～步骤(25)； 

(16)若pU<p或p≤pL，则令其中p为S、I、R状态出现的实际概率；否则执行下述步骤(17)～步骤(24)； 

(17)若且则按式(9)描述的活动算子计算

(18)若且则按式(5)描述的传染算子计算

(19)若$>{\mathrm{SIR}}_i^{t-1}=S$>且$>{\mathrm{SIR}}_i^t=R,$>则令$>{\mathrm{SIR}}_i^t=S,$>$>v_{\mathrm{ij}}^t=x_{\mathrm{ij}}^{t-1};$>

(20)若$>{\mathrm{SIR}}_i^{t-1}=I$>且$>{\mathrm{SIR}}_i^t=S,$>则令$>{\mathrm{SIR}}_i^t=I,$>$>v_{\mathrm{ij}}^t=x_{\mathrm{ij}}^{t-1};$>

(21)若且则按式(6)描述的病态算子计算

(22)若且则按式(7)描述的治愈算子计算

(23)若$>{\mathrm{SIR}}_i^{t-1}=R$>且$>{\mathrm{SIR}}_i^t=S$>或者$>{\mathrm{SIR}}_i^t=I,$>则令$>{\mathrm{SIR}}_i^t=R,$>$>v_{\mathrm{ij}}^t=x_{\mathrm{ij}}^{t-1};$>

(24)若且则按式(8)描述的免疫算子计算

(25)令j=j+1，若j≤n，则转上述步骤(16)，否则转步骤(26)； 

(26)将超出可行域的变量值压回到可行域内； 

(27)按式(10)描述的生长算子计算得到

(28)令i=i+1，若i≤N，则转上述步骤(9)，否则转步骤(29)； 

(29)若新得到的全局最优解与最近一次获得的全局最优解之间的误差满足最低要求ε，则转下述步骤(32)； 

(30)保存新得到的全局最优解； 

(31)令t=t+1，若t≤G，则转上述步骤(8)，否则转步骤(32)； 

(32)结束。 

有益效果 

本发明和现有技术相比，具有如下优点： 

1、本发明公开的是一种具有全局收敛性的新型优化算法，该算法采用基于KM传染病模型，该模型与上述免疫算法所采用的理论完全不同。该算法假设在某个生态系统存在N个生物个体，每个生物个体由n个特征来表征。该生态系统存在一种传染病，且在N个生物个体之间传染。该传染病攻击的是生物个体的部分特征。生物个体染病后可以被治愈，治愈后的生物个体不会再染病，即获得免疫能力。个体的体质强弱是通过该个体的某些特征的染 病、某些特征的治愈与某些特征已获得免疫的情况综合决定的。体质强壮的个体能继续生长，而体质虚弱的生物个体则停止生长。该算法通过利用传染算子、病态算子、治愈算子、免疫算子和活动算子使生物个体之间相互交换信息：PPI指数高的个体通过病态算子和免疫算子向PPI指数低的个体传递强壮特征的信息，使得PPI指数低的个体能向好的方向生长；传染算子和治愈算子通过使个体获得其它某些个体的平均特征信息，从而降低了该个体陷入局部最优的概率；活动算子通过使个体的活跃度提高，从而扩大了搜索范围。本算法具有搜索能力强和全局收敛性的特点，为复杂函数优化问题的求解提供了一种解决方案。 

2、SIR算法中涉及的个体是一个种群中的个体，其相关的传染算子、病态算子、免疫算子和活动算子是通过利用KM传染病模型的三个基本假设来进行构造的，完全不需要与要求解的实际优化问题相关，因此SIR算法可以获得通用的传染算子、病态算子、免疫算子和活动算子； 

3、免疫算法中的免疫算子与SIR算法中的免疫算子的构造方法完全不同，前者是利用疫苗选择和疫苗接种两种操作来构造；后者是利用其它已具有免疫能力的个体的一些特征来替换待免疫个体的对应特征的方法来构造，相当于将已具有免疫能力的个体的血清注入待免疫个体的体内，使其获得免疫能力。因此，SIR算法中的免疫算子构造方法依据充分，构造方法既简单又通用； 

4、本发明SIR算法的特点如下： 

1)时间复杂度较低。SIR算法的时间复杂度计算过程如表2所示，其时间复杂度与演化时期G、个体规模N、变量个数n以及各算子的时间复杂度以及其他辅助操作相关。 

表2SIR算法的时间复杂度计算表 

2)SIR算法的搜索能力很强。SIR算法采用KM传染病模型进行构造，算子构造方法既简单又易于扩展，算子种类丰富，可以使SIR算法具有很强的搜索能力。 

3)SIR算法具有全局收敛性。其理由的理论分析如下： 

由SIR算法知，生态系统是一个离散的空间，但每个个体N)是在连续的实数空间取值。个体总个数为N，每个个体即为优化问题(1)的一个试探解，其目标函数值为(按式(2)计算)，则所有个体的状态所形成的集合为 

$>F=\left\{F\left(X_i^t\right)\right|X_i^t\in H\}$>

进一步令 

F＝{F₁,F₂,…,F_N}，F₁≤F₂≤…≤F_N           (A) 

不失一般性，令F₁即为我们所求的全局最优解。将式(11)的下标取出形成 一个集合，即 

U={1，2，…，N} 

集合U中的元素就是随机搜索时每个个体可能所处的状态。假设在某时期我们搜索到的最好目标函数值为F_i，其对应的状态为i。显然，由式(A)知，下一时期搜索时，若向更优的状态k转移，则应满足k<i；相反，若向更差的状态k转移，则应满足k>i，如表A所示。 

表A随机搜索时状态转移 

有F₁≤F(X)≤F_N，将H划分为非空子集为： 

$>\underset{i=1}{\overset{N}{\Sigma }}\left|X_S^i\right|=N;$>

令X^i,j(i＝1,2,…,N,j＝1,2,…,)表示中第j个状态。个体在进化过程中，从一个状态(i，j)转移到另外的状态(k，l)可表示为X^i,j→X^k,l，则假定：从X^i,j到X^k,l的转移概率为p_ij,kl，从X^i,j到中任一状态的转移概率为p_ij,k，从中任一状态到中任一状态的转移概率为p_i,k，则有 

$>p_{\mathrm{ij},k}=\underset{l=1}{\overset{\left|X_S^k\right|}{\Sigma }}{p}_{\mathrm{ij},\mathrm{kl},}$>$>\underset{k=1}{\overset{N}{\Sigma }}{p}_{\mathrm{ij},k}=1,$>$>p_{i,k}\ge p_{\mathrm{ij},k}$>

$>p_{i,k}\ge p_{\mathrm{ij},k}\to \underset{k=1}{\overset{N}{\Sigma }}{p}_{i,k}\ge \underset{k=1}{\overset{N}{\Sigma }}{p}_{\mathrm{ij},k}=1,$>而$>0\le \underset{k=1}{\overset{N}{\Sigma }}{p}_{i,k}\le 1,$>故有 

$>\underset{k=1}{\overset{N}{\Sigma }}{p}_{i,k}=1---\left(B\right)$>

引理1在SIR算法中，$>\forall X^{i,j}\in X_S^i,i=\mathrm{1,2},···,N,j=\mathrm{1,2},···,\left|X_S^i\right|,$>满足： 

$>\forall k>i,p_{i,k}=0---\left(C\right)$>

$>\exists k<i,p_{i,k}>0---\left(D\right)$>

(1)式(C)的证明。设状态i为时期t某个体X^t的状态，该状态i当然就是该个体至今已达到的最好状态。在SIR算法中，每次进行新的演化都总是对该个体当前状态i进一步向更好状态的更新，即有 

$>F\left(X^{t+1}\right)\le F\left(X^t\right)\Rightarrow \forall k>i,p_{\mathrm{ij},\mathrm{kl}}=0\Rightarrow \forall k>i,p_{\mathrm{ij},k}=\underset{l=1}{\overset{\left|X_S^k\right|}{\Sigma }}{p}_{\mathrm{ij},\mathrm{kl}}=0\Rightarrow \forall k>i,p_{i,k}=0$>

上式的含义是：若i为时期t某个体的状态(也必是该个体已达到的最好状态)，在时期t+1该个体的演化只会向更好的状态更新，所以从i开始不可能转移到比i差的任何其它状态上去；由式(A)知，若要F_k>F_i，则比状态i差的状态k必满足k>i，也即最好状态要么保持原状、要么只能向更好的状态更新(即做到步步不差)，如表A所示。 

(2)式(D)的证明。设某个体的当前状态为i，当然必是该个体迄今为止已达到的最好状态，在时期t+1，该个体随机选择传染算子、病态算子、治愈算子、免疫算子和活动算子等操作进行演化以期转移到更好的状态k上。此时，有两种情况出现： 

a)若i是全局最优状态，即i=1，则下一步转移必选k=1(因为不可能转移到比当前状态还差的状态上去)，即必以概率p_1,1=1转移到该全局最优状态上去。因p_1,1=1>0，命题得证； 

b)若i不是全局最优状态，则在全局最优状态1和当前状态i之间必至少存在一中间状态k(如表A所示)，使得F₁≤F_k<F_i，即1≤k<i，此时当前状态i可以转移到状态k上去(因为新状态k比当前状态i更优)，也就是p_i,k>0，命题得证。 

综合上述情况可得证毕。 

Iisufescu M在文献《Finite Markov Processes and Their Applications，Wiley: Chichester,1980》中提出下列定理： 

定理1设P′是一n阶可归约随机矩阵，也就是通过相同的行变换和列变换后可以得到$>P\prime =\left(\begin{array}{ccc}C& ···& 0\\ R& ···& T\end{array}\right),$>其中C是m阶本原随机矩阵并且R≠0，T≠0，则有 

$>P^{\prime \infty }=\underset{k\to \infty }{\lim }{P}^{\prime k}=\underset{k\to \infty }{\lim }\left(\begin{array}{ccc}{C}^k& ···& 0\\ \underset{i=1}{\overset{k-1}{\Sigma }}{T}^{i}R{C}^{k-i}& ···& T^k\end{array}\right)=\begin{array}{c}\left(\begin{array}{ccc}{C}^{\infty }& ···& 0\\ R^{\infty }& ···& 0\end{array}\right)\end{array}$>

上述的矩阵是一个稳定的随机矩阵且P′^∞＝1′P′^∞，P′^∞＝P′⁰P′^∞唯一确定并且与初始分布无关，P′^∞满足如下条件： 

$>P^{\prime \infty }={\left[p_{\mathrm{ij}}\right]}_{n\times n},\left(\begin{array}{c}{p}_{\mathrm{ij}}>\mathrm{0,1}\le i\le n,1\le j\le m\\ p_{\mathrm{ij}}=\mathrm{0,1}\le i\le n,m<j\le n\end{array}\right)$>

定理1的证明过程非常复杂，具体证明过程可参见文献《Finite Markov Processes and Their Applications，Wiley:Chichester,1980》。 

定理2SIR算法具有全局收敛性。 

证明：对于每个可看为是有限Markov链上的一个状态，根据引理1中式(C)的结论可得，该Markov链的转移矩阵为 

由式(B)知，P′矩阵中每行概率之和为1。又根据引理1中式(D)结论得 

由以上可知P′是N阶可归约随机矩阵(Markov概率矩阵)，满足定理1的条件，所以下式成立： 

$>P^{\prime \infty }=\underset{k\to \infty }{\lim }\left(\begin{array}{ccc}{C}^k& ···& 0\\ \underset{i=1}{\overset{k-1}{\Sigma }}{T}^{i}R{C}^{k-i}& ···& T^k\end{array}\right)=\begin{array}{c}\left(\begin{array}{ccc}{C}^{\infty }& ···& 0\\ R^{\infty }& ···& 0\end{array}\right)\end{array}$>

因C^∞＝C＝(1)，T^∞＝0，故必有R^∞＝(1,1,…,1)^T，这是因为Markov转移矩阵P′中每行的概率之和为1。因此有 

$>P^{\prime \infty }=\left(\begin{array}{cccc}1& 0& ···& 0\\ 1& 0& ···& 0\\ ·& ·& ·& ·\\ ·& ·& ·& ·\\ ·& ·& ·& ·\\ 1& 0& ···& 0\end{array}\right),$>且为稳定的随机矩阵。 

上式表明，当k→∞时，概率p_i,1=1，i=1，2，…，N，也即无论初始状态如何，最后都能以概率1收敛到全局最优状态1上。于是得 

$>\underset{t\to \infty }{\lim }p\{F\left(X_i^t\right)\to F(X*)\}=1,i=\mathrm{1,2},···,N$>

因此，SIR算法具有全局收敛性，证毕。 

附图说明

附图是SIR算法处理流程。 

具体实施方式

以下结合附图和具体实例对本发明作进一步的详细描述。 

如附图所示，SIR算法处理流程如下所述(开始时期为t=0)： 

(1)时期t，随机产生生态系统中个体i的疾病传染率β和治愈率r。 

(2)利用KM模型式(3)对个体i计算时期t的易感率S_i(t)、染病率I_i(t)和消除愈R_i(t)。 

(3)在{S_i(t)，I_i(t)，R_i(t)}中确定哪一个最大？有以下三种情况出现： 

(3.1)若是S_i(t)最大，则表明个体i在时期t将处于S状态(即未染病)，这时再判断个体i原来(即时期t-1)处于何种状态，有3种情况： 

(A)若个体i原来处于S状态，即表明个体i原来未染病，现在也未染病， 即S→S，则个体i继续按习惯的方式活动并生长，此时按活动算子更新个体i的生长特征

(B)若个体i原来处于I状态，即表明个体i原来已染病，现在未染病，即I→S，该情况不符合SIR模型的三个假设，此情况不可能出现，则此时个体i依然保持原来的I状态，且个体i的生长特征不发生变化。 

(C)若个体i原来处于R状态，即表明个体i原来染病后已治愈，已不可能再染病(即已免疫)，而现在处于易感状态，即R→S，该情况不符合SIR模型的三个假设，此情况不可能出现，则此时个体i依然保持原来的R状态，且个体i的生长特征不发生变化。 

(3.2)若是I_i(t)最大，则表明个体i在时期t将处于I状态，这时再判断个体i原来(即时期t-1)处于何种状态，有3种情况： 

(A)若个体i原来处于S状态，即表明个体i原来未染病，现在已染病，即S→I，则个体i按传染上疾病进行处理，此时按传染算子更新个体i的生长特征

(B)若个体i原来处于I状态，即表明个体i原来已染病，现在也已染病(即病一直未治愈)，即I→I，则此时个体i依然继续活动，但已处于I状态，此时按活动算子更新个体i的生长特征

(C)若个体i原来处于R状态，即表明个体i原来染病后已治愈，已不可能再染病，而现在处于I状态，即R→I，该情况不符合SIR模型的三个假设，此情况不可能出现，则此时个体i依然保持原来的R状态，且个体i的生长特征不发生变化。 

(3.3)若是R_i(t)最大，则表明个体i在时期t将处于R状态，这时再判断个体i原来(即时期t-1)处于何种状态，有3种情况： 

(A)若个体i原来处于S状态，即表明个体i原来未染病，现在已处于免疫R状态，即S→R，该情况不符合SIR模型的三个假设，此情况不可能出现，则此时个体i依然保持原来的S状态，且个体i的生长特征不发生变化。 

(B)若个体i原来处于I状态，即表明个体i原来已染病，现在已处于免疫R状态，即I→R，则此时个体i病已治愈，现已处于免疫R状态，此时按治愈算子更新个体i的生长特征

(C)若个体i原来处于R状态，即表明个体i原来已处于免疫状态，现在还处于免疫R状态，即R→R，则此时个体i依然继续活动，但处于R状态，此时按活动算子更新个体i的生长特征

(4)不断重复步骤(2)～步骤(4)，直到每个每个生物个体都处理完为止。然后，转步骤(5)。 

(5)令t=t+1，不断重复步骤(1)～步骤(5)，直到找到全局最优解为止。 

下面结合具体的实例对本发明的实施过程作一介绍： 

(1)确定要求解的实际优化问题，将该问题转化成式(1)所描述的标准形式。即 

(2)若实际优化问题是求maxf(X)，则改为min-f(X)。 

(3)若可能，将实际优化问题的所有变量区间进行压缩，即 

若0≤x_i≤a_i，a_i≥0，i=1，2，…，n，则将x_i=a_iy_i代入实际优化问题，这是实际优化问题是关于变量y_i的优化问题，0≤y_i≤1。 

若-a_i≤x_i≤0，a_i≥0，i=1，2，…，n，则将x_i=a_iy_i代入实际优化问题，这是实际优化问题是关于变量yi的优化问题，-1≤y_i≤0。 

若-b_i≤x_i≤a_i，a_i≥0，b_i≥0，i=1，2，…，n，则将x_i=(a_i+b_i)y_i-b_i代入实 际优化问题，这是实际优化问题是关于变量y_i的优化问题，0≤y_i≤1。 

若-a_i≤x_i≤a_i，a_i≥0，i=1，2，…，n，则将x_i=a_iy_i代入实际优化问题，这是实际优化问题是关于变量y_i的优化问题，-1≤y_i≤1。 

(4)按表2确定SIR算法的参数。 

(5)执行优化计算，搜索全局最优解。 

(6)最优解y_i获得后，在利用下面的方法求出x_i即可，i=1，2，…，n。 

若是按-b_i≤x_i≤a_i进行转化的，则x_i=(a_i+b_i)y_i-b_i；否则x_i=a_iy_i，i=1，2，…，n。 

为了更清楚的说明上述操作方法，下面举例来说明： 

(1)对于实际优化问题，求n=100，200，400，600，800，1000，1200时的全局最优解。 

$>\max f\left(X\right)=-20-e+20\exp (-0.2\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{x}_i^2})+\exp \left(\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}\cos \left(2\pi x_i\right)\right)$>

s.t. 

-10≤x_i≤10,i＝1,2,…,n 

(2)将该优化问题转化成式(1)所描述的标准形式，即 

$>\min f\left(X\right)=20+e-20\exp (-0.2\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{x}_i^2})-\exp \left(\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}\cos \left(2\pi x_i\right)\right)$>

s.t. 

-10≤x_i≤10,i＝1,2,…,n 

(3)令x_i=10y_i，Y=(y₁，y₂，…，y_n)，则得 

$>\min f\left(Y\right)=20+e-20\exp (-2\sqrt{\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}{y}_i^2})-\exp \left(\frac{1}{n}\underset{i=1}{\overset{n}{\Sigma }}\cos \left(2\pi y_i\right)\right)$>

s.t. 

-1≤y_i≤1,i＝1,2,…,n 

(4)确定算法的参数，如表3所示。 

表3求解过程各参数取值方法 

参数名>取值方法>演化时期G>G=8000>最优解的最低误差要求ε>ε=10^-8变量数n>n=100，200，400，600，800，1000，1200>个体数N>N=500>活动算子参数m_I，m_Em_I=2，m_E=1>状态S、I、R出现的概率上限pS、pI、pR>pS=1/3，pI=2/3，pR=1>其它所有未列出的参数>均已按算法的取值要求自动随机取值>

(5)利用SIR算法进行求解，所得结果如表4所示。 

表4计算结果 

(6)采用SIR算法求得的最优解在y_i在[-2.9324E-10，3.2574E-10]之内，转化后得x_i在[-2.9324E-9，3.2574E-9]内，i=1，2，…，n。