【作者】 ；
【导师】 ；
【作者基本信息】 山东师范大学， 信息管理及电子商务， 2009， 博士
【摘要】 最优化问题是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问题,其目的是从众多备选方案中选择出使目标函数达到最小或最大的方案。优化方法涉及的应用领域很广,问题种类与性质繁多,根据不同的原则可以给出不同的分类。根据决策变量的取值类型,可分为函数优化问题与组合优化问题(又称离散优化问题)。离散优化问题是一类重要的优化问题,随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,且其大部分都是NP-hard问题。这些问题正越来越受到运筹学、应用数学、计算机科学及管理科学等诸多学科的高度重视。很长时间以来,人们试图寻找解决各种组合问题的有效算法。长期的努力在此问题上取得了一定的成效,但NP问题仍然是21世纪一个最具挑战性的科学难题,是在理论信息学中计算复杂度理论领域里至今没有解决的问题。群体智能优化方法是一个新兴的研究领域,为复杂优化问题的求解提供了一个有效手段,已引起相关领域学者的广泛关注。其中有代表性的有意大利学者Marco Dorigo于1991年提出的蚁群优化方法和1995年James Kennedy和Russell Eberhart基于对鸟群、鱼群捕食行为的模拟,提出的粒子群优化方法。由于这些方法概念简明、所需设置的参数较少、实现方便,特别用以解决复杂的组合优化问题具有优越性,迅速得到国际优化计算领域的认可,并在工程设计、生产优化等应用领域取得成功的应用。论文首先系统深入地分析了离散粒子群算法的本质,构建了一种简便高效的二元离散粒子群算法。然后,提出了一种全新的求解线性顺序问题的离散粒子群算法。其次,对置换流水车间调度问题初始解集的各种构建方法进行了比较分析。最后,提出了一种能够减少早熟现象的并行蚁群算法。论文的主要研究工作与创新点归纳如下:1、对“离散型粒子群算法的本质”进行了探索。通过对经典的离散型粒子群算法中各部件进行拆分和分析;并在分析的基础上,对这些部件以一种全新的方式重新组合起来,构建了一种简便高效的离散粒子群算法。新算法中每个粒子的新位置仅同其当前位置、其前一个位置、其历史最优位置和其邻域内的历史最优位置有关。对于各元素仅用0和1表示的二值问题,在这些位置,这些元素要么是0,要么是1。粒子中各元素在新位置取0或者1的概率,仅同以上位置该元素取0或者1的比例相关;即各元素在新位置的取值正比例于其当前位置、其历史最优位置和其邻域内的历史最优位置的取值,而负比例于其前一个位置的取值。该算法无需涉及在离散型粒子群算法中难以解释的“速度”的概念,没有使用sigmoid函数,无需对任何变量值施加变化范围限制,仅使用基于值比例的概率,公式简洁易于理解。该探索提供了一种窥视二元离散粒子群算法的新角度,为未来进一步探索离散粒子群算法的本质提供了一个基点。在De Jong Test Suite测试集上,运行该离散粒子群算法,并与经典的离散粒子群算法进行比较。测试表明,提出的算法简便高效。另外,还在算法中引入了一个领袖粒子(Queen Informant)。该粒子使用单独的类似蚁群信息素的更新规则,并向所有其它粒子提供信息;而仅有当前全局历史最优解向其提供信息。该粒子类似量子,有两部分组成,其各元素两个值分别表示该元素取0和1的比例概率。在算法中加入领袖粒子,将其运行结果同先前的运行结果和经典算法的运行结果进行比较。实证表明,领袖粒子的引入有效地加快了算法的收敛速度,且没有增加函数的评估计算量。2、求解线性顺序问题(Linear Order Problem,LOP)的离散粒子群算法。线性顺序问题是一种NP-hard的组合优化问题,其每个解可用一个“n个数的排列”来表示。他让某矩阵的行和列同时使用这个排列顺序,使得该矩阵主对角线以上元素值的总和最大化。论文提出了一种简便的离散粒子群算法,无需交换、交叉、变异、插入、删除等算子,仅需在每个粒子中存储各元素在其排列中的位置,而不是排列本身。将这些位置看成可以左右移动的;每个粒子的速度是由其元素左右移动形成的,从而对粒子的速度有一个清晰直观的解释。并用连续型的粒子群算法更新每个元素在其排列中的位置,然后用排序的方式确定各元素在排列中的相对位置即可。将该算法同基于交换算子的粒子群算法在标准LOLIB测
