Development of a  Smell Agent Optimization Algorithm for Combinatorial Optimization Problems

Development of a  Smell Agent Optimization Algorithm for Combinatorial Optimization Problems.

ABSTRACT

This thesis presents the development of the smell agent optimization (SAO) algorithm. The developed algorithm consists of three modes (sniffing, trailing and random modes). The evaporation of small 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 model 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 small molecules due to the Brownian nature of the smell molecules. This is largely responsible for 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 that 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 processor to start the entire process of the SAO all over again.

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

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

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

INTRODUCTION

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 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.

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.

StudentsandScholarship Team.