（运筹学与控制论专业论文）蚂蚁算法在工件排序问题上的应用研究.pdf

摘要 蚂蚁算法是一种源于生物世界的随机搜索算法，而工件排序问题则是运筹学 当中一个重要的分支。本文针对工件排序问题中的单机排序问题、平行机排序问 题和同顺序作业问题分别给出了不同的蚂蚁算法，并与禁忌搜索算法进行了比 较，说明了蚂蚁算法的性能，对其过程和结果做了一定的分析。 关键词：蚂蚁算法工件排序问题禁忌搜索算法 中图分类号：0 2 2 a b s t r a c t a n tc o l o n yo p t i m i z a t i o na l g o r i t h misak i n do fs e a r c ha l g o r i t h mf r o m b i o l o g i c a lw o r l d s c h e d u l i n gp r o b l e mi sav e r yi m p o r t a n tb r a n c ho f o p e r a t i o nr e s e a r c h i nt h i sa r t i c l e ，d i f f e r e n ta n tc o l o n yo p t i m i z a l i o n a l g o r i t h m sa r eg i v e nt os o l v es i n g l em a c h i n ep r o b l e m ，p a r a l l e lp r o c e s s o r s p r o b l e ma n df l o ws h o pp r o b l e m a n dt h e ya r ec o m p a r e dw i t ht a b o o s e a r c h a l g o r it h mt os h o wt h ep e r f o r m a n c eo fa n tc o l o n yo p t i m i z a t i o na l g o r it h i n t h ep r o c e s sa n dt h er e s u l to fa n tc o l o n yo p t i m i z a t i o na l g o r i t h ma r ea l s o a n a l y z e d k e yw o r d s ：a n tc o l o n yo p t i m i z a t i o n ，s c h e d u li n gp r o b l e m ，t a b o o s e a r c h 第一章引言 蚂蚁算法( 矗n tc o l o n yo p t i m i z a t i o n ，简称a c o ) 是一种源于生物世界的仿生 物随机搜索算法，诞生至今只有短短的几年时间。自从意大利学者d o r i g o 在1 9 9 6 年提出了蚂蚁算法开始 卜2 ，其在组合优化的许多问题中得到应用，并得到不 错的结果。作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通 过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于模 拟仿真中使用的是入工蚂蚁概念，因此有时亦被称为蚂蚁系统。近年来，该算法 在工件排序问题上也有了一定的进展 5 一1 3 ，但是研究的范围还是有所局限，研 究成果并不是很多。本文主要针对一系列的工件排序问题给出经过不同优化的蚂 蚁算法。 1 1 、蚂蚁算法的原理 据昆虫学家的观察和研究，发现生物世界中的蚂蚁有能力在没有任何可见提 示下找出从其窝巢至食物源的晟短路径，并且能随环境的变化而变化，适应性地搜 索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路 径上释放一种蚂蚁特有的分泌物f 言息激素( p h e r o m o n e ) ( 本文简称为信息素) ， 使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行动。当一些路 径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，以致信息素强度增大 ( 当然，随时间的推移会逐渐减弱) ，后来的蚂蚁选择该路径的概率也越高，从而更 增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为( a u t o c a t a l y t i cb e h a v i o r ) 。由于其原理是一种正反馈机制，因此，也可将蚂蚁t 1 雪( a n t c o l o n y ) t 里解成所谓的增强型学习系统( r e i n f o r c e m e n tl e a r n i n gs y s t e m ) 。 用于优化领域的人工蚂蚁算法，其基本原理吸收了生物界中蚂蚁群体行为的 某些显著特征：1 ) 能察觉小范围区域内状况并判断出是否有食物或其他同类的 信息素轨迹；2 ) 能释放自己的信息素；3 ) 所遗留的信息素数量会随时间而逐步 减少。由于自然界中的蚂蚁基本没有视觉，既不知向何处去寻找和获取食物，也 不知发现食物后如何返回自己的巢穴，因此它们仅仅依赖于同类散发在周围环境 中的特殊物质信息素，来决定自己何去何从，有趣的是，尽管没有任何先验 知识，但蚂蚁们还是有能力找到从其巢穴到食物源的最佳路径，甚至在该路线上 放置障碍物之后，它们仍然能很快重新找到新的最佳路线。 l 2 、蚂蚁算法的简单实例 这罩用一个形象的实例来说明蚂蚁算法的原理： 假设有两条道路可从蚂蚁的巢穴到达食物点，分别记为a b d 和a c d 食物点 图一、蚂蚁寻食 其中a b 和b d 的路径长度为1 ，a c 和c d 的路径长度为2 ，从食物到d 点距离 为l ，从巢穴到a 点距离为1 。 在t = 0 时刻，假设有2 0 只蚂蚁从巢穴出发到达a 点，它们将以相同的概念 进行路径选择，因此会有1 0 只蚂蚁选择a b d 道路，有l o 只蚂蚁选择a c d 道 路。 在t = 4 时刻，第一组到达食物源的蚂蚁将折回。 在t = 5 时刻，两组蚂蚁将在d 点相遇。此时b d 上的信息素数量与c d 上的相 同，因为各有1 0 只蚂蚁选择了相应的道路。从而有5 只返回的蚂蚁将选择b d 而另5 只将选择c d 。 在t = 8 时刻，前5 个蚂蚁将返回巢穴，而a c 、c d 和b d 上各有5 个蚂蚁。 在t = 9 时刻，前5 个蚂蚁又回到a 并且再次面对往左还是往右的选择。这时， 2 a b 上的轨迹数是2 0 而a c 上是1 5 ，因此将有较为多数的蚂蚁选择往左，从而 增强了该路线的信息素。 随着该过程的继续，两条道路上信息素数量的差距将越来越大，直至绝大多 数蚂蚁都选择了最短的路线。正是由于一条道路要比另一条道路短，因此，在相 同的时间区间内。短的路线会有更多的机会被选择。 i 3 、蚂蚁算法的适用范围 从蚂蚁算法自身的特点来看，最早提出蚂蚁算法主要是用来解决著名的旅行 商问题( t s p ) 的，并以t s p 问题为测试基准，与其它常用的一些启发式算法进行 比较，其结果比较好【3 。而自从蚂蚁算法在t s p 上取得成效以来，已陆续渗透到 其它问题领域中，如：二次分配问题、工件排序问题、图着色问题、大规模集成 电路设计、通讯网络中的负载平衡问题、车辆调度问题等等，在许多方面表现出 相当好的性能 4 】。由于蚂蚁算法对图的对称性和目标函数没有特殊的要求，因 此可以应用于各种非对称性问题和非线性问题。 由于蚂蚁算法特殊的生物性质，它不仅适用于目前的串行计算机，更易于未 来的并行计算，其运行效率就会大幅度提高。这一点从蚂蚁算法提出之初就以分 布式优化方法来命名即可看出。这也是蚂蚁算法相比较于其它算法的优势，也是 未来利用分布并行计算来解决大规模问题的一个很好的思路，将有很大的研究潜 力。 1 4 、蚂蚁算法的一般过程 符号说明： n a 一蚂蚁个数； 巩能见度( v i s i b i l i t y ) ； f 。轨迹上信息素的强度( i n t e n s i t y ) ； a r 。蚂蚁k 留下的信息素数量，一般可以定义为 r 。= q7 乙，若叠萎蔷最优路径上； p f 蚂蚁k 的转移概率，与f “”+ r p 。成正比j 是尚未访问结点 轨迹强度的更新方程为勺= p + 勺+ a r 。； k 其中，各参数的含义为： 口轨迹的相对重要性( 口0 ) ； 能见度的相对重要性( 0 ) p 轨迹的持久性( o p d j 的时候，w ，p ，较大的值的能见度较高， 这与实际情况也是相符的。而分母中减去t 是为了使分母的值不会因为t 越来 越大，因为如果不采取这种控制手段，随着t 越来越大，使能见度刁。的值变得 非常小，从而使得蚂蚁无法通过能见度，7 i i 区别不同的选择位置。 ( 4 ) 蚂蚁个数r l a ：o o r i g o 等人的文献对经典的t s p 问题所得到的经验结果表明， 当n a 大致等于工件个数n 的时候，效果最佳 3 ，因此本算法中也将采用n a = n 的设计。 ( 5 ) p 、口、q ：这些参数设定目前尚无理论上的依据，目前只能通过试 验数据来确定，已经公布的结果都是针对特定的问题而言，最早的数据是通过求 解t s p 的问题库中的一些例子得到，其经验结果为： 1 ) 0 口5 ： 2 ) 1 5 ； 3 ) o 1 p 0 9 9 ，其中脓o 7 最佳； 4 ) 1 q 1 0 0 0 0 。 在本文所述的蚂蚁算法中，取口= 1 ，口= 1 ，p = 0 7 ，q = i 。 2 2 2 、a c o s 算法的伪代码 s t e p l 、p 。0 7 ；f 。2 1 0 ；f 。r 。5 ；气= l r m a x ，v i ，j = l n 口= 1 ，口2 1 ； 生成初始解s ，计算其最优值v b e s t ； s t e p 2 、f o rk = l n t n t 为迭代次数 f o ra n t = l n a f o r i = l n 对每个工件j 计算能见度和转移概率p ；i ； 生成随机数p ，根据随机数p 和转移概率r 确定位置i 上的工件 e n d 得到当前的最优排序s b ； 对s b 进行局部改进，计算目标值； 根据目前得至4 的最优排序s b 计算f f ； 如果得到的最优排序s b 的目标值比原来s 的目标值好，令s = s b ； e n d 勺2 p + f + f ，v i ，j = l 1 1 ； e n d s t e p 3 、得到最优排序s ，计算最优目标值。 9 2 2 3 、a c o s 算法分析 在a c o s 算法中使用了2 - o p t 即两交换法对解进行局部改进。所谓2 - o p t 方 法就是将两个边交换，这里就是将两个位置上的工件进行交换( 见图二 。 原始状态： r e 二e 三 三 2 - o p t 以后。 p e 二臣 三正工三 图二、2 - o p t 过程 蚂蚁算法虽然在一些组合优化难题上与其他启发式算法相比更具有竞争力， 但比之个别精致的局部改进算法比如t s 算法、模拟退火法等相比仍然是相形见 绌【3 】，所以在使用蚂蚁算法的过程中，一般都要使用一些局部改进的方法对解 进行优化。这里选择了使用2 - o p t 方法，一方面这种局部改进方法比较简单可行， 另一方面也方便与t s 算法进行比较。 从上面的伪代码中可以看出，由于局部改进2 - o p t 的复杂度为o ( n 2 ) ，所以 a c o s 算法的复杂度应该为o ( n t * n a + n 2 ) ，由于选择了n a 是个接近n 的数值， 所以实际的算法复杂度为o ( n t n 3 ) 。 2 。3 、单机捧序问题中的禁忌搜索算法 在t s 算法中，有三个因素非常关键，一是初始解，这是因为t s 算法对初始 解有非常强的依赖性，可以这么说一个好的初始解对于最终结果的影响是巨大 的；另一个是邻域的定义，邻域的定义可以有很多种，如果定义的太小，则可能 让t s 算法产生循环，无法跳出局部最优；第三个就是禁忌表的长度，长度太长 可能会使之跳过最优解，太短却可能陷入循环。 为了显示两种算法的公平性，首先对初始解的选择这里使用了w s p t 规则， 这点明显对t s 算法有利，这是因为a c o s 算法对于初始解不敏感，所以初始解的 好坏并不能对结果有很大的影响，而t s 算法却依赖于初始解；其次由于a c o s 算 法本身不存在邻域的问题，但在a c o s 算法中有2 o p t 的局部优化过程，所以在这 1 0 里对2 - o p t 和t s 算法中的邻域使用同样的定义；最后是在t s 算法中选用了7 作为禁 忌表的长度，这也是参考了历史实验的结果 1 7 】。 2 3 1 、邻域定义 t s 算法中对于邻域的要求很讲究，在尝试了几种邻域的定义方式后，最终 选定了下面的一种邻域： 设z o = 【z iz ：，2 。】是工件下标的一个排列，邻域定义为 n ( z o ) = 妇iz 是对z 0 中的一对z ，与z ，交换得到，i = 1 , 2 ，h ，= i + 1 ，”) 。 实验结果表明这样一种邻域的定义对于单件排序问题的解决是比较合适的。 在a c o s 算法中的2 o p t 也是使用了这样一种交换定义，这样才能比较公平的 比较a c o s 算法与t s 算法的结果。 2 3 2 、t s 算法伪代码 s t e p l 、选择初始可行排序s l 和迭代终止数k ，把禁止搜索表置空，置k = 1 ，s 。= s ，； s t e p 2 、从量的邻域里选择一个候选可行排序s ， 如果变换墨一s 被禁忌搜索元素禁止，令s 。= s 。，转s t e p 3 如果变换墨一s 没被禁忌搜索元素禁止，令s k + = s ，把变换的逆变换放 在顶部，把禁忌搜索表中的其他元素的位置依次下移一位，若禁忌搜索表的元素 超过固定的数，则删去最后的元素。若s 的目标函数值小于瓯的目标函数值，则 令s 。= s ，转s t e p 3 ； s l e p 3 、如果k _ k ，算法终止，否则令k = k + 1 ，转s t e p 2 。 2 3 3 、t s 算法分析 t s 算法的复杂度与其邻域的定义有很大的关系，在前面定义的邻域下，t s 算法的复杂度是o ( n t + n2 ) ，其中n t 为迭代次数。与a c o s 算法的o ( n t + n 3 ) 相比 其复杂度比较低，计算时间少，后面的实验数据也说明了这点。 2 4 、实验数据 对于这样一类排序问题，t 瓠l k d 给出一种随机生成例子的方法【2 2 1 ： ( 1 ) 每个工件的加工时间p ，在 1 ，1 0 0 1 这个区间内随机生成； ( 2 ) 每个工件的权值w ，在【1 ，1o 】这个区间内随机生成； ( 3 ) 每个工件的完工期限d 在区间 睁n 一t f 一半，耖”卯+ 半， ，其中盯决定数据在区间肿心 位置偏向，r d d 决定区间的宽度。t f 、r d d 的值从集合 o 2 ，0 4 ，0 6 ，o 8 ) 之 中取。 本文中的实验将取5 种数据类型，分别是： ( 1 ) 、t f = o 8 ，r d d = 0 2 ， ( 2 ) 、t f = 0 8 ，r d d = o 4 ， ( 3 ) 、t f = 0 8 ，r d d - - o 6 ， ( 4 ) 、t f = 0 6 ，r d d = 0 8 ， ( 5 ) 、t f = 0 6 ，r d d = 0 6 。 事实上还有其他不同的”和r d d 的搭配，但是由于其他类型的数据将会使 目标函数值的结果比较小，难以显示出两种算法之间的差异性，因而挑选了卜面 5 种数据类型的数据来做比较。 2 5 、实验结果及分析 实验说明：所有的实验都在c p u 为a m d l 7 0 0 + ，内存为2 5 6 md d r ，系统 为w i n 2 0 0 0 的机器上运算，编程软件为m a t l a b ，本文中所有的实验皆如此。 实验一、对于不同的t f 、r d d 的取值，设计了5 组数据，每组数据1 0 个例子 分别对n = 2 0 ，n = 3 0 ，n = 4 0 的情况做实验，两种算法迭代次数限定为4 0 次，结 果见表2 ： ( 表格说明：a t 表示a c o s 算法的 结果要劣于t s 算法的结果的燃m 表示笔裂麓篆紫巾 表示t s 算法1 0 次计算的平均时间，a t 表示a c o s 算法1 0 次计算的平均时间 单位都为秒钟。) 表2 、不同数据类型的两种算法结果比较 t fr d da t a tt t a t 0 80 29100 9 2 80 4 5 4 6 8 8 5 7 9 0 80 49l00 8 8 40 4 5 7 98 9 5 1 5 n = 2 00 80 61 0 0 0 0 9 0 70 4 5 9 58 9 2 1 8 0 60 89l00 7 3 90 4 5 7 98 9 4 9 8 0 60 68200 8 2 50 4 5 3 l8 9 1 4 0 0 80 263l0 9 7 51 0 7 0 23 0 7 2 3 5 0 80 41 0000 9 0 41 0 6 8 53 0 6 5 0 1 n = 3 00 80 61 0000 9 1 61 0 8 1 43 0 3 7 8 o 6o 890l0 8 1 91 0 7 6 43 0 3 3 1 2 0 60 61 0000 7 2 l1 0 8 2 93 0 4 5 0 80 29l00 9 6 1 2 1 5 1 4 8 0 1 9 3 8 o 80 41 00 0 0 9 0 2 2 1 4 0 88 0 3 8 2 7 n = 4 0 0 8 0 69010 9 1 92 1 8 1 28 1 ，0 0 6 2 0 60 81 00 0 0 7 8 3 2 1 6 4 27 9 9 6 7 0 60 6 1 0 0 00 8 0 92 1 0 4 77 8 ，1 9 8 5 分析实验一当中的数据，可以发现在固定迭代次数的基础上，a c o s 算法得 到的解要优于t s 算法，在所有的例子里，a c o s 算法有9 2 的例子得到的结果 要优于t s 算法的结果。而对于不同的数据类型，从表2 中可以发现两者之间的 优势有明显的不同，其中当t f = 0 。6 、r d d = 0 8 和t f = 0 6 、r d d = 0 6 这两种情况 的结果a c o s 算法要明显好于t s 算法，而当t f = 0 8 、r d d = 0 2 的时候，a c o s 算法要略好于t s 算法，但差距不是很明显。从实验数据中可以说明，a c o s 算 法适用于不同情况的数据类型，且在数据比较偏重于数据区问的中心的时候 ( t f = 0 6 ) 效果更好。 a c o s 算法与t s 算法相比一个劣势在于计算时间比较长，其实从两种算法 的复杂度以及表2 中的计算时间可以发现这两种算法之间差n a 倍( 也就是i 3 倍， 因为a c o s 算法中设h a = n ) ，也就是差蚂蚁的个数的倍数。由于a c o s 算法本身 有一个比较好的特性就是这是一种隐并行算法，也就是每只蚂蚁都可以独立使用 一个计算机计算，所有的蚂蚁进行并行运算，这样每台机器的计算时问其实也就 将与t s 算法的时间差距不大了，这也就是a c o s 算法的优势。 实验二、对于不同的运算时间，设计了两组数据，计算时间分别为3 0 s 、6 0 s ，每 组随机生成5 个例子，令n = 7 0 ，t f = 0 6 ，r d d = 0 6 ，结果见表3 、表4 ： 表3 ：t = 3 0 s 的情况 l 2345 总和 t s 算法 5 05 05 4 6 45 72 7 5 a c o s 算法 5 35 44 56 46 52 8 l ( 统计说明：表格中的数据为计算结果，a c o s 算法结果与t s 算法结果相同的 次数为1 次，优于t s 算法结果的次数为1 次，劣于t s 算法结果的次数为3 次， 需= 1 0 2 1 8 ， 表4 ：t = 6 0 s 的情况 12345 总和 t s 算法 6 7 5 8 4 67 18 23 2 4 a c o s 算法 4 44 95 06 47 82 8 5 ( 统计说明：表格中的数据为计算结果，a c o s 算法结果优于t s 算法结果的次 数为4 次，劣于t s 算法结果的次数为1 次，尝鬈黼= 8 7 9 6 ) 分析实验二当中的数据，可以发现如果固定计算时间，在时j 、b j 比较少的情况 下( 3 0 s ) ，t s 算法要优于a c o s 算法；而当计算时间较多的情况下( 6 0 s ) ，a c o s 算法的结果要优于t s 算法，这说明t s 算法的收敛速度要比a c o s 算法快，但 在时问比较充裕的情况下，a c o s 算法有着自己的优势，这是因为t s 算法虽然 有禁忌表，但是依然可能会陷在某个局部邻域中无法跳出，而a c o s 算法却能 非常好的跳出局部最优，能够更加接近全局最优解。 纵观上面两个实验虽然结果看起来a c o s 算法要优于t s 算法，但并不是说 t s 算法就不好，因为t s 算法的优差取决于其初始解和禁忌表的长度等因素，事 实上有很多t s 的改进方法可以很好的提高t s 算法的解。这里做出这样的比较， 只是说明a c o s 算法与其它的一些类似t s 算法的启发式算法相比，有更好的寻 找全局最优的能力。 2 6 、a c o s 算法迸一步分析 ( 一) 、寻解过程分析 三只蚂蚁鲤耳解站栗 图三 图三给出的是所有蚂蚁中三只蚂蚁所找到的解( 未做过局部改进) ，由图二 可以发现每只蚂蚁的寻解过程其实并没有明显的收敛趋势，这是因为能见度的设 置和以及对信息素强度设置了上下限的缘故，由于蚂蚁数并不是很多，不同的蚂 蚁的选择由于随机性的问题选择不同，使得能见度和信息素变化很快，解不会很 快就成熟。还有这也可能与问题的解的空间有关，由于可行解可能有非常多，造 成不同的蚂蚁走不同的路都能找到较好的解，从而使得解很难收敛起来。 4 0 只蚂蚁母敬选代的平均结果 图四 图四表达的是4 0 只蚂蚁在每次迭代过程中的解的平均值，也就是每个点都 是一次迭代的均值结果，由于这个结果是在局部改进以前得到的，所以可以发现 当所有的蚂蚁搜寻完一次后，所得的结果也没有明显的收敛性，原因与图一的原 因可能相同，似乎可以认为蚂蚁算法的解其实发散的。 以上的结论仍只是一种猜想，还有待理论上的支持。这也是以后对于蚂蚁算 法本身特性值得研究的地方。 ( 二) 、其它改进思路 此外，还可以对蚂蚁算法进行进一步的改进，如果选择t s 算法而不是2 - o p t 来进行局部改进的话，则可以充分利用这两种算法的优势，得到的结果将会更好， 而时间上则不会增加太多，这是因为t s 算法与2 - o p t 的复杂度都是o ( n 2 ) ，只是 t s 算法多了一个n t 次迭代的次数，所以从时间上来说两者差距并不大，却能得 到不错的效果。 最后由于蚂蚁算法对目标函数的不敏感性，这里设计的a c o s 算法完全适 用于其它的目标函数的问题。 第三章、蚂蚁算法解决平行机排序问题 3 1 、平行机排序问题描述 平行机排序问题是多处理机排序问题的一种情况。平行机排序问题的研究在 理论和应用上都有重要的意义。在理论上，平行机排序问题是单机排序问题的推 广：在应用上，平行机排序问题则具有更广泛的实际背景。 在平行机排序问题中，通常假定有n 个任务t = 正，疋，l ) ，m 台处理机 p = 毋，最，己) ，处理机类型分为同速机、恒速机和变速机，对于同速机，其 加工速度均相同，通常设为l ；对于恒速机，其加工速度向量为b = ( 反，6 ：，b 。) ， 其中处理机p 的加工速度为b 。( i = 1 , 2 ，m ) 。在这两种情况下，任务集的加工时 间向量均设为p = ( a ，p 2 ，p ，) ，其中，任务的加工时间为p ，( = 1 , 2 ，) 。 如果处理机是变速机，则任务的加工时间与处理机加工速度之问的关系可以用加 工时间矩阵p 来表示。 p = p l h 。p 2 月 p m n 其中，任务一的加工时间为p 。( f - 1 , 2 ，m ，j = 1 , 2 ，一) 。 这晕考虑最一般的情形即变速机的问题，因为从上面的定义可以知道同速机 和恒速机都是变速机的特殊情况。此外这里主要考虑不可中断时间表长问题，即 n t 过程中工件不可被中断，必须完成一个才能换上下一个。目标函数研究最小 时问表长问题，即c 一问题，用三元组记号为胄。0c 一。 出于对于同速机不可中断极小化时间表长排序问题己0c 。是n p - - 难问 题，即使是对两台处理机也是如此【1 4 】。所以对于更一般情形的月，l c 。，这个 问题也是n p 一难的，此结论明显成立。 3 2 、平行机排序问题的蚂蚁算法 平行机排序问题由于有了i l l 台机器，所以就不能再使用前面单机排序问题 中的蚂蚁算法的思路，因为这里已经不再是只有1 1 个位置让n 个工件去选择了。 这也可能就是为何尚未发现研究此类问题的蚂蚁算法的文章的原因。 由于这里研究的是c m 。问题，工件一旦安排在某个机器上以后，该台机器上 的工件的加工顺序不需要考虑，由此得到一个思路，将工件与机器对应，对每个 工件选择其合适的机器来加工。不过与单机排序问题的分派不一样的是对于单 机排序问题中的n 个位鼍一旦被分派出去就不能再重复使用了，而这罩的m 台 机器却可以重复使用。由于除了工件选择问题上其它的问题与单台的机器差别不 是很大，所以参数上的选择与a c o s 算法中的基本一致，但在工件选择方面和 局部改进方面都不再一样，这里为了与a c o s 算法区别，记这种算法为a c o p 算法。 a c o p 算法与a c o s 算法的区别主要在于工件选择和局部改进这两个方面。 工件选择就如前文所述，在于可以选择的位置是可重复的：而局部改进这里不再 单纯使用2 - o p t 这种局部搜索方式，这是由于其工件选择的方式不同，所以在2 - o p t 的基础上再加上对不同机器的选择，即不仅仅两台机器上的工件之间可以进行交 换，每个工件还可以选择其它的机器进行加工( 见图五) 。由于不需要考虑每台 机器上的加工顺序，所以这种交换方式是可行的。 两台机器上的工件进行交换： p l p 2 一台机器上的工件改到另一台上加工： p l p 2 图五：a c o p 算法的工件交换过程 a c o p 算法流程与a c o s 算法类似，这里就不再重述。 9 挚 日 野 3 3 、平行机排序问题的t s 算法 与a c o s 算法一样，这里也与t s 算法进行比较，只是这里的t s 算法的邻 域定义与a c o p 算法中的局部改进的定义一样，同时为了给t s 算法一个比较好 的初始解，这里使用这样一个规则；对每个工件，选择一个加工时间最短的机器 来加工。 3 4 、实验结果及分析 由于这里只有工件的加工时间这一个变量，所以在设计实验数据的时候只是 简单的在区间f 1 ，1 0 0 当中随机生成。 实验一、这里分别考虑了2 0 、4 0 、6 0 个工件和2 、3 台平行机的情况，每组实验 1 0 次，实验结果见表5 ： ( 说明：a t 表示a c o p 算法的结果要 劣于t s 算法的结果的娥胛表示篙筹糍器筹巾表和 算法1 0 次计算的平均时间，a t 表示a c o p 算法1 0 次计算的平均时间，单位都 为秒钟。) 表5 ：a c o p 算法与t s 算法比较 a t弋t t瓯 m = 2n = 2 0 46o0 9 9 4 l0 8 0 0 17 5 8 7 5 n = 4 0 64o0 9 9 5 63 0 9 22 8 3 1 5 6 n = 6 09l00 9 9 2 96 9 3 4 66 3 5 5 9 5 m = 3n = 2 0 640 0 9 7 4 4 1 1 3 7 51 0 5 2 0 4 n - - 4 0 9ol0 9 7 0 74 3 0 4 63 9 。2 0 3 2 n = 6 02170 9 9 9 89 9 8 5 88 9 8 7 2 从实验一的结果中可以发现，对于m 不大的情况下比如m = 2 、3 ，a c o p 算 2 0 法较t s 略好，但差距不是很明显。在所有的例子中有6 0 的例子a c o p 算法得 到的结果要优于t s 算法，有2 6 7 的例子两种算法得到的结果相等。出现这种 差距不明显的情况一方面与算法本身有关系，另一方面也可能是因为目标函数的 设定造成不同解之间差距很小。 实验二、下面考虑1 0 0 个零件，2 台机器的情况，两种算法分别计算l o s 和3 0 s ， 每组实验5 次。实验结果见表6 、表7 ： 表6 ：t = l o s 的情况 l2345 总和 t s 算法1 8 3 81 8 5 51 7 7 71 8 8 81 6 6 69 0 2 4 a c o s 算法 1 8 3 41 8 4 11 7 7 41 8 8 31 6 6 3 8 9 9 5 ( 统计说明；表格中的数据为计算结果，a c o p 算法结果优于t s 算法结果的次 数为s 次，锅需铲= 9 9 6 8 ， 表7 ：t = 3 0 s 的情况 l23 45 总和 t s 算法 1 7 8 41 7 6 01 6 5 41 8 9 31 7 0 88 7 9 9 a c o s 算法 1 7 7 21 7 4 91 6 4 81 8 5 3 1 6 9 98 7 2 1 ( 统计说明：表格中的数据为计算结果，a c o p 算法结果优于t s 算法结果的次 数为s 次，篙器铲圳小， 从实验二的结果中可以发现，a c o p 算法与t s 算法相比，在3 0 s 内的结果 之比较1 0 s 内的结果之比小，这说明时间较多的情况下，a c o p 算法更有可能找 到较优的解。这与a c o p 算法的随机性有关，其更适合于全局寻优。 3 5 、a c o p 算法迸一步分析 根据其它的实验发现，当m 比较大的情况下，t s 算法的优势很明显，a c o p 2 算法即使计算的时间比较长也得不到较t s 算法更好的解。这首先与蚂蚁算法的 设计上有关，与单机排序问题一样，可以想象如果将蚂蚁算法的局部改进方法从 2 - o p t 改成为t s 算法，则得到的结果会有明显的改进，此外这可能与这种问题的 解的空间结构特点有关。由于可行解比较多，再加上其一定的随机性，使得蚂蚁 寻到的可行解并不是一个很好的初始解，虽然同样有局部优化过程，但与t s 算 法相比依然有差距。因此当m 较大的时候，如果使用蚂蚁算法加上t s 算法的局 部搜索也许会更有优势。 a c o p 算法只适用于目标函数为类似c 。的问题，对于其它形式的目标函数 还需要重新进行设计。 第四章蚂蚁算法解决车间作业排序问题 4 1 、车间作业排序问题描述 多处理机的另一种情况是多类型机( d e d i c a t e d p r o c e s s o l 苫) 。多类型机指的是 m 个处理机具有不同的功能。在多处理机环境中，被加工的任务需要在不同的处 理机上加工。这就是车间作业排序问题。在这类问题中有三种类型的问题，分别 是同顺序作业问题、自由作业排序问题和异顺序作业排序问题。 设甩为每个工件需要加工的机器数，如果每个作业需要在每个处理机上加 工，即”，= m ，= 1 , 2 ，胛，而且每个作业的工序也相同，即在处理机上的加丁 的顺序相同，把这里车间排序问题称为同顺序作业或流水作业( f l o ws h o p ) 。 如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之 为异顺序作业( j o bs h o p ) 。 如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把它 称为自由顺序作业或开放作业( o p e ns h o p ) 。 车间作业排序问题除个别少数问题外，均无多项式算法。这里主要研究的是 同顺序作业排序问题，也称为流水作业排序问题。其一般问题模型为：设有m 台处理机p = 鼻，最，只) ，1 1 个作业j = i ，。，以，以，各作业在每台处理机上 都需要加工。作业，在处理机只上的加工记为工序毛，其加工时问为 p 。( f = 1 , 2 ，m ，= 1 , 2 ，挖) 。各作业依次在处理机e ，最，己上完成各道工序。 为了简化问题，这里主要考虑只有两台处理机的情况。 对于只有两台处理机的同顺序排序问题f 2 0 c 一，有一个常用的算法是 j o h n s o n 算法。而这里研究的是一类特殊的目标函数问题，即在满足使得最大加 工时间c 一最小的基础上，寻求所有工件加工时间之和c ，最小化，这样的问 题记为f 2 1 | l e x ( c , 。，c ，) ，虽然f 2 i i c 。是有多项式时间算法，但由于 e 2 1 1 c ，已经是强n p 一难的问题 1 4 】，因此f 20l e x ( c 。x ，q ) 也是强n p 一难 的问题 2 3 1 。 4 2 、同顺序作业问题，20 上蹦( c m 缸，c f ) 的蚂蚁算法 在文 1 0 】中设计了一种变形的蚂蚁算法来解决f 2 | | l e x ( c ，c ，) ，之所以 称为变形是由于其忽视了能见度因子和转移概率这两个概念，而这两个其实是蚂 蚁算法中不可缺少的概念。没有了这两个概念，文 1 0 】中给出的算法其实也只能 算是一个学习型的启发式算法，并没有真正体现出蚂蚁算法思想的过程，这里记 该算法为a c o l 算法。本文根据a c o 算法的基本思想给出了一个解决 f 2 i jl e x ( c 。，c j ) 问题的蚂蚁算法，记为a c o f 算法。本文将对a c o f 算法、 a c o l 算法以及t s 算法同时进行比较。而与t s 算法的比较则是文【l o 中所未曾 涉及的。 4 2 1 、“c 一检查”的基本思想 a c o f 算法与前面的其它蚂蚁算法最大的区别在于，在a c o f 算法中，使用 “c 。检查”这一规则。使用c 。检查这一规则的原因是为了使所寻找的解都满 足最大加工时间c 一最小化的这个约束条件。 在介绍“c 一检查”这一规则以前要先介绍一下j o h n s o n 算法【1 4 。算法如 下： ( 1 ) 把工件按工序加工时间分为两个子集；j l = i p ， 见， 。对于满足于p u = p 2 ，的工件可以分在两个子集中的任一个 当中； ( 2 ) 先将集合一中的工件按p l j 不减排列( s p t 规则) ，再将集合以中的工件按 p ：，不增扫 列( l p t 规则) 。 在书 1 4 】中证明了j o h n s o n 算法对于f 20c 。这样一个问题产生的解是最优 解，但需要说明的是，不满足j o h n s o n 算法规则的排序也可能是最优排序。 “( _ 。检查”的过程就是首先利用j o h n s o n 算法计算出对于整个工件集 ，= ，l ，2 ，以) 的f 20 c 一问题的最优目标值v b e s t ，然后定义已经在前i 一1 个 位置上排好的工件集为t t ，然后在第i 个位置上寻找最合适的工件i ，再令剩下 未排的工件集合为s ，利用j o h n s o n 算法先对集合s 进行排序，然后按次序得到 排序c r j s ，如果排序t r j s 所求出的q 。的目标值等于v b e s t ，则认为j 符合“c 。 检查”，也就是在第i 个位置上的工件可以是j ；否则认为第j 个工件不合适，寻 找下一个除了工件j 以外最合适的工件，然后再次进行“c 。检查”。很明显， 如果排序o - j s 所求出的c 。的目标值等于v b e s t ，那么一定存在一个f 2 | | c m 。问 题的最优排序且其前面部分工件的排序正好为盯j 。而且使用这样一种规则也能 保证一定能至少找到一个f 2ol e x ( c m a x c ，) 问题的可行解。 4 2 2 、a c o f 算法的基本思想 对于f 20 l e x ( c 。，c j ) 这样的一种问题，由于是流水作业，旦工件的 先后次序定了，则在每台机器上的加工顺序也就定了，所以完全可以看作类似于 单台机器加工的方法来解决，a c o f 算法与a c o l 算法的区别在于转移概率、 能见度的设计以及工件选择的方式，而与前面的蚂蚁算法的区别则在于其“c m 。、 检查”和工件选择的方式。 a c o f 算法中的能见度的定义为r a2 面i 瓦了吉丽其中i 是第i 台机器已经排好工件的总加工时间。这样设计的好处在于从直观上来看，加工时 间较短的工件似乎更应该被放到前面来加工。转移概率的定义以及其他参数设置 则与a c o s 算法中的一致。 由于a c o f 算法中也使用了“c 检查”，这样就造成其在工件加工上不能 再像以前的蚂蚁算法一样可以直接根据转移概率来选择工件。所以这里就仿照文 【7 】设计了一种方法，即设计一个概率p ，当生成的随机数大于p 的时候，就从未 排序的工件中按顺序挑选满足“c 。检查”的工件；当随机数不大于p 的时候， 就按照转移概率的大小从大到小的选择满足“c m 。检查”的工件。 在一只蚂蚁得到一个可行解以后，还是需要对其进行局部搜索优化，这罩仍 然采用2 - o p t 方法，但在每次交换的过程中，还必须重新计算c 。，显然只有满 足c 。最小的交换才是可行的。 4 2 3 、a c o f 算法的伪代码 s t e p i 、p = 0 7 ；r 。2 1 0 ：f 。2 f 一5 ；气= r 。，v i ，j 2 1 n 口= 1 ，口= 1 ：p = 0 9 ； 根据j o h n s o n 算法生成初始解s ，计算其最优值； s t e p 2 、f o rk = l n t n t 为迭代次数 f o ra n t = l n a f o ri = l n 对每个工件j 计算能见度巩和转移概率； 生成随机数p p i f p p p 从未排序的工件中按顺序挑选满足“c 一检查”的工件； e l s e 按照转移概率的大小选择满足“c 一检查”的工件； e n d e f l d 得到当前的最优排序s b ； 利用2 - 叩t 对s b 进行局部优化，计算目标值； 根据目前得到的最优排序s b 计算“； 如果得到的最优排序s b 的目标值比原来s 的目标值好，令s = s b e n d 2 p + 勺+ a t f ，v i ，j = l n ； e n d s t e p 3 、得到最优排序s ，计算最优目标值。 2 6 4 3 、同顺序作业问题f 2 | | l e x ( c m 戡，c ，) 的t s