Sage Journals: Discover world-class research

Abstract

This article presents a critical evaluation of swarm intelligence techniques for solving combinatorial optimization problems. Since, unarguably, the traveling salesman’s problem is the most developed, studied, and popular combinatorial problem, this study uses it as a benchmark. After a number of experimental investigations involving 24 popular but complex benchmark symmetric traveling salesman’s problem instances and 15 asymmetric traveling salesman’s problem of the 19 instances available in TSPLIB95, the African buffalo optimization proved to be the best algorithm in terms of efficiency and effectiveness in solving the problems under investigation.

Keywords

Swarm intelligence techniques combinatorial optimization traveling salesman’s problems

Introduction

The recent advances in science and engineering have led to the merger of several disciplines in multidisciplinary researches that have led to several scientific and technological breakthroughs the world over. One of the visible areas of interdisciplinary research is in robotic engineering.¹ Robotics basically involves the interaction and utilization of principles and concepts between mathematics, chemistry, physics, artificial intelligence, electronics, and mechanical engineering in the design of hardware that can move and act in different ways to achieve a given objective.^2,3 The interaction of artificial intelligence and robotics helps to create machines that emulate man and other animals.⁴ In fact, robots are only as “intelligent” as the artificial intelligence techniques/programs that control them.⁵ One of the biggest contributions of artificial intelligence (AI), therefore, is the creation of “smarter” robots. Examples of these smarts robots include robotic pets,⁶ robotic cockroaches,⁷ robotic toys, robotic tennis players, advanced prostheses,⁸ and so on. The traveling salesman’s problem (TSP), which is a popular concept of artificial intelligence, finds relevance in robotics especially in robotic flow shops, multirobot routing, robotic path planning, and so on.^9,10 Furthermore, in robotics, to unravel the traveling costs between two goals/targets for a robot, there must, first, be a plan for a collision-free path between the targets and the robot, hence the need for TSP principles.¹¹

In virtually all manufacturing processes, cost reduction without compromising efficiency and effectiveness is a major consideration all over the world. The quest for cost minimization and profit maximization has led researchers to investigate the possibility of drawing inspiration from nature to attempt solutions to myriads of problems in engineering, science, mathematics, economics, technology, and industrial processes. These efforts have yielded several dividends, leading to the proposal of a number of bioinspired algorithms such as the ant colony optimization (ACO),¹² African buffalo optimization (ABO),¹³ firefly optimization (FFA),¹⁴ honeybee mating optimization for TSP (HBMO-TSP),¹⁵ particle swarm optimization (PSO),¹⁶ genetic algorithm (GA),¹⁷ bat algorithm (BA),¹⁸ adaptive simulated annealing with greedy search (ASA-GS),¹⁹ and so on. These algorithms have been applied to solve a number of optimization problems such as TSP,²⁰ numerical optimization of benchmark test functions,²¹ tuning of proportional, integral and derivative (PID) controllers,²² vehicle routing,²³ networking and other logistic problems,²⁴ among others, with amazing results. In general, bioinspired algorithms have been one of the major scientific breakthroughs in the past three decades through their exploitation of intelligence characteristics of animals, plants, and other natural elements in the ecosystem in their cooperative or competitive mechanisms in arriving at solutions.

In particular, swarm intelligence algorithms refer to the branch of optimization algorithms that simulate and model the imprecision, randomized, and stochastic features of these physical, chemical, or biological elements in arriving at marvelous solutions. The sheer number of the existing swarm intelligence techniques (scores of them, actually) creates room for healthy comparative performance assessments of these algorithms in order to assist researchers and users, in general, in determining the “best” choice whenever there is an optimization problem to solve. This is the motivation for this study.

Specifically, this article examines the application of some metaheuristics (FFA, simulated annealing (SA), ABO, GA, PSO, ACO, BA) and two hybrid-algorithms-turned-heuristics (HBMO-TSP and ASA-GS) to solve the benchmark TSP available in TSPLIB95.²⁵

The rest of this article is organized as follows: The second section examines combinatorial optimization and the comparative algorithms; third section deals with the experimental setting, simulation outcomes, and discussions; a critical evaluation of the performances cost considerations is the focus of the fourth section; and the final section draws conclusions on the study.

Combinatorial optimization

Combinatorial optimization is a branch of computer science that is concerned with searching for an optimal object/path/method/solution among a set of objects/paths/methods/solutions especially in situations where an exhaustive search is not feasible. Examples of such problems include the minimum spanning tree problem, the packing problem, the TSP, and so on.²⁶

The TSP is about the most popular combinatorial problem in literature today. It is basically the problem of a particular salesman who has customers scattered all over a big city or in a number of locations within a geographical area. The salesman has a duty to visit all of his customers and then return to an initial starting location with the constraint of visiting each location only once and possibly not repeat a route. The objective is to identify the closest or cheapest route. The concept of the TSP has found application in a number of real-life situation in industry such as in car assembly plants where car manufacturers need the cheapest and fastest procedure to assemble cars. Other application areas include a post office official who is required to deliver mails to different locations and then return to the initial starting location, a school bus driver who is required to pick school children from various locations and return them to their homes after school, robotic path planning, robotic scheduling, and so on.^20,27

