SIR-DNA传染病动力学优化算法
|
摘要
为了解决某些复杂优化问题,采用基于DNA的SIR(susceptible-infectious-recovered)传染病模型构建了SIR-DNA算法。该算法将优化问题的求解过程设想成一种传染病在一个生态系统中的若干动物个体之间传播的过程,其传播规律可用SIR传染病模型描述。传染病攻击的是动物个体若干个致病基因中某些位点。对于不同的动物个体,其哪些致病基因及其中的哪些点位被攻击完全是随机的;若一个动物个体被治愈,其哪些免疫基因及其中的哪些位点获得免疫也完全是随机的。因传染病每次攻击的是个体的极小部分基因,故每次处理的变量数很少,从而实现了算法的天然降维;因采用基于DNA的SIR传染病模型,故可以区分不同的传染病毒在致病机理之间的差异;利用SIR模型所描述的疾病传播机理构造出了S-S、S-I、I-I、I-R、R-R和R-S等算子,使个体之间能通过疾病传播天然地充分交换信息。测试结果表明,该算法具有搜索能力强的特点,对求解复杂优化问题具有很高的收敛速度。
To solve some complicated optimization problems, this paper constructs the SIR-DNA algorithm by using the DNA-based SIR(susceptible-infectious-recovered) epidemic model. The algorithm takes the solving process of an optimization problem as the process that an infectious disease spreads among animal individuals in an ecosystem, and its spreading law can be described by the SIR epidemic model. What the infectious disease attack is some sites lying in some pathogenic genes of an animal individual. For different animal individual, which pathogenic genes and associated sites are attacked by the contagious disease, are completely random. If an infected individual is cured, which immune genes and associated sites will possess of immunization, are completely random. Because an infectious disease attacks only a small part of genes each time, only a small number of variables will be processed each time, thus a natural dimension reduction is realized. Because the DNA-based SIR epidemic model is applied,the difference of pathogenic mechanisms among different infectious diseases can be differentiated. The algorithm uses the transferring mechanism of the infectious disease described by the SIR epidemic model to construct S-S, S-I,I-I, I-R, R-R and R-S operators so as to enable individuals to exchange feature information among them easily, fully and naturally. Some case studies show that the algorithm has the characteristics of strong search capability and high convergence speed for the complicated functions optimization problems.
To solve some complicated optimization problems, this paper constructs the SIR-DNA algorithm by using the DNA-based SIR(susceptible-infectious-recovered) epidemic model. The algorithm takes the solving process of an optimization problem as the process that an infectious disease spreads among animal individuals in an ecosystem, and its spreading law can be described by the SIR epidemic model. What the infectious disease attack is some sites lying in some pathogenic genes of an animal individual. For different animal individual, which pathogenic genes and associated sites are attacked by the contagious disease, are completely random. If an infected individual is cured, which immune genes and associated sites will possess of immunization, are completely random. Because an infectious disease attacks only a small part of genes each time, only a small number of variables will be processed each time, thus a natural dimension reduction is realized. Because the DNA-based SIR epidemic model is applied,the difference of pathogenic mechanisms among different infectious diseases can be differentiated. The algorithm uses the transferring mechanism of the infectious disease described by the SIR epidemic model to construct S-S, S-I,I-I, I-R, R-R and R-S operators so as to enable individuals to exchange feature information among them easily, fully and naturally. Some case studies show that the algorithm has the characteristics of strong search capability and high convergence speed for the complicated functions optimization problems.
引文
[1]Adleman L M.Molecular computation of solution to combinatorial problems[J].Science,1994,266(5187):1021-1024.
[2]Zhang Xuncai,Zhao Hailan,Cui Guangzhao,et al.Research advances and prospect of DNA computing[J].Computer Engineering and Applications,2007,43(10):44-47.
[3]Takahashi K,Yaegashi S,Asanuma H,et al.Photo-and thermoregulation of DNA nanomachines[C]//LNCS 3892:Proceedings of the 11th International Workshop on DNA Computing,London,Jun 6-9,2005.Berlin,Heidelberg:Springer,2005:336-346.
[4]Wu Fan,Li Kenli.An algorithm in tile assembly model for N queen problem[J].Acta Electronica Sinica,2013,41(11):2174-2180.
[5]Li Kenli,Luo Xing,Wu Fan,et al.An algorithm in tile assembly model for maximum clique problem[J].Journal of Computer Research and Development,2013,50(3):666-675.
[6]Yao Qingan,Zheng Hong,Wang Hongmei.DNA computing model for shortest path problem based on k-armed molecule and sticker operation[J].Journal of Jilin University:Information Science Edition,2014,32(6):653-656.
[7]Xu Jinglei,Zhao Hongchao,Liu Xiyu.Closed circle DNAalgorithm of traveling salesman problem[J].Computer Engineering&Science,2014,36(1):111-114.
[8]Ma Ying,Yin Zhixiang.DNA computing model for the graph vertex coloring problem by plasmids[J].Journal of Anhui University of Science and Technology:Natural Science,2015,35(2):64-67.
[9]Wu Xue,Song Chenyang,Zhang Nan,et al.DNA algorithm for maximum matching problem based on sticker computation model[J].Computer Science,2013,40(12):127-132.
[10]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics[J].Proceedings of the Royal Society of London:Series A,1927,115(772):700-721.
[11]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics(II):the problem of endemicity[J].Proceedings of the Royal Society of London,1932,138(795):55-83.
[12]Wang Qian,Wang Tingting.Stability analysis of a SIRS epidemic model[J].Journal of Capital Normal University:Natural Science Edition,2016,37(2):5-11.
[13]Huang Guangqiu.SIS epidemic model-based optimization[J].Journal of Computation Science,2014,5(1):32-50.
[14]Liang J J,Qu B Y,Suganthan P N,et al.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization,201212[R].Singapore:Nanyang Technological University,2013.
[15]Chuang Yaochen,Chen C T,Hwang C.A simple and efficient real-coded genetic algorithm for constrained optimization[J].Applied Soft Computing,2016,38:87-105.
[16]Koro?ec P,?ilc J,Filipi?B.The differential ant-stigmergy algorithm[J].Information Sciences,2012,192:82-97.
[17]Beheshti Z,Shamsuddin S M.Non-parametric particle swarm optimization for global optimization[J].Applied Soft Computing,2015,28:345-359.
[18]Al-Roomi A R,El-Hawary M E.Metropolis biogeographybased optimization[J].Information Sciences,2016,360:73-95.
[19]Mukherjee R,Debchoudhury S,Das S.Modified differential evolution with locality induced genetic operators for dynamic optimization[J].European Journal of Operational Research,2016,253(2):337-355.
[20]Zhao Zhiwei,Yang Jingming,Hu Ziyu,et al.A differential evolution algorithm with self-adaptive strategy and control parameters based on symmetric Latin hypercube design for unconstrained optimization problems[J].European Journal of Operational Research,2016,250(1):30-45.
[21]Li Genghui,Cui Laizhong,Fu Xianghua,et al.Artificial bee colony algorithm with gene recombination for numerical function optimization[J].Applied Soft Computing,2017,52:146-159.
[2]张勋才,赵海兰,崔光照.DNA计算的研究进展及展望[J].计算机工程与应用,2007,43(10):44-47.
[4]吴帆,李肯立.基于自组装的N皇后问题DNA计算算法[J].电子学报,2013,41(11):2174-2180.
[5]李肯立,罗兴,吴帆,等.基于自组装模型的最大团问题DNA计算算法[J].计算机研究与发展,2013,50(3):666-675.
[6]姚庆安,郑虹,王红梅.基于k-臂分子求解最短路径的DNA计算模型[J].吉林大学学报:信息科学版,2014,32(6):653-656.
[7]徐京雷,赵洪超,刘希玉.旅行商问题的闭环DNA算法[J].计算机工程与科学,2014,36(1):111-114.
[8]马莹,殷志祥.图顶点着色问题的质粒DNA计算[J].安徽理工大学学报:自然科学版,2015,35(2):64-67.
[9]吴雪,宋晨阳,张楠,等.最大匹配问题的粘贴DNA算法[J].计算机科学,2013,40(12):127-132.
[12]王茜,王婷婷.SIRS传染病模型的稳定性分析[J].首都师范大学学报:自然科学版,2016,37(2):5-11.
[2]Zhang Xuncai,Zhao Hailan,Cui Guangzhao,et al.Research advances and prospect of DNA computing[J].Computer Engineering and Applications,2007,43(10):44-47.
[3]Takahashi K,Yaegashi S,Asanuma H,et al.Photo-and thermoregulation of DNA nanomachines[C]//LNCS 3892:Proceedings of the 11th International Workshop on DNA Computing,London,Jun 6-9,2005.Berlin,Heidelberg:Springer,2005:336-346.
[4]Wu Fan,Li Kenli.An algorithm in tile assembly model for N queen problem[J].Acta Electronica Sinica,2013,41(11):2174-2180.
[5]Li Kenli,Luo Xing,Wu Fan,et al.An algorithm in tile assembly model for maximum clique problem[J].Journal of Computer Research and Development,2013,50(3):666-675.
[6]Yao Qingan,Zheng Hong,Wang Hongmei.DNA computing model for shortest path problem based on k-armed molecule and sticker operation[J].Journal of Jilin University:Information Science Edition,2014,32(6):653-656.
[7]Xu Jinglei,Zhao Hongchao,Liu Xiyu.Closed circle DNAalgorithm of traveling salesman problem[J].Computer Engineering&Science,2014,36(1):111-114.
[8]Ma Ying,Yin Zhixiang.DNA computing model for the graph vertex coloring problem by plasmids[J].Journal of Anhui University of Science and Technology:Natural Science,2015,35(2):64-67.
[9]Wu Xue,Song Chenyang,Zhang Nan,et al.DNA algorithm for maximum matching problem based on sticker computation model[J].Computer Science,2013,40(12):127-132.
[10]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics[J].Proceedings of the Royal Society of London:Series A,1927,115(772):700-721.
[11]Kermack W O,Mckendrick A G.Contributions to the mathematical theory of epidemics(II):the problem of endemicity[J].Proceedings of the Royal Society of London,1932,138(795):55-83.
[12]Wang Qian,Wang Tingting.Stability analysis of a SIRS epidemic model[J].Journal of Capital Normal University:Natural Science Edition,2016,37(2):5-11.
[13]Huang Guangqiu.SIS epidemic model-based optimization[J].Journal of Computation Science,2014,5(1):32-50.
[14]Liang J J,Qu B Y,Suganthan P N,et al.Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization,201212[R].Singapore:Nanyang Technological University,2013.
[15]Chuang Yaochen,Chen C T,Hwang C.A simple and efficient real-coded genetic algorithm for constrained optimization[J].Applied Soft Computing,2016,38:87-105.
[16]Koro?ec P,?ilc J,Filipi?B.The differential ant-stigmergy algorithm[J].Information Sciences,2012,192:82-97.
[17]Beheshti Z,Shamsuddin S M.Non-parametric particle swarm optimization for global optimization[J].Applied Soft Computing,2015,28:345-359.
[18]Al-Roomi A R,El-Hawary M E.Metropolis biogeographybased optimization[J].Information Sciences,2016,360:73-95.
[19]Mukherjee R,Debchoudhury S,Das S.Modified differential evolution with locality induced genetic operators for dynamic optimization[J].European Journal of Operational Research,2016,253(2):337-355.
[20]Zhao Zhiwei,Yang Jingming,Hu Ziyu,et al.A differential evolution algorithm with self-adaptive strategy and control parameters based on symmetric Latin hypercube design for unconstrained optimization problems[J].European Journal of Operational Research,2016,250(1):30-45.
[21]Li Genghui,Cui Laizhong,Fu Xianghua,et al.Artificial bee colony algorithm with gene recombination for numerical function optimization[J].Applied Soft Computing,2017,52:146-159.
[2]张勋才,赵海兰,崔光照.DNA计算的研究进展及展望[J].计算机工程与应用,2007,43(10):44-47.
[4]吴帆,李肯立.基于自组装的N皇后问题DNA计算算法[J].电子学报,2013,41(11):2174-2180.
[5]李肯立,罗兴,吴帆,等.基于自组装模型的最大团问题DNA计算算法[J].计算机研究与发展,2013,50(3):666-675.
[6]姚庆安,郑虹,王红梅.基于k-臂分子求解最短路径的DNA计算模型[J].吉林大学学报:信息科学版,2014,32(6):653-656.
[7]徐京雷,赵洪超,刘希玉.旅行商问题的闭环DNA算法[J].计算机工程与科学,2014,36(1):111-114.
[8]马莹,殷志祥.图顶点着色问题的质粒DNA计算[J].安徽理工大学学报:自然科学版,2015,35(2):64-67.
[9]吴雪,宋晨阳,张楠,等.最大匹配问题的粘贴DNA算法[J].计算机科学,2013,40(12):127-132.
[12]王茜,王婷婷.SIRS传染病模型的稳定性分析[J].首都师范大学学报:自然科学版,2016,37(2):5-11.