Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

12.1 Introduction

The observation of living organisms is an interesting research field not only for biologists. A new current within artificial intelligence called swarm intelligence acquired significance in the 1990s [15]. Those studies were inspired by observation of animals and insects living in colonies [44]. We have finally got successful experiments and methods based on ant or termite colony observation [13, 20, 43, 45]. Observations of birds in V-formation inspired many researchers to create and to develop the concept of particle swarm optimization. [24]. Those studies in the field of AI were also inspired by information obtained from marine biologists on the collective intelligence of a shoal of fish or plankton. Other sources of inspiration stemmed from the development of industry, in particular the automotive industry in that case. Particle swarm optimization was created thanks to studies on, among others, sandblasting of a car body or other corroded metal parts. Hence, generally, this branch of AI has been called swarm intelligence [11, 14, 25, 38]. Conversion of those intelligence mechanisms prevailing among simple individuals into the field of computer systems resulted in creation of the current sometimes called computational swarm intelligence. It exists parallel to the branch of science called multiagent systems and those two fields often overlap one another. Although they are often not directly based on associations with colonies of living organisms, they are often similar in their rules of operation. They enable creation of interesting implementations in the domain of parallel computing. The development of swarm intelligence was preceded by the development of multiple-valued logic, in particular, fuzzy logic. The author of fuzzy logic is an American professor at Columbia University in New York City and Berkeley University in California, Lotfi A. Zadeh, who published the paper entitled “Fuzzy Sets” in the journal, Information and Control, in 1965 [5]. He defined the term of fuzzy set there, thanks to which imprecise data could be described using values from the interval (0,1). The number assigned to them represents their degree of membership in this set. It is worth mentioning that in his theory Zadeh used the article on three-valued logic published 45 years before by a Pole, A. Janukasiewicz [6]. That is why many scientists in the world regard this Pole as the "father" of fuzzy logic. The next decades saw the rapid development of fuzzy logic. As the next milestones in the history of that discipline one should necessarily mention L-R representation of fuzzy numbers proposed by D. Dubois and H. Prade [7, 8], which enjoys great success today. Coming back to the original analogy, an observer can see a trend, that is, a general increase during a rising tide or decrease during low tide, regardless of momentary fluctuations of the water surface level. This resembles a number of macro- and micro-economic mechanisms where trends and time series can be observed. The most obvious example of that seems to be the bull and bear markets on stock exchanges, which indicate the general trend, while shares of individual companies may temporarily fall or rise. The aim is to capture the environmental context of changes in the economy or another limited part of reality. Changes in an object described using fuzzy logic [30, 32] seem to be thoroughly studied in many papers. But it is not necessarily the case as regards linking those changes with a trend [39, 41, 42]. This might be the opportunity to apply generalizations of fuzzy logic which are, in the opinion of authors of that concept, W. Kosiński [9,10,11] and his team [12, 13], Ordered Fuzzy Number (OFN) [28, 33, 40]. There are already interesting studies available published by well-known scientists [1, 18] that present successful implementation of fuzzy logic to swarm intelligence methods, including methods inspired by ant and termite colonies. However, according to the best knowledge of the authors of this chapter, nobody thus far has published studies on implementation of ordered fuzzy logic into ant colony optimization. This fact was one of the reasons for execution of the research described in this chapter. The main emphasis here is on application of a new hybrid method of ant colony optimization (ACO) with implemented decision logic of an ant calculated in the OFN domain in order to solve the optimum route selection problem. To make a comparison, the authors selected several well-known ant methods and several heuristic methods dedicated to solving the same problem, the methodology of which does not use either swarm intelligence or, in particular, ACO.

Fig. 12.1
figure 1

ACO block diagram

Full size image

12.2 Application of Ant Colony Algorithms in Searching for the Optimal Route

Ant colony optimization is currently one of the best known ant colony algorithms. It was first defined by Dorigo, Di Caro, and Gambardell in 1999 [16] as a method for discrete optimization problems. ACO was presented as the algorithm that can find a good route using a graph. It was inspired by foraging theory [14] both for ant colonies and for discrete optimization problems. This algorithm is designed for solving two kinds of static and dynamic optimization problems. In the general case, ant colony optimization is performed according to the diagram shown in Fig. 12.1). Studies of ant colony algorithms commenced based on observation of ant colony environments. The scientists noticed the interesting fact that ants communicate mainly using chemical substances which they produce. As has already been mentioned, the key matter in this algorithm is indirect foraging communication represented by pheromone trace. The advantage of the evaporation of that pheromone is that it can prevent convergence for local optimum solutions. Assuming there is no evaporation issue, each time each path selected by the first artificial agents would be treated in the same way and would be equally attractive, which would make it inapplicable to optimization problems. Thus, when one ant finds a good path from the colony to the food source, this path becomes preferable for other ants. The idea behind the ACO [13] algorithm is to follow that behavior using artificial agents moving within the frame of a graph in order to solve a given problem. The ACO algorithm has been used for solving the traveling salesman problem. This algorithm has an advantage over genetic algorithms or the simulated annealing algorithm. Its important feature is that for a dynamically changing graph, the ACO algorithm can work continuously and it can adapt to the changes in real-time. Thanks to such properties, it has been applied to the method of solving the problem of network routing and urban transportation systems.

