Development of a Smell Agent Optimization Algorithm for Combinatorial Optimization Problems
Chapter One
Aim and Objectives
This research aims to develop a smell agent optimization algorithm (SAO) based on the random concentration of smell particles and the detection capability of an agent. This will then be applied to the robot path planning problem in a static environment with dynamic obstacle positions and the minimum spanning tree problem.
In order to achieve the stated aim, the following objectives are formulated:
- To develop the mathematical model of the smell agent optimization algorithm and present the algorithmic procedure necessary for its realization. This will involve examining the smell detection capability of various agents and determining the detection strength and nature of detection organs in order to establish modelling parameters and also determine the influencing factors of most agents towards efficient smell
- To codify the developed mathematical model in 1 using MATLAB R2017a simulation environment and hence develop a generalized user-friendly graphical user interface (GUI) based
- To evaluate the performance of the developed SAO using a collection of thirty- nine (39) subset of multidimensional and multi-peak applied mathematical optimization benchmark functions. This will contain both multimodal (such as Ackley, Dejong Cosine Mixture etc.) and unimodal (such as Beale, Booth, Easom, ellipsoid etc.) functions and both are used to evaluate the general performance of the developed algorithm in comparison with
- To apply the gaseous Brownian motion optimization (GBMO) algorithm and the fruit fly optimization algorithm (FFOA) on the benchmark problems in 3) for the purpose of comparison and validation. The GBMO and FFOA were selected because the former is inspired by the turbulent rotational properties of gas and the later by its abilities to detect food using its strong sense of
- To apply the developed SAO in solving two typical combinatorial optimization problems and comparing its performance with those of particle swarm optimization (PSO) and smell detection agent (SDA) based approaches using optimality precision and convergence as performancemetrics:
- To determine the optimal path in a robot path planning problem in a static search environment in the presence of obstacles with dynamically changing positions.
- To develop an optimized solution for the minimum spanning tree
The PSO and SDA were selected because PSO has been widely used in solving combinatorial optimization problems (Mac et al., 2017; Norouzi et al., 2016) while the SDA was developed purposely for path planning problems (Chandra, 2016).
CHAPTER TWO
LITERATURE REVIEW
This chapter is divided into two subsections. In the first subsection, the review of fundamental concepts which are relevant for the mathematical modelling, parameter establishment and development of the proposed smell agent algorithm are discussed. In the second subchapter, some of the previous research works, which are related to the proposed research area are critically reviewed.
Review of Fundamental Concepts
The section is focused on smell and the viewpoint of various fields of study on the smell. This is basically to understand the constituent nature of smell, its evaporation from source and mathematical deductions necessary for the formulation of the proposed smell agent optimization (SAO). There are also reviews on some optimization algorithms relevant to the research, benchmark test functions and the performance metrics.
Biology of Sense of Smell
Smell is the ability to perceive (sense) the odour or scent of a chemical substance through the nose by means of the olfactory nerves (Smell-(n.d), 2017). This is usually, made of a chemical compound of different molecules evaporating from a source with a molecular weight of less than 300 Da (Amoore & Hautala, 1983). Detection and discrimination of these chemicals in the environment are critical for the survival of most organisms. Virtually, all chemosensory organisms starting from the unicellular form to the most advanced multicellular creature has the capability to detect chemicals substances within their surroundings through a process called chemosensation (Sookoian et al., 2011). Chemosensation relies on the olfactory organ which contains a large number of chemoreceptors used by organisms to locate food, mates and avoiding danger. These chemoreceptors are generally classified into odorant receptors and pheromone receptors which mostly detect general odours and pheromones respectively (Ranaldi, 2011; Wysocki & Beauchamp, 1984). The pheromone receptors of an individual create a chemical compound which influences the behaviours of another individual of the same species. The pheromone is an exquisite and highly sensitive receptor capable of detecting low-level pheromone chemicals such that, random odorants molecules in the environment are not mistaken as pheromone cues (Morrison, 2014; Ranaldi, 2011).
Olfactory system
As stated earlier, olfaction is the process of detecting the presence of certain chemical compounds in the air through chemosensation. The chemical compounds which are odour molecules travel into the nasal cavity, where they are detected by the olfactory receptors. At this point, the olfactory receptor neuron fires and transmits an impulse into the olfactory bulb at the top of the nasal passage. This connects to the olfactory centre in the cerebral cortex for odour perception and recognition and to the limbic system which controls the expression of emotion and instinctive behaviours (Amoore & Hautala, 1983; Stevenson, 2009). This process is similar to biological organisms which have the ability of olfaction. The olfaction process in man, dog, rat and shark which are potential agents in the developed SAO are therefore discussed as follows.
The olfactory system of man
An important element in distal odorous object detection is the capacity to follow the scent trail or odour plume. This element is fundamental to the existence of several animal species including human beings (Stevenson, 2009). Through odorant chemical identification, human beings can identify harmful objects such as carbon monoxide, button batteries, iron pills, cleaning products, pesticides, hydrocarbons, wild mushrooms etc. Humans and many other animals also use odorant molecules (olfaction) to identify food substances such as ripe fruits etc. Although in industrialized nations, humans rarely use olfaction for the detection of food substance, they still possess a strong capacity to follow odorant trails (Porter et al., 2007; Stevenson, 2009) using specialized olfactory receptors.
Researchers have estimated about five to six million olfactory receptors in man, each having a specific sensation for a particular ligand (ligand, in this case, refers to a specific sensation for a particular smell molecule). This enables man to be able to detect over one trillion different odours (Morrison, 2014). It is however believed that each odorant molecules triggers several olfactory receptors which create a unique combination of neural impulses that are interpreted as a single odour scent. The biological structure of the olfactory system of man is given in Figure 2.1
CHAPTER THREE
MATERIALS AND METHOD
Introduction
This chapter presents the development of the mathematical model of the proposed smell agent optimization SAO algorithm. The relevant assumptions necessary for the development of SAO are also presented. The procedures adopted for the implementation of gaseous Brownian motion optimization (GBMO) and fruit fly optimization algorithm (FFOA), which were used to benchmark the performance of SAO, are presented. All the mathematical equations governing the selected standard optimization benchmark test functions for performance evaluation are also presented. The models of the path planning cost function and the minimum spanning tree problems are also presented.
Materials
In this section, the materials used for the implementation of the research presented in this report are discussed. These materials involve the specification of the computer system used and the software used for the implementation.
Computer System
All the simulations performed in this research were carried out using HP Pro desktop computer situated at the Mechatronics Laboratory of the NLNG Multi-user laboratory, Ahmadu Bello University Zaria. The specifications of this computer are given in Table 3.1.
CHAPTER FOUR
RESULTS AND DISCUSSIONS
Introduction
In this chapter, the results obtained when the developed smell agent optimization was applied on the thirty-nine-standard benchmark functions in comparison with the results obtained using fruit fly optimization algorithm and shark smell optimization algorithm are presented. The results were presented based on the modality (unimodal and multimodal) of the test functions. The performance of the algorithm on robot path planning and minimum spanning tree when compared with particle swarm optimization and smell detection agent optimization are also presented.
Performance of the Algorithms on Uni-modal Test Function
The thirty-nine test functions selected were classified into unimodal and multimodal function. Ten of these functions were unimodal and twenty-nine were multimodal. Table 4.1 shows the results obtained when the developed SAO, the GBMO and the FFOA were used to evaluate the optimum of the unimodal functions. The algorithms were run ten times and each run was performed for three thousand iterations. Out of the ten (10) runs, the best, worst, mean, median and standard deviations were recorded and only the best run was used as a metric for comparing the performance of the developed SAO with FFOA and GBMO. Due to the number of data contained in Table 4.1, the table is divided into sub tables a and b. However, the test functions in both sub tables were assigned a continuous function number ranging from F1 to F10. In Table 4.1a, the first five unimodal functions were presented while in Table 4.1b, the last five unimodal functions were presented.
CHAPTER FIVE
CONCLUSION AND RECOMMENDATION
Summary
In this thesis, the development of a novel computational intelligent algorithm called the smell agent optimization has been presented. The concept of the algorithm was inspired by the smelling ability of various biological organisms and the intuitive behaviours of the agent to follow the smell trails and eventually identify the object generating the smell. The developed SAO consists of three basic modes, named as sniffing mode, trailing mode and random mode. The process of the SAO is initialized by randomly generating initial population of smell molecules. Each molecule is assigned a random velocity and the fitness of their initial position is evaluated. The molecule with the overall best fitness is selected as the agent and the sniffing mode (which is the basic mode of the SAO) was modelled from the concept of hydrostatic pressure of gas. The fitness of the sniffing mode is evaluated and the position of the agent is updated to the position of the sniffed molecule with the best fitness. The trailing mode is then developed using the current position of the agent and the position of the molecules with the worst sniffed fitness. The Brownian motion nature of the smell molecules makes it difficult for the agent to account for all the evaporating smell molecules. This can lead to the agent getting trapped in a “state of confusion” and consequently leading to the loss of smell trail. To account for this situation in the SAO, a random mode which allows the agent to take a random step in the search space was introduced. The performance of the SAO was first evaluated using a collection of 39 applied mathematical optimization benchmark functions. Performance of the SAO on the benchmark functions was compared with that FFOA and GBMO. Thereafter, the SOA was applied to path planning model and MST problems and results were compared withB PSO and SDA based path planning and MST problems. In order to ensure an easier simulation with the SAO, a graphical user interface was developed for users which have little or no knowledge of programming in MATLAB.
Conclusion
This thesis has presented the development of the SAO algorithm for solving various optimization problems. The SAO was developed using the information deduced from sense of smell of an agent based on chemistry, physics and biology perspective. This information was mathematically modelled into three modes (Sniffing, Trailing and Random) and the modes were codified as SAO using MATLAB 2017a.
The developed SAO was applied to evaluate the optimum value of thirty-nine applied mathematical optimization benchmark functions. The benchmark functions were carefully selected with diverse property and their complexity was determine through a formulated function metric. The performance of SAO on the benchmark functions was compared with FFOA and GBMO algorithm. All the algorithms were simulated for a total of 3000 iterations and results showed that, the SAO is highly efficient in obtaining the optimum of the test functions.
When compared with FFOA and GBMO, the developed SAO algorithm obtained the best result for the functions in 56.41% of the thirty-nine test functions while the FFOA and the GBMO obtained the best results in 10.26% and 17.95% of the total test functions respectively. Nonetheless, all the algorithms obtained the same results in 15.38% of the benchmark functions. The performance of the developed algorithm in terms of convergence rate was also evaluated and results showed that, FFOA is much faster than the SAO in all the test functions except in Watson functions. When the SAO was compared with GBMO, it was observed that, both algorithms converged to their optimum solution almost at the same time.
The performance of SAO on MST and path planning problem and results shows that the SAO is efficient in solving these problems. Results showed that SAO performed better than PSO and SDA by 11.41% and 83.29% on the path planning respectively. In the case of MST, the SAO had similar performance with PSO but performed better with 3.03% over the SDA in the first scenario and had 15.97% and 20.67%, 8.94% and 14.14% over PSO and SDA on the second and third scenarios respectively in terms of the cost function.
Contributions to Knowledge
The contributions to knowledge of this thesis, which involves the development of a novel optimization algorithm inspired by the phenomenon of smell are listed as follows:
- The thesis has developed a novel Smell Agent Optimization (SAO) algorithm for solving various degree of optimization problems was developed
- The performance evaluation of the developed SAO through comparison with FFOA and GBMO on a total of 39 carefully selected applied mathematical optimization test functions. Results showed that the SAO performed better in 41% of the functions, the FFOA performed better in 10.26% of the function while the GBMO performed better in 17.95% of the functions. However, the algorithms obtained similar results in 15.38% of thefunctions.
- The developed SAO was applied to solve a model of path planning Simulation results when compared with PSO and SDA algorithm, showed that the SAO obtained the best results in terms of cost function with a percentage improvement of 11.41% and 83.29% over PSO and SDA respectively. The developed SAO was also applied to minimum spanning tree problem and simulation results was also compared with that of PSO and SDA algorithms. In the three scenarios of MST considered, the SAO obtained a better cost with a percentage improvement of 15.97% and 8.94% over PSO on the second and third scenario respectively. However, both SAO and PSO obtained the same cost in the first When compared with SDA, the SAO performed better with a percentage improvement of 3.03%, 20.67% and 14.14% on the three scenarios respectively.
- In this thesis, an interactive graphical user interface (GUI) simulator in order to ease simulation of the test functions with the SAO was
Limitations
Although, the aim of this research which is the development of an optimization algorithm inspired by the phenomenon of smell has been successfully achieved, however, it could not establish that all the molecules evaporating from a smell source are accounted for by the agent. Thus, it is assumed that the agent only makes its decision on the smell molecules it perceived.
Recommendations for Future Work
Though, the SAO parameters (such as: temperature, mass, iteration, step movement and olfaction capacity) can take constant values, the choice of these values plays a significant role in the general performance of the algorithm. Thus, the following areas are highlighted for consideration.
- In practical situations, increase in temperature of gas molecules increases its evaporation and the velocity of the gas. Since the smell molecules in SAOare
considered as gas molecules, a method to adaptively select temperature can be considered. This method should be such that, the temperature has a decreasing value as the algorithm moves towards the optimum solution. This will enable the algorithm to converge faster and eventually terminate the optimization process when the minimum (i.e. zero) value of the temperature is attained.
- In this thesis, all the gas molecules were assumed to have a fixed mass. Perhaps, in practical situations, that is not always the case. Making the mass of the gas molecule adaptive in SAO can be For example, larger value of mass favours the exploitation capability of the agent while smaller value will favour exploration.
- It has been stated that, every smell agent has a specific capacity of If this capacity is known for a particular animal (agent), the developed SAO can easily be termed the animal (agent) based optimization. However, there is no known empirical study specifying the numerical values of olfaction capacity of agents. Since this capacity plays a significant role in the developed SAO, determining this parameter empirically for a specific agent can be considered.
- The possibility of developing a novel algorithm using other sensory systems such as sense of test, sense of feel and sense of hearing can be For example, the system of sense of smell and sense of taste are coordinated through the chemo- sensation process. Thus, if an algorithm can be developed using sense of smell, similar algorithm can also be developed using sense oftaste.
- The developed SOA can be hybridized or cascaded with similar computational intelligent algorithm such as PSO, SDA, ABC AFSA etc. for improved performance.
The developed SAO can also be applied to problems related other fields like, image and signal processing, power systems, sensor networks etc.
REFERENCES
- Abdechiri, M., Meybodi, M. R., & Bahrami, H. (2013). Gases Brownian motion optimization: an algorithm for optimization (GBMO). Applied Soft Computing, 13(5), 2932-2946.
- Abdelkader, M., Shaqura, M., Ghommem, M., Collier, N., Calo, V., & Claudel, C. (2014). Optimal multi-agent path planning for fast inverse modeling in UAV- based flood sensing applications. Paper presented at the 2014 International Conference on Unmanned Aircraft Systems, ICUAS 2014 – Conference Proceedings.
- Abdullah, N. R. H., Musirin, I., & Othman, M. M. (2010, 23-24 June 2010). Computational intelligence technique for solving power scheduling optimization problem. Paper presented at the 2010 4th International Power Engineering and Optimization Conference (PEOCO).
- Abedinia, O., Amjady, N., & Ghasemi, A. (2016). A new metaheuristic algorithm based on shark smell optimization. Complexity, 21(5), 97-116.
- Achtelik, M. W., Lynen, S., Weiss, S., Chli, M., & Siegwart, R. (2014). Motion- and uncertainty-aware path planning for micro aerial vehicles. Journal of Field Robotics, 31(4), 676-698. doi: 10.1002/rob.21522
- Ahmadigorji, M., & Amjady, N. (2016). A multiyear DG-incorporated framework for expansion planning of distribution networks using binary chaotic shark smell optimization algorithm. Energy, 102, 199-215.
- Amoore, J. E., & Hautala, E. (1983). Odor as an ald to chemical safety: odor thresholds compared with threshold limit values and volatilities for 214 industrial chemicals in air and water dilution. Journal of applied toxicology, 3(6), 272-290.
- Awad, M. K., El‐ Shafei, M., Dimitriou, T., Rafique, Y., Baidas, M., & Alhusaini, A. (2017). Power‐ efficient routing for SDN with discrete link rates and size‐ limited flow tables: A tree‐ based particle swarm optimization approach. International Journal of Network Management.