The TSP consists of two kinds of problems, namely, symmetric and asymmetric TSP. In the symmetric TSP, the distance/cost between location a to b is the same as that between location b to location a in all instances in the graph. On the other hand, in the asymmetric TSP, there exists, at least, an instance in the graph where the distance/cost between locations j to k is not the same as that between location k to j. ²⁸

Comparative algorithms

In discussing the performance assessment of swarm intelligence techniques, this study examines nine optimization algorithms comprising of seven metaheuristics and two hybrid algorithms designed to serve as heuristics. Heuristic algorithms refer to such methods that are developed to provide solutions to some specific kinds of problems by thoroughly exploiting some a priori knowledge of the problem under consideration. There are of less scope than the mataheuristics. The use of heuristics enable algorithms to obtain quality solutions to difficult optimization problems at a reasonable time, even though they are still near-exact algorithms, like their metaheuristic counterparts.²⁹ That is to say that heuristic algorithms do not guarantee the exact optimal solutions.

Metaheuristics, on the other hand, simply means “beyond heuristics” and are generally expected to have broader applications than heuristics through the use of intelligent memory, experiential, and other biases to help guide the search process.³⁰ In general, metaheuristic algorithms employ some local search in addition to global exploration through the use of randomizations. Randomizations help these algorithms to steer away from being restricted to a local environment to a more global search. The overall aim of any metaheuristic algorithm is to achieve the best possible result by using internal mechanisms to achieve adequate exploration and exploitation of the search space.³¹ Broadly, metaheuristics have wide applicability ranging from bioinformatics to telecommunications, robotic engineering, economics, manufacturing,³² and so on.

Similarly, hybrid algorithms is simply the combination of two or more heuristics and/or metaheuristics in order to solve a problem. The benefit of algorithm hybridization is to harness the strengths of each of the algorithms while avoiding their particular noticeable weaknesses. The overall benefit of hybridization of algorithms being greater efficiency and effectiveness of the search enterprise.³³

Genetic algorithm

The GA was developed by John Holland in the early 1970s as a model of biological evolutions which uses such operators as selection, crossover, mutation, and inversion. It uses the computation to represent a population of individuals as x–y chromosomes in the form of character strings. The selected individuals in a population are made to evolve through crossover and mutations to form the next generation from where the best generations are selected to form the next generation. This process is continued until we arrive at the optimal or near optimal solution to a particular problem. Real-life applications of GAs include automotive design, robotics, airline revenue management, control engineering, water resource management, software testing, and so on.^34,35

The GA was originally invented to optimize problems that can be represented as a vector of binary values. In such problems, the GA has proven to be very effective. The efficiency of the GA is, however, in doubt, partly because it employs a complicated fitness function in addition to its use of several parameters such as population size, crossover, mutation rate, recombination, selection operator, and so on.³⁶ The GA pseudocode is shown in Figure 1.

Figure 1.

GA pseudocode. GA: genetic algorithm.

Ant colony optimization

This is one of the most popular metaheuristic algorithms in literature. The ACO algorithm was developed by Marco Dorigo and Di Caro in 1999 after some initial work on the ant system by Marco Dorigo and ant colony system by Dorigo and Gambardella.³⁷ The ACO was inspired by the random walk of ants in search of food. Once a food source is located, the ant that discovered the food carries a particle of the food and, as it returns to the nest, usually follows a shorter route and continually deposits some amount of pheromones as a way of informing other ants of its breakthrough. The neighboring ants, perceiving the scent of the pheromone, will likely join the successful ant to track the food source.

Once these ants get to the food source, they, in turn, carry some fragments of the food and on their way back to the nest, drop pheromones as they further optimize the route of the initial ant. This process increases the pheromone concentration on the favorite ‘shortest’ route and in that process attracts other ants. Within a short while, the colony of ants are on the optimized route moving to and from the food source. On the other hand, when an ant arrives at the food and could not find food, may be, because that food is exhausted or the particular ant missed the direction of the food source, on its way back, it drops no pheromone and so with time that route loses its attraction due to pheromone evaporation. This situation leads the ants to explore other areas.³⁸ The ACO pseudocode is presented in Figure 2.

Figure 2.

ACO pseudocode. ACO: ant colony optimization.

Particle swarm optimization

PSO, inspired by the flocking of birds and schooling of fishes in search of food, was proposed by Kennedy and Eberhart as a population-based, stochastic, global optimization technique with the aim of being simple, easy to implement yet efficient search technique.³⁹ Till date, it has proven to be a very successful algorithm enjoying wide applicability in several problem domains. The PSO harnesses the velocity and positions of these simple ants in its search for solutions.

