In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s phe...In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s pheromone trails and reinforcing trails at best paths until eventually a single path is followed. On the other hand, RFD is based on copy- ing how drops form rivers by eroding the ground and de- positing sediments. In a rough sense, RFD can be seen as a gradient-oriented version of ACt. Several previous experi- ments have shown that the gradient orientation of RFD makes this method solve problems in a different way as ACt. In particular, RFD typically performs deeper searches, which in turn makes it find worse solutions than ACt in the first exe- cution steps in general, though RFD solutions surpass ACt solutions after some more time passes. In this paper we try to get the best features of both worlds by hybridizing RFD and ACt. We use a kind of ant-drop hybrid and consider both pheromone trails and altitudes in the environment. We apply the hybrid method, as well as ACt and RFD, to solve two NP-hard problems where ACt and RFD fit in a different manner： the traveling salesman problem （TSP） and the prob- lem of the minimum distances tree in a variable-cost graph （MDV）. We compare the results of each method and we an- alyze the advantages of using the hybrid approach in each case.展开更多
对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(rescheduling rus...对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(rescheduling rush jobs with loads locked on single machine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.展开更多
文摘In this paper we hybridize ant colony optimiza- tion （ACt） and river formation dynamics （RFD）, two related swarm intelligence methods. In ACt, ants form paths （prob- lem solutions） by following each other＇s pheromone trails and reinforcing trails at best paths until eventually a single path is followed. On the other hand, RFD is based on copy- ing how drops form rivers by eroding the ground and de- positing sediments. In a rough sense, RFD can be seen as a gradient-oriented version of ACt. Several previous experi- ments have shown that the gradient orientation of RFD makes this method solve problems in a different way as ACt. In particular, RFD typically performs deeper searches, which in turn makes it find worse solutions than ACt in the first exe- cution steps in general, though RFD solutions surpass ACt solutions after some more time passes. In this paper we try to get the best features of both worlds by hybridizing RFD and ACt. We use a kind of ant-drop hybrid and consider both pheromone trails and altitudes in the environment. We apply the hybrid method, as well as ACt and RFD, to solve two NP-hard problems where ACt and RFD fit in a different manner： the traveling salesman problem （TSP） and the prob- lem of the minimum distances tree in a variable-cost graph （MDV）. We compare the results of each method and we an- alyze the advantages of using the hybrid approach in each case.
文摘对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(rescheduling rush jobs with loads locked on single machine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.
