第２３卷第１期２０１０年２月模式识别与人工智能
ＰＲ＆ＡＩ
Ｖ０１．２３Ｎｏ．１
Ｆｅｂ２０ｌＯ
蚁群算法一阶欺骗性问题的时间复
陈峻１，２孙海鹰１
杂度分析
１（扬州大学信息工程学院计算机系扬州２２５００９）
２（南京大学计算机软件新技术国家重点实验室南京２１００９３）
摘要文中研究蚁群算法求解欺骗性问题时的时间复杂度．以蚁群算法一阶欺骗性问题ｎ－ｂｉｔ陷阱问题为例，证明使用信息素带限的最大最小蚁群算法求解儿－ｂｉｔ陷阱问题达到最优解的时间复杂度为Ｏ（ｎ２ｍｌｎｎ），其中／Ｉ，为问题的规模，ｍ为蚂蚁的个数．实验结果验证上述结论的正确性．
关键词蚁群优化，ｍｂｉｔ陷阱问题，欺骗性问题
中图法分类号ＴＰ３０１．６
ＴｉｍｅＣｏｍｐｌｅｘｉｔｙＡｎａｌｙｓｉｓｏｆＡｎｔＣｏｌｏｎｙＡｌｇｏｒｉｔｈｍ
ｏｎＦｉｒｓｔＯｒｄｅｒＤｅｃｅｐｔｉｖｅＰｒｏｂｌｅｍ
ＣＨＥＮＬｉｎ９１ｔ－，ＳＵＮＨａｉ—Ｙｉｎｌ
１（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒ，ＣｏｌｌｅｇｅｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＹａｎｇｚｈｏｕＵｎｉｖｅｒｓｉｔｙ，
Ｙａｎｇｚｈｏｕ２２５００９）
２（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｆｏｒＮｏｖｅｌＳｏｆｔｗａｒｅＴｅｃｈｎｏｌｏｇｙ，ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００９３）
ＡＢＳＴＲＡＣＴ
Ｔｈｅｔｉｍｅｃｏｍｐｌｅｘｉｔｙｏｆａｎｔｃｏｌｏｎｙｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ）ｏｎｔｈｅｄｅｃｅｐｔｉｖｅｓｙｓｔｅｍｓｉｓａｎａｌｙｚｅｄ．Ｂａｓｅｄｏｎｔｈｅｓｔｕｄｙｏｆｔｈｅｎ—ｂｉｔｔｒａｐｐｒｏｂｌｅｍｗｈｉｃｈｉｓａｆｉｒｓｔｏｒｄｅｒｄｅｃｅｐｔｉｖｅｐｒｏｂｌｅｍｏｆＡＣＯ，Ｉｔｉｓｐｒｏｖｅｄｔｈａｔｔｉｍｅｃｏｍｐｌｅｘｉｔｙｆｏｒｎ—ｂｉｔｔｒａｐｐｒｏｂｌｅｍｉｓＯ（ｎ２ｍｌｎｎ）ｂｙｍａｘ—ｍｉｎａｎｔｓｙｓｔｅｍ（ＭＭＡＳ），ｗｈｉｃｈｉｓａｎＡＣＯｗｉｔｈｌｉｍｉｔａｔｉｏｎｓｏｎｔｈｅｐｈｅｒｏｍｏｎｅｏｎｅａｃｈｅｄｇｅ．Ｈｅｒｅ，ｎｉｓｔｈｅｓｉｚｅｏｆｔｈｅｐｒｏｂｌｅｍａｎｄｍｉｓｔｈｅｎｕｍｂｅｒｏｆａｒｔｉｆｉｃｉａｌａｎｔｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｃｏｎｆｉｒｍｔｈｅｃｏｒｒｅｃｔｎｅｓｓｏｆｔｈｅｃｏｎｃｌｕｓｉｏｎｓ．
ＫｅｙＷｏｒｄｓＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ，凡一ｂｉｔ
ＴｒａｐＰｒｏｂｌｅｍ，ＤｅｃｅｐｔｉｖｅＰｒｏｂｌｅｍ
１引言
蚁群算法‘１卅是意大利学者Ｍ．Ｄｏｒｉｇｏ、Ｖ．Ｍａｎｉｅｚｚｏ和Ａ．Ｃｏｌｏｒｎｉ于２０世纪９０年代初提出的～种智能优化算法．他们模拟蚂蚁寻找食物过程中通过信息素作用于环境以致影响其他个体而呈现出生物的自组织现象，首先设计出蚂蚁系统（ＡｎｔＳｙｓ．ｔｅｒｎ，ＡＳ），并应用于求解旅行商问题（ＴＳＰ），获得较
￥国家自然科学基金（Ｎｏ．６０６７３０６０、６０７７３１０３）、江苏省自然科学基金（Ｎｏ．ＢＫ２００８２０６）和江苏省教育厅自然科学基金（№．０８ＫＪＢ５２００１２）资助项目
收稿口期：２００９—０７—０７；修回日期：２００９—０９—２７
作者简介陈峻，男，１９５１年生，教授，博士生导师，主要研究方向为进化算法和系统优化．Ｅ－ｍａｉｌ：ｌｃｈｅｎ＠ｙｚｅｎ．ｎｅｔ．孙海鹰，女，１９８４年生，硕士研究生，主要研究方向为进化算法、系统优化．
万方数据