Ahmet D. Bahadir
We are faced with many challenges in life, and we are able to find solutions to most of these challenges with our minds. We drive home from work and we try to find the best route considering the traffic, the cost and time required to make it to our destination. We consider cost, fuel consumption, maintenance, and after-sale service and then select the best alternative when buying a car. An airline company assigns pilots to the flights considering work hour constraints and aircraft maintenance schedule. A company has limited budget and many project alternatives. Each project has a cost and revenue and the company tries to find the best projects that will maximize the revenue. In each case, the optimum solution is desired. The problems can be modeled as a mathematical problem in which an objective function, decision variable and constraints exist. The objective is the maximum revenue, the decision variables are the projects and the constraint is the limited budget for the company. However, most of these theoretical problems are more complex in practice and need special solution search methods.
Once a problem is formulated, the next step is to use a solution method to find an optimum solution. Finding an optimum solution is similar to finding a treasure on a mountain or in the ground with limited time. If there is no sign of the best location or no guidance to the right direction, this search is pointless and a waste of time. In other words what this means is that we merely hope to find the best solution and continue on digging. This is obviously not an efficient method. Sometimes helpful information is provided for the location of the treasure and we directly climb the mountain to reach it. Most cases are between these two strategies. One can look at some places randomly and look for some clues of treasure, then move to another location and continue until he gives up or finds the treasure. Another useful approach might be looking for the treasure with a group of people. Each group member chooses a random path and shares information about their experiences until they reach the treasure . These methods are trial-and-error based search methods.
People use their intelligence and instincts when they try to find a solution for a problem. We tend to choose the directions that will take us minimum time when driving home. Kids learn using trial and error methods and we tend to solve problems in daily life using trial-and-error approaches. The solutions that are based on trial-and-error are called heuristics. Heuristics methods can find a good solution to a complex problem in a reasonable amount of time but there is no guarantee that the solution is best. These methods are preferred when the best solution is not required and a good solution is desired in a short time. Computer programs and simulations are developed to solve large-scale complex problems using heuristics.
The best designs, solutions, inspirations, and engineering mechanisms that are beyond the reach of current technology are abundantly found in nature. Scientists visualize and simulate the behavior of animals in nature and apply their strategies to problem solving. These strategies provide successful heuristics methods.
Ants teach us how to find the right path
The behaviors of ants provide a good solution method to solve complex problems on graphs. An ant leaves its nest and randomly chooses a path to look for food. If it finds the location of food, it returns to the colony and leaves traces of a chemical on the return path called “pheromone.” When another ant finds this chemical, the ant follows the same path to reach the food. More ants that follow this path leave the same chemical markings, making the path more attractive to follow. If the path is long and unattractive, the chemical evaporates and loses its attractiveness as it is not used frequently. If a path is used more frequently, it will be more attractive for an ant as each ant leaves traces of chemical one on top of the other . The most attractive path is the path that is shortest or optimal since it is preferred by many ants that make the chemicals denser and keep it fresh all the time.
It is required to find the shortest path to an optimal solution of a complex problem. A graph is used to analyze all the possible paths and hence find out the shortest path. The traveling salesman problem is a famous example of such problem. There are many possible combinations of the optimal solution. The required computational time becomes exponential as the size of the problem gets bigger. On the other hand, ant colony optimization can provide good solutions in a very short time.
The search algorithm works in such a way that each ant randomly selects a path in the search space and the length of the paths (value of the objective function) are recorded. The solution developer arbitrarily assigns ants to the search space and allows them to select a path. This search process is replicated many times and as one path is selected more frequently, then it means this path is shorter and better than other paths and hence can be preferred as a good solution. This solution is recorded as the best solution to a large scale problem.
Social behaviors of bird and fish swarms
Modeling the social behaviors of animals in their natural habitats provides us a way to reach a good solution. Bees, termites, ants, birds, fish and wasps are good examples of animals that have a social and collaborative life style. These animals work together in a social environment and interact with each other to continue their life and supply their basic need of food. Food is distributed often times far away from where these animals are located and they have to find a trail to reach their food without knowing the exact location. The physical paths and mental strategies used by each animal to find a solution to their problems—which is in a way like developing a natural algorithm to find the right way to the food—is noteworthy enough to do extra research.
Algorithm designers have modeled the strategies of these species and found out that it can be used to find an optimal solution to a problem . If a group of birds is considered, the information that each bird in the flock is equal to the solution has been obtained so far. The best known food location signals the best solution. This information is distributed in the flock and other birds move to this location to focus on the area. The move from one place to another by each bird represents the development of a solution in the optimization problem. The most important issue is the collaboration of each individual in the flock, whether it is a bird or a fish.
In a flock, each bird acts as an agent to achieve a global objective while co-operating with other members without any conflict. Each member in the flock is governed by local rules and interactions among which agents lead the flock to its global objective. As mentioned, this objective might be to find food, foraging or constructing shelter. The behaviors of these agents illustrates that a self-organized social community exists without any education and experience as there is no central control in this system. A member of the flock does move according to directives from an authority or according to a plan. Each member coordinates its movement according to movements of its neighbors. Each bird stays close enough to the flock so it does not lose it. It also avoids collisions if the members of the flock move very close to each other. This is called “separation.” Each agent follows the average heading of its group which is called “alignment.” Since there is no leader or bird which makes the commands, the movement of the entire flock is the result of collaboration. Each member is free to fly in any location point of the flock. As there are more eyes that are collaboratively looking for food, one bird uses the eyes of all other birds. It is interesting to note that a school of fish show a similar organized behavior. An observer might conclude that the motion of these groups is pre-planned, but in reality they are not.
The motion of a school of fishes and flocks of birds are animated in computers, and their movements are modeled using mathematical formulations. The flock starts its motion from a current location X0. Let’s say that f(x) is the problem that needs to be maximized, i.e., we would like to find a solution X that will maximize f(x). The function corresponds to the best location that the food is abundant for the bird flock. The flock moves from X0 to X1 then X2 and ends with Xn which is the last point during the search. Each point represents a possible location for the food, the best is represented as:
This is the point where the food is abundant and the swarm concentrates to this area. When the swarm moves from Xn-1 to Xn based on the velocity vector given,
note that the new location is determined based on the inertia, personal experience and social influence. Then when they find food, every member benefits from the result.
Artificial bee colony is another method that is used in optimization problems. Each honey bee goes to look for food and returns to the hive with some nectar . The bee then dances in the hive signaling the amount of nectar it found at the source. Other bees choose one source depend on the dances of returning bees and they also return to the hive with some nectar. The amount of nectars is evaluated and the abandoned food sources are replaced with sources that have less food. The amount of food corresponds to the objective of the optimization problem that will be maximized. The number of returning bees with nectar corresponds to the number of solutions to the problem. Since bees share information through dancing, the location that has the highest amount of food is determined as the optimum solution to the problem.
Bat algorithm, firefly algorithm, krill herd algorithm, and intelligent water drops are some other important methods that are inspired from nature. It is also worth mentioning that new methods are being tested and we can expect that they will be in use in the near future. These methods basically mimic the behaviors and strategies used in nature and apply these strategies in solving real life mathematical problems.
Nature as a source for humankind
Nature is the service of mankind as a source of food, a shelter, and a source of life with its oxygen and water. Humankind now realizes that nature contains solutions to their problems more than ever. Biomimetics, a science that has been developed recently, is the science that analyzes the systems, processes, models and materials of the creatures in nature and develops methods that help to solve real world problems. Bath University in the UK developed a database that contains the engineering systems of natural creatures and when a new machine, material or solution is developed, scientists benefit from this database. They estimate that only 10% of the potential in the nature is currently being used. The heuristic methods that have been analyzed in this article are only some of the available algorithms.
How can animals display such a level of knowledge to find methods and solutions? Do they develop them all by themselves? Are they able to share knowledge among themselves in a conscious way so as to reach optimum results, or are they born with these capabilities? Nature offers a banquet of amazing phenomena for us to ponder over with all sorts of models and systems to provide solutions for many human problems.
In other words, intelligent human beings benefit from the strategies of the species that are not intelligent. It means that there is another global intelligence behind what is beyond the reach of human capability.
Yang, Xin-She. 2010. Nature-inspired Metaheuristics Algorithms, Luniver Press, 2nd Edition, UK.
Dorigo, Marco, Thomas Stutzle. 2004. Ant Colony Optimization, MIT Press.
Reynolds, Craig. 1987. “Flocks, Herds, and Schools: A Distributed Behavioral Model”, Computer Graphics, Vol. 21(4), July.
Karaboga, D., B. Basturk. 2007. “A Powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm,” Journal of Global Optimization, Vol. 39 (3), pp. 459-171, November.