ABSTRACT
This thesis presents the development of smell agent optimization (SAO) algorithm. The developed algorithm consists of three modes (sniffing, trailing and random modes). The evaporation of smell molecules from the smell source is modelled into sniffing mode using the concept of the hydrostatic pressure of gas and positions of molecules. The fitness of the sniffing mode is evaluated and the molecule with the most favourable fitness is taken as the agent. The olfaction capacity of the agent is then evaluated and the training mode is developed using the current position of the agent and the position of the molecules with the current worst fitness. In practical scenarios, it is usually difficult for the agent to account for all the evaporating smell molecules due to the Brownian nature of the smell molecules. This is largely responsible for the agent to 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 is modelled. The agent evaluates the fitness of the random mode and decides whether to continue its trailing process or to start the entire process of the SAO all over again. This process continues until the object (optimum result) generating the smell is identified. The performance of the developed SAO was evaluated using a total of thirty-nine (39) optimization benchmark functions. Simulations were performed using MATLAB R2017a and results were compared with the results obtained using the fruit fly optimization algorithm (FFOA) and gaseous Brownian motion optimization (GBMO). Results showed that the SAO obtained the best results in twenty-two (22) functions (56.41%) while the FFOA and GBMO obtained the best results in four (4) and seven (7) (10.26% and 17.95%) functions respectively. However, there were similar results in six (6) of the functions (15.38%). The convergence rate of the algorithms was also compared and results showed that the FFOA converged faster than the SAO in all the functions except in one, while the GBMO converged faster than the SAO in 24 of the functions. These convergence results are expected because the computation time in FFOA and GBMO is similar to the computation time required to evaluate one and two modes in SAO respectively. The developed SAO was applied to path planning problem and three scenarios of minimum spanning tree (MST) problem and results were compared with particle swarm optimization (PSO) and smell detection agent (SDA). Though all the algorithms obtained an optimized obstacle free path, results showed that SAO performed better than PSO and SDA in terms of cost by 11.41% and 83.29% respectively. On the MST model, the SAO and PSO obtained the same cost in the first scenario and 3.03% improvement over SDA. In the second scenario, the SAO obtained a better cost with 15.97% and 20.67% improvement over PSO and SDA respectively. In the third scenario, the SAO obtained a better cost with 8.94% and 14.14% improvement over PSO and SDA respectively. These results showed that the developed SAO is highly efficient and can compete significantly well with other algorithms reported in the literature.
TABLE OF CONTENTS
CHAPTER ONE: INTRODUCTION
1.1 Background 1
1.2 Motivation 7
1.3 Significance of Research 8
1.4 Statement of Problem 11
1.5 Aim and Objectives 12
1.6 Methodology 14
1.7 Thesis Organisation 17
CHAPTER TWO: LITERATURE REVIEW
2.1 Introduction 18
2.2 Review of Fundamental Concepts 18
2.2.1 Biology of Sense of Smell 18 2.2.1.1 Olfactory system 19
2.2.2 Chemistry of Sense of Smell 27
2.2.2.1 Smell agent algorithm deduction from chemistry perspective 27
2.2.3 Physics of Sense of Smell 30
2.2.3.1 Characteristics of gas 30
2.2.3.2 Mathematical properties of gas 32
2.2.4 Gaseous Brownian motion optimization 33
2.2.5 Fruit Fly Optimization Algorithm 36
2.2.6 Particle Swarm Optimization (PSO) 39
2.2.7 Smell Detection Agent (SDA) 41
2.2.8 Metrics for measuring the Complexity of Optimization Problem 43
2.2.8.1 Qualifying the complexity of function optimization 44
2.2.9 Robot pathfinding 60
2.2.9.1 Visibility graph algorithm 61
viii
2.2.9.2 Artificial potential field 65
2.2.10 Minimum spanning tree problem 67
2.2.10.2 Prim‟s algorithm 70
2.3 Review of similar works 72
CHAPTER THREE: MATERIALS AND METHOD
3.1 Introduction 85
3.2 Materials 85
3.2.1 Computer System 85
3.2.2 MATLAB 86
3.3 Methods 86
3.3.1 Smell Agent Optimization (SAO) algorithm 86
3.3.2 Sniffing Mode 88
3.3.2.1 Population 88
3.3.2.2 Updating smell velocity and position 92
3.3.3 Trailing mode 94
3.3.4 Random Mode 96
3.4 Flow of SAO Algorithm 98
3.5 Important assumptions 99
3.6 SAO Parameter Selection 102
3.7 Application of SAO on the Benchmark function 103
3.8 Application of SAO in Path Planning 109
3.9 Application of SAO to Minimum Spanning Tree (MST) 115
3.10 SAO GUI Simulator 119
3.11 Performance Comparison 119
CHAPTER FOUR: RESULTS AND DISCUSSION
4.1 Introduction 122
4.2 Performance of the Algorithms on Uni-modal Test Function 122
ix
4.3 Performance of the Algorithms on Multi-modal Test Function 126
4.4 Application to Part Planning 134
4.5 Application to Minimum Spanning Tree 139
4.6 Simulation with SAO GUI 145
CHAPTER FIVE: CONCLUSION AND RECOMMENDATION
5.1 Summary 147
5.2 Conclusion 148
5.3 Limitations 150
5.4 Contributions to Knowledge 149
5.5 Recommendation for Future Work 150
REFERENCES 153
APPENDIX A 161
MATLAB CODE FOR SAO 161
APPENDIX B 165
MATLAB CODE FOR BENCHMARK FUNCTIONS 165
APPENDIX C 172
Path Planning Cost Function 172
APPENDIX D 174
MST Cost Function 174
CHAPTER ONE
INTRODUCTION
1.1 Background
Efforts to adopt an acceptable definition of intelligence still elicit debates among various disciplines. Dictionaries (Crystal, 2004; English, 2007) have defined intelligence as the power of understanding, comprehending and profiting from experience, the power to interpret and having the capability for thought and reason especially to a high degree. The mechanisms of “intelligence”, which are exhibited by all living systems, share similarities in terms of complexity, organisation and adaptability as a whole. Over the years, experts have understandably sought for means of codifying intelligence systems into algorithms dedicated to solving some complex problems in engineering and related disciplines. This triggered the development of a new field of study called computational intelligence (CI) which was popularized by James C. Bezdek about 24 years ago (Bezdek, 1994). Perhaps, the first appearance of CI was way back in 1983 where the International Journal of Computational Intelligence (IJCI) was reported to be the title of the Canadian journal by its editors and founders Gordon McCalla and Nick Cercone (Bezdek, 2013). Mu‟azu stated that “computational intelligence consists of any science supported technologies and approaches for analysing, creating, and developing intelligent systems (Mu’azu, 2006, 2016). „Intelligent‟ in this case refers to the utilization of engineering techniques that have, to one extent or another, been borne out of human reasoning, adaptation or learning, biological cognitive structures or principles of evolution, natural physical or chemical processes.
2
Many experts have also referred to the term computational intelligence (CI) as the ability of a computer system to learn precisely a certain task, from a given set of data and/or empirical observation (Siddiqui & Hojjat, 2013). The IEEE World Congress on Computational Intelligence and the IEEE Neural Network Council formalized this term in the summer of 1994 in Orlando, Florida (Xing & Gao, 2014). Perhaps, till date, researchers have not come to a conclusive agreement as to a precise definition of computational intelligence (Zimmermann, 1999). This is because it is difficult to start with anything precise; the precision has to be achieved through a certain process. But, strictly speaking, computational intelligence is a set of nature-inspired computational models and approaches capable of addressing real-world problems to which traditional or mathematical model may be limited due to any or all of the following reasons:
1) The problem or process may be too complex for mathematical reasoning.
2) The problem or process may be dynamic and stochastic in nature.
3) The solution space of the problem may be too large for mathematical computation.
4) The problem or process may contain uncertainties.
All these characteristics are exhibited by most real life (non-linear) science, economic, social and engineering problems. These non-linear type problems require several assumptions in order to transform them to their near-linear equivalents for easy computation. However, the outputs of such linear computations usually do not depict entirely the real-life situations, except in a scenario where the exact solution to real life situations is not critical. Thus, agent-based computational intelligent techniques are capable of providing superb and promising alternatives in such scenario.
3
The obvious high-level intelligent agents are human beings. An intelligent agent is a rational entity that performs actions, in a relatively autonomous (independent) way, in its environment on behalf of its user. However, there are classes of intelligent agents (for example, natural phenomena, such as water drop, flower pollination, river formation, etc. or animals, such as fish, dogs, worms, insects, etc. or even bacterial, amoeboid, etc.) which could be more intelligent than humans in terms of coordination and organizations (Poole & Mackworth, 2010). An example of this intelligent organization is the Ant colonies. A single ant might not be very intelligent, but the entire colony will act more intelligently and organized than any individual ant. The ant colony can discover the location of food and search this location in order to exploit the food source effectively as well as adapt to changes in the environment using some specialized skills (Poole & Mackworth, 2010; Xing & Gao, 2014).
In the past decades, several researchers have developed various agent-based biological and nature-inspired CI algorithms for solving various optimization problems. The foraging behaviours of ant systems were codified into an algorithm in (Dorigo et al., 1996). Algorithms based on the intelligent behaviour of fish (Lei. et al., 2002), bacterial foraging (Passino, 2002), firefly (Yang, 2010), swarm particles (Eberhart & Kennedy, 1995), bee (Karaboga & Basturk, 2007) etc. have also been developed. The performance of all these algorithms on suitable problems such as in (Malarvizhi & Kumar, 2015; Pradhan et al., 2016; Sundaram et al., 2016; Tijani & Mua’zu, 2015; Turabieh & Abdullah, 2011) has demonstrated their effectiveness in solving real word problems. It is, however, important to note that, there is no known single nature-inspired optimization method capable of solving all optimization problems. This is known as the “no free lunch” theorem (Wolpert & Macready, 1997). This is because, the solution to
4
every real word problem can directly or indirectly be formulated using a particular algorithm that mimics a nature or bio-inspired phenomena. For example, the pheromone trail and pattern movement of ant system can be said to mimic the lane and edge detection problem in transportation and image processing respectively. Similarly, the path planning and trajectory problem of a robot can be linked to an agent seeking to identify the molecular movement of an object (smell) which evaporates and travels into the olfactory organ (nose), where they activate special cells that send a message to the brain for adequate judgment. Thus, it is the focus of this thesis to develop a mathematical model and codify the intuitive movement of an agent towards smell (odorant) molecule as the agent seeks to identify the source of that smell or odorant.
The sense of smell (olfaction) is one of the five senses through which the world is perceived. Through the sense of smell, humans and other animals can perceive a variety of chemicals (Linda, 2005). In fact, with a good sense of smell, humans and other agents (especially dogs) can perceive the molecular concentration of smell and intuitively trace or follow this concentration in order to identify its source. This is possible because the nose has a mechanism that can recognize sensory information within its surroundings and transmit this information to the brain, where it is processed to simulate internal interpretation of the external world (Axel, 2005). These interpretations help the smell agent to determine the optimized path which constitutes the search or solution space. In this case, the object which radiates the odour molecule is the solution that resides in the search space for which the proposed algorithm is based. Thus, it is hoped that a metaheuristic optimization algorithm using the path trailing ability of smell agents be developed for solving various degrees of combinatorial optimization problems.
5
In virtually all optimization problems, the complexity and structure of the problems increase as the dimension of the problem increases. In such situations, an exhaustive search is not feasible. Thus, a technique capable of operating in a domain of such optimization problems in which a set of possible solution is discrete or can be reduced to discrete with a common goal of finding the best solution is termed combinatorial optimization. Combinatorial optimization is an indication of optimization problems with an extremely large (combinatorial) increase in the number of possible solutions as the problem size increases. Initially, the performance of the develop smell agent algorithm is to be evaluated using a subset of multidimensional and multi-peak applied mathematical optimization benchmark functions. This is to ascertain the optimality, precision and the convergence of the developed smell agent algorithm. Thereafter, the algorithm would be used to develop an efficient robot path planning technique in a dynamic environment with a static positioning of obstacles and minimum spanning tree problem.
The framework of the proposed smell agent optimization follows the general fundamental framework of nature-inspired algorithm. The properties and structure of every nature-inspired computational algorithm hinge on the following (Abdullah et al., 2010; Poole & Mackworth, 2010):
1) Population: Every nature-inspired algorithm is initialized with a randomly generated set of initial population. This initial population are usually depicted as the population of the natural phenomenon on which the algorithm is based. Thus, the population of the proposed SAO is initialized by a set of the randomly generated initial population of smell molecules. These smell molecules were
6
deployed in the optimization hyperspace and the fitness of each molecule is evaluated.
2) Dimension: This is a function of the optimization problem which the computational algorithm seeks to explore. Perhaps, many real-life optimization problems are multi-dimensional in nature. Therefore, to efficiently evaluate the performance of any newly developed optimization algorithm, it is often customary to do so using a selection of multi-dimensional problems. If this is successful, then the general belief is that solving problem with simple dimension will be an efficient process.
3) Control Parameters: These parameters are formulated to guide the movement of the algorithm, as it evolves towards the optimum solution in the search space. The modelling choices of these parameters are usually dependent on the natural phenomenon on which the algorithms are based. If these parameters are not properly selected, the optimum performance of the algorithms will be greatly affected. In the proposed SAO, the control parameters include the mass and temperature of the gas molecules. Also, since the trailing capabilities of agent depend on their size of olfactory lobe, an olfaction capacity of the agent will also be assigned.
4) Stopping Criteria: These are additional parameters which are used to terminate the evolution process of the optimization algorithms. The basic stopping criteria for all computational intelligent algorithm is the iteration. The iteration is used by the algorithms to repeat the same process (in discrete form) over a specified number of time until a converged solution is obtained.
5) Fitness function: The fitness function which is also called the objective or cost function is the optimization problem which the computational intelligence
7
algorithm hopes to solve efficiently. The complexity of the fitness function depends on the dimensionality of the optimization problem, the nature of the constraints and the number of decision variables it contained.
6) Obey the “No free lunch theorem”: There is no single computational intelligent algorithm that is general for solving all optimization problems. Since these algorithms are mostly developed by the observation of the natural phenomenon, it is generally believed that the performance of an algorithm is best and convincingly evaluated using some optimization problems which mimic the behaviour of the algorithm.
7) Obey the “The no see the forest for the tree rule”: Every nature-inspired algorithm is expected to determine the best possible solution from a set of available possible alternative solutions. To do this, the algorithm has to be able to evaluate all the possible solutions in the search space from which the best (optimum) solution is to be identified. Thus, the inability of the algorithm to evaluated all the solution in the entire search space (No see the forest) in order to determine effectively the best possible solution (the tree) is termed the “No see the forest for the tree”.
1.2 Motivation
The sense of smell which is also called olfaction is termed as “the ability to detect or discover something by the faculty of smell” (Morrison, 2014). This ability is exhibited by nearly all living organisms. Animals employ the sense of smell for detecting and avoiding danger, mating, searching for food, searching for the conducive environment and changes in climatic conditions (Doty et al., 1985). Due to the usefulness of olfaction, advancement in security and surveillance have employed animals with a
8
highly-developed sense of smell, like wolfs, dogs etc, to search hard to find targets which release a detectable plume (Furton & Myers, 2001). When these detectable plumes evaporate from a region of high density (source), it is conveyed by the wind toward the region of high concentration and consequently generating an odour plume. This odour plume is typically a conic (elliptical) shape evaporating laterally in the direction of downwind (Marques et al., 2006). The distance covered by the plume is mostly determined using advection phenomena and spreading is usually due to turbulent rotation. In the aftermath of these behaviours, the temporal average and spatial odour concentrations decrease as the distance to the odour source increases. Since the odour plume located near the odour source releases profile of odour with maximum average concentration close to the source, the problem of searching different sources of multiple such odour in a confined environment can therefore be formulated or translated into a stochastic or metaheuristic optimization problem where the goal is to focus on determining the local optimum path leading to the odour source. This algorithm should be able to identify this optimal path quickly since the smell source identification depends on the distance to the smell source, the concentration of the smell and the density of the transmission medium (air).
1.3 Significance of Research
The integral part of modern engineering practice and industrial design revolves around modelling, simulation and optimization. Significant efforts and tremendous achievements have been recorded in all these components over the last few years. Perhaps, one of the challenging issues which still remains a bottleneck to researchers is the unavailability of an optimization resource that is of general application. Due to the quest to address these challenges, most of the present research trend in optimization
9
techniques has drifted towards using nature-inspired computational methods. Thus, the significance of this research, which aims to develop a smell agent optimization algorithm, hinges on the following:
1) The “no free lunch” theorem: All computational intelligent algorithms are inspired by observation of various natural phenomena. Mostly, the behaviours of these natural phenomena can be traced and transformed into equivalent real-life optimization problems. Since all real-life problems do not exhibit a common inherent structure and model, it has been stated that no single optimization algorithm or computational intelligent model has the capability of solving all of them (Wolpert & Macready, 1997). In nearly all optimization problems, the characteristics of the cost function for the problem at hand are almost always ignored. However, these optimization algorithms are always applied to these problems with little or no modification(s). When detailed characteristics of the optimization problem‟s cost function are considered, it then becomes obvious that every optimization algorithm is unique to a certain kind of optimization problem a priori. In 1995, David Walpert demonstrated that all computational algorithms that seek for the extremum of cost functions act exactly in the same manner according to any performance measure when averaged across all cost functions (Wolpert & Macready, 1995, 1997). This led to the formulation of the “no free lunch” (NLF) theorem which states that, “if algorithm A outperform an algorithm B on a set of cost functions, then, there must exist exactly as many other functions where algorithm B outperforms algorithm A” (Lakkaraju et al., 2017; Wolpert & Macready, 1997). Thus, the performance of every optimization algorithm can be effectively maximized when a suitable cost function is carefully selected. Therefore, in developing a new algorithm, the ideal thing is to
10
first study the natural phenomenon behind the algorithm and thereafter, a suitable optimization problem can then be identified. It is on the basis of this theorem that, this research hopes to develop efficient algorithm using the path trailing abilities of smell agent for combinatorial optimization problems. The developed algorithm is applied to path planning and minimum spanning tree problem.
2) Real word optimization problem: Many practical problems are large-scale and complex and could be challenging to fully capture and understand using mathematical models. However, most optimization tools are tested on some very small-scale problems. This is because the non-linearities in the large-scale problems are more than what optimization methods can handle. Thus, assumptions and approximations become a necessity. Since the real-world problems are mostly complex, research tends to use over-simplified models for approximating the real systems. This introduces several unknown factors (uncertainties) that reduce the accuracy of the results and validation of the models (Marques et al., 2006; Pugh & Martinoli, 2007). Robot path planning problem is a typical example of an oversimplified real-world problem. Given a starting and final position of a robot, the path planning problem is to seek for a set of motions which will enable the robot to move between the two positions without colliding or been obstructed or stopped by an obstacle. The robot has to identify the optimal path and be able to locate the final position (target) in the shortest amount of time. This is usually a difficult task to achieve since the robot does not have an intelligent means of identifying the nature of the environment. Researchers have over the years employed various CI algorithms (S. Wang et al., 2016; X. Wang et al., 2016; Zhang et al., 2016) for optimal path planning.
11
However, selecting a CI technique which will provide the optimal path planning when compared with all other algorithms has always been a critical issue. Since the algorithm proposed in this research is inspired by the path trailing behaviour of a smell agent, validating the algorithm with an engineering problem (path planning and minimum spanning tree) having the same or similar characteristics will be the ideal thing to do.
1.4 Statement of Problem
Combinatorial optimization involves the mathematical study of arraignment, ordering, selection or grouping of discrete objects. The complexity of combinatorial problem usually increases as the problem dimension becomes very large. Solving these large dimensional problems usually requires an enormous amount of time and computational resources before a combination of discrete solution (which may not even be optimum) is obtained. Over the years, researchers have sought for an efficient means of solving these problems with a common focus on obtaining the best possible combination of results within a short possible interval of time. This quest plays a significant role in the development of already well-established and widely accepted fields of computational intelligence algorithms. Interestingly, these algorithms have appeared to be more efficient (in terms of computation, precision and complexity) in solving various degrees of optimization problems when compared with the traditional methods. Generally speaking, all computational intelligence algorithms were developed through careful observation of various natural phenomena. The majority were focussed only on the foraging behaviours of most natural behaviours of some biological agents as the agents seek to identify the location of food source within its environment. In several situations, the nature and concentration of the food do influence the behaviour of the agent. For example, the movement of fish in water is attracted towards the region of high
12
concentration of food. The implication of this is that, the movement of fish is restricted to only the region of high concentration of food. However, considering only the foraging movement of the agents towards the food source does not truly represent the real-life scenario of a biological system. This leads to the problem of imbalance between exploration and exploitation, increasing the chances of poor convergence and subsequently leading the algorithm into local minima. Considering these limitations and bearing in mind the “no free lunch theorem” this research developed a new optimization algorithm using the natural phenomenon of smell. In the proposed research, the Brownian nature of the smell molecules as they evaporate from the smell source towards the agent is mathematically modelled. Thereafter, the trailing behaviour of the agent towards the smell source after sniffing the smell molecules is also developed. These mathematical models were codified and the resulting bio-inspired optimization algorithm is termed smell agent optimization (SAO). The performances of SAO will be evaluated through comparison with gaseous Brownian motion optimization (GBMO) and fruit fly optimization (FFO) on a total of thirty-nine (39) applied mathematical optimization benchmark functions. After the performance evaluation, the proposed algorithm will be used to develop a model of robot path planning and minimum spanning tree and results were compared with that of particle swarm optimization (PSO) and smell detection agent (SDA) algorithm.
1.5 Aim and Objectives
The aim of this research is to develop a smell agent optimization algorithm (SAO) based on the random concentration of smell particles and 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.
13
In order to achieve the stated aim, the following objectives are formulated:
1) 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 detection.
2) 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 simulator.
3) 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 others.
4) 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 olfaction.
5) 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 performance metrics:
14
a) 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.
b) To develop an optimized solution for the minimum spanning tree problem.
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).
1.6 Methodology
The step by step procedures adopted to achieve the proposed smell agent optimization algorithm are highlighted as follows:
1) Development of smell agent optimization (SAO) algorithm. To efficiently carry out this method, the following procedure is adopted:
a) All the necessary parameters (such as velocity, molecular mass, population, temperature, position, iteration, agent, olfaction etc.) required to develop the mathematical model of the proposed algorithm are established.
b) The mathematical model of the proposed SAO algorithm is developed using the parameters established in item a).
c) The model of SAO algorithm to be developed is codified using MATLAB R2017a simulation environment.
d) A generalized user-friendly graphical user interface (GUI) is developed for the codified SAO developed in c)
15
2) The optimality and performance of the proposed algorithm in 1) is evaluated using thirty-nine (39) carefully selected benchmark mathematical optimization test functions.
a) Mathematical function are formulated as a metric which is used to determine the complexity of each of the selected benchmark functions.
b) The modality, plateau, valley, decomposability and dimensionality of each test function is determined using their respective hyperspace structure and the formulated metric function in 2a)
c) The algorithm to be developed in 1) is applied to the selected test functions and precision and convergence time is used as performance metrics.
3) Replication of the GBMO and the FFOA.
a) The performance of the replicated GBMO is evaluated using the selected test functions in item 2).
b) The performance of the replicated FFOA is also evaluated using the same test function.
c) Items 3a) and 3b) are compared with the SAO to be developed in 1) as a means of validation.
4) The developed SAO is used to develop an efficient path planning model for a mobile robot.
a) A suitable model of visibility graph based mobile robot path planning is developed using Euclidean distance as an objective function.
b) A static environmental scenario is generated in a square field area with dynamic positions of robot and goal.
16
c) The developed SAO is employed to determine the shortest path to move from a specified initial position to a specified final position while avoiding collision with the obstacles.
5) The developed SAO is employed to develop an efficient model of minimum spanning tree
a) Defined the vertex of the minimum spanning tree problem containing tree different scenario (the first scenario contains 15 vertices; the second scenario contains 20 vertices and the third scenario contains 30 vertices).
b) Initialize the edges of each vertex connecting each order in each of the scenarios of (a.).
c) Starting from the edge with the most minimum weight, compute the weight at each vertex (node)
d) Perform item 5 c) until the most minimum weight is obtained.
6) Items 4) and 5) are repeated using the PSO and SDA based approaches and the performances compared with that of the SOA based approach using optimality precision and convergence as performance metrics.
1.7 Scope of Study
The scope of this research which developed a novel optimization algorithm (smell agent optimization) inspired by the phenomenon of smell are highlighted as follows:
1) The research will not, at this point, develop some empirical formulae for selecting/determining the control parameters (i.e. temperature and mass) of the developed SAO.
2) The research will not, at this point, model an empirical formula for the psychological and environmental conditions which have direct effect on the
17
smell perception of the agent. It will be assumed that these and other physical factors as well as the olfactory lobes contribute to the olfaction capacity of the agent.
1.8 Thesis Organisation
The introduction to the thesis has been presented in Chapter One. The rest of the thesis is structured as follows: Detailed review of related literature and relevant fundamental concept on smell perception, benchmark functions and the selected optimization problems are presented in Chapter Two. In-depth approach and relevant mathematical models describing the smell agent optimization, path planning and minimum spanning tree were presented in Chapter Three. The analysis, performance and discussion of results were analysed in Chapter Four. Conclusions and recommendations make up Chapter Five. Quoted references and Appendices are also provided at the end of this thesis.
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