Each agent, called particles in PSO, represents a solution to the problem being solved using five major parameters, namely, the current position, the particles’ best position, the best position found by its neighbor, the individual particle’s knowledge of its best position achieved so far, as well as its current velocity. Using a simple rule, a particle updates its velocity and position with each iteration as the algorithm progresses until it reaches termination condition. Moreover, an information repository is maintained that documents the best achieved objective function values for each particle involved in the search process.³⁹

PSO models the behavior of, for example, a swarm of birds searching for a food source. The entire particles converge on the best solution through the use of the information gathered by each particle, the neighboring particle, as well as that obtained from the entire flock. The algorithm starts by initializing the particles in the search space, followed by updating the position and velocity of each particle in each iteration. The PSO pseudocode is presented in Figure 3.

Figure 3.

PSO pseudocode. PSO: particle swarm optimization.

Honeybee mating optimization algorithm for the TSP

HBMO-TSP is a hybridization of HBMO algorithm, the expanding neighborhood search strategy, and the multiple phase neighborhood search-greedy randomized adaptive search procedure algorithm. It is a successful experiment of developing a hybrid algorithm to serve as a heuristic.¹⁵ The HBMO-TSP is presented in Figure 4.

Figure 4.

HBMO-TSP pseudocode. HBMO-TSP: honeybee mating optimization for traveling salesman’s problem.

Adaptive simulated annealing with greedy search

ASA-GS is a recently developed local search algorithm based on SA and with components of greedy search method designed primarily to solve the TSP. It is another successful experiment to adapt a metaheuristic into a heuristic in order to obtain an effective and efficient performance. This algorithm is a combination of SA with three kinds of mutations and different probabilities during its search.

The ASA-GS uses greedy search mechanism to speed up its convergence rate. Similarly, it employs such parameters as cool coefficient of the temperature, greedy search time, compulsive accept time, and the probability of new solution accept probability parameters depending on the size of the TSP instance.¹⁹ The ASA-GS pseudocode is shown in Figure 5.

Figure 5.

ASA-GS pseudocode. ASA-GS: adaptive simulated annealing with greedy search.

African buffalo optimization

The ABO algorithm is a simulation of the movement and herd management structure of the African buffalos as they move around the African deserts, savannah, and forests in search of lush grazing lands. The African buffalos manage their large herds of, sometimes, up to 1200 using two major sounds: /waaa/ asking the buffalos to further explore the landscape and /maaa/ sounds that require the buffalos to further exploit their immediate environments for possible solutions (see ABO pseudocode in Figure 6).

Figure 6.

ABO pseudocode. ABO: African buffalo optimization.

Bat algorithm

The BA is a swarm intelligence optimization algorithm developed in 2010 by Yang.⁴⁰ The BA simulates and models the echolocation or biosonar features of microbats (see Figure 7). Since its design and implementation, a few other variants of this algorithm have been developed.

Figure 7.

BA pseudocode. BA: bat algorithm.

The classical BA and its variants such as the improved BA have been successfully applied in a wide range of fields. Some of these fields are the continuous optimization, TSP, clustering problems, combinatorial optimization, image processing, and so on.¹⁸

Firefly optimization

This population-based algorithm, which was inspired by the flashing attitude of fireflies, was developed by Xin-She Yang.⁴¹ In this algorithm, a number of fireflies work together to solve a problem through bioluminescent glowing that enables them to efficiently solve problems. The solutions to problems are modelled as a firefly whose flashes are proportional to the quality of solutions they represent. As a result, a brighter firefly attracts other colleagues, and this aids further exploration of the search space.

The four main characteristics of the algorithm include⁴²

All fireflies are unisex, so they are attracted by a brighter colleague notwithstanding the sex.

The brightness of a firefly is a function of the distance between the fireflies: the nearer they are to one another, the more the effect of the brightness of the brighter firefly and vice versa.

If there is no brighter firefly than a particular firefly, the firefly without a brighter colleague moves randomly.

The landscape of the objective function affects the brightness of the firefly. The brightness of the firefly is proportional to the objective function in a maximization problem. The FFA pseudocode is presented in Figure 8.

Figure 8.

FA pseudocode.

Experiment

The experiments in this study were performed with the aid of a MATLAB code and executed in a MATLAB 2012b by Mathworks Inc. Compiler on Intel Duo Core™ i7-3770 CPU, 3.40 GHz with 4 GB RAM.

To authenticate the veracity of the comparative algorithms in solving the TSP, the authors carried out experiments on about 24 symmetric and 15 asymmetric TSP TSPLIB95.⁴³ The city coordinates data are available in literature.⁴⁴

Experimental parameters

For the sets of experiments involving PSO, the parameters are as follows: population size, 200; iteration (T _max), 1000; inertia weight, 0.85; C₁:2; C₂:2, rand1 (0,1) rand2 (0,1). For the experiments involving other algorithms, in this study, Table 1 contains the details of the parameters used. Also, it is important to note the following vital equations for ASA-GS