Route selection: An ant shall travel the distance from point i to point j with the probability of:

$$\begin{aligned} p_{ij}=\frac{(\tau ^{\alpha }_{ij})(\eta ^{\beta }_{ij})}{\sum (\tau ^{\alpha }_{ij})(\eta ^{\beta }_{ij})} \end{aligned}$$
(12.1)

where \( \tau _{ij}\) is the quantity of pheromone on the route i,j, \(\eta _{ij} \) defines attraction of the route i,j, \( \alpha \) is the parameter used for effect control \( \tau _{ij}\), and \(\beta \) is the parameter used for effect control \(\eta _{ij}\).

Pheromone update: This issue is represented by the following formula.

$$\begin{aligned} \tau _{ij}=p\tau _{ij}+\varDelta \tau _{ij} \end{aligned}$$
(12.2)

where \(\tau _{ij} \) is the quantity of pheromone on the route i,j, \(\varDelta \tau _{ij} \) represents the quantity of remaining pheromone, and P is the pheromone evaporation scale.

Below, we present a more detailed pseudocode of one of the numerous ant colony algorithms, called the ACS (ant colony system), that is, ant colony optimization. Tables 12.1 and 12.2 present the most important ant colony optimization algorithms dedicated to TSP in the chronological order of their publishing. In the methodological sense, all the algorithms listed below and described in the following section are direct successors of the ant system. This is due to an obvious reason, the ant system method, which has become the foundation for the entire new branch of knowledge, was the first worldwide success of then young scientist, Marco Dorigo. Now Professor M. Dorigo [14] is a world-class expert in the field of swarm intelligence. The set of methods presented below is in chronological order.

figure a

12.3 OFNAnt, a New Ant Colony Algorithm

Implementation of OFN to the ant colony system consists mainly in determination of the trend and in establishing relationship to the order of the OFN. This order is used in OFNAnt in two ways. It is related to pheromone evaporation on the route and its mathematical description, and it also concerns the decision-making process of a single ant.

Table 12.1 ACO algorithms that have already been applied to the TSP
Full size table
Table 12.2 List of analyzed problems including their optimum values
Full size table

The pheromone quantity on the route is updated in accordance with OFN arithmetic. If the pheromone trace (quantity) on the route increases, then this trend is marked as a positive order trend, whereas if this quantity decreases it is marked as a negative order trend. Each pass of the kth ant, which is associated with placing pheromone trace results in the update of the pheromone trace on the route by the amount left by the ant resulting in positive order on the route with increasing trend and with negative order for decreasing trend of the route. The above relationship is pursuant to the formula:

$$\begin{aligned} \tau _{ij}[l_{A},1^{-}_{A},1^{+}_{A},p_{A}]\leftarrow \tau _{ij}[l_{A},1^{-}_{A},1^{+}_{A},p_{A}] + \sum ^{m}_{k=1} \varDelta \tau ^{k}_{ij}[l_{k},1^{-}_{k},1^{+}_{k},p_{k}] \end{aligned}$$
(12.3)

Every ant constructs a complete route, and the ants make a decision at each stage of the route construction. This creates a multistage process of fuzzy control. When talking about route construction, we usually refer to the situation when an ant located in town i wants to go to town j and makes a decision based on the following information.

  1. 1.

    Parameters defining the effect of the pheromone trace \(\tau ^{\alpha }_{ij} \).

  2. 2.

    (b) Parameters defining the effect of heuristic information \(\eta ^{\beta }_{ij} \), used to estimate attraction of the route.

  3. 3.

    \(N^{k}_{i}\) Parameter representing the list of k available neighbors of an ant. The "available" neighbors mean the towns that have not been visited yet.

Fig. 12.2
figure 2

An ant located in the town i selects next town j

Full size image

The decision-making process taken by an ant at each node of the route is associated with calculation of fuzzy probability in the OFN sense. The probability is calculated pursuant to the following redefined formula of the route selection probability (Fig. 12.2).

