《一个蚁群优化模型的期望性能分析.doc》由会员分享，可在线阅读，更多相关《一个蚁群优化模型的期望性能分析.doc（5页珍藏版）》请在三一文库上搜索。
1、一个蚁群优化模型的期望性能分析Expected performance of ant colony optimization model YU Xue-cai， ZHANG Tian-wen (School of Computer Science & Technology, Harbin Institute of Technology, Harbin 150001, China) Abstract: When applying ant colony optimization metaheuristic to combinatorial problems, the combination of
2、an ant colony optimization algorithm and a problem instance may be not a CBS and the pheromone model and its updating rule may make the algorithm converge at the worst solution. This paper developed an ant colony optimization model for solving the k-minimum spanning tree problem which was NP-hard an
3、d analyzed the influence of two updating rules of the pheromone model over the performance of the ant colony optimization algorithm. Analysis showed that the iteration expected quality of the algorithm continuously decreased with the former while increasing with the latter. To utilize all solutions
4、produced, the augmented objective of each infeasible solution was defined in such way that the objective value of each feasible solution was not altered and that of each infeasible solution must be greater than that of the worst feasible solution. Key words：ant colony optimization; augment pheromone
5、 update; combinatorial optimization problem; k-minimum spanning tree problem; augmented objective 0 引言 ?砸先河呕?的第一个算法蚂蚁系统1被提出之后, 人们对其改进和应用2,3作了大量研究。但近年来, 研究的热点已经转向理解蚁群优化的行为47, 特别是信息素建模组合优化的关键问题8。C. Blum等人发现蚂蚁系统模型求解某些组合优化问题的实例时, 其信息素模型更新规则实现的正反馈机制可能使算法收敛到最差解, 具体表现为蚁群的迭代期望质量连续下降。研究例子有作业调度问题5和k-最小生成树问题4,
6、8。蚂蚁系统模型的这种行为在设计蚂蚁算法时应该避免，基于这一目标, 本文研究蚂蚁系统模型求解k-最小生成树问题, 其创新点在于: a)对原来的信息素模型参数的意义重新作了规定, 使其直接表示边被选择的概率; b) 开发了一种新的解构造规则; c)考虑了使用可行解更新和所有解更新两种更新规则，并定义了不可行解的不可行量和扩展目标函数。分析表明, 仅使用可行解的更新规则同样会使蚁群的迭代期望质量连续下降, 算法收敛到最差解；而使用所有解的更新规则则避免了这个问题, 算法收敛到最优解?一。 1 k-最小生成树 k-最小生成树(KMST)问题是最小生成树(MST)问题的一个推广: 给定一个边带权的无向
7、图G=(V,E)(|V|=n且|E|=m), 对任意eE, 边权(e)N(N0)。KMST的目标就是在G中找到一棵恰有k条边的树Tk使之最小化: f(Tk)=eE(Tk)(e)(1) ?MST不同的是, 一般的KMST是NP难的。 2 KMST的一个蚁群优化算法 ?偕柰?G的所有边已经按某个序排好:e1,em, 则KMST的解结构定义长度为m的二进制串,第i位对应边ei。 如果第i位为1, 表示边ei在二进制串对应的树Tk中；相反, 如果第i位为0, 表示边ei不在二进制串对应的树Tk中。与此解结构相应的信息素模型是一个包含m个分量的向量, 每个i分量对应一个边ei。信息素模型的值表示对应的边
8、被选择的概率, 这与大多数文献中的描述不同。算法1给出了基于这个信息素模型的求解KMST蚁群优化算法的抽象伪代码，Nant表示总的蚂蚁数。 ?惴?1 KMST的一个蚁群算法 ?跏蓟?信息素模型: InitPherModel(); while 终止条件没满足 do for 蚂蚁I=1,Nant do 用信息素模型构造解TIk=solu(); end for ?畔啬透?新update(T1k,TNantk); end while ?谒惴?1中，信息素模型先被初始化, 之后蚁群利用信息素模型参数构造一组解, 被构造的这组解用于更新信息素模型。后面的两个算法步被迭代地反复执行, 直到终止条件得到满足, 如超过了时间限制或最大迭代步数。下面详细定义算法1中的三个操作。 a)initPherModel()， 在算法开始时, 信息素模型的m个分量被设置为相同的值0.5。 b)Solu() 在每个迭代步, 所有的蚂蚁构造一个长为m的二进制序列sI。对sI的每个分量i, 蚂蚁根据信息素模型参数i随机地设置 siI=irnd?01（2） 其中:rnd是一个均匀分布在0,1的随机数。表达式ab?01的意思是如果a