t_{cool} = α \times (N 0 . 5 - 1.0) (α \times N 0 . 5)

ρ = e - (F (cbest) - F (cold) / t_{current} \times (10.0 \times N / OPT))

Table 1.

Experimental parameters.

ABO		ACO		ASA-GS		HBMO		GA
Parameter	Values	Parameters	Values	Parameters	Values	Parameters	Values	Parameter	Values
Population	40	Ants	D*	Population	Number of nodes	Queen	1	Generation	100
	2.0	β	5.0	t _initial	1000	Drones	200	β	2.0
lp1	0.6	ρ	0.65	ρ	See equation (3)	Spermateca	50	ρ	0.1
lp2	0.5	α	1.0	Opt	Tour length	Mating drones	50	Ro	0.33
	1.0	qo	200	tv	N/10	Brood	50	Crossover rate	1.0
N/A	–	qo	0.9	t _current	t _current × t _cool	α	0.9	qo	0.9
N/A	–	N/A	–	t _cool	See equation (3)	Mating flights	1000	φr	0.3
N/A	–	N/A	–	t _end	0.005	w1	3	φ ρ	0.2
N/A	–	N/A	–	t _greedy	β × N	w2	4	τ _min	τ _max/20
N/A	–	N/A	–	N/A	–	ϕ	10⁻ ¹⁰	τ _max	1 − (1 − ρ)
Total number of run	50		50		50		50		50

ABO: African buffalo optimization; ACO: ant colony optimization; ASA-GS: adaptive simulated annealing with greedy search; HBMO: honeybee mating optimization; GA: genetic algorithm; N/A: not applicable.

Experimental data

In the first experiment, 10 benchmark TSP instances from the TSPLIB⁴⁵ ranging from 52 cities to 14,051 cities were investigated. The choice of the TSP data sets is made in such a way as to test the capacity of the comparative algorithms in searching edges and nodes of less than 100 cities (Berlin52, St70, Pr76, and Rat99) to searching TSP of less than 200 cities (Pr107, Pr124, Ch130, Pr152, and U159) and then to problems that run to a few hundreds of cities (Rat575 and Brd14051). The stopping criterion is when there is no more improvement in the best result obtained by the comparative algorithms.

Experimental results and discussion

In evaluating the performance of swarm intelligence techniques in solving combinatorial optimization problems, the performance of popular and very effective cum efficient algorithms in literature, namely, PSO, ABO, ACO, and the GA^9,10 was investigated in the first experiment. The experimental parameters are presented in Table 1, and the simulation results are shown in Table 2.

Table 2.

Comparative experimental results.

TSPLIB problem	TSPLIB values	ABO		PSO		ACO		GA
		Best	Rel. error %	Best	Rel. error %	Best	Rel. error %	Best	Rel. error %
Berlin52	7542	7542	0	7542	0	7549	0.09	7542	0
St70	675	676	0.15	717.53	6.3	696.62	3.2	710.49	5.19
Pr76	108,159	108,167	0.01	118028	9.13	110,917	2.55	115,329	6.63
Rat99	1211	1211	0	1278	5.53	1236	2.06	1269	4.79
Pr107	44,303	44,407	0.01	44,436	0.3	44,354	0.12	44,417	0.26
Pr124	59030	59,058	0.05	59,283	0.43	59,113	0.14	59,247	0.37
Ch130	6110	6111	0.02	6181.4	1.15	6141	0.51	6158.3	0.79
Pr152	73,682	73,730	0.07	73,898	0.29	7,3835	0.21	73,872	0.26
Rat575	6773	6777	0.06	6910	2.02	6876	1.52	6897	1.83
Brd14051	469,385	469,835	0.1	477,346	1.7	476,949	1.61	477,304	1.69

Rel. error % = relative error percentage; best = best result obtained by an algorithm; ABO: African buffalo optimization; PSO: particle swarm optimization; ACO: ant colony optimization; GA: genetic algorithm.

In Table 2, relative error percent values were obtained with the formula

Rel . error = ((Best - TSPLIB value) / TSPLIB value) \times 100

As can be seen in Table 2 and Figure 9, the ABO clearly proved to be more effective than the other algorithms (PSO, ACO, and GA) in that it was able to obtain the closest solution in all the test cases under investigation. For instance, apart from obtaining the closest results to the optimal solution, the ABO got optimal results in Berlin52 and Rat99 and the ACO in u159. Meanwhile, the PSO and the GA were only able to obtain the optimal result in Berlin52. Similar trend can be observed in the paired samples statistical test outcome where ABO has the least mean score of −64.4000000 standard deviation of 19.4482779 as well as least standard error mean of 44.0974174 when compared with the optima (see the shaded portion of Table 3).

Figure 9.

Simulation output chart.

Table 3.

Paired samples test.

		Paired differences					t	df	Significance (two-tailed)
		Mean	Standard eeviation	Standard error mean	95% Confidence interval of the difference
		Mean	Standard eeviation	Standard error mean	Lower	Upper
