一种基于流水车间调度问题的蚁群算法英文文献翻译.doc

一种基于流水车间调度问题的蚁群算法 概要 蚁群系统算法（ACS），是受自然界中真正蚂蚁寻找食物的行为启发，而产生的的一种新颖的模仿蚁群觅食行为的智能算法。這篇文章第一次把蚁群系统算法引入到n/m/P/C问题，n/m/P/C问题是一个NP-hard先后顺序问题，用于找到n个工件以相同的顺序在m台机器上加工，n个工件在每台机器上最优的加工顺序，使最大流程时间达到最小。为了证实蚁群算法是一种先进的成熟的算法，在众所周知的Taillard基准测试问题集上做了计算实验，用蚁群算法与其它的启发式算法比如遗传算法、模拟退火，邻域搜索等相比较，计算结果显示ACS在n/m/P/C问题上事一种很有效的启发式算法。 1.引言 考虑一个先后顺序问题，如下： 有n个不同的工件要在m台机器上完成加工问题指出，并且是个著名的NP-hard问题。 在过去的40年中，n/m/P/C问题引起了很多研究员的注意。尽管解决n/m/P/C问题最佳的方法可以通过列举的方法获得，像穷举和分解法，这些方法会带来超高的计算量，即使是对于那些中等的不是很大的问题。为了达到实际的目的，经常进行分配去寻找启发式的方法以产生最佳的解决方法并使得相关计算费用比较少。这就导致了许多启发式程序的诞生发展。 当前文献中可用的解决这个问题的启发式方法可分为两类：初始序列的产生阶段和改进阶段。在初始序列的产生阶段中，一但工件的操作顺序被确定，那就固定不变了，不能被颠倒.一些关于n/m/P/C问题的建设性启发在文献中都有提到，计算结果表明这种NEH和SPIRIT启算法方法是当前可用的最好的也是被我们所熟知的方法。另一方面，改良型启发先以一个最初的方法启动，在用一种手段来反复的获得改良方法。在最近几年，在这一理论上应用启发式算法已经被广泛的推广进行，启发式算法已经成为了一种可以在较少的限制下应用于不同的最优化问题的相当普遍的计算结构。实际上，有一类算法可以随机化改进启发式算法。这一类型的方法包括：遗传算法（GA），模拟退火算法（SA），还有禁忌搜索。文献表明这些方法在NP-hard组合优化问题上起到很大的作用。 蚁群系统算法（ACS），是Dorigo和Gambardella在1997年首先提出的，是解决组合优化问题的一种很新很有希望的启发式算法。在这篇论文中，我们为n/m/P/C问题编写一个ACS算法。这个算法将用来和以前用的GA，SA和临近搜索算法（NS），一类由Taillard提出的基准问题将被用于这次比较。论文的其余本分分配如下：在下一个章节，我们介绍一下ACS的背景。然后我们介绍一下在第3节中应用的ACS的描述。我们执行n/m/P/C问题的ACS算法是第4节的任务。在Taillard基准问题上计算结果并进行和其他启发式算法的比较将在第5节被执行。最后，我们将在第6节用一个概要结束这篇文章。 2.ACS算法的背景 ACS是蚁群优化（ACO）的一种特殊的启发式算法，是一种解决不相关联优化问题的自然的有创造力的启发式算法。第一个ACO系统是由Dorigo介绍的，被叫做蚂蚁系统（AS），它是计算人员在研究组合优化问题的结果。蚂蚁系统的来源是自然界中使人感兴趣的蚂蚁觅食行为，真实的蚂蚁可以在没有视觉信号的情况下找到从食物源头到它们巢穴的最短路径。它们通过一种带有芬芳的香精来交流关于食物来源的信息，这一芬芳香精被叫做信息素。当行走时，蚂蚁将在路过的地面上分泌信息素而且有一定几率跟随前边的蚂蚁留下的信息素行走。路径上不断增长的大量的信息素给予后来的蚂蚁很大的鼓舞，从而使得后来的蚂蚁会更高几率的跟随前边的蚂蚁留下的信息素行走，因为蚂蚁经过食物源由短路径回到巢穴要快于那些由长路径回来的蚂蚁。所以，短的路径上的信息素密度将比长路径上的大，所以，由此推理，这就造成了短路径是那个的信息素增长量将远远大于长路径，从而导致了了所有的蚂蚁都能很快的选择出短路径。对真实蚂蚁觅食行为的描述可以被模拟用来解决组合优化问题：客观价值相应食物源的质量，仿真蚂蚁搜寻实质问题的解决方法模拟真实蚂蚁搜寻它们的环境，适应的记忆相应信息素的踪迹。另外，仿真蚂蚁和和局部启发功能相结合从而指导对适宜解进行一遍仔细的搜寻。 ACO方法已经被成功的应用于解决组合优化问题。这些例子都包括：旅行商问题，连续排序问题，二次分配问题，车量路径问题，行程安排问题，图表着色问题，分割问题，动力系统最优化问题，还有无线通讯网络问题。一种非常有效的以ACO为基础的启发式ACS将在下一节被论述。 3.蚁群系统 ACS进来被用来在对称和非对称旅行商问题上同其他启发式算法相比较，这在表1中被体现。三条程序被反复提到直到一些结束条件被验证。首先，一组仿真蚂蚁被放置在起始节点依照某些初始化规则，每个蚂蚁利用重复的使用随即贪吃规则建立一条路径；其次，当构建自己的路径时