基于改进蚁群算法的服务组合优化

《基于改进蚁群算法的服务组合优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３５卷第２期计算机学报Ｖｏｌ．３５Ｎｏ．２２０１２年２月ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＦｅｂ．２０１２基于改进蚁群算法的服务组合优化夏亚梅１），２）程渤１）陈俊亮１）孟祥武１）刘栋１）１）（北京邮电大学网络与交换技术国家重点实验室北京１００８７６）２）（北京邮电大学软件学院北京１００８７６）摘要为进行服务组合优化及适应服务组合优化过程中Ｗｅｂ服务的动态性、不稳定性以及多种ＱｏＳ属性限制等问题，提出一种多信息素动态更新的蚁群算法ＭＰＤＡＣＯ，包括ＭＰＤＡＣＯ局部优化算法和ＭＰＤＡＣＯ全局优化算法，该算法基于建立的服务组合

2、模型，在基本蚁群算法基础上进行研究和改进，可以适应服务组合优化过程中发生的服务无效以及服务中ＱｏＳ变化等情况．另外，为使算法能较快地收敛于最优解，在实验基础上对蚁群算法策略进行了改进．为验证以上算法的有效性，在一个旅游领域的服务推荐系统中对算法进行了仿真实验，实验结果表明文中提出的算法较基本蚁群算法及一种应用于服务选择的遗传算法有更好的性能．关键词语义网；服务组合；服务选择；蚁群算法；最优化中图法分类号ＴＰ３１１犇犗犐号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１２．００２７０犗狆狋犻犿犻狕犻狀犵犛犲狉狏犻犮犲狊犆狅犿狆狅狊犻狋犻狅狀犅犪狊

3、犲犱狅狀犐犿狆狉狅狏犲犱犃狀狋犆狅犾狅狀狔犃犾犵狅狉犻狋犺犿ＸＩＡＹａＭｅｉ１），２）ＣＨＥＮＧＢｏ１）ＣＨＥＮＪｕｎＬｉａｎｇ１）ＭＥＮＧＸｉａｎｇＷｕ１）ＬＩＵＤｏｎｇ１）１）（犛狋犪狋犲犓犲狔犔犪犫狅狉犪狋狅狉狔狅犳犖犲狋狑狅狉犽犻狀犵犪狀犱犛狑犻狋犮犺犻狀犵犜犲犮犺狀狅犾狅犵狔，犅犲犻犼犻狀犵犝狀犻狏犲狉狊犻狋狔狅犳犘狅狊狋狊牔犜犲犾犲犮狅犿犿狌狀犻犮犪狋犻狅狀狊，犅犲犻犼犻狀犵１００８７６）２）（犛犮犺狅狅犾狅犳犛狅犳狋狑犪狉犲犈狀犵犻狀犲犲狉犻狀犵，犅犲犻犼犻狀犵犝狀犻狏犲狉狊犻狋狔狅犳犘狅狊狋狊牔犜犲犾犲犮狅犿犿狌狀犻犮

4、犪狋犻狅狀狊，犅犲犻犼犻狀犵１００８７６）犃犫狊狋狉犪犮狋Ｉｎｏｒｄｅｒｔｏｏｐｔｉｍｉｚｅｓｅｒｖｉｃｅｓｃｏｍｐｏｓｉｔｉｏｎ，ａｄａｐｔｔｈｅｄｙｎａｍｉｃａｎｄｉｎｓｔａｂｌｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆＷｅｂｓｅｒｖｉｃｅｓａｎｄｔｈｅｌｉｍｉｔａｔｉｏｎｏｆｍｕｌｔｉＱｏＳａｔｔｒｉｂｕｔｅｓｉｎｔｈｅｐｒｏｃｅｓｓｏｆｓｅｒｖｉｃｅｓｃｏｍｐｏｓｉｔｉｏｎ，ｔｈｉｓｐａｐｅｒｐｕｔｓｆｏｒｗａｒｄａｎａｌｇｏｒｉｔｈｍｎａｍｅｄＭｕｌｔｉｐｈｅｒｏｍｏｎｅａｎｄＤｙｎａｍｉｃａｌｌｙＵｐｄａｔｉｎｇＡｎｔＣｏｌｏ

5、ｎｙＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍ（ＭＰＤＡＣＯ），ｗｈｉｃｈｉｎｃｌｕｄｅｓｏｎｅｇｌｏｂａｌｏｐｔｉｍｉｚｉｎｇａｌｇｏｒｉｔｈｍａｎｄａｎｏｔｈｅｒｌｏｃａｌｏｐｔｉｍｉｚｉｎｇａｌｇｏｒｉｔｈｍ．Ｔｈｅａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｉｓｂａｓｅｄｏｎｔｈｅＡＣＯａｎｄｃｏｍｐｏｓｉｔｉｏｎｍｏｄｅｌｔｈａｔｈａｓｂｅｅｎｂｕｉｌｔ，ｃａｎｆｉｔｆｏｒｓｕｃｈｃｏｎｄｉｔｉｏｎｓａｓｓｅｒｖｉｃｅｉｎｖａｌｉｄａｔｉｏｎ，ＱｏＳｃｈａｎｇｉｎｇ，ｅｔｃ．Ｉｎａｄｄｉｔｉｏｎ，ｔｈｅａｌｇｏｒｉｔｈｍｈａｓｉｍｐｒｏｖｅｄ

6、ｔｈｅＡＣＯｓｔｒａｔｅｇｙｏｎｔｈｅｂａｓｉｓｏｆｅｘｐｅｒｉｍｅｎｔｔｏｍａｋｅｉｔｓｅｌｆｂｅａｂｌｅｔｏｃｏｎｖｅｒｇｅｔｏｏｐｔｉｍａｌｓｏｌｕｔｉｏｎ．Ｉｎｏｒｄｅｒｔｏｖｅｒｉｆｙｔｈｅｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｅａｂｏｖｅａｌｇｏｒｉｔｈｍｓ，ｔｈｉｓｐａｐｅｒｍａｋｅｓａｓｉｍｕｌａｔｉｏｎｅｘｐｅｒｉｍｅｎｔｏｎａｐｒｏｔｏｔｙｐｅｉｎｔｏｕｒｉｓｍ，ａｎｄｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｔｗｏａｌｇｏｒｉｔｈｍｓａｒｅｍｏｒｅｅｆｆｅｃｔｉｖｅｔｈａｎＡＣＯａｎｄｔｈｅＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍａｐ

7、ｐｌｉｅｄｔｏｓｅｒｖｉｃｅｓｅｌｅｃｔｉｏｎ．犓犲狔狑狅狉犱狊ｓｅｍａｎｔｉｃ；ｓｅｒｖｉｃｅｓｃｏｍｐｏｓｉｔｉｏｎ；ｓｅｒｖｉｃｅｓｅｌｅｃｔｉｏｎ；ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ；ｏｐｔｉｍｉｚａｔｉｏｎ收稿日期：２００８０５２６；最终修改稿收到日期：２０１２０１０５．本课题得到国家“九七三”重点基础研究发展规划项目基金（２０１１ＣＢ３０２７０４）与国家自然科学基金（６１００１１１８）资助．夏亚梅，女，１９７６年生，博士，讲师，主要研究方向为动态服务组合、最优化理论、云计算．Ｅｍａｉｌ：ｘｉａｙａｍｅｉ＠ｇｍａｉｌ．

8、ｃｏｍ．程渤，男，１９７５年生，博士，副教授，主要研究方向为服务组合、物联网等．陈俊亮，男，１９３３年生，教授，博士生导师，中国科学院院士，中国工程院院士，主要研究领域为语义网．