Pair 1	Optima – ABObest	–64.4000000	139.4482779	44.0974174	–164.1552887	35.3552887	–1.460	9	.178
Pair 2	Optima – GAbest	–1587.5790000	3145.2593537	994.6183390	–3837.5619997	662.4039997	–1.596	9	.145
Pair 3	Optima – PSObest	–1874.9930000	3738.3480199	1182.1694429	–4549.2460730	799.2600730	–1.586	9	.147
Pair 4	Optima – ACObest	–1079.6620000	2431.4963404	768.9066558	–2819.0496990	659.7256990	–1.404	9	.194

Using the cumulative relative error as a yardstick, the cumulative relative error percentage of ABO is a mere 0.57% compared to PSO’s 26.85%, ACO’s 17.03%, and GA’s 21.81%. The outstanding performance of ABO is traceable to the algorithms use of relatively fewer parameters than its competitors. Another possible reason for the ABO’s effectiveness could be its use of straightforward calculation of fitness function. This development lends credence to the need for lean metaheuristics design as recently advocated by some experts.^23,46

Performance cost consideration

The primary focus of the second experiment is to investigate the performance cost of the algorithms because the time needed to get optimal or near-optimal solutions may be as important as the solutions themselves since time correlates with cost in production engineering as well as in business, generally. An efficient algorithm, therefore, has to be one that obtains good solutions at a reasonable time.⁴⁷ The CPU time was used to evaluate the algorithms’ performance cost in this study. The fastest CPU time spent in solving each of the benchmark TSP instances is indicated in Table 3. The comparative algorithms are The ABO, GA,⁹ HBMO,⁴⁸ ACO,¹⁰ SA,¹⁹ and ASA-GS.¹² The experiments were carried out using benchmark TSP cities ranging from 16 to 14,051 cities. The results are presented in Table 4.

Table 4.

Comparative performance cost considerations.

TSPLIB	ABO	GA	HBMO	ACO	SA	ASA-GS
Problem	(s)	(s)	(s)	(s)	(s)	(s)
Ulysses16	0.03	0.16	–	–	0.02	–
Eil51	0.04	1.16	0.17	112.1	3.77	3.91
Berlin52	0	2.77	0.19	116.7	3.07	3.83
St70	0.08	–	–	226.1	3.35	5.15
Pr76	0.08	6.73	0.53	272.4	2.63	5.49
KroA100	0.03	16.5	0.62	615.1	3.32	7.14
Tsp225	0.09	16.2	5.38	4039	–	–
Ch130	0.08	14.4	1.28	–	5.29	8
Rat99	0.09	26.4	0.58	–	4.83	–
Pr107	0.11	18.2	1.01	–	2	7.78
Pr124	0.07	20.5	1.08	–	1.93	9.01
Pr136	0.08	30.5	1.35	–	7.08	9.86
Pr152	0.09	31.1	2.21	–	3.69	10.85
Rat783	0.05	26.4	71.1	0.63	3.45	78.9
Brd14051	78.9	–	902	–	–	2081
Total	79.82	210.81	987.87	5381.69	44.43	2229.92

ABO: African buffalo optimization; GA: genetic algorithm; HBMO: honeybee mating optimization; ACO: ant colony optimization; SA simulated annealing; ASA-GS: adaptive simulated annealing with greedy search.

The good run of the ABO continues as can be seen in Table 4. The ABO, aside from its effectiveness in obtaining solutions, is also efficient in its search by utilizing fewer computer resources than its peers. The ABO obtained optimal solutions faster than every other algorithm under review here in all the test cases; the only exception being in Ulysses 16 where the SA marginally obtained a better result of 0.02 to ABO 0.03 s. The ABO’s exceptional performance becomes more glaring when one considers that the other algorithms are among the best in literature and were published only recently.¹⁰

A further analysis reveals that it took ABO a total of 79.82 seconds to solve all the 15 TSP instances under investigation (including, of course, the most time-consuming Brd14051). The GA spent 210.81 s to provide solutions to 13 cases excluding Brd14051. The HBMO spent 987.87 s; ACO took 5381.69 s for just six TSP instances; SA took 44.43 s for 13 test cases excluding the time-consuming Brd14051; and ASA-GS spent 2229.92 s for 12 TSP instances. From the foregoing discussion and analysis, it is safe to conclude that the ABO is at least 12 times faster than the HMBO and 27 faster than ASA-GS. Similarly, juxtaposing the TSP test cases attempted by the other algorithms with the results obtained by ABO in those same instances, the ABO is 59.24 faster than SA; 277.38 faster than the GA, and over 14,545 faster than ACO.

In conclusion, the ABO has proved to be more efficient than its peers. Again, its efficiency is attributable to its lean metaheuristic design concept coupled with its straightforward fitness, the regular communication among the buffalos, and regular updating of the location of the best buffalo in each iteration.

ABO, BA, and FFA