$$\begin{aligned} P^{k}_{ij}[l_{A},1^{-}_{A},1^{+}_{A},p_{A}]=\frac{\vert \tau _{ij}[l_{A},1^{-}_{A},1^{+}_{A},p_{A}]\vert ^{\alpha } \vert \eta _{ij}[l_{A},1^{-}_{A},1^{+}_{A},p_{A}]\vert ^{\beta }}{\sum _{l\in N^{k}_{i}}\vert \tau _{ij}[l_{k},1^{-}_{k},1^{+}_{k},p_{k}]\vert ^{\alpha } \vert \eta _{ij}[l_{k},1^{-}_{k},1^{+}_{k},p_{k}]\vert ^{\beta } } \end{aligned}$$
(12.4)

12.4 Experiment

12.4.1 Experiment Execution Method

In this section, the author compares the effectiveness of heuristic methods, metaheuristic methods, and the new hybrid method OFNAnt. All those methods are tested using 10 benchmarks for their performance in solving an NP-hard problem such as TSP. Thus, it is a comparison of well-known algorithms with a completely new approach represented by OFN arithmetics implemented to control an ant colony in order to solve optimizing problems [21, 22, 27]. They are tested according to the following principles.

  1. 1.

    As regards ant colony algorithms, a program with implemented method is run three times at t \(=\) 10 for each problem, and for implementation of heuristic algorithms a program is also run three times, but without additional parameters.

  2. 2.

    Effectiveness of a given algorithm is assessed as follows:

    • By specification of the obtained result (route length)

    • As a percentage, that is, optimum achieved in x%, as presented in the table including the set of benchmarks

  3. 3.

    A graph showing the effectiveness of individual algorithms is presented for each of the 10 problems.

  4. 4.

    Each such graph is provided with a short summary where the obtained results are discussed.

  5. 5.

    An overall graph showing the effectiveness of all algorithms is presented at the end. The value optimum achieved in x% is totaled for each algorithm, and thus the overall score per 1,000 available points is calculated. Such a data presentation allows easy assessment of the hierarchy of all the algorithms on the basis of the 10 benchmarks used for tests.

12.4.2 Software Used for Experiment

The author’s own implementation of ant colony methods developed in JAVA language was used in the experiments and the results obtained by the implementation were verified on the basis of ACOTSP [14]. The author’s OFNAnt method was added to the implementation. The CONCORDE application was developed to solve symmetric TSP-type problems and other problems of network optimization [3, 17]. The application is supported by the Office of Naval Research, National Science Foundation, and by the School of Industrial and System Engineering at the Georgia Institute of Technology, United States. This program uses the cutting planes algorithm. The interface of the program shows the optimum solution searching process displayed at the end of each main iteration. The edges are colored according to currently calculated LP value (linear programing relaxation). At the moment when a new, better solution is found, the color of edges is changed to red. The program includes several algorithms designed to create edges used by the program to search for the optimum solution. Those algorithms include:

  1. 1.

    Delaunay triangulation

  2. 2.

    Minimum spanning tree

  3. 3.

    Different variations of nearest neighbors

The program also includes several heuristic [2] algorithms for the TSP problem. Those algorithms include:

  1. 1.

    Greedy algorithm (GR)

  2. 2.

    Boruvka algorithm (BOR)

  3. 3.

    Quck Boruvka algorithm (QBOR)

  4. 4.

    Nearest neighbor algorithm (NN)

  5. 5.

    Lin-Keringhana algorithm (LK)

Table 12.3 List of analyzed problems including their optimum values
Full size table

12.4.3 Experimental Data

Table 12.3 shows 10 benchmarks selected from the TSPlib library of TSP problems, including the expected optimum value for each. They were applied in a way described in the previous paragraph as a set of benchmarks for testing well-known algorithms and a new OFNAnt method.

12.5 Results of Experiment

A number of tests were performed according to the above-specified rules, using 10 selected problems. Results of individual tests are presented below assisted by the diagram and a brief note for each.

Eil51 The authors presented an experiment for 51 towns, the optimum value for which amounts to 426. As a result of the calculations 7 out of 10 algorithms generated an optimum result. It is worth noting that only one classical algorithm (ALK) generated the best result. Other ALK algorithms showed low effectiveness for a relatively small problem. All ant colony algorithms showed excellent performance when solving the above problem (Fig. 12.3).

Fig. 12.3
figure 3

Graphical representation of the results for the problem Eil51

Full size image

