基于量子粒子群算法求解整数规划.docx

基于量子粒子群算法求解整数规划.docx基于量子粒子群算法求解整数规划摘要:通过引入量子行为来增强粒子的全局收敛能力,提出了量子粒子群优化算法(QPSO),并用于求解整数规划问题。测试函数的仿真结果表明,通过适当的参数设置,并将每次迭代所生成的实数值截至整数值后进行下一次迭代,可以保证QPSO算法求解的精度,提高收敛速度且能有效避免早熟。关键词:粒子群算法;量子粒子群算法;整数规划中图分类号:O22文献标志码:A文章编号:1001―3695(2007)03―0079―03IP(IntegerProgramming,整数规划)是要求决策变量取整数值的优化问题,在解决任务调度、资金分配、股票分析、网络设计和VLSI电路设计等问题中具有重要的应用。Gall等人[1]早在20世纪六七十年代就曾用进化算法(EA)解决整数规划问题。较之于其他几种方法,如分枝限界法、割平面法、完全枚举法等,在处理规模较大的整数规划问题时,EA具有计算量小的优点,因此应用越来越普遍。但这种方法也存在自身的局限性。Rudolph[2]运用遗传算法,发现用一个固定长度的二进制位串来表示一个在非约束整数空间进行搜索而得到二进制位串编码的可能解的方法不可行;另一种通过进化策略(ES),将搜索空间Zn嵌入到Sn并且将实数截至整数的方法也不是经常有效的。原因在于这些用于搜索实数最小值的进化算法的某些特性在整数搜索空间中并不需要,因为在l1准则中两点的最小距离为1,这样,只有步长大于1时才进行搜索。因此EA解决IP应该直接在整数空间进行。因此本文考虑如下一般形式的整数规划问题:其中,Z是整数集,S是一个无约束的可行性区域。事实上,整数规划问题的最大化在文献中也很普遍,但在本文中将仅仅考虑IP的无约束最小化情况,这是因为一个最大化问题可以很容易地转换成一个最小化问题。PSO(ParticleSwarmOptimization,粒子群算法)是一种群体智能算法,是继遗传算法等进化算法以后新出现的一类智能优化算法。它模拟鸟类的觅食行为,是受到生物群体模型启发而设计的一种智能算法。该算法最大的特点是容易实现,且控制参数少、计算速度快。??本文采用改进的粒子群优化算法――量子粒子群算法,提出了解决整数规划问题的新方法。??Kennedy和Eberhart于1995年提出的PSO算法是一种基于群体的具有全局搜索能力的随机优化算法[3]。粒子群算法与其他进化算法类似,也采用群体和进化的概念,同样也是依据个体(粒子)的适应值大小进行操作。所不同的是,粒子群算法不像其他进化算法那样对于个体使用进化算子,而是将每个个体Xi=(xi1,xi2,…,xiD)看做是在D维搜索空间中的一个没有体积和重量的粒子,并在搜索空间中以一定的速度Vi=(vi1,vi2,…,viD)飞行。该飞行速度由个体的最好位置Pi=(pi1,pi2,…,piD)和群体的最好位置pgd??进行动态调整。粒子状态更新操作如下:其中,学****因子φ1和φ2决定社会群体pg和个体认知pi的相互影响。自PSO算法提出后,学者们也进行了大量有关提高算法收敛性和多样性的工作。一般来说,对于基于群体的搜索优化方法,适当地控制全局搜索和局部搜索能力对有效地找到最优解起到关键作用。Eberhart和Shi[4]发现PSO可以有效地进行广域搜索但缺乏精确搜索,因此他们引进