To conclude this evaluation, a third round of experiments were performed involving some of the most recently designed algorithms: the ABO, BA, and the FFA. These are some of the best performing algorithms in literature presently. They were designed with some of the latest designed technologies in mind. They could be referred to as the 21st century algorithms. The experiment involved 16 symmetric TSP and 15 ATSP test instances. The symmetric TSP test instances are Oliver 30, Eil51, Berlin52, St70, Eil76, KroA100, KroB100, KroC100, KroD100, KroE100, Eil101, Pr107, Pr124, Pr136, Pr144, Pr152, and Pr299. The asymmetric TSP instances are Br17, Ftv33, Ftv35, Ftv38, P43, Ftv44, Ftv47, Ry48p, Ft53, Ftv55, Ftv55, Ftv64, Ftv70, Ft70, Kro124p, and Rbg333. The experimental outcome of this investigation is presented in Table 5.

Table 5.

Simulation results of ABO, BA, and FFA.

TSP cases	Optima	ABO		BA		FFA
TSP cases	Optima	Best	Time	Best	Time	Best	Time
Oliver30	420	425		420	0.3	420	0.4
Eil51	426	426.38	0.040	430	1.7	426	1.6
Berlin52	7542	7542	0.002	7542	2.8	7542	2.2
St70	675	676	0.080	675	4.1	675	4.3
Eil76	538	538	0.033	538	5.5	543	5.3
KroA100	21,282	21,554	0.041	21,292	10.1	21,282	10.3
KroB100	22,140	22,160	0.060	22,373	12.1	22,183	11.6
KroC100	20,749	20,755	0.030	20,802	12.0	20,756	12.8
KroD100	21,294	21,347	0.022	21,727	12.6	21,408	12.4
KroE100	22,068	22,088	0.029	22,323	12.0	22,079	11.6
Eil101	629	640	0.027	640	13.5	643	13.3
Pr107	44,303	44,407	0.106	44,618	14.4	44,303	12.6
Pr124	59,030	59,058	0.074	59,030	19.7	59,030	18.8
Pr136	96,772	96,784	0.077	100,485	24.2	97,716	24.1
Pr144	58,537	58,587	0.028	58,588	29.9	58,546	30.9
Pr152	73,682	73,650	0.091	74,172	28.5	74,033	32.1
br17	39	39.9	0.028	39	0.4	39	0.2
ftv33	1286	1289	0.029	1348	1.8	1286	2.8
ftv35	1473	1481	0.030	1490	1.9	1473	2.7
ftv38	1530	1536	0.026	1530	2.5	1530	3.0
p43	5620	5645	0.080	5632	2.7	5620	2.8
ftv44	1613	1614	0.032	1725	4.2	1620	5.1
ftv47	1776	1777	0.029	1842	3.9	1795	5.5
ry48p	14,422	14,459	0.037	14,790	3.7	14,453	4.4
ft53	6905	6905	0.028	7105	5.1	6993	6.8
ftv55	1608	1610	0.029	1686	5.3	1628	7.0
ftv64	1839	1839	0.041	2068	6.2	1903	7.0
ftv70	1950	1955	0.049	2238	6.7	2173	7.8
ft70	38,673	38,753	0.039	2238	6.7	39,668	8.5
kro124p	36,230	36,275	0.056	40,070	13.2	39,438	15.8
rbg323	1326	1326	2.050	1713	237.4	1599	245.1
Total		3.323			448.8		528.8

ABO: African buffalo optimization; BA: bat algorithm; FFA: firefly optimization; TSP: traveling salesman’s problem.

Table 5 shows the excellent performance of the algorithms under investigation here. In terms of obtaining the optimal solution, all the algorithms did quite well. For instance, ABO obtained five optimal results to BA’s six and FFA’s 11. Those are commanding performances by the recently developed algorithms. However, a closer look reveals that ABO’s results were closer to the optimal results than the other two algorithms. Metaheuristics are actually near-exact algorithms.

Moreover, in terms of the efficiency of the algorithms, that is where there is a wide gulf in performances. The ABO was more efficient than the other algorithms in all test instances, whether in the symmetric or asymmetric cases. It obtained solutions in less time than the other algorithms. Overall, ABO spent 3.323 s to provide solutions to all the test instances. Meanwhile, the BA took 448.8 s and the FFA 528.8 s. As pointed out earlier, this is a major hallmark of a good algorithm.⁴⁷

Conclusion

This article examined some swarm intelligence techniques in providing solutions to combinatorial optimization problems, namely the symmetric and asymmetric TSP. The TSP, though an Artificial Intelligence concept, has been successfully applied to robotic path planning, robotic flow shop, robot routing, robotic scheduling, and so on.^49,27 After an investigation of 24 benchmark symmetric and 15 asymmetric test instances from the TSPLIB, the conclusion is that, overall, the ABO proved to be a more efficient and effective algorithm, then the FFA, HBMO, GA, BA, PSO, ASA-GS, ACO in that order. The reason for the good performance of the first two algorithms could be traceable to recent innovations in optimization algorithm design. The HBMO-TSP puts up a very good performance in spite of its use of several parameters. Its excellent showing could be because it was designed primarily for the TSP, thus serving as a heuristic.

