Introduction to Nature-Inspired Algorithms
This chapter is an introduction to nature-inspired algorithms. It first discusses the reason why such algorithms have been very popular in the last decade. Then, different classifications of such methods are given. The chapter also includes the algorithms
- PDF / 356,840 Bytes
- 5 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 294 Views
Abstract This chapter is an introduction to nature-inspired algorithms. It first discusses the reason why such algorithms have been very popular in the last decade. Then, different classifications of such methods are given. The chapter also includes the algorithms and problems investigated in this book.
In the field of Artificial Intelligence (AI), there is a large number of nature-inspired techniques to solve a wide range of problems. One of the most specialized areas in AI with the most nature-inspired techniques is Computational Intelligence (CI). There is no agreed definition for CI, but a large number of researchers believe it is equivalent to the field of Soft Computing. In both of these fields, the main objective is to develop inexact solutions for NP-complete problems where there is not exact solution that runs in polynomial time. As an example, the Traveling Salesman Problem (TSP) is worth mentioning here, in which a traveller wants to find the shortest path to visit n cities in a country. As example is shown in Fig. 1 where the objective is to find the shortest path to visit 20 biggest cities in Australia. Assuming that the traveller can visit any city in any order and (s)he can travel directly from one city to any other, all the possible connections between cities are shown in Fig. 2. This problem seems very simple since there are only 20 cities. However, this chapter shows that it is one of the most challenging NP-hard problems that humankind has ever faced. The size of search space can be calculated using n!. This means that S. Mirjalili (B) · J. Song Dong Institute for Integrated and Intelligent Systems, Griffith University, Nathan, Brisbane, QLD 4111, Australia e-mail: [email protected] J. Song Dong Department of Computer Science, School of Computing, National University of Singapore, Singapore, Singapore e-mail: [email protected] © Springer Nature Switzerland AG 2020 S. Mirjalili et al. (eds.), Nature-Inspired Optimizers, Studies in Computational Intelligence 811, https://doi.org/10.1007/978-3-030-12127-3_1
1
2
S. Mirjalili and J. Song Dong
Fig. 1 Twenty biggest cities in Australia
Fig. 2 The search space of finding the shortest route to visit 20 cities in Australia
there are there are 2.432902e + 18 possible tours to search from. If it takes someone to calculate the length of each tour one second, it takes 77,000,000,000 years to search the entire search space, which is nearly 20 times longer than the big bang. Even using a computer is not helpful here. Assuming that we use a computer with 2.0 GHz CPU, which means 2,000,000,000 instructions per second, checking all the possible routes will take nearly 38 years. Adding one city to this problem increases this period of time to nearly 810 years. The main challenge in such NP-hard problems is the exponential growth in the resources (often time and memory) required to solve them. The growth of n! is even more then exponential as can be seen in Fig. 3. Exact methods are effective for emblems with polynomial time and their
Data Loading...
