VOLUME 3, NOVEMBER 2010
Zulkifli Zainal Abidin
B.Eng Computer and Information Engineering (International Islamic University Malaysia)
Project title: DrosoBOTs-Swarms of Mini Autonomous Surface Vehicles with Animal Inspired Metaheuristic Algorithm Approach
In contrast to other existing algorithms, the fly algorithm will compute the best surrounding direction before moving towards that direction. Similar to the other algorithms such as the Bee Algorithm, shrinking is ultimately important in this algorithm. Currently, this new algorithm is focused upon examining the best shrinking method. Although this algorithm is mainly based upon gradient information, randomization is imposed in order to solve the local optimum problem. Its capability to solve problem with multiple peaks will also be harnessed.
As the purpose of this algorithm is mainly for swarming robotics, this study focuses on the possibility of real swarming with the implementation of sensors. The previous existing algorithm purely concentrates on fast varying motion that can be performed by the organism or applied to the nature of particles. Although FOA is still based on the motion of the fly, it has also introduced features that can actually be performed by slow varying agents such as an autonomous surface vehicle (ASV). A real agent will collect data along the path. In our case, it’s considered as crucial point and must be taken into the consideration. Thus, this algorithm is based on the scenario where a fly is actually collecting data in its path and it changes directions according to stochastic conditions.
Thus, under real circumstances, each agent would be able to investigate each peak in a particular confined area. The searching process also can be described as pseudo code below:
Proposed Pseudo code
1. Initialization using Lévy Flight motion
2. Choosing the best location
3. While (terminating condition is not met)
4. Examine surrounding points and identify best heading direction (find location attractiveness, simply smelling)
5. Examine points on that direction with different distance (go to location found). In this algorithm, this is known as shooting process
6. Select the best point to be next reference point and loop again
7. Terminate while location is in range of 0.001
FOA process begins with initialization by using Lévy Flight motion. Each fly will be dispatch and find its own current best location. In the mean time, each fly also “smell” if there is any other source of food better than the points it was visited and eventually examining the best heading direction for the next iteration process. Like the “fruit flies”, there share information among them and stop at the location where the targeted location is consider as the most profitable among them. The details implementation of this pseudo code is described on the next section.
Lévy Flight Motion is based on the Lévy Distribution which is a skewed distribution (Fig. 1). Hence, the destinations produced by the Lévy Flight Motion will have a further distance than the destinations created by normal distribution when c is greater than 1.
Figure 1: The Levy Distribution
The surrounding of the known best points is then explored. To yield sensible results, the smelling process must involve 10 flies or more. A circle with a small radius is set around the best known point (Fig. 2). The flies are distributed on the perimeter of the circle at equal angles. The best direction will then be chosen. This is the basic idea of the smelling algorithm. After selecting the best direction, tracking process can be conducted along the direction that is selected. Instead of having the varying angles as in the smelling process, the tracking process will have its radius varying from the known best point for the flies involved. The point which is the best and better than the known best point will be selected as the new known best point.
Figure 2: The Shooting Process