Rather disturbing is the performance of ASA-GS that had a similar design concept like the HBMO-TSP but fell short of expectations. It proved to be a slow algorithm. This may be due to its use of several parameters. Finally, the ACO’s below par performance could be traceable to its use of path construction mechanism rather than the better-performing path-improvement mechanism trend of modern optimization algorithm development.

In view of the above findings, it is our belief that robotic researchers and engineers confronted with robotic path planning, flow shop, multirobot routing, and scheduling will find the findings of this study useful in their robotic designs and manufacturing. Finally, we recommend further research interdisciplinary investigations between artificial intelligence and robotics as we believe that these two disciplines hold a great promise for human development and advancement

Footnotes

Acknowledgements

This article is a revised and expanded version of a paper entitled “African Buffalo Optimization: A Swarm Intelligence Technique” presented at IEEE-IRIS 2015, October 18–20, 2015, Langkawi, Malaysia. The authors appreciate the Faculty of Computer Systems and Software engineering, Universiti Malaysia Pahang for funding and the Ministry of Higher Education, Malaysia, for financial assistance.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This study was funded by Faculty of Computer Systems and Software Engineering, Universiti Malaysia Pahang under grant GRS 1403118 and Ministry of Higher Education, Malaysia, under Fundamental Research Grant Scheme RDU 140101.

References

Padir

Chernova

. Guest editorial special issue on robotics education. IEEE Trans Edu 2013; 56: 1–2.

Benitti

FBV

. Exploring the educational potential of robotics in schools: a systematic review. Comp Edu 2012; 58: 978–988.

Joshi

. Some important aspects to enhance the quality of the technical education system for better industry-institute interaction. Strategic role of tertiary education and technologies for sustainable competitive advantage, vol. 222, 2013. Available at http://www.igi-global.com/chapter/some-important-aspects-enhance-quality/78443 (accessed 26 February 2017).

Rautaray

Agrawal

. Vision based hand gesture recognition for human computer interaction: a survey. Artif Intell Rev 2015; 43: 1–54.

Nilsson

. Principles of artificial intelligence. Burlington: Morgan Kaufmann, 2014.

Segura

Cramer

Gomes

. “Revive!: reactions to migration between different embodiments when playing with robotic pets.” In: Proceedings of the 11th international conference on interaction design and children, 2012, pp. 88–97.

Landgraf

Akkad

Nguyen

. A multi-agent platform for biomimetic fish. In: Conference on biomimetic and biohybrid systems, 2012, pp. 365–366.

McMullen

Hotson

Katyal

. Demonstration of a semi-autonomous hybrid brain–machine interface using human intracranial EEG, eye tracking, and computer vision to control a robotic upper limb prosthetic. IEEE Trans Neural Sys Rehabilitat Eng 2014; 22: 784–796.

Chen

Kong

Fang

. A fast two-stage ACO algorithm for robotic path planning. Neural Comput Appl 2013; 22: 313–319.

10.

Galceran

Carreras

. A survey on coverage path planning for robotics. Robot Auto Sys 2013; 61: 1258–1276.

11.

Arora

Gigras

Arora

. Robotic path planning using genetic algorithm in dynamic environment. Int J Comput Appl 2014; 89: 8–12.

12.

Di Caro

Dorigo

. AntNet: Distributed stigmergetic control for communications networks. J Artif Intell Res 1998; 9: 317–365.

13.

Odili

Mohmad Kahar

. African buffalo optimization (ABO): a new meta-heuristic algorithm. J Adv Appl Sci 2015; 03: 101–106.

14.

Arora

Singh

. The firefly optimization algorithm: convergence analysis and parameter selection. Int J Comput Appl 2013; 69: 48–52.

15.

Marinakis

Marinaki

Dounias

. Honey bees mating optimization algorithm for the Euclidean traveling salesman problem. Inform Sci 2011; 181: 4684–4698.

16.

Hui-liana

Xian-lib

. Discrete particle swarm optimization for TSP based on neighborhood [J]. Appl Res Comput 2011; 2: 30.

17.

Dong

Xue

. An ant system-assisted genetic algorithm for solving the traveling salesman problem. Int J Adv Comput Technol 2012; 4: 165–171.

18.

Osaba

Yang

Diaz

. An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems. Eng Appl Artif Intell 2016; 48: 59–71.

19.

Geng

Chen

Yang

. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search. Appl Soft Comput 2011; 11: 3680–3689.

20.

Odili

. Application of ant colony optimization to solving the traveling salesman’s problem. Sci J Elect Elect Eng 2013; 2013, 1: 175–177.

21.

Odili

Kahar

MNM

. Numerical function optimization solutions using the African buffalo optimization algorithm (ABO). British J Math Comput Sci 2015; 10(1): 1–12.

22.

