在上一篇文章里介绍了用遗传算法解学生选导师分配问题，点击进入

在过去的一篇文章里也介绍了用PSO算法优化BP神经网络，点击进入

本文将介绍用QPSO算法解学生选导师分配问题。QPSO(Quantum-behaved Particle Swarm Optimization)，即量子行为的粒子群算法，是一种改进的PSO算法，其增强了粒子的全局搜索能力，保证了搜索结果的全局收敛性。

在量子空间中，粒子的速度和位置不能同时确定，因此在QPSO算法中只需要确定粒子的位置，其方程为：

其中，u为[0,1]内变化的随机数，L的方程为：

其中β为收缩扩张系数，M为粒子的数目，Pi为第i个粒子的pbest

算法中只有一个控制参数β，其值一般随迭代次数的增加而线性减小。

为了延缓QPSO算法的早熟趋势，需要对L和β进行改进。随时间t增长，粒子所经历的个体最优位置pbest就越接近群体的最佳位置gbest，mbest与每个粒子的位置的差距也越来越小，这样粒子的搜索范围非常小，导致粒子群进化停滞。为此，将参数β随时间作线性增长，将延缓粒子群陷入早熟。公式如下：

其中，maxiter是迭代的最大次数

即便β增长到0.9，但在算法搜索后期，仍然有粒子所经历的个体最优位置pbest与群体的最佳位置gbest非常接近，导致参数L非常小，因此对参数L做如下改进：

其中ε取0.0005，A取0.5

【算法分析】关于学生选导师分配问题的描述在之前的文章中已写过，在此不再熬述。之前遗传算法中的染色体，在QPSO算法中就是粒子，两者代表的物理意义完全意一样，只是名称不同。并且在遗传算法中设计的成本函数同样适用。只是迭代进化的过程中，使用量子粒子群算法替换了遗传算法。

【实验仿真】本文的实验过程与上篇文章的遗传算法实验类似，因此，只需用下列Python代码替换geneticoptimize函数及之后部分即可。

#QPSO算法
def qpsooptimize(domain, costf, swarmSize = 5000,
                    beta = 1.7, maxiter = 100):
    #粒子群
    swarm = []
    #粒子长度
    swarmLength = len(domain)
    #粒子当前适应度值
    swarmfitness = []
    #个体最优值
    pBest = []
    #个体最优适应度值
    pBestfitness = []
    #全局最优值
    gBest = []
    #全局最优适应度值
    gBestfitness = 2147483647
    #粒子平均最好位置
    mbest = []
    #初始化种群
    for i in range(swarmSize):
        vec = [random.randint(domain[j][0], domain[j][1])
               for j in range(swarmLength)]
        swarm.append(vec)
        
        swarmfitness.append(0)
        
        vec = [0 for j in range(swarmLength)]
        pBest.append(vec)
        
        pBestfitness.append(2147483647)
    for i in range(swarmLength):
        gBest.append(0)
        mbest.append(0)
    
    #主循环    
    for i in range(maxiter):
        for j in range(swarmSize):
            swarmfitness[j] = costf(swarm[j])
            #更新个体最优值
            if pBestfitness[j] > swarmfitness[j]:
                pBestfitness[j] = \
                    copy.deepcopy(swarmfitness[j])
                pBest[j] = copy.deepcopy(swarm[j])
                
                #更新全局最优值
                if gBestfitness > swarmfitness[j]:
                    gBestfitness = \
                        copy.deepcopy(swarmfitness[j])
                    gBest = copy.deepcopy(swarm[j])
        
        #更新粒子平均最好位置
        for j in range(swarmLength):
            p = 0
            for k in range(swarmSize):
                p += swarm[k][j]
            mbest[j] = p / float(swarmSize)
        
        
        #更新粒子位置
        beta = 0.3 * (maxiter + i) / maxiter + 0.3
        for j in range(swarmSize):
            for k in range(swarmLength):
                p1 = random.random()
                p2 = random.random()
                p = (p1 * pBest[j][k] + p2 * gBest[k]) / \
                    float(p1 + p2)
                l = 2 * beta * abs(mbest[k] - swarm[j][k])
                if l < 0.0005:
                    l = 0.5 * random.random()
                
                if random.random() > 0.5:
                    swarm[j][k] = p - l / 2 * \
                        math.log(1 / random.random())
                else:
                    swarm[j][k] = p + l / 2 * \
                        math.log(1 / random.random())
                
                swarm[j][k] = int(swarm[j][k] + 0.5)
                
                if swarm[j][k] < domain[k][0]:
                    swarm[j][k] = domain[k][0]
                elif swarm[j][k] > domain[k][1]:
                    swarm[j][k] = domain[k][1] 

        #打印当前最优值
        print "%d : %d" % (i, gBestfitness)
    return gBest

teachers, students, teacherPlanCount, studentCount = loadData()
domain = [(0, teacherPlanCount - 1 - i) 
          for i in range(studentCount)]
s = qpsooptimize(domain, teahcercost)
printsolution(s)

使用QPSO算法得到的实验结果并不如GA算法，这是让我很费解的地方。每个算法都有其适用的领域，也许QPSO算法并不适合这种粒子的值都严格是整数的场合(纯属猜想)。

发这篇文章还有一个目的，在网上一直都没有找到QPSO算法的完整实现，看到的代码写得都不好，因此决定把自己写的拿出来与大家分享。