بهینه سازی کلونی مورچه ها همراه با برنامه های مهاجران برای مسئله پویای فروشنده سیار با عوامل ترافیک

Traditional ant colony optimization (ACO) algorithms have difficulty in addressing dynamic optimization problems (DOPs). This is because once the algorithm converges to a solution and a dynamic change occurs, it is difficult for the population to adapt to a new environment since high levels of pheromone will be generated to a single trail and force the ants to follow it even after a dynamic change. A good solution to address this problem is to increase the diversity via transferring knowledge from previous environments to the pheromone trails using immigrants schemes. In this paper, an ACO framework for dynamic environments is proposed where different immigrants schemes, including random immigrants, elitism-based immigrants, and memory-based immigrants, are integrated into ACO algorithms for solving DOPs. From this framework, three ACO algorithms, where immigrant ants are generated using the aforementioned immigrants schemes and replace existing ants in the current population, are proposed and investigated. Moreover, two novel types of dynamic travelling salesman problems (DTSPs) with traffic factors, i.e., under random and cyclic dynamic environments, are proposed for the experimental study. The experimental results based on different DTSP test cases show that each proposed algorithm performs well on different environmental cases and that the proposed algorithms outperform several other peer ACO algorithms.

Ant colony optimization (ACO) algorithms emulate the behaviour of real ant colonies when they search for food from their nest to food sources. Ants communicate via their pheromone trails in order to complete this “food-searching” task as efficiently as possible. ACO algorithms have proved to be effective optimization methods in many real-world applications [16], [17], [20] and [42]. Traditionally, researchers have focused on ACO to address static optimization problems (SOPs), e.g., the travelling salesman problem (TSP). For SOPs, the environment remains fixed during the execution of algorithms [3], [5] and [34]. However, in many real-world problems, we have to deal with dynamic environments [31]. For dynamic optimization problems (DOPs), the problem may change over time regarding the objective function, decision variables, problem instance, constraints, and so on. Such uncertainties may change/move the optimum, and, thus, the problem becomes more challenging and has much in common with many real-world scenarios. The aim, when solving SOPs, is to obtain an optimal or near-optimal solution efficiently, whereas for DOPs the aim is to track the optimal solution over time with the environmental changes. ACO algorithms can adapt to dynamic changes since they are inspired from nature, which is a continuous adaptation process [31]. More precisely, they can adapt to dynamic changes by transferring knowledge from past environments [7]. However, traditional ACO algorithms cannot adapt well to dynamic changes once the ants reach the stagnation behaviour, where ants follow the same path, since the pheromone will be distributed into a single trail. Therefore, using the pheromone trails of the previous environment in the new environment will not be sufficient since ants will be biased by the previous path even after a dynamic change. The algorithm loses its adaptation capability since it does not maintain the diversity within the population. A simple way to address this problem is to consider every change as the arrival of a new problem instance which needs to be solved from scratch and re-initialize the pheromone trails. However, this restart strategy is computationally expensive and usually not efficient. Recently, developing strategies for ACO algorithms to enhance their performance for DOPs and increase their adaptation capabilities has attracted a lot of attention [11]. The strategies developed include: (1) local and global restart strategies [27]; (2) pheromone manipulation schemes to maintain or increase diversity [21], [35] and [37]; (3) memory-based approaches [25] and [28]; and (4) memetic algorithms [36]. These methods have been applied to different types of dynamic TSPs (DTSPs) due to its importance for many real-world applications [39] and [42]. As we have seen in many evolutionary algorithms (EAs) for binary-encoded DOPs, immigrants schemes are effective when applied to different DOPs [49], [51], [55] and [60]. Immigrants enable an EA to maintain the diversity of the population at a certain level, by introducing new individuals into the current population [24]. A good start has been made on ACO algorithms for permutation-encoded DOPs, where immigrant ants are generated to the population [35] and [37]. In [35], the random immigrants ACO (RIACO) and elitism-based immigrants ACO (EIACO) have been applied on a DTSP where the cities are exchanged with other cities stored in a spare pool over time. In [37], the memory-based immigrants ACO (MIACO) has been applied on a DTSP with traffic factors. The difference between RIACO, EIACO, and MIACO lies on the way immigrants are generated. In RIACO, EIACO, and MIACO, immigrants are generated randomly, using the best ant from the previous environment as the base to generate immigrants, and using the best ant from a memory as the base to generate immigrants, respectively. In this paper, we further investigate the performance of ACO algorithms with immigrants schemes on different dynamic test cases. RIACO, EIACO and MIACO are applied on two novel variations of DTSPs, e.g., DTSP with random and cyclic traffic factors, and they are systematically constructed from several static TSP problem instances. A series of different DTSPs are generated to investigate the weaknesses and strengths of RIACO, EIACO, and MIACO for solving DTSPs. This paper also carries out experiments on sensitivity analysis with respect to several important parameters, such as the immigrants replacement rate, the size of the memory structures used in the proposed framework and the range of the traffic factors, on the performance of the investigated ACO algorithms for DTSPs. Moreover, the proposed algorithms are compared against several peer ACO algorithms on DTSPs. The rest of the paper is organized as follows. Section 2 describes the field of dynamic optimization. Section 3 describes the proposed DTSPs variations. Section 4 describes a conventional ACO for DOPs. Section 5 describes existing approaches on different DTSPs. Section 6 first describes the framework of ACO algorithms with immigrants schemes and then describes the proposed algorithms. Section 7 presents and analyzes several experimental studies for different key parameters and compares the proposed algorithms with existing ones. Finally, Section 8 concludes this paper with discussions on the directions for future work.

Different immigrants schemes have been successfully applied to EAs to address different DOPs [52] and [60]. In this paper, we integrate immigrants schemes with ACO to address a permutation-encoded DOP, i.e., the DTSP with traffic factors. We generate two types of dynamic environments: (1) the traffic factor changes randomly; and (2) the traffic factor changes in a cyclic pattern where the environments will re-appear. Three algorithms are proposed, i.e., RIACO, EIACO, and MIACO, where random immigrants, elitism-based immigrants, and memory-based immigrants are generated, respectively, and replace the worst ants in the current population in order to transfer knowledge to the pheromone trails and maintain diversity, which is important when addressing DOPs. From the experimental studies of comparing the proposed algorithms on different cases of DTSPs, the following concluding remarks can be drawn. First, immigrants enhance the performance of ACO for DTSPs. Second, RIACO performs well in quickly and significantly changing environments. Third, EIACO performs well in slowly and slightly changing environments. Fourth, MIACO performs well in cyclic changing environments, where previous environments will re-appear. Fifth, the proposed algorithms perform better than other peer ACO algorithms in DTSPs. Sixth, the evaporation rate in MMMMAS and the long-term memory size in MIACO depends on the magnitude of a dynamic change. Seventh, a high level of diversity or too much knowledge transferred do not always enhance the performance of ACO in DTSPs. Hence a good balance between the diversity generated and the knowledge transferred achieves good performance in DTSPs. Finally, a small immigrants replacement rate is usually a good choice for RIACO, EIACO and MIACO in DTSPs. For future work, it will be interesting to adapt the replacement rate instead of using a small fixed value [61]. Another future work is to include the dynamic time-linkage (DTL) property [4] and [40], where the value at time t is dependent on at least one earlier solution, to the traffic factors. DTL is very common in real-world applications. For example, in a car navigation systems where traffic factors are considered, if the optimal routing path for a specific destination is provided to all cars at the current moment, then the traffic on the same “optimal” route will increase and make the route no longer optimal or congested in the future