Odili

Mohmad Kahar

. African buffalo optimization approach to the design of PID controller in automatic voltage regulator system. In: National conference for postgraduate research, Universiti Malaysia Pahang, Pekan, Pahang, 24–25 September 2016, pp. 641–648.

23.

Sörensen

. Metaheuristics—the metaphor exposed. Int Trans Operat Res 2015; 22: 3–18.

24.

Kunna

Kadir

TAA

Jaber

. Large-scale kinetic parameter identification of metabolic network model of E. coli Using PSO. Adv Biosci Biotechnol 2015; 6: 120.

25.

Reinelt

. “Tsplib95” Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR), Heidelberg, 1995. Available at https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ (accessed 26 February 2017).

26.

Wolsey

Nemhauser

. Integer and combinatorial optimization. John Wiley & Sons, 2014.

27.

Petiot

Chedmail

Hascoët

. Contribution to the scheduling of trajectories in robotics. Robot Comput Integrat Manuf 1998; 14: 237–251.

28.

Odili

Kahar

MNM,

Anwar

. African buffalo optimization: a swarm-intelligence technique. Proc Comput Sci 2015; 76: 443–448.

29.

Safari

. Wildlife and Big 5. http://sasafari.com/wildlife-and-the-big-five/, vol. 2016 (accessed 26 February 2017).

30.

Prakasam

Savarimuthu

. Metaheuristic algorithms and probabilistic behaviour: a comprehensive analysis of ant colony optimization and its variants. Artif Intell Rev 2015; 45(1): 1–34.

31.

Blum

Roli

. Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Sur (CSUR) 2003; 35: 268–308.

32.

Osman

Kelly

. Meta-heuristics: theory and applications. Berlin: Springer Science & Business Media, 2012.

33.

Espinosa-Aranda

Garcia-Rodenas

Angulo

. A framework for derivative free algorithm hybridization. In: Adaptive and natural computing algorithms. Springer, 2013, pp. 80–89.

34.

Dasgupta

Michalewicz

. Evolutionary algorithms in engineering applications. Springer Science & Business Media, 2013.

35.

Srivastava

Kim

. Application of genetic algorithm in software testing. Int J soft Eng Appl 2009; 3: 87–96.

36.

Man

Tang

KS,

Kwong

. Genetic algorithms: concepts and designs. Springer Science & Business Media, 2012.

37.

Anwar

Salama

KM,

Abdelbar

. Instance selection with ant colony optimization. Proc Comput Sci 2015; 53: 248–256.

38.

Xin

Zhang

. Application of ACO to vehicle routing problems using three strategies. International Conference on Logistics Engineering, Management and Computer Science (LEMCS 2015), 2015.

39.

Kefi

Rokbani

Krömer

. A New ant supervised-PSO variant applied to traveling salesman problem. In: Hybrid intelligent systems: 15th international conference HIS 2015 on hybrid intelligent systems, Seoul, South Korea, 16–18 November 2015, p. 87.

40.

Gandomi

Yang

Alavi

. Bat algorithm for constrained optimization tasks. Neural Comput Appl 2013; 22: 1239–1255.

41.

Yeomans

Yang

. Municipal waste management optimisation using a firefly algorithm-driven simulation-optimisation approach. Int J Proc Manag Benchm 2014; 4: 363–375.

42.

Matsushita

. Firefly algorithm with dynamically changing connections. In: 2015 IEEE congress on evolutionary computation (CEC), 2015, pp. 2672–2677.

43.

Reinelt

. Tsplib95, 1995, http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95 (accessed 26 February 2017).

44.

Georg

. MP-TESTDATA-The TSPLIB symmetric traveling salesman problem instances. 2008. Available at http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/ (accessed 26 February 2017).

45.

Reinelt

. TSPLIB—A traveling salesman problem library. ORSA J Comput 1991; 3: 376–384.

46.

Sörensen

Glover

. Metaheuristics. In: Encyclopedia of operations research and management science. Berlin: Springer, 2013, pp. 960–970.

47.

Baritompa

Hendrix

. On the investigation of stochastic global optimization algorithms. J Global Optim 2005; 31: 567–578.

48.

Odili

. Application of ant colony optimization to solving the traveling salesman’s problem. Sci J Elect Elect Eng 2013; 2013: 175–177.

49.

Lagoudakis

Markakis

Kempe

. Auction-based multi-robot routing. In: Robotics: science and systems, 2005, pp. 343–350.

A comparative evaluation of swarm intelligence techniques for solving combinatorial optimization problems

Abstract

Keywords

Introduction

Combinatorial optimization

Comparative algorithms

Genetic algorithm

Ant colony optimization

Particle swarm optimization

Honeybee mating optimization algorithm for the TSP

Adaptive simulated annealing with greedy search

African buffalo optimization

Bat algorithm

Firefly optimization

Experiment

Experimental parameters

Experimental data

Experimental results and discussion

Performance cost consideration

ABO, BA, and FFA

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

References