D198 Another test was performed for 198 towns and it showed the advantage of ant colony algorithms (ALM) over ALK algorithms again. This time 5 out of 10 available ALM algorithms have found the optimum, but AS achieved a result only 0.01% worse than the optimum. The best ALK, namely Lin-Kernighan achieved 99.70% of the optimum, which is quite a good result. Other ALK algorithms achieved only 88% of the optimum value (Fig. 12.4).

Fig. 12.4
figure 4

Graphical representation of the results for the problem D198

Full size image

Pcb442 represents the problem covering 442 towns. It is the hardest problem thus far, because only 3 out of 10 tested algorithms, BWAS, EAS, and ACS have found the optimum. MMAS missed the best solution by only 0.01%. Leading algorithms as regards this problem also include, respectively: ASRK with the result of 99.79%, AS 99.64%, and LK 99.43%. As can be noted, 3 ALM algorithms achieved optimum, one missed the optimum by the skin of its teeth, then, two further ALM algorithms achieved very good results and, again, the best of the ALK algorithms, that is, LK was the last on the list. The remaining ALK algorithms performed even worse than for the problem with 318 towns and achieved from 80 to 87% of the optimum (Fig. 12.5).

Fig. 12.5
figure 5

Graphical representation of the results for the problem Pcb442

Full size image

Rat783 represents the problem covering 783 towns. In this case 3 algorithms achieved optimum solution, namely EAS, MMAS, and ACS; BWAS missed the optimum solution by 0.02%, and ASRK missed it by 0.07%. For the first time we have the situation where the ALK algorithm, that is, LK with the score of 99.72% outdistanced a representative of ALM algorithms, the AS algorithm with the score of 99.69%. Other ALK algorithms were unrivaled (Fig. 12.6).

Fig. 12.6
figure 6

Graphical representation of the results for the problem Rat783

Full size image

Pr2392 The last of the 10 presented problems was also the biggest one as it included as many as 2,392 towns. There is no doubt that the bigger the problem is, the worse the solutions. The first four places on the list were taken by ALM algorithms, where ACS was the best with the score of 99.59%. One of the ALK algorithms, namely LK, was fifth on the list with the score of 98.63%. Two subsequent places on the list were taken by ALM algorithms, that is, by EAS with the score of 98.39% and by AS with the score of 97.80%. The remaining ALK algorithms followed the trend of worse solutions and with the increased problem complexity they achieved from 79 to 85% of the optimum.

12.6 Summary and Conclusions

Having performed a number of experiments according to the rules specified above, one can be certain about the superiority of ant colony algorithms over classical algorithms (Fig. 12.7). There was only one case out of 10 studied samples, where the Lin-Kernighan (LK) algorithm achieved better results than all other known methods, including ant colony methods. This could have resulted from the nature of the problem, that is, nrw1379. In that case the results obtained by the LK algorithm were only slightly worse than the results of the OFNAnt algorithm. For the remaining files, the LK algorithm outpaced, at best, only older ant colony methods, AS and EAS. The remaining algorithms from the group of heuristic methods performed definitely much worse than the leading algorithms. They fulfilled the optimum solution within the range from 79 to 89%, which is far from the results of the leading algorithms. The noticeable feature of the studied group of algorithms is their tendency for worse results with the increase of problem magnitude. A clear example of that tendency is the seventh tested problem, pcb1173. This statement is confirmed by problem d1291 and further large datasets. The diagram presented above, which summarizes all performed tests, shows the hierarchy of all algorithms and their respective scores. The maximum available score is 1,000 points. The scores closest to the maximum were achieved by representatives of ant colony algorithms, including OFNAnt with the score of 999.31 points. It is worth noting that the first four places on the list of optimum solution searching efficiency are taken by ant colony algorithms. Subsequent places on the list are taken by representatives of heuristic methods with their definite leader, the LK algorithm, which is widely regarded as one of the best methods for solving the traveling salesman problem. Ant colony algorithms represent a new generation of optimizing algorithms using a metaheuristic approach to NP-hard problems, the approach that gave excellent results. Ant colony algorithms find many more applications other than TSP. Those applications include many real-life fields. Based on the results of experiments with the new method using trend and fuzzy logic, one can also expect obtaining interesting solutions for problems other than those where ant colonies have already been successfully applied. The new method, OFNAnt, which is a hybrid combination of ACO and OFN, and introduces fuzzy decision of an ant, is the first known attempt to implement the arithmetic of Ordered Fuzzy Numbers to ant colony optimization. Performed experiments confirmed efficiency of that method in solving TSP problems. Currently, there are ongoing works on application of the modification of that method for solving problems of other classes.

Fig. 12.7
figure 7

Graphical representation of the results for the problem Pr2392

Full size image