离散群体智能算法的研究与应用
|
摘要
最优化问题是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问题,其目的是从众多备选方案中选择出使目标函数达到最小或最大的方案。优化方法涉及的应用领域很广,问题种类与性质繁多,根据不同的原则可以给出不同的分类。根据决策变量的取值类型,可分为函数优化问题与组合优化问题(又称离散优化问题)。离散优化问题是一类重要的优化问题,随着计算机科学、管理科学和现代化生产技术等的日益发展,这类问题与日俱增,且其大部分都是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测试集上进行比较,表明该算法具有强大的优势。该方法适用于解元素在解排列中的绝对位置比相对位置更为重要的各种组合优化问题。
3、对置换流水车间调度问题(Permutation Flowshop Scheduling Problem.PFSP)初始解集构建方法的比较分析。群体智能算法解决优化问题的第一个步骤是创建一个初始解集。需要一定数量的初始解集的群体智能算法包括遗传算法(Genetic Algorithm,GA)、发散搜索算法(Scatter Search,SS)、粒子群优化算法(Particle Swarm Optimization,PSO),Memetic算法(Memetic Algorithm,MA),差分进化算法(Differential Evolution Algorithm,DE)等等。这些方法都已被用于求解该问题。如何创建一个高质量高多样性的初始解集以便减少求解的整体运行时间,始终是一个待解决的问题。对置换流水车间调度问题,先前的初始解比较研究仅限于创建出单个解的方法之间的解质量比较分析。论文将各种初始解集构建方法应用到Taillard提出的PFSP测试集上(共120个算例),比较它们产生的初始解集的质量,并用各种距离测度比较解集的多样性,从而为求解PFSP问题的群体智能算法的进一步改进提供了基点。一个有效的算法在很大程度上依赖于好的合适的初始解集,您可以根据这些初始解集构建方法的特性和您的算法自身的特点,选择合适的初始解集构建方法。
4、基于信息素交叉算子和排斥算子的并行蚁群算法。在并行蚁群算法中,多个蚁群同时并行存在。本算法充分利用了这个特点,提出了一种减少算法过早局部收敛的办法。它引入了两个新算子:信息素交叉算子和排斥算子。算法采用主/从模式、星形拓扑连接;主机位于中心位置。最初,多个蚁群同时被随机初始化,然后始终同时并行运行。每个子种群都是一个可以独立运行的蚁群优化系统,它们拥有属于自己的信息素矩阵和α、β、ρ等参数。当主机检测到某个蚁群已陷入局部最优解时,就利用信息素交叉算子、信息素排斥算子和多个已发现的次最优解,重新初始化这个蚁群。主、从机间仅需传送几个次最优解和几个参数,通信量极小。文中还给出了该算法的异步并行实现。该算法被用于解决TSP问题,实证表明,该算法提高了问题求解效率。
Many scientific,engineering and economic problems need the optimization of a set of decision-making variables with the aim of choosing the optimum one from many candidate schemes to minimize or maximize the objective function.The application of optimization methods is very extensive,and it involves a lot of problems and these problems have different characteristics.According to different principles,they can be divided into different classes.For example,according to the value type of the decision-making variable,they can be divided into two classes, function optimization problem and combinational optimization problem(namely, discrete optimization problem).The discrete optimization problem is an important optimization problem,and with the development of computer science,the science of the management and the technology of the modern production,it is getting more and more attention by the subjects of operational research,applied mathematics,computer science and management science.Most part of these problems being optimized is NP-hard problem.Since many years,people are trying to look for efficient algorithms to solve the combinational problem,and many efficient algorithms have been proposed,but NP problem is still a science difficulty problem in the 21century,and it is not solved in the complexity field of the theory informatics yet.
Swarm intelligent optimization method is an emerging area of research,which provides an effective tool for solving complex optimization problems,and it has attracted extensively attentions from different research areas.The comprehensive and typical methods of swarm intelligence optimization are Ant Colony Optimization (ACO) and Particle Swarm Optimization(PSO).ACO was offered in 1991 by Marco Dorigo,an Italian researcher.And James Kennedy and Russell Eberhart offered PSO based on the simulating of birds colonys' and fish colonys' preying action in 1995. These methods received recognition in international optimization computing field rapidly because the methods are simple in concept,few in parameters,and easy in implementation,especially in solving complex combinational optimization problem,it was also applied successfully in engineering design and production optimization.In this dissertation,after the essential components of discrete particle swarm are searched systematically,a simple and effective binary discrete PSO is introduced.Then it gives a modified discrete PSO for linear order problem.The next,it presents a comparison of initial population generation schemes for permutation flowshop scheduling problem with the makespan criterion.Finally,it proposes a parallel multiple ant colonies optimization which can avoid some stagnating states of the iteration in the basic ACO.
The main contributions and innovative viewpoints of this dissertation are summarized as follows:
(1) In Search of the essential binary Discrete Particle Swarm.In this part,the canonical particle swarm algorithm is broken down into its essential components,and reinterpreting them in another ways as new program.After that,these essential components are recombined in a different manner which builds a fast and easy binary discrete PSO(BPSO).In this algorithm each particle represents a candidate solution of the problem being solved in which all solution elements can only be either 0 or 1.In next position of a particle,the probability of a certain particle element assuming a value of 0 or 1 is in positive proportion to value 0 or 1 of this element in the current position of the particle,the historic best position it experienced,and the historic best position experienced of its immediate neighbors in the topological population;but in negative proportion to value 0 or 1 of this element in the former position of the particle.This algorithm doesn't involve the meaning of velocity which is usually hard to be defined in the discrete PSO.Furthermore,it only use value proportion probability,and needn't sigrnoid function and quantitative limitation on any variable. Iterative formulas are simple,reliable and easy to understand.It provides a new angle of observation point to the essential of binary discrete PSO and a solid base for future research.Experimental results show that this algorithm is faster than the Standard binary discrete PSO on a suite of test functions,and that accuracy is improved for most benchmark functions used.
A queen informant is also introduced.It informs all the other particles,but only the global best particle updates it.It has two parts and each part owns the same dimension as other particle.Each value in the queen informant represents the proportion probability of a particle element assuming a value of 0 or 1.Its updating rule is the same as that of pheromone in the ACO.It doesn't increase the number of function evaluations;however,it appears that it greatly speeds up the convergence. Simulation experiments also prove its efficiency and good performance.
(2) Discrete Particle Swarm Optimization for Linear Order Problem.The linear order problem(LOP) consists of finding a permutation of the columns(and rows) of a matrix of weights in order to maximize the sum of the weights in the triangle above the main diagonal of this matrix.It is a NP-hard problem.This paper introduces a modified discrete PSO(DPSO) for LOP.It doesn't use exchange,crossover,mutation, insertion and deletion operators.But the positions of elements in solution permutation are stored in the particle instead of elements themselves.We only change our observation point of view and conceive the velocity as the shift in the position of elements.So the particle position is updated in much the same way as the canonical continuous PSO.Then the updated solution permutation was obtained by sorting the values of the updated position of elements.Experiments on instances in LOLIB show that the modified DPSO is promising in the linear order problem.It is suitable to the optimization of the kind of permutation problems in which solution absolute positioning of the elements is more important than relative positioning of the elements.
(3) A Comparison of Initial Population Generation Schemes for Permutation Flowshop Scheduling Problem with the Makespan Criterion.Initializing a population of solutions is the first period in many swarm intelligence techniques,such as Genetic Algorithm(GA),Scatter Search(SS),Particle Swarm Optimization(PSO),Memetic Algorithm(MA),Differential Evolution Algorithm(DE),etc.These approaches are applied to solve permutation flowshop scheduling problem(PFSP).It is an open issue how to create a high-quality and diverse initial population in order to reduce the computational time of these techniques.However,previous comparative studies only involved the initial methods which produced only a single initial solution.This article compares the quality and diversity of the population which are created by different initial population constructions for minimizing makespan in PFSP on Taillard(1993)'s famous benchmarks.This paper can be seen as a starting point for future research needs of improving and developing better approaches to PFSP.You can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization implementations.And the efficiency of algorithms can be largely increased by selecting a good initial population.In a word, you can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization schemes we have analyzed.
(4) Parallel Ant Colony Algorithm using both Pheromone Crossover and Repulsive Operator based on Multi-Optimum for TSP.At the same time,many ant colonies exist in parallel ant colony optimization.Making full use of this characteristic,it proposes a new method to induce local premature convergence.It introduces two operators: pheromone crossover and repulsive operator.It employs master/slave paradigm,star topology.Master processor locates in the center,and every slavery ant colony owns its pheromone array and parameters.Above all,several slavery ant colonies are created, and then they perform iterating and updating their pheromone arrays respectively. Once a colony ant system arrives at stagnating state,the master processor reinitializes it by using both pheromone arithmetic crossover and repulsive operator based on multi-optimum.At the same time,the main parametersα,βand p of algorithm are adjusted self-adaptively.It can avoid some stagnating states of the iteration in basic ant colony optimization.The contents of communication between master processor and slave processors only are some parameters and several sub-optimum solutions,the computation to communication time ratio is relatively small.In this paper,a parallel asynchronous algorithm process is also presented.At the end of this paper,the experimental result is presented to show the effectiveness of this method for TSP.
群体智能优化方法是一个新兴的研究领域,为复杂优化问题的求解提供了一个有效手段,已引起相关领域学者的广泛关注。其中有代表性的有意大利学者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测试集上进行比较,表明该算法具有强大的优势。该方法适用于解元素在解排列中的绝对位置比相对位置更为重要的各种组合优化问题。
3、对置换流水车间调度问题(Permutation Flowshop Scheduling Problem.PFSP)初始解集构建方法的比较分析。群体智能算法解决优化问题的第一个步骤是创建一个初始解集。需要一定数量的初始解集的群体智能算法包括遗传算法(Genetic Algorithm,GA)、发散搜索算法(Scatter Search,SS)、粒子群优化算法(Particle Swarm Optimization,PSO),Memetic算法(Memetic Algorithm,MA),差分进化算法(Differential Evolution Algorithm,DE)等等。这些方法都已被用于求解该问题。如何创建一个高质量高多样性的初始解集以便减少求解的整体运行时间,始终是一个待解决的问题。对置换流水车间调度问题,先前的初始解比较研究仅限于创建出单个解的方法之间的解质量比较分析。论文将各种初始解集构建方法应用到Taillard提出的PFSP测试集上(共120个算例),比较它们产生的初始解集的质量,并用各种距离测度比较解集的多样性,从而为求解PFSP问题的群体智能算法的进一步改进提供了基点。一个有效的算法在很大程度上依赖于好的合适的初始解集,您可以根据这些初始解集构建方法的特性和您的算法自身的特点,选择合适的初始解集构建方法。
4、基于信息素交叉算子和排斥算子的并行蚁群算法。在并行蚁群算法中,多个蚁群同时并行存在。本算法充分利用了这个特点,提出了一种减少算法过早局部收敛的办法。它引入了两个新算子:信息素交叉算子和排斥算子。算法采用主/从模式、星形拓扑连接;主机位于中心位置。最初,多个蚁群同时被随机初始化,然后始终同时并行运行。每个子种群都是一个可以独立运行的蚁群优化系统,它们拥有属于自己的信息素矩阵和α、β、ρ等参数。当主机检测到某个蚁群已陷入局部最优解时,就利用信息素交叉算子、信息素排斥算子和多个已发现的次最优解,重新初始化这个蚁群。主、从机间仅需传送几个次最优解和几个参数,通信量极小。文中还给出了该算法的异步并行实现。该算法被用于解决TSP问题,实证表明,该算法提高了问题求解效率。
Many scientific,engineering and economic problems need the optimization of a set of decision-making variables with the aim of choosing the optimum one from many candidate schemes to minimize or maximize the objective function.The application of optimization methods is very extensive,and it involves a lot of problems and these problems have different characteristics.According to different principles,they can be divided into different classes.For example,according to the value type of the decision-making variable,they can be divided into two classes, function optimization problem and combinational optimization problem(namely, discrete optimization problem).The discrete optimization problem is an important optimization problem,and with the development of computer science,the science of the management and the technology of the modern production,it is getting more and more attention by the subjects of operational research,applied mathematics,computer science and management science.Most part of these problems being optimized is NP-hard problem.Since many years,people are trying to look for efficient algorithms to solve the combinational problem,and many efficient algorithms have been proposed,but NP problem is still a science difficulty problem in the 21century,and it is not solved in the complexity field of the theory informatics yet.
Swarm intelligent optimization method is an emerging area of research,which provides an effective tool for solving complex optimization problems,and it has attracted extensively attentions from different research areas.The comprehensive and typical methods of swarm intelligence optimization are Ant Colony Optimization (ACO) and Particle Swarm Optimization(PSO).ACO was offered in 1991 by Marco Dorigo,an Italian researcher.And James Kennedy and Russell Eberhart offered PSO based on the simulating of birds colonys' and fish colonys' preying action in 1995. These methods received recognition in international optimization computing field rapidly because the methods are simple in concept,few in parameters,and easy in implementation,especially in solving complex combinational optimization problem,it was also applied successfully in engineering design and production optimization.In this dissertation,after the essential components of discrete particle swarm are searched systematically,a simple and effective binary discrete PSO is introduced.Then it gives a modified discrete PSO for linear order problem.The next,it presents a comparison of initial population generation schemes for permutation flowshop scheduling problem with the makespan criterion.Finally,it proposes a parallel multiple ant colonies optimization which can avoid some stagnating states of the iteration in the basic ACO.
The main contributions and innovative viewpoints of this dissertation are summarized as follows:
(1) In Search of the essential binary Discrete Particle Swarm.In this part,the canonical particle swarm algorithm is broken down into its essential components,and reinterpreting them in another ways as new program.After that,these essential components are recombined in a different manner which builds a fast and easy binary discrete PSO(BPSO).In this algorithm each particle represents a candidate solution of the problem being solved in which all solution elements can only be either 0 or 1.In next position of a particle,the probability of a certain particle element assuming a value of 0 or 1 is in positive proportion to value 0 or 1 of this element in the current position of the particle,the historic best position it experienced,and the historic best position experienced of its immediate neighbors in the topological population;but in negative proportion to value 0 or 1 of this element in the former position of the particle.This algorithm doesn't involve the meaning of velocity which is usually hard to be defined in the discrete PSO.Furthermore,it only use value proportion probability,and needn't sigrnoid function and quantitative limitation on any variable. Iterative formulas are simple,reliable and easy to understand.It provides a new angle of observation point to the essential of binary discrete PSO and a solid base for future research.Experimental results show that this algorithm is faster than the Standard binary discrete PSO on a suite of test functions,and that accuracy is improved for most benchmark functions used.
A queen informant is also introduced.It informs all the other particles,but only the global best particle updates it.It has two parts and each part owns the same dimension as other particle.Each value in the queen informant represents the proportion probability of a particle element assuming a value of 0 or 1.Its updating rule is the same as that of pheromone in the ACO.It doesn't increase the number of function evaluations;however,it appears that it greatly speeds up the convergence. Simulation experiments also prove its efficiency and good performance.
(2) Discrete Particle Swarm Optimization for Linear Order Problem.The linear order problem(LOP) consists of finding a permutation of the columns(and rows) of a matrix of weights in order to maximize the sum of the weights in the triangle above the main diagonal of this matrix.It is a NP-hard problem.This paper introduces a modified discrete PSO(DPSO) for LOP.It doesn't use exchange,crossover,mutation, insertion and deletion operators.But the positions of elements in solution permutation are stored in the particle instead of elements themselves.We only change our observation point of view and conceive the velocity as the shift in the position of elements.So the particle position is updated in much the same way as the canonical continuous PSO.Then the updated solution permutation was obtained by sorting the values of the updated position of elements.Experiments on instances in LOLIB show that the modified DPSO is promising in the linear order problem.It is suitable to the optimization of the kind of permutation problems in which solution absolute positioning of the elements is more important than relative positioning of the elements.
(3) A Comparison of Initial Population Generation Schemes for Permutation Flowshop Scheduling Problem with the Makespan Criterion.Initializing a population of solutions is the first period in many swarm intelligence techniques,such as Genetic Algorithm(GA),Scatter Search(SS),Particle Swarm Optimization(PSO),Memetic Algorithm(MA),Differential Evolution Algorithm(DE),etc.These approaches are applied to solve permutation flowshop scheduling problem(PFSP).It is an open issue how to create a high-quality and diverse initial population in order to reduce the computational time of these techniques.However,previous comparative studies only involved the initial methods which produced only a single initial solution.This article compares the quality and diversity of the population which are created by different initial population constructions for minimizing makespan in PFSP on Taillard(1993)'s famous benchmarks.This paper can be seen as a starting point for future research needs of improving and developing better approaches to PFSP.You can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization implementations.And the efficiency of algorithms can be largely increased by selecting a good initial population.In a word, you can select a proper initialization scheme for your algorithm according to the characteristic of your algorithm and properties of these initialization schemes we have analyzed.
(4) Parallel Ant Colony Algorithm using both Pheromone Crossover and Repulsive Operator based on Multi-Optimum for TSP.At the same time,many ant colonies exist in parallel ant colony optimization.Making full use of this characteristic,it proposes a new method to induce local premature convergence.It introduces two operators: pheromone crossover and repulsive operator.It employs master/slave paradigm,star topology.Master processor locates in the center,and every slavery ant colony owns its pheromone array and parameters.Above all,several slavery ant colonies are created, and then they perform iterating and updating their pheromone arrays respectively. Once a colony ant system arrives at stagnating state,the master processor reinitializes it by using both pheromone arithmetic crossover and repulsive operator based on multi-optimum.At the same time,the main parametersα,βand p of algorithm are adjusted self-adaptively.It can avoid some stagnating states of the iteration in basic ant colony optimization.The contents of communication between master processor and slave processors only are some parameters and several sub-optimum solutions,the computation to communication time ratio is relatively small.In this paper,a parallel asynchronous algorithm process is also presented.At the end of this paper,the experimental result is presented to show the effectiveness of this method for TSP.
引文
[1]Beni G,Wang J.Swarm intelligence in cellular robotic systems[C].Proceeding of NATO Advanced Workshop on Robots and Biological System Ⅱ.Ciocco,Tuseany,Italy,1989:26-30.
[2]Beni G.From Swarm Intelligence to Swarm Robotics[A].In:Sahin E and Spears W M.Swarm Robotics[M].Berlin,Heidelbeg:Springer-Verlag,2005,1-9.
[3]Dorigo M,Maniezzo V,Colomi A.The ant system:An autocatalytic optimizing process[R].Politecnico di Milano,Italy:Technical Report No.91-016,1991.
[4]Kennedy J,Eberhart R C.Particle swarm optimization[C].Proceedings of the 1995 IEEE International Conference on Neural Networks(Perth,Australia).Piscataway,NJ,IEEE Service Center,1995:1942-1948.
[5]Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999.
[6]Kennedy J,Eberhart R C.Swarm Intelligence[M].San Francisco:Morgan Kaufmann division of Academic Press,2001
[7]Millonas M M.Swarms,phase transitions,and collective intelligence[A].Langton,C G.(Eds):Artificial Life Ⅲ[M],MA:Addison-Welsey,Reading,1994:417-45.
[8]Dorigo M,Birattari M.Swarm intelligence[EB/OL]:http://scholarpedia.org/arti cle/Swarm_Intelligence,Scholarpedia,2007:
[9]贺益君.群智能优化方法及其在化学化工中的应用研究[D].杭州:浙江大学,2008.
[10]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C].Proceedings of the 1st European Conference on Artificial Life,1991:134-142.
[11]Gambardella L M,Dorigo M.Ant-Q:A reinforcement learning approach to the traveling salesman problem[C].Proeeedings of the 12th International Conference on Machine Learning,1995:252-260.
[12]Dorigo M,Maniezzo V,Colomi A.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.
[13]Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[14]Bonabeau E,Dorigo M.Inspiration for optimization from social insect behavior[J].Nature,2000,406(6):39-42.
[15]Michael J B K,Jean-Bernard B,Laurent K.Ant-like task and recruitment in cooperative robots[J].Nature,2000,406(31):992-995.
[16]Jackson D E,Holcombe M,Ratnieks F L W.Trail geometry gives polarity to ant foraging networks[J].Nature,2004,432(7019):907-909.
[17]Dorigo M,St(u|¨)zle T.Ant colony optimization[M].Cambridge,MA:MIT Press,2004.
[18]刘彦鹏.蚁群优化算法的理论研究及其应用[D].杭州:浙江大学,2007.
[19]St(u|¨)zle T,Hoos H H.MAX-MIN ant system and Local search for the traveling salesman problem[C].Proceedings of the 1997 IEEE International Conference on Evolutionary Computation,Indianapolis,Indiana,Piscataway,NJ,IEEE Service Center,1997:309-314
[20]St(u|¨)zle T,Hoos H H.MAX-MIN ant system and local search for combinatorial optimization problems[A].In:Voss S,Martello S,Osman I,et al.Eds.Meta-Heuristies:Advanees and trends in local search paradigms for optimization[M].Dordrecht:Kluwer Academic Publishers,1999:137-154.
[21]St(u|¨)zle T,Hoos H H.MAX-MIN ant systems[J].Future Generation Computer Systems,2000,16(8):889-914.
[22]Blum C,Roli A,Dorigo M.HC-ACO:The hyper-cube framework for ant colony optimization[C].Proceedings of MIC'2001 -Metaheuristics International Conference,2001,2:399-403.
[23]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man and Cybernetics-part B,1996,26(1):29-41.
[24]Bullnheimer B,Hartl R F,Strauss C.A new rank-based version of ant system:a computational study[J].Central European Journal for operations Research and Economics,1999,7(1):25-38.
[25]Bullnheimer B,Kotsis G.,Strauss C.Parallelization strategies for the ant system[A].In:Leone R D,Murli A,Pardalos P,Toraldo G.(Eds.) High Performance and Algorithms and Software in Nonlinear Optimization,No.24 in Kluwer Series of Applied Optmization[M],Dordrecht,Netherlands:Kluwer Academic Publishers,1998:87-100
[26]Middendorf M,Reischle F,Schmeck F.Information exchange in multi colony ant algorithms[C].Proceedings of International Parallel and Distributed Processing Symposium(Jos(?) D,Rolim P,ed.),Springer,2000:645-652.
[27]Shu-Chuan Chu,John F.Roddick,Jeng-Shyang Pan.ant colony system with communication strategies[J].Information Science,2004,167:63-76.
[28]Talbi E-G,Roux O,Fonlupt C,Robilard D.Parallel ant colonies for the quadratic assignment problem[J].Future Generation Computer Systems,2001,17:441-449.
[29]Piriyakumar D,Levi P.A new approach to exploiting parallelism in ant colony algorithm[C].Proceedings of International Symposium onMicromechatronics and Human Science(Stone P,ed.),2002:237-243.
[30]Cheng-Fa Tsai,Chun-Wei Tsai,Ching-Chang Tseng.A new hybrid heuristic approach for solving large traveling salesman problem[J].Information Science,2004,166(1-4):67-81
[31]Kawamura H,Yamamoto M,Suzuki K,Ohuchi A.Multiple ant colonies algorithm based on colony level interactions[J].IEICE Transactions on Fundamentals of Electronics,Communications,and Computer Sciences,2000,E83-A(2):371-379.
[32]Kawamura H,Yamamoto M,Ohuchi A.Improved multiple ant colonies systems for traveling salesman problems[A].Kozan E,Ohuchi A:Operation research/management science at work[M].Boston,MA:Kluwer Academic Publishers,2002:43:41-52.
[33]萧蕴诗,李炳宇,吴启迪.求解TSP问题的模式学习并行蚁群算法[J].控制与决策,2004,19(8):882-888.
[34]Randall M,Lewis A.A parallel implementation of ant colony algorithm[J].Parallel and Distributed Computing,2002,62:1421-1432.
[35]Merkle D,Middendorf M.Fast ant colony optimization on runtime reconfigurable processor arrays[J].Genetic Programming and Evolvable Machine,2002,3(4):345-361.
[36]Blum C,Dorigo M.The Hyper-Cube framework for ant colony algorithm[J].IEEE Transactions on SMC,2004,34(2):1161-1172.
[37]Alba E,Leguizamon G,Ordonez G.Analyzing the behavior of parallel ant colony systems for large instances of the task scheduling problem[C].20th IEEE International Parallel and Distributed Processing Symposium,2005:14-23.
[38]Craus M,Rudeanu L.Parallel framework for ant-like algorithms[C].Third International Symposium on Algorithms,Models and Tools for Parallel Computing on Heterogeneous Networks,2004:36-41
[39]Chu D,Till M,Zomaya A.Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model[A].In:Nedjah N,Alba E.Parallel Evolutionary Computations.Berlin,Heidelberg:Springer,2006:177-198.
[40]Islam M T,Thulasiraman P,Thulasiram R K.A parallel ant colony optimization algorithm for all-pair routing in MANETs[J].Proceedings of the International Parallel and Distributed Processing Symposium,2003:259-266.
[41]章春芳.自适应的并行蚁群算法及其应用[D].扬州:扬州大学,2006:.
[42]黄席樾,张著洪,何传江,胡小兵,马笑潇.现代智能算法理论及应用[M].北京:科学出版社,2005.
[43]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[44]Stiizle T.Parallelization strategies for ant colony optimization[C].Proceedings of PPSN-Ⅴ,Fifth International Conference on Parallel Problem Solving from Nature (Eiben A E,B(a|¨)ck T,Schoenauer M,Schwefel H P,Eds.),Lecture Notes in Computer Science,Berlin,Springer-Verlag,1998,1498:722-731.
[45]Middendorf M,Reischle F,Schmeck H.Multi colony ant algorithms[J].Journal of Heuristics,2002,8(3):305-320.
[46]Eberhart R C,Kennedy J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan,1995:39-43.
[47]van den Bergh F,Engelbrecht AP.Using Neighborhoods with the Guaranteed Convergence PSO[C].Proceedings of the IEEE Swarm Intelligence Symposium,2003:235-242.
[48]Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part Ⅰ:background and development[J].Natural Computing,2007,6(4):467-484.
[49]Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part Ⅱ:hybridisation,combinatorial,multicriteria and constrained optimization,and indicative applications[J].Natural Computing,2008,7(1):109-124.
[50]Wei Pang,Kang-ping Wang,Chun-guang Zhou,Long-jiang Dong,Ming Liu,Hong-yan Zhang,Jian-yu Wang.Modified Particle Swarm Optimization Based On Space Transformation for Solving Traveling Salesman Problem[C].Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,2004:2342-2346.
[51]Tasgetiren M F,Liang Y C,Sevkli M.Gencyilmaz G.Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem[C].4th International Workshop on Ant Colony Optimization and Swarm Intelligence,ANTS2004,LNCS 3172 by Springer-Verlag,2004:382-390.
[52]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G Particle swarm optimization algorithm for single machine total weighted tardiness problem[C].Proceedings of the 2004 Congress on Evolutionary Computation (CEC'04),Portland,Oregon,2004:1412-1419.
[53]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem[C].Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems (IMS2004),Sakarya,Turkey,2004:431-441.
[54]Cagnina L,Esquivel S,Gallard R.Particle swarm optimization for sequencing problems:a case study[A].Proceedings of the 2004 Congress on Evolutionary Computation[C].Portland:Institute of Electrical and Electronics Engineers Inc,2004,536-541.
[55]Mohemmed A W,Sahoo N C.Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics[A].Discrete Dynamics in Nature and Society[M].New York,USA:Hindawi Publishing Corporation,Volume 2007,Article ID 27383,2007.
[56]Clerc M.Discrete Particle Swarm Optimization:A Fuzzy Combinatorial Bla ck Box[EB/OL]:http://clerc.maurice.free.fr/PSO/Fuzzy_Discrete_PSO/Fuzzy_D PSO.htm,2009:.
[57]Wei Pang,Kang-ping Wang,Chun-guang Zhou,Long-jiang Dong.Fuzzy Discrete Particle Swarm Optimization for Solving Traveling Salesman Problem[C].Proceedings of the 4th International Conference on Computer and Information Technology (CIT04),IEEE Computer Society,2004.
[58]Laskari E C,Parsopoulos K E,Vrahatis M N.Particle swarm optimization for integer programming[C].Proc.of the IEEE Congress on Evolutional Computation(CEC2002),Honolulu,USA,2002:1582-1587.
[59]Saiman A,Ahmad I,Al-Madani S.Particle swarm optimizationfor task assignment Problem[J].Microprocessors and Microsystems,2002,26:363-371.
[60]Kennedy J,Eberhart R.A Discrete Binary Version of the Particle Swarm Algorithm[C].IEEE Conference on Systems,Man,and Cybernetics,Orlando,FA,1997:4104-4109.
[61]Tasgetiren M F,Yun-Chia Liang.A Binary Particle Swaarm Optimization Algorithm for Lot Sizing Problem[J].Journal of Economic and Social Research.2003,5(2):1-20.
[62]Coello C,Luna E.Use of Particle Swarm Optimization to Design Combinational Logic Circuits[C].5~(th) International Conference,ICES2003,Springer,Lecture Notes in Computer Science,VOL 2606,Trondheim,Northway,2003:398-409.
[63]HUANG Yan-Xin,ZHOU Chun-Guang,ZOU Shu-Xue,Wang Yan.A Hybrid Algorithm on Class Cover Problems[J].Journal of Software,2005,16(4):513-522.
[64]Liao C J,Tseng C T,Luarn,P.A discrete version of particle swarm optimization for flowshop scheduling problems[J].Computer& Operations Research,2007,34:3099-3111.
[65]Mnarice Clerc.Discrete Particle Swarm Optimization,by the Traveling Salesman Problem[EB/OL]:http://www.mauriceclere.net,2009:.
[66]Schoofs L,Naudts B.Swarm intelligence on the binary constraint satisfaction problem[C].Proc.of the IEEE Congress on Evolution Computation(CEC 2002),Honolulu,Hawaii,USA,2002:1444-1449.
[67]Rameshkumar K,Suresh R K,Mohanasundaram K M.Discrete Particle Swarm Optimization(DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Manspan[C].Proc.ICNC 2005,LNCS3612,2005:572-581.
[68]Wang Kang-ping,Huang Lan,Zhou Chun-guang et al.Particle Swarm optimization for traveling salesman problem[C].IEEE Service Center,Proceedings of the Second International Conference on Machine Learning and Cybernetics,Xi'an,IEEE Press,2003,5:1583-1585.
[69]葛宏伟,梁艳春,周春新.一种新的基于改进粒子群算法的Job-Shop调度方法[C].2004年全国博士生学术论坛论文集,2004,9:1-7
[70]Shi X H,Xing X L,Wang Q X,Zhang L H,Yang X W,Zhou C G,Liang Y C.A discrete PSO method for generalized TSP problem[C].Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,2004:378-2383.
[71]Weijun Xia,Zhiming Wu.An effective hybrid optimization approach for multi-objective flexible job-scheduling problems[J].Computers & Industrial Engineenng 2005,48:409-425.
[72]Chen Ai-ling,Yang Gen-ke,Wu zhi-ming.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem[J].Journal of Zhejiang University SCIENCE A,2006:7(4),607-614.
[73]Hu X,Eberhart R C,Shi Y.Swarm Intelligence for permutation optimization:a case study on n-queens problem[C].Proceeding of the IEEE Swarm Intelligence Symposium 2003(SIS 2003),Indianapolis,Indiana,USA,2003:243-246.
[74]Pan Q K,Tasgetiren M F,Liang Y C.A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem with makespan criterion[C].Proceedings of the International Workshop on UK Planning and Scheduling Special Interest Group,UK PLANSIG2005,City University,London,2005:34-43
[75]潘全科,王文宏,潘群,朱剑英.解决Job Shop问题的粒子群优化算法[J].机械科学与技术,2006,25(6):675-679.
[76]Cuiru Wang,Jiangwei Zhang,Jing Yang,Chaoju Hu,Jun Liu.A Modified Particle Swarm Optimization Algorithm and its Application for Solving Traveling Salesman Problem[C].International Conference on Neural Networks and Brain,2005:689-694.
[77]王翠茹,张江维,王玥,衡军山.改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005,32(6):47-51.
[78]杨轻云.约束满足问题与调度问题中离散粒子群算法研究[D].吉林:吉林大学,2006.
[79]钟一文.智能优化方法及其应用研究[D].杭州:浙江大学,2005.
[80]熊磊.粒子群算法在离散优化问题中的研究[D].桂林:广西师范大学,2006
[81]CLERE M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]Proc.of the Congress on Evolutionary Computation,Piscataway,1999:1951-1957.
[82]Benioff P.The Computer as a physical system:a microscopic quantum mechanical Hamiltonian model of computers as represented by turing machines[J].Journal of Statistical Physics,1980,22:563-591.
[83]Feynman R.Simulating physics with computers[J].International Journal of Theoretical Physics,1982,21(6):467-488.
[84]De Jong K A.An analysis of the behaviour of a class of genetic adaptive systems[D].Michigan:Ph.D.Thesis,University of Michigan,1975:.
[85]Spears W.De Jong Test Functions From William M.Spears[EB/OL]:http://www.c s.uwyo.edu/-wspears/functs.dejong.html,2007:
[86]Marsaglia G,Zaman A.The KISS generator[R].Florida,USA:Department of Statistics,Florida State University,Tallahassee,1993
[87]Reinelt G.The Linear Ordering Problem:Algorithms and Applications.Research and Exposition in Mathematics(vol.8)[M].Berlin:Heldermann Verlag,1985.
[88]Chiarini B H.New Algorithm for the Triangulation of Input-Output Tables and the Linear Ordering Problem[D].The Graduate School of the University of Florida,2004
[89]Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].New York,NY,USA:W.H.Freeman & Co.,1979:.
[90]Reinelt G..LOLIB[EB/OL].http://www.iwr.uni-heidelberg.de/groups/comopt/so ftware/LOLIB/index.html;1997:.
[91]Ronald,S.(1998).More distance functions for order-based encodings[M].Proceedings of the IEEE Conference on Evolutionary Computation,IEEE Press,New York,1998:558-563.
[92]Laguna M,Marti R.Scatter Search:Methodology and Implementation in C[M].Boston:Kluwer Academic Publishers,2003.
[93]Resendee M G C,Ribeiro C C.Greedy Randomized Adaptive Search Procedures:Advances and Applications[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[94]Festa P,Resende M G C.An annotated bibliography of GRASP,Part Ⅰ:Algorithms[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[95]Festa P,Resende M G C.An annotated bibliography of GRASP,Part Ⅱ:Applications[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[96]吴启迪,汪镭.智能微粒群算法研究及应用[M].江苏:江苏教育出版社社,2005.
[97]Johnson S M.Optimal two-and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1:61-68.
[98]Baker K R.Introduction to Sequencing and Scheduling[M].New York:Wiley,1974:.
[99]Garey M R,Johnson D S,Sethi R.The Complexity of Flowshop and Jobshop Scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[100]周国华.生产作业调度问题的软计算方法研究[D].成都:西南交通大学,2003.
[101]甘应爱,田丰.运筹学[M].北京:清华大学出版社,1990:.
[102]Wagner D B.Dynamic Programming[J].The Mathematical Journal,1995,5(4):42-51.
[103]Bellman R.On the Theory of Dynamic Programming[C].Proceedings of the National Academy of Sciences,1952:716-719.
[104]Blazewicz J.et al.Scheduling Computer and Manufacturing Process[M].2~(nd)Printing.Berlin,Heidelberg:Springer,2001:.
[105]Held M,Karp R M.A Dynamic Programming Approach to Sequencing Problems[J].Journal of the Society for Industrial and Applied Mathematics,1962,10(1):196-210.123
[106]Reza Hejazi S,Saghafian S.Flowshop-Scheduling Problems with Makespan Criterion:A Review[J].International Journal of Production Research,2005,43(14):2895-2929.
[107]Doig A,Land A H.An Automatic Method for Solving Discrete Programming Problems[J].Econometrica,1960,28:497-520.
[108]Dakin R J.A Tree-Search Algorithm for Mixed Integer Programming Problems[J].The Computer Journal,1965,8(3):250.
[109]陈庆华,谢政.整数规划[M].长沙:国防科技大学出版社,1992:.
[110]Lageweg B J,Lenstra J K,Kan A.A General Bounding Scheme for the Permutation Flow-Shop Problem[J].Operations Research,1978,26(1):53-67.
[111]Carlier J,Rebai I.Two Branch and Bound Algorithms for the Permutation Flowshop Problem[J].European Journal of Operational Research,1996,90:238-251.
[112]Haouari M,Ladhari T.A Branch-and-Bound-Based Local Search Method for the Flow Shop Problem[J].Journal of the Operational Research Society,2003,54(10):1076-1084.
[113]Ladhari T,Haouari M.A Computational Study of the Permutation Flow Shop Problem Based on a Tight Lower Bound[J].Computers and OperationsResearch,2005,32(7):1831-1847.
[114]Fisher M L.The Lagrangian Relaxation Method for Solving Integer Programming Problems[J].Management Science,1981,27(1):1-18.
[115]Fisher M L.An Applications Oriented Guide to Lagrangian Relaxation[J].Interfaces,1985,15(2):10-21.
[116]Liu G,Luh P B,Resch R.Scheduling Permutation Flow Shops Using theLagrangian Relaxation Technique[J].Annals of Operations Research,1997,70:171-189.
[117]Palmer D S.Sequencing jobs through a multi-stage process in the minimum total time:a quick method of obtaining a near optimum[J].Operational Research Quarterly,1965,16(1):101-107.
[118]Gupta J.A Functional Heuristic Algorithm for the Flowshop Scheduling Problem[J].Operational Research Quarterly,1971,22:39-47.
[119]Campbell H G,Dudek R A,Smith M L.A Heuristic Algorithm for the n-Job, m-Machine Scheduling Problem[J].Management Science,1970,16:630-637.
[120]Dannenbring D G An Evaluation of Flow Shop Sequencing Heuristics[J].Management Science,1977,23(11):1174-1182.
[121]Nawaz M,Enscore E,Ham I.A Heuristic Algorithm for the m-Machine,n-Job Flowshop[J].OMEGA:The International Journal of Management Sciences,1983,11(1):91-95.
[122]Taillard E.Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1990,47(1):65-74.
[123]Turner S,Booth D.Comparison of Heuristics for Flow Shop Sequencing[J].OMEGA:The International Journal of Management Sciences,1987,15(1):75-78.
[124]Ruiz R,Maroto C.A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics [J].European Journal of Operational Research,2005,165:479-494.
[125]Kalczynski P J,Kamburowski J.On the NEH Heuristic for Minimizing theMakespan in Permutation Flowshops[J].OMEGA:The International Journal ofManagement Sciences,2007,35:53-60.
[126]Ho J C,Chang Y L.A New Heuristic for the n-Job,m-Machine Flow-Shop Problem[J].European Journal of Operational Research,1991,52(2):194-202.
[127]Suliman S M A.A Two-Phase Heuristic Approach to the Permutation Flow-Shop Scheduling Problem[J].International Journal of Production Economics,2000,64(1):143-152.
[128]Kirkpatrick S,Gelatt Jr C D,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[129]Laarhoven P J M,Aarts E H L.Simulated Annealing:Theory and Applications[M].MA,USA:Kluwer Academic Publishers Norwell,1987:.
[130]Koulamas C,Antony S R,Jaen R.A Survey of Simulated Annealing Applications to Operations Research Problems[J].Omega(Oxford),1994,22(1):41-56.
[131]Osman I H,Potts C N.Simulated Annealing for Permutation Flow-Shop Scheduling[J].Omega(Oxford),1989,17(6):551-557.
[132]Ogbu F A,Smith D K.The Application of the Simulated Annealing Algorithm tothe Solution of the mlmlCmax Flowshop Problem[J].Computers andOperations Research,1990,17(3):243-253.
[133]Ogbu F,Smith D.Simulated Annealing for the Permutation Flowshop Problem[J].Omega,The International Journal of Management Science,1990,19(1):64-67.
[134]Ishibuchi H,Misaki S,Tanaka H.Modified Simulated Annealing Algorithms for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1995,81:388-398.
[135]Zegordi S H,Itoh K,Enkawa T.Minimizing Makespan for Flow Shop Scheduling by Combining Simulated Annealing with Sequencing Knowledge[J].European Journal of Operational Research,1995,85(3):515-531.
[136]Wodecki M,Bozejko W.Solving the Flow Shop Problem by Parallel Simulated Annealing[C].Lecture Notes in Computer Science,2001:236-247.
[137]Glover F.Further Paths for Integer Programming and Links to Artificial Intelligence [J].Computer and Operations Research,1986,13:533-549.
[138]Hansen P.The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming[C].Congress on Numerical Methods in Combinatorial Optimization.Capri,Italy,1986:70-145.
[139]Glover F.Tabu Search:Part Ⅰ[J].ORSA Journal on Computing,1989,1(3):190-206.
[140]Glover F.Tabu Search:Part Ⅱ[J].ORSA Journal on Computing,1990,2(1):4-32.
[141]Glover F,Taillard E.A User's Guide to Tabu Search[J].Annals of Operations Research,1993,41(1):l-28.
[142]Glover F W,Laguna M.Tabu Search[M].Berlin,Heidelberg:Springer,1997:.
[143]Widmer M,Hertz A.A New Heuristic Method for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1989,41(2):186-193.
[144]Reeves C R.Improving the Efficiency of Tabu Search for Machine Scheduling Problems[J].Journal of Operational Research Society,1993,44(4):375-382.
[145]Moccellin J V.A New Heuristic Method for the Permutation Flow Shop Scheduling Problem[J].The Journal of the Operational Research Society,1995,46(7):883-886.
[146]Nowicki E,Smutnicki C.A Fast Tabu Search Algorithm for the PermutationFlow-Shop Problem[J].European Journal of Operational Research,1996,91:160-175.
[147]Taillard E.Benchmarks for basic scheduling problems[J].European Journal of Operational Research,1993,64:278-285.
[148]Ben-Daya M,Al-Fawzan M.A Tabu Search Approach for the Flow ShopScheduling Problem[J].European Journal of Operational Research,1998,109(1):88-95.
[149]Solimanpur M,Vrat P,Shankar R.A Neuro-Tabu Search Heuristic for the FlowShop Scheduling Problem[J].Computers and Operations Research,2004,31(13):2151-2164.
[150]Grabowski J,Wodecki M.A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion[J].Computers and Operations Research,2004,31(11):1891-1909.
[151]Holland J H.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan press,1975:.
[152]Jog P,Suh J Y,van Gucht D.The Effects of Population Size,Heuristic Crossoverand Local Improvement on a Genetic Algorithm for the Traveling SalesmanProblem[C].Proceedings of the third international conference on Geneticalgorithms table of contents,1989:110-115.
[153]Ishibuchi H et al.Genetic Algorithms and Neighborhood Search Algorithmsfor Fuzzy Flowshop Scheduling Problems[J].Fuzzy Sets and Systems,1994,67(1):81-100.
[154]Chen C L,Vempati V S,Aljaber N.An Application of Genetic Algorithms for Flow Shop Problems[J].European Journal of Operational Research,1995,80:389-396.
[155]Reeves C R.A Genetic Algorithm for Flowshop Sequencing[J].Computers Operations Research,1995,22(1):5-13.
[156]Murata T,Ishibuchi H,Tanaka H.Genetic Algorithms for Flowshop Scheduling Problems[J].Computers and Industrial Engineering,1996,30(4):1061-1071.
[157]Reeves C R,Yamada T.Genetic Algorithms,Path Relinking and the Flowshop Sequencing Problem[J].Evolutionary Computation journal,1998,6(1):230-234.
[158]Ponnambalam S G.Constructive and Improvement Flow Shop Scheduling Heuristics:An Extensive Evaluation[J].Production Planning & Control,2001,12(4):335-344.
[159]Wang L,Zheng D Z.An Effective Hybrid Heuristic for Flow Shop Scheduling[J].International Journal of Advanced Manufacturing Technology,2003,21(1):38-44.
[160]Ruiz R,Maroto C,Alcaraz J.New Genetic Algorithms for the Permutation Flowshop Scheduling Problem[C].Proceedings of the Fifth Metaheuristic International Conference,Kyoto,2003:63-1.
[161]Ruiz R,Maroto C,Alcaraz J.Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem[J].OMEGA,the International Journal ofManagement Science,2006,34:461-476.
[162]Stutzle T.An Ant Approach to the Flow Shop Problem[C].Proceedings of European Congress on Intelligent Techniques and Soft Computing.Aachen,Germany,1998:1560-1564.
[163]Ying K-C,Liao C-J.An Ant Colony System for Permutation Flow-Shop Sequencing[J].Computers and Operations Research,2004,31(5):791-801.
[164]Ying K-C,Liao C-J.An Ant Colony System for Permutation Flow-Shop Sequencing[J].Computers and Operations Research,2004,31(5):791-801.
[165]Merkle D,Middendorf M.An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems[C].Proceedings of EvoWorkshops,2000:287-296.
[166]Tasgetiren M F,et al.Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem[C].Fourth International Workshop on Ant Algorithms and Swarm Intelligence,ANTS2004,2004:382-389.
[167]Rameshkumar K,Suresh R K,Mohanasundaram K M.Discrete Particle Swarm Optimization(DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[C].Lecture Notes in Computer Science,2005:572-581.
[168]Lian Z,Gu X,Jiao B.A Similar Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[J].Applied mathematics and computation,2006,175(1):773-785.
[169]Liu B,Wang L,Jin Y H.An Effective PSO-Based Memetic Algorithm for FlowShop Scheduling[J].Systems,Man and Cybernetics,Part B,IEEE Transactionson,2007,37(1):18-27.
[170]Liao C J,Tseng C T,Luarn P.A Discrete Version of Particle SwarmOptimization for Flowshop Scheduling Problems[J].Computers and Operations Research,2007,34(10):3099-3111.
[171]Pan Q K,Tasgetiren M F,Liang Y C.A Discrete Particle Swarm Optimization Algorithm for the Permutation Flowshop Sequencing Problem with Makespan Criterion[J].European Journal of Operational Research,Computers & Industrial Engineering,2008,55(4):795-816.
[172]Werner F.On the Heuristic Solution of the Permutation Flow Shop Problem by Path Algorithms [J].Computers and Operations Research,1993,20(7):707-722.
[173]Stutzle T.Applying Iterated Local Search to the Permutation Flow Shop Problem[R].TU Darmstadt:Technical Reprot AIDA-98-04,FG Intellektik,1998.
[174]Moscato P.On Evolution,Search,Optimization,Genetic Algorithms and Martial Arts:Towards Memetic Algorithms[R].Pasadena,CA,USA:Caltech Concurrent Computation Program,C3P Report 826,1989.
[175]Ravetti M G,Nakamura F G,Meneses C N,Resende M G C,Mateus G R,Pardalos P M.Hybrid heuristics for the permutation flow shop problem[R].Technical Report(TD-6V9MEV).Florham Park,NJ:AT&T Labs Research,Florham Park,NJ 07932,2006.
[176]Tavakkoli-Moghaddam R,Gholipour-Kanani Y,Cheraghalizadeh R.A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems[J].International Journal of Management Science and Engineering Management,2008,3(2):119-130.
[177]Glover F.A Template for Scatter Search and Path Relinking[C].Third European Conference on Artificial Evolution,1997:3-54.
[178]Nowicki E,Smutnicki C.Some aspects of scatter search in the flow shop problem[J].European Journal of Operational Research,2006,169(2):654-666.
[179]Bozejko W,Wodecki M.Parallel scatter search algorithm for the flow shop sequencing problem[C].Lecture Notes in Computer Science,2008,4967:180-188
[180]Storn R,Price K.Differential evolution-A simple and efficient adaptive scheme for globaloptimization over continuous spaces[R].Berkeley:University of California,1995.
[181]Storn R,Price K.Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous space[J].Journal of Global Optimization,1997,11:341-359.
[182]Lampinen J.A bibliography of differential evolution algorithm[EB/OL].http://www.lut.fi/～jlampine/debiblio.htm,2002.
[183]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G.Differential Evolution Algorithm for Permutation Flowshop Sequencing Problem with Makespan Criterion[C].Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems(IMS2004),2004:442-452.
[184]Moccellin J a V,dos Santos M O.An Adaptive Hybrid Meta-Heuristic for Permutation Flowshop Scheduling[J].Journal of the Operational Research Society,2000,46:883-886.
[185]Kai S,Genke Y.An Effective Hybrid Optimization Algorithm for the Flow Shop Scheduling Problem[C].Information Acquisition,2006 IEEE International Conference,2006:1234-1238.
[186]Framinan J M,Leisten R,Rajendran C.Different initial sequences for the heuristic of Nawaz,Enscore and Ham to minimize makespan,idletime or flowtime in the static permutation flowshop sequencing problem[J].International Journal of Production Research,2003,41(1):121-148.
[187]Framinan J M,Gupta J N D,Leisten R.A Review and Classification of Heuristics for Permutation Flow-Shop Scheduling with Makespan Objective[J].Journal of the Operational Research Society,2004,55(12):1243-1255.
[188]Duda J.A critical review of the newest biologically-inspired algorithms for flowshop scheduling problem[J].Task Quarterly,2007,11(1-2):7-19.
[189]Prabhaharan G.,Khan B S,Rakesh L.Implementation of grasp in flow shop scheduling[J].International Journal of Advanced Manufacturing Technology,2006,30(11-12):1126-1131.
[190]Jarboui B,Ibrahim S,Siarry P,Rebai A.A combinatorial particle swarm optimization for solving permutation flowshop problems[J].Computers &Industrial Engineering,2008,54(3):526-538.
[191]Zobolas G I,Tarantilis C D,Ioannou G.Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm[J].Computers & Operations Research,2009,36(4):1249-1267.
[192]Campos V,Laguna M,Mart(?) R.Context-independent scatter search and tabu search for permutation problems[J].INFORMS Journal on Computing,2005,17:111-122.
[193]Levenshtein V I.Binary codes capable of correcting deletions,insertions,and reversals[J].Soviet Physics-Doklady,1966,10:707-710.
[194]Taillard E.Scheduling instances[EB/OL]http://mistic.heig-vd.ch/taillard/pr oblemes.dir/ordonnancement.dir/ordonnancement.html.
[195]覃钢力,杨家本.自适应调整信息素的蚁群算法[J].系统仿真学报,2002,14(1):31-33.
[196]Botee H M,Bonabeau E.Evoluting ant colony optimization[J].Complex Systems,1998,1(2):149-159.
[197]郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践,2002,25(9):88-91,136.
[198]李万庆,李彦苍.求解复杂优化问题的基于信息熵的自适应蚁群算法[J].数学的实践与认识,2005,35(2):134-139.
[199]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[200]Dorigo M,Luca M.The Ant-Q:algorithm applied to the nuclear reload problem.Annals of Nulear Energy,2002,29(12):1455-1470.
[201]Koh B,George A,Haftka R,Fregly B.Parallel Asynchronous Particle Swarm Optimization,International Journal for Numerical Methods in Engineering,2006,67(4):578-595.
[202]St(u|¨)tzle T.ACOTSP.V1.0.tar.gz[EB/OL]http://iridia.ulb.ac.be/-mdorigo/ACO/aco-code/public-software.html,2004.
[203]Reinelt G TSPLIB95[EB/OL].http://www.iwr.uni-heidelberg.de/groups/como pt/software/TSPLIB95/index.html,2007.
[206]高祥.启发式求解大规模流水调度问题[D].哈尔滨:哈尔滨理工大学,2006
[207]高守玮.一类Flow shop生产调度问题及其优化方法之分析与研究[D].上海:上海交通大学,2007.
[208]Wolpert D H,Macready W G.No Free Lunch Theorems for Optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67.
[2]Beni G.From Swarm Intelligence to Swarm Robotics[A].In:Sahin E and Spears W M.Swarm Robotics[M].Berlin,Heidelbeg:Springer-Verlag,2005,1-9.
[3]Dorigo M,Maniezzo V,Colomi A.The ant system:An autocatalytic optimizing process[R].Politecnico di Milano,Italy:Technical Report No.91-016,1991.
[4]Kennedy J,Eberhart R C.Particle swarm optimization[C].Proceedings of the 1995 IEEE International Conference on Neural Networks(Perth,Australia).Piscataway,NJ,IEEE Service Center,1995:1942-1948.
[5]Bonabeau E,Dorigo M,Theraulaz G.Swarm Intelligence:From Natural to Artificial Systems[M].New York:Oxford University Press,1999.
[6]Kennedy J,Eberhart R C.Swarm Intelligence[M].San Francisco:Morgan Kaufmann division of Academic Press,2001
[7]Millonas M M.Swarms,phase transitions,and collective intelligence[A].Langton,C G.(Eds):Artificial Life Ⅲ[M],MA:Addison-Welsey,Reading,1994:417-45.
[8]Dorigo M,Birattari M.Swarm intelligence[EB/OL]:http://scholarpedia.org/arti cle/Swarm_Intelligence,Scholarpedia,2007:
[9]贺益君.群智能优化方法及其在化学化工中的应用研究[D].杭州:浙江大学,2008.
[10]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C].Proceedings of the 1st European Conference on Artificial Life,1991:134-142.
[11]Gambardella L M,Dorigo M.Ant-Q:A reinforcement learning approach to the traveling salesman problem[C].Proeeedings of the 12th International Conference on Machine Learning,1995:252-260.
[12]Dorigo M,Maniezzo V,Colomi A.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41.
[13]Dorigo M,Gambardella L M.Ant Colony System:A Cooperative Learning Approach to the Traveling Salesman Problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
[14]Bonabeau E,Dorigo M.Inspiration for optimization from social insect behavior[J].Nature,2000,406(6):39-42.
[15]Michael J B K,Jean-Bernard B,Laurent K.Ant-like task and recruitment in cooperative robots[J].Nature,2000,406(31):992-995.
[16]Jackson D E,Holcombe M,Ratnieks F L W.Trail geometry gives polarity to ant foraging networks[J].Nature,2004,432(7019):907-909.
[17]Dorigo M,St(u|¨)zle T.Ant colony optimization[M].Cambridge,MA:MIT Press,2004.
[18]刘彦鹏.蚁群优化算法的理论研究及其应用[D].杭州:浙江大学,2007.
[19]St(u|¨)zle T,Hoos H H.MAX-MIN ant system and Local search for the traveling salesman problem[C].Proceedings of the 1997 IEEE International Conference on Evolutionary Computation,Indianapolis,Indiana,Piscataway,NJ,IEEE Service Center,1997:309-314
[20]St(u|¨)zle T,Hoos H H.MAX-MIN ant system and local search for combinatorial optimization problems[A].In:Voss S,Martello S,Osman I,et al.Eds.Meta-Heuristies:Advanees and trends in local search paradigms for optimization[M].Dordrecht:Kluwer Academic Publishers,1999:137-154.
[21]St(u|¨)zle T,Hoos H H.MAX-MIN ant systems[J].Future Generation Computer Systems,2000,16(8):889-914.
[22]Blum C,Roli A,Dorigo M.HC-ACO:The hyper-cube framework for ant colony optimization[C].Proceedings of MIC'2001 -Metaheuristics International Conference,2001,2:399-403.
[23]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man and Cybernetics-part B,1996,26(1):29-41.
[24]Bullnheimer B,Hartl R F,Strauss C.A new rank-based version of ant system:a computational study[J].Central European Journal for operations Research and Economics,1999,7(1):25-38.
[25]Bullnheimer B,Kotsis G.,Strauss C.Parallelization strategies for the ant system[A].In:Leone R D,Murli A,Pardalos P,Toraldo G.(Eds.) High Performance and Algorithms and Software in Nonlinear Optimization,No.24 in Kluwer Series of Applied Optmization[M],Dordrecht,Netherlands:Kluwer Academic Publishers,1998:87-100
[26]Middendorf M,Reischle F,Schmeck F.Information exchange in multi colony ant algorithms[C].Proceedings of International Parallel and Distributed Processing Symposium(Jos(?) D,Rolim P,ed.),Springer,2000:645-652.
[27]Shu-Chuan Chu,John F.Roddick,Jeng-Shyang Pan.ant colony system with communication strategies[J].Information Science,2004,167:63-76.
[28]Talbi E-G,Roux O,Fonlupt C,Robilard D.Parallel ant colonies for the quadratic assignment problem[J].Future Generation Computer Systems,2001,17:441-449.
[29]Piriyakumar D,Levi P.A new approach to exploiting parallelism in ant colony algorithm[C].Proceedings of International Symposium onMicromechatronics and Human Science(Stone P,ed.),2002:237-243.
[30]Cheng-Fa Tsai,Chun-Wei Tsai,Ching-Chang Tseng.A new hybrid heuristic approach for solving large traveling salesman problem[J].Information Science,2004,166(1-4):67-81
[31]Kawamura H,Yamamoto M,Suzuki K,Ohuchi A.Multiple ant colonies algorithm based on colony level interactions[J].IEICE Transactions on Fundamentals of Electronics,Communications,and Computer Sciences,2000,E83-A(2):371-379.
[32]Kawamura H,Yamamoto M,Ohuchi A.Improved multiple ant colonies systems for traveling salesman problems[A].Kozan E,Ohuchi A:Operation research/management science at work[M].Boston,MA:Kluwer Academic Publishers,2002:43:41-52.
[33]萧蕴诗,李炳宇,吴启迪.求解TSP问题的模式学习并行蚁群算法[J].控制与决策,2004,19(8):882-888.
[34]Randall M,Lewis A.A parallel implementation of ant colony algorithm[J].Parallel and Distributed Computing,2002,62:1421-1432.
[35]Merkle D,Middendorf M.Fast ant colony optimization on runtime reconfigurable processor arrays[J].Genetic Programming and Evolvable Machine,2002,3(4):345-361.
[36]Blum C,Dorigo M.The Hyper-Cube framework for ant colony algorithm[J].IEEE Transactions on SMC,2004,34(2):1161-1172.
[37]Alba E,Leguizamon G,Ordonez G.Analyzing the behavior of parallel ant colony systems for large instances of the task scheduling problem[C].20th IEEE International Parallel and Distributed Processing Symposium,2005:14-23.
[38]Craus M,Rudeanu L.Parallel framework for ant-like algorithms[C].Third International Symposium on Algorithms,Models and Tools for Parallel Computing on Heterogeneous Networks,2004:36-41
[39]Chu D,Till M,Zomaya A.Parallel ant colony optimization for 3D protein structure prediction using the HP lattice model[A].In:Nedjah N,Alba E.Parallel Evolutionary Computations.Berlin,Heidelberg:Springer,2006:177-198.
[40]Islam M T,Thulasiraman P,Thulasiram R K.A parallel ant colony optimization algorithm for all-pair routing in MANETs[J].Proceedings of the International Parallel and Distributed Processing Symposium,2003:259-266.
[41]章春芳.自适应的并行蚁群算法及其应用[D].扬州:扬州大学,2006:.
[42]黄席樾,张著洪,何传江,胡小兵,马笑潇.现代智能算法理论及应用[M].北京:科学出版社,2005.
[43]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[44]Stiizle T.Parallelization strategies for ant colony optimization[C].Proceedings of PPSN-Ⅴ,Fifth International Conference on Parallel Problem Solving from Nature (Eiben A E,B(a|¨)ck T,Schoenauer M,Schwefel H P,Eds.),Lecture Notes in Computer Science,Berlin,Springer-Verlag,1998,1498:722-731.
[45]Middendorf M,Reischle F,Schmeck H.Multi colony ant algorithms[J].Journal of Heuristics,2002,8(3):305-320.
[46]Eberhart R C,Kennedy J.A new optimizer using particle swarm theory[C].Proceedings of the Sixth International Symposium on Micro Machine and Human Science,Nagoya,Japan,1995:39-43.
[47]van den Bergh F,Engelbrecht AP.Using Neighborhoods with the Guaranteed Convergence PSO[C].Proceedings of the IEEE Swarm Intelligence Symposium,2003:235-242.
[48]Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part Ⅰ:background and development[J].Natural Computing,2007,6(4):467-484.
[49]Banks A,Vincent J,Anyakoha C.A review of particle swarm optimization.Part Ⅱ:hybridisation,combinatorial,multicriteria and constrained optimization,and indicative applications[J].Natural Computing,2008,7(1):109-124.
[50]Wei Pang,Kang-ping Wang,Chun-guang Zhou,Long-jiang Dong,Ming Liu,Hong-yan Zhang,Jian-yu Wang.Modified Particle Swarm Optimization Based On Space Transformation for Solving Traveling Salesman Problem[C].Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,2004:2342-2346.
[51]Tasgetiren M F,Liang Y C,Sevkli M.Gencyilmaz G.Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem[C].4th International Workshop on Ant Colony Optimization and Swarm Intelligence,ANTS2004,LNCS 3172 by Springer-Verlag,2004:382-390.
[52]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G Particle swarm optimization algorithm for single machine total weighted tardiness problem[C].Proceedings of the 2004 Congress on Evolutionary Computation (CEC'04),Portland,Oregon,2004:1412-1419.
[53]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop sequencing problem[C].Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems (IMS2004),Sakarya,Turkey,2004:431-441.
[54]Cagnina L,Esquivel S,Gallard R.Particle swarm optimization for sequencing problems:a case study[A].Proceedings of the 2004 Congress on Evolutionary Computation[C].Portland:Institute of Electrical and Electronics Engineers Inc,2004,536-541.
[55]Mohemmed A W,Sahoo N C.Efficient Computation of Shortest Paths in Networks Using Particle Swarm Optimization and Noising Metaheuristics[A].Discrete Dynamics in Nature and Society[M].New York,USA:Hindawi Publishing Corporation,Volume 2007,Article ID 27383,2007.
[56]Clerc M.Discrete Particle Swarm Optimization:A Fuzzy Combinatorial Bla ck Box[EB/OL]:http://clerc.maurice.free.fr/PSO/Fuzzy_Discrete_PSO/Fuzzy_D PSO.htm,2009:.
[57]Wei Pang,Kang-ping Wang,Chun-guang Zhou,Long-jiang Dong.Fuzzy Discrete Particle Swarm Optimization for Solving Traveling Salesman Problem[C].Proceedings of the 4th International Conference on Computer and Information Technology (CIT04),IEEE Computer Society,2004.
[58]Laskari E C,Parsopoulos K E,Vrahatis M N.Particle swarm optimization for integer programming[C].Proc.of the IEEE Congress on Evolutional Computation(CEC2002),Honolulu,USA,2002:1582-1587.
[59]Saiman A,Ahmad I,Al-Madani S.Particle swarm optimizationfor task assignment Problem[J].Microprocessors and Microsystems,2002,26:363-371.
[60]Kennedy J,Eberhart R.A Discrete Binary Version of the Particle Swarm Algorithm[C].IEEE Conference on Systems,Man,and Cybernetics,Orlando,FA,1997:4104-4109.
[61]Tasgetiren M F,Yun-Chia Liang.A Binary Particle Swaarm Optimization Algorithm for Lot Sizing Problem[J].Journal of Economic and Social Research.2003,5(2):1-20.
[62]Coello C,Luna E.Use of Particle Swarm Optimization to Design Combinational Logic Circuits[C].5~(th) International Conference,ICES2003,Springer,Lecture Notes in Computer Science,VOL 2606,Trondheim,Northway,2003:398-409.
[63]HUANG Yan-Xin,ZHOU Chun-Guang,ZOU Shu-Xue,Wang Yan.A Hybrid Algorithm on Class Cover Problems[J].Journal of Software,2005,16(4):513-522.
[64]Liao C J,Tseng C T,Luarn,P.A discrete version of particle swarm optimization for flowshop scheduling problems[J].Computer& Operations Research,2007,34:3099-3111.
[65]Mnarice Clerc.Discrete Particle Swarm Optimization,by the Traveling Salesman Problem[EB/OL]:http://www.mauriceclere.net,2009:.
[66]Schoofs L,Naudts B.Swarm intelligence on the binary constraint satisfaction problem[C].Proc.of the IEEE Congress on Evolution Computation(CEC 2002),Honolulu,Hawaii,USA,2002:1444-1449.
[67]Rameshkumar K,Suresh R K,Mohanasundaram K M.Discrete Particle Swarm Optimization(DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Manspan[C].Proc.ICNC 2005,LNCS3612,2005:572-581.
[68]Wang Kang-ping,Huang Lan,Zhou Chun-guang et al.Particle Swarm optimization for traveling salesman problem[C].IEEE Service Center,Proceedings of the Second International Conference on Machine Learning and Cybernetics,Xi'an,IEEE Press,2003,5:1583-1585.
[69]葛宏伟,梁艳春,周春新.一种新的基于改进粒子群算法的Job-Shop调度方法[C].2004年全国博士生学术论坛论文集,2004,9:1-7
[70]Shi X H,Xing X L,Wang Q X,Zhang L H,Yang X W,Zhou C G,Liang Y C.A discrete PSO method for generalized TSP problem[C].Proceedings of the Third International Conference on Machine Learning and Cybernetics,Shanghai,2004:378-2383.
[71]Weijun Xia,Zhiming Wu.An effective hybrid optimization approach for multi-objective flexible job-scheduling problems[J].Computers & Industrial Engineenng 2005,48:409-425.
[72]Chen Ai-ling,Yang Gen-ke,Wu zhi-ming.Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem[J].Journal of Zhejiang University SCIENCE A,2006:7(4),607-614.
[73]Hu X,Eberhart R C,Shi Y.Swarm Intelligence for permutation optimization:a case study on n-queens problem[C].Proceeding of the IEEE Swarm Intelligence Symposium 2003(SIS 2003),Indianapolis,Indiana,USA,2003:243-246.
[74]Pan Q K,Tasgetiren M F,Liang Y C.A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem with makespan criterion[C].Proceedings of the International Workshop on UK Planning and Scheduling Special Interest Group,UK PLANSIG2005,City University,London,2005:34-43
[75]潘全科,王文宏,潘群,朱剑英.解决Job Shop问题的粒子群优化算法[J].机械科学与技术,2006,25(6):675-679.
[76]Cuiru Wang,Jiangwei Zhang,Jing Yang,Chaoju Hu,Jun Liu.A Modified Particle Swarm Optimization Algorithm and its Application for Solving Traveling Salesman Problem[C].International Conference on Neural Networks and Brain,2005:689-694.
[77]王翠茹,张江维,王玥,衡军山.改进粒子群优化算法求解旅行商问题[J].华北电力大学学报,2005,32(6):47-51.
[78]杨轻云.约束满足问题与调度问题中离散粒子群算法研究[D].吉林:吉林大学,2006.
[79]钟一文.智能优化方法及其应用研究[D].杭州:浙江大学,2005.
[80]熊磊.粒子群算法在离散优化问题中的研究[D].桂林:广西师范大学,2006
[81]CLERE M.The swarm and the queen:towards a deterministic and adaptive particle swarm optimization[C]Proc.of the Congress on Evolutionary Computation,Piscataway,1999:1951-1957.
[82]Benioff P.The Computer as a physical system:a microscopic quantum mechanical Hamiltonian model of computers as represented by turing machines[J].Journal of Statistical Physics,1980,22:563-591.
[83]Feynman R.Simulating physics with computers[J].International Journal of Theoretical Physics,1982,21(6):467-488.
[84]De Jong K A.An analysis of the behaviour of a class of genetic adaptive systems[D].Michigan:Ph.D.Thesis,University of Michigan,1975:.
[85]Spears W.De Jong Test Functions From William M.Spears[EB/OL]:http://www.c s.uwyo.edu/-wspears/functs.dejong.html,2007:
[86]Marsaglia G,Zaman A.The KISS generator[R].Florida,USA:Department of Statistics,Florida State University,Tallahassee,1993
[87]Reinelt G.The Linear Ordering Problem:Algorithms and Applications.Research and Exposition in Mathematics(vol.8)[M].Berlin:Heldermann Verlag,1985.
[88]Chiarini B H.New Algorithm for the Triangulation of Input-Output Tables and the Linear Ordering Problem[D].The Graduate School of the University of Florida,2004
[89]Garey M R,Johnson D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].New York,NY,USA:W.H.Freeman & Co.,1979:.
[90]Reinelt G..LOLIB[EB/OL].http://www.iwr.uni-heidelberg.de/groups/comopt/so ftware/LOLIB/index.html;1997:.
[91]Ronald,S.(1998).More distance functions for order-based encodings[M].Proceedings of the IEEE Conference on Evolutionary Computation,IEEE Press,New York,1998:558-563.
[92]Laguna M,Marti R.Scatter Search:Methodology and Implementation in C[M].Boston:Kluwer Academic Publishers,2003.
[93]Resendee M G C,Ribeiro C C.Greedy Randomized Adaptive Search Procedures:Advances and Applications[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[94]Festa P,Resende M G C.An annotated bibliography of GRASP,Part Ⅰ:Algorithms[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[95]Festa P,Resende M G C.An annotated bibliography of GRASP,Part Ⅱ:Applications[R].Florham Park,NJ:AT&T Labs Research Technical Report,2008.
[96]吴启迪,汪镭.智能微粒群算法研究及应用[M].江苏:江苏教育出版社社,2005.
[97]Johnson S M.Optimal two-and three-stage production schedules with setup times included[J].Naval Research Logistics Quarterly,1954,1:61-68.
[98]Baker K R.Introduction to Sequencing and Scheduling[M].New York:Wiley,1974:.
[99]Garey M R,Johnson D S,Sethi R.The Complexity of Flowshop and Jobshop Scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.
[100]周国华.生产作业调度问题的软计算方法研究[D].成都:西南交通大学,2003.
[101]甘应爱,田丰.运筹学[M].北京:清华大学出版社,1990:.
[102]Wagner D B.Dynamic Programming[J].The Mathematical Journal,1995,5(4):42-51.
[103]Bellman R.On the Theory of Dynamic Programming[C].Proceedings of the National Academy of Sciences,1952:716-719.
[104]Blazewicz J.et al.Scheduling Computer and Manufacturing Process[M].2~(nd)Printing.Berlin,Heidelberg:Springer,2001:.
[105]Held M,Karp R M.A Dynamic Programming Approach to Sequencing Problems[J].Journal of the Society for Industrial and Applied Mathematics,1962,10(1):196-210.123
[106]Reza Hejazi S,Saghafian S.Flowshop-Scheduling Problems with Makespan Criterion:A Review[J].International Journal of Production Research,2005,43(14):2895-2929.
[107]Doig A,Land A H.An Automatic Method for Solving Discrete Programming Problems[J].Econometrica,1960,28:497-520.
[108]Dakin R J.A Tree-Search Algorithm for Mixed Integer Programming Problems[J].The Computer Journal,1965,8(3):250.
[109]陈庆华,谢政.整数规划[M].长沙:国防科技大学出版社,1992:.
[110]Lageweg B J,Lenstra J K,Kan A.A General Bounding Scheme for the Permutation Flow-Shop Problem[J].Operations Research,1978,26(1):53-67.
[111]Carlier J,Rebai I.Two Branch and Bound Algorithms for the Permutation Flowshop Problem[J].European Journal of Operational Research,1996,90:238-251.
[112]Haouari M,Ladhari T.A Branch-and-Bound-Based Local Search Method for the Flow Shop Problem[J].Journal of the Operational Research Society,2003,54(10):1076-1084.
[113]Ladhari T,Haouari M.A Computational Study of the Permutation Flow Shop Problem Based on a Tight Lower Bound[J].Computers and OperationsResearch,2005,32(7):1831-1847.
[114]Fisher M L.The Lagrangian Relaxation Method for Solving Integer Programming Problems[J].Management Science,1981,27(1):1-18.
[115]Fisher M L.An Applications Oriented Guide to Lagrangian Relaxation[J].Interfaces,1985,15(2):10-21.
[116]Liu G,Luh P B,Resch R.Scheduling Permutation Flow Shops Using theLagrangian Relaxation Technique[J].Annals of Operations Research,1997,70:171-189.
[117]Palmer D S.Sequencing jobs through a multi-stage process in the minimum total time:a quick method of obtaining a near optimum[J].Operational Research Quarterly,1965,16(1):101-107.
[118]Gupta J.A Functional Heuristic Algorithm for the Flowshop Scheduling Problem[J].Operational Research Quarterly,1971,22:39-47.
[119]Campbell H G,Dudek R A,Smith M L.A Heuristic Algorithm for the n-Job, m-Machine Scheduling Problem[J].Management Science,1970,16:630-637.
[120]Dannenbring D G An Evaluation of Flow Shop Sequencing Heuristics[J].Management Science,1977,23(11):1174-1182.
[121]Nawaz M,Enscore E,Ham I.A Heuristic Algorithm for the m-Machine,n-Job Flowshop[J].OMEGA:The International Journal of Management Sciences,1983,11(1):91-95.
[122]Taillard E.Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1990,47(1):65-74.
[123]Turner S,Booth D.Comparison of Heuristics for Flow Shop Sequencing[J].OMEGA:The International Journal of Management Sciences,1987,15(1):75-78.
[124]Ruiz R,Maroto C.A Comprehensive Review and Evaluation of Permutation Flowshop Heuristics [J].European Journal of Operational Research,2005,165:479-494.
[125]Kalczynski P J,Kamburowski J.On the NEH Heuristic for Minimizing theMakespan in Permutation Flowshops[J].OMEGA:The International Journal ofManagement Sciences,2007,35:53-60.
[126]Ho J C,Chang Y L.A New Heuristic for the n-Job,m-Machine Flow-Shop Problem[J].European Journal of Operational Research,1991,52(2):194-202.
[127]Suliman S M A.A Two-Phase Heuristic Approach to the Permutation Flow-Shop Scheduling Problem[J].International Journal of Production Economics,2000,64(1):143-152.
[128]Kirkpatrick S,Gelatt Jr C D,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[129]Laarhoven P J M,Aarts E H L.Simulated Annealing:Theory and Applications[M].MA,USA:Kluwer Academic Publishers Norwell,1987:.
[130]Koulamas C,Antony S R,Jaen R.A Survey of Simulated Annealing Applications to Operations Research Problems[J].Omega(Oxford),1994,22(1):41-56.
[131]Osman I H,Potts C N.Simulated Annealing for Permutation Flow-Shop Scheduling[J].Omega(Oxford),1989,17(6):551-557.
[132]Ogbu F A,Smith D K.The Application of the Simulated Annealing Algorithm tothe Solution of the mlmlCmax Flowshop Problem[J].Computers andOperations Research,1990,17(3):243-253.
[133]Ogbu F,Smith D.Simulated Annealing for the Permutation Flowshop Problem[J].Omega,The International Journal of Management Science,1990,19(1):64-67.
[134]Ishibuchi H,Misaki S,Tanaka H.Modified Simulated Annealing Algorithms for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1995,81:388-398.
[135]Zegordi S H,Itoh K,Enkawa T.Minimizing Makespan for Flow Shop Scheduling by Combining Simulated Annealing with Sequencing Knowledge[J].European Journal of Operational Research,1995,85(3):515-531.
[136]Wodecki M,Bozejko W.Solving the Flow Shop Problem by Parallel Simulated Annealing[C].Lecture Notes in Computer Science,2001:236-247.
[137]Glover F.Further Paths for Integer Programming and Links to Artificial Intelligence [J].Computer and Operations Research,1986,13:533-549.
[138]Hansen P.The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming[C].Congress on Numerical Methods in Combinatorial Optimization.Capri,Italy,1986:70-145.
[139]Glover F.Tabu Search:Part Ⅰ[J].ORSA Journal on Computing,1989,1(3):190-206.
[140]Glover F.Tabu Search:Part Ⅱ[J].ORSA Journal on Computing,1990,2(1):4-32.
[141]Glover F,Taillard E.A User's Guide to Tabu Search[J].Annals of Operations Research,1993,41(1):l-28.
[142]Glover F W,Laguna M.Tabu Search[M].Berlin,Heidelberg:Springer,1997:.
[143]Widmer M,Hertz A.A New Heuristic Method for the Flow Shop Sequencing Problem[J].European Journal of Operational Research,1989,41(2):186-193.
[144]Reeves C R.Improving the Efficiency of Tabu Search for Machine Scheduling Problems[J].Journal of Operational Research Society,1993,44(4):375-382.
[145]Moccellin J V.A New Heuristic Method for the Permutation Flow Shop Scheduling Problem[J].The Journal of the Operational Research Society,1995,46(7):883-886.
[146]Nowicki E,Smutnicki C.A Fast Tabu Search Algorithm for the PermutationFlow-Shop Problem[J].European Journal of Operational Research,1996,91:160-175.
[147]Taillard E.Benchmarks for basic scheduling problems[J].European Journal of Operational Research,1993,64:278-285.
[148]Ben-Daya M,Al-Fawzan M.A Tabu Search Approach for the Flow ShopScheduling Problem[J].European Journal of Operational Research,1998,109(1):88-95.
[149]Solimanpur M,Vrat P,Shankar R.A Neuro-Tabu Search Heuristic for the FlowShop Scheduling Problem[J].Computers and Operations Research,2004,31(13):2151-2164.
[150]Grabowski J,Wodecki M.A Very Fast Tabu Search Algorithm for the Permutation Flow Shop Problem with Makespan Criterion[J].Computers and Operations Research,2004,31(11):1891-1909.
[151]Holland J H.Adaptation in Natural and Artificial Systems[M].Ann Arbor:University of Michigan press,1975:.
[152]Jog P,Suh J Y,van Gucht D.The Effects of Population Size,Heuristic Crossoverand Local Improvement on a Genetic Algorithm for the Traveling SalesmanProblem[C].Proceedings of the third international conference on Geneticalgorithms table of contents,1989:110-115.
[153]Ishibuchi H et al.Genetic Algorithms and Neighborhood Search Algorithmsfor Fuzzy Flowshop Scheduling Problems[J].Fuzzy Sets and Systems,1994,67(1):81-100.
[154]Chen C L,Vempati V S,Aljaber N.An Application of Genetic Algorithms for Flow Shop Problems[J].European Journal of Operational Research,1995,80:389-396.
[155]Reeves C R.A Genetic Algorithm for Flowshop Sequencing[J].Computers Operations Research,1995,22(1):5-13.
[156]Murata T,Ishibuchi H,Tanaka H.Genetic Algorithms for Flowshop Scheduling Problems[J].Computers and Industrial Engineering,1996,30(4):1061-1071.
[157]Reeves C R,Yamada T.Genetic Algorithms,Path Relinking and the Flowshop Sequencing Problem[J].Evolutionary Computation journal,1998,6(1):230-234.
[158]Ponnambalam S G.Constructive and Improvement Flow Shop Scheduling Heuristics:An Extensive Evaluation[J].Production Planning & Control,2001,12(4):335-344.
[159]Wang L,Zheng D Z.An Effective Hybrid Heuristic for Flow Shop Scheduling[J].International Journal of Advanced Manufacturing Technology,2003,21(1):38-44.
[160]Ruiz R,Maroto C,Alcaraz J.New Genetic Algorithms for the Permutation Flowshop Scheduling Problem[C].Proceedings of the Fifth Metaheuristic International Conference,Kyoto,2003:63-1.
[161]Ruiz R,Maroto C,Alcaraz J.Two New Robust Genetic Algorithms for the Flowshop Scheduling Problem[J].OMEGA,the International Journal ofManagement Science,2006,34:461-476.
[162]Stutzle T.An Ant Approach to the Flow Shop Problem[C].Proceedings of European Congress on Intelligent Techniques and Soft Computing.Aachen,Germany,1998:1560-1564.
[163]Ying K-C,Liao C-J.An Ant Colony System for Permutation Flow-Shop Sequencing[J].Computers and Operations Research,2004,31(5):791-801.
[164]Ying K-C,Liao C-J.An Ant Colony System for Permutation Flow-Shop Sequencing[J].Computers and Operations Research,2004,31(5):791-801.
[165]Merkle D,Middendorf M.An Ant Algorithm with a New Pheromone Evaluation Rule for Total Tardiness Problems[C].Proceedings of EvoWorkshops,2000:287-296.
[166]Tasgetiren M F,et al.Particle Swarm Optimization Algorithm for Permutation Flowshop Sequencing Problem[C].Fourth International Workshop on Ant Algorithms and Swarm Intelligence,ANTS2004,2004:382-389.
[167]Rameshkumar K,Suresh R K,Mohanasundaram K M.Discrete Particle Swarm Optimization(DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[C].Lecture Notes in Computer Science,2005:572-581.
[168]Lian Z,Gu X,Jiao B.A Similar Particle Swarm Optimization Algorithm for Permutation Flowshop Scheduling to Minimize Makespan[J].Applied mathematics and computation,2006,175(1):773-785.
[169]Liu B,Wang L,Jin Y H.An Effective PSO-Based Memetic Algorithm for FlowShop Scheduling[J].Systems,Man and Cybernetics,Part B,IEEE Transactionson,2007,37(1):18-27.
[170]Liao C J,Tseng C T,Luarn P.A Discrete Version of Particle SwarmOptimization for Flowshop Scheduling Problems[J].Computers and Operations Research,2007,34(10):3099-3111.
[171]Pan Q K,Tasgetiren M F,Liang Y C.A Discrete Particle Swarm Optimization Algorithm for the Permutation Flowshop Sequencing Problem with Makespan Criterion[J].European Journal of Operational Research,Computers & Industrial Engineering,2008,55(4):795-816.
[172]Werner F.On the Heuristic Solution of the Permutation Flow Shop Problem by Path Algorithms [J].Computers and Operations Research,1993,20(7):707-722.
[173]Stutzle T.Applying Iterated Local Search to the Permutation Flow Shop Problem[R].TU Darmstadt:Technical Reprot AIDA-98-04,FG Intellektik,1998.
[174]Moscato P.On Evolution,Search,Optimization,Genetic Algorithms and Martial Arts:Towards Memetic Algorithms[R].Pasadena,CA,USA:Caltech Concurrent Computation Program,C3P Report 826,1989.
[175]Ravetti M G,Nakamura F G,Meneses C N,Resende M G C,Mateus G R,Pardalos P M.Hybrid heuristics for the permutation flow shop problem[R].Technical Report(TD-6V9MEV).Florham Park,NJ:AT&T Labs Research,Florham Park,NJ 07932,2006.
[176]Tavakkoli-Moghaddam R,Gholipour-Kanani Y,Cheraghalizadeh R.A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems[J].International Journal of Management Science and Engineering Management,2008,3(2):119-130.
[177]Glover F.A Template for Scatter Search and Path Relinking[C].Third European Conference on Artificial Evolution,1997:3-54.
[178]Nowicki E,Smutnicki C.Some aspects of scatter search in the flow shop problem[J].European Journal of Operational Research,2006,169(2):654-666.
[179]Bozejko W,Wodecki M.Parallel scatter search algorithm for the flow shop sequencing problem[C].Lecture Notes in Computer Science,2008,4967:180-188
[180]Storn R,Price K.Differential evolution-A simple and efficient adaptive scheme for globaloptimization over continuous spaces[R].Berkeley:University of California,1995.
[181]Storn R,Price K.Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous space[J].Journal of Global Optimization,1997,11:341-359.
[182]Lampinen J.A bibliography of differential evolution algorithm[EB/OL].http://www.lut.fi/～jlampine/debiblio.htm,2002.
[183]Tasgetiren M F,Sevkli M,Liang Y-C,Gencyilmaz G.Differential Evolution Algorithm for Permutation Flowshop Sequencing Problem with Makespan Criterion[C].Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems(IMS2004),2004:442-452.
[184]Moccellin J a V,dos Santos M O.An Adaptive Hybrid Meta-Heuristic for Permutation Flowshop Scheduling[J].Journal of the Operational Research Society,2000,46:883-886.
[185]Kai S,Genke Y.An Effective Hybrid Optimization Algorithm for the Flow Shop Scheduling Problem[C].Information Acquisition,2006 IEEE International Conference,2006:1234-1238.
[186]Framinan J M,Leisten R,Rajendran C.Different initial sequences for the heuristic of Nawaz,Enscore and Ham to minimize makespan,idletime or flowtime in the static permutation flowshop sequencing problem[J].International Journal of Production Research,2003,41(1):121-148.
[187]Framinan J M,Gupta J N D,Leisten R.A Review and Classification of Heuristics for Permutation Flow-Shop Scheduling with Makespan Objective[J].Journal of the Operational Research Society,2004,55(12):1243-1255.
[188]Duda J.A critical review of the newest biologically-inspired algorithms for flowshop scheduling problem[J].Task Quarterly,2007,11(1-2):7-19.
[189]Prabhaharan G.,Khan B S,Rakesh L.Implementation of grasp in flow shop scheduling[J].International Journal of Advanced Manufacturing Technology,2006,30(11-12):1126-1131.
[190]Jarboui B,Ibrahim S,Siarry P,Rebai A.A combinatorial particle swarm optimization for solving permutation flowshop problems[J].Computers &Industrial Engineering,2008,54(3):526-538.
[191]Zobolas G I,Tarantilis C D,Ioannou G.Minimizing makespan in permutation flow shop scheduling problems using a hybrid metaheuristic algorithm[J].Computers & Operations Research,2009,36(4):1249-1267.
[192]Campos V,Laguna M,Mart(?) R.Context-independent scatter search and tabu search for permutation problems[J].INFORMS Journal on Computing,2005,17:111-122.
[193]Levenshtein V I.Binary codes capable of correcting deletions,insertions,and reversals[J].Soviet Physics-Doklady,1966,10:707-710.
[194]Taillard E.Scheduling instances[EB/OL]http://mistic.heig-vd.ch/taillard/pr oblemes.dir/ordonnancement.dir/ordonnancement.html.
[195]覃钢力,杨家本.自适应调整信息素的蚁群算法[J].系统仿真学报,2002,14(1):31-33.
[196]Botee H M,Bonabeau E.Evoluting ant colony optimization[J].Complex Systems,1998,1(2):149-159.
[197]郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践,2002,25(9):88-91,136.
[198]李万庆,李彦苍.求解复杂优化问题的基于信息熵的自适应蚁群算法[J].数学的实践与认识,2005,35(2):134-139.
[199]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10):1240-1245.
[200]Dorigo M,Luca M.The Ant-Q:algorithm applied to the nuclear reload problem.Annals of Nulear Energy,2002,29(12):1455-1470.
[201]Koh B,George A,Haftka R,Fregly B.Parallel Asynchronous Particle Swarm Optimization,International Journal for Numerical Methods in Engineering,2006,67(4):578-595.
[202]St(u|¨)tzle T.ACOTSP.V1.0.tar.gz[EB/OL]http://iridia.ulb.ac.be/-mdorigo/ACO/aco-code/public-software.html,2004.
[203]Reinelt G TSPLIB95[EB/OL].http://www.iwr.uni-heidelberg.de/groups/como pt/software/TSPLIB95/index.html,2007.
[206]高祥.启发式求解大规模流水调度问题[D].哈尔滨:哈尔滨理工大学,2006
[207]高守玮.一类Flow shop生产调度问题及其优化方法之分析与研究[D].上海:上海交通大学,2007.
[208]Wolpert D H,Macready W G.No Free Lunch Theorems for Optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |