粒子群优化算法[17]是一种进化算法。它使用随机解作为它的初始解,通过一次次的迭代后找到问题的最优解,并通过适应度对解的品质做一个评价。它的规则比遗传算法简单,既没有交贪婪机制也没有交叉机制。目前,离散粒子群算法和模糊粒子群算法用于求解二次分配问题。对一些有着多个目标的QAP问题而言,模糊粒子群算法也能较好的求出其最优解。
意大利学者 M。Dorigo 受到自然界中蚂蚁群体行为特性的启发提出了蚁群算法[23]。目前,动态自适应蚂蚁算法[13]、最大最小蚂蚁算法[14]、HAS-QAP[15]、并行蚁群算法[16]等蚂蚁算法被应用于二次分配问题的求解。信息素的管理是这些算法中的一个重要组成部分。存放在 的矩阵中的信息素: , 是设备 i 在位置 j 上的有效性。从实验的结果上可以看出,蚂蚁算法能很好的求解二次分配问题中的抽象问题。
禁忌搜索算法[21]把局部邻域进行了扩充,从整体上对问题进行一个寻优。该算法首先通过局部搜索找到该区域的最优解并将其标记,其次在下一次搜索中避开已经标记出来的解,来使得搜索途径更加有效。对邻域函数、禁忌对象、禁忌表和藐视准则实施不同的法案,能使得构成不同的禁忌搜索算法。固定禁忌表的禁忌搜索算法、鲁棒禁忌搜索算法、并行禁忌搜索算法等禁忌搜索算法用于求解二次分配问题。
Thomas教授提出GRASP算法。该算法与上述算法中所使用的方法都有很大的不同(它的每次迭代都是随机的)。GRASP算法每次迭代都会生成一个限制侯选列表,并从限制候选表中随机选择元素作为它的初始解,再对该解进行局部搜索将其优化。算法会进行多次局部搜索,因此也会产生多个局部最优解。通过比较这些局部最优解,把结果最佳的作为全局次优解。Li Ying和Pardalos用GRASP算法对QAPLIB库中88个二次分配问题进行求解[20],为大多数实例求得了在当时的最佳结果。
二次分配问题研究现状(2):http://www.youerw.com/yanjiu/lunwen_82950.html