ABSTRACT
his research was aimed at the development of an improved artificial fish swarm optimization algorithm based on knowledge (normative and situational) in cultural algorithm and crossover operator called the modified Cultural Artificial Fish Swarm Algorithm with Crossover (mCAFAC). The Normative and Situational knowledge inherent in cultural algorithm were utilized to guide the step size as well as the direction of evolution of AFSA at different configurations, in order to combat the ease at which AFSA falls into local minima. An inertial weight selection is adopted such that the algorithm can adaptively select its parameters (visual and step size) when searching for global solution. Crossover operator was applied to fuse the AFSA and the modified Cultural Artificial Fish Swarm Algorithm called the mCAFAC, in order to enhance its convergence to a global minimal. Four variations of mCAFAC (mCAFAC_Ns, mCAFAC_Sd, mCAFAC_NsSd and mCAFAC_NsNd) were implemented in Matlab R2013b using different configurations of the cultural knowledge. A total of sixteen test functions (Ackley, Cosine Mixture, Rastrigirn etc.) were employed to evaluate the performance of each mCAFAC variant. Simulation results showed that the mCAFAC outperformed the original AFSA with the mCAFAC_NsSd having superior performance over all the other variants.mCAFAC_NsSd produced the best result in 9 out of the 16 test cases (56.25%) while mCAFAC_NsNd produced the best result in 1 out of the 16 test cases (6.25%), mCAFAC_Ns produced the best result in 3 out of the 16 test cases (18.75%) and mCAFAC_Sd produced the best result in 1 out of the 16 test cases (6.25%). All the variants, including the standard AFSA, the modified AFSA and the replicated ABC produced the same result in 2 out of the 16 test cases (12.5%).mCAFAC_NsSd was then applied to determine the optimal values of the weighting matrices (Q and R) of linear quadruple regulator (LQR) controller.This was validated on the quadrupleInverted Pendulum (QIP) model where the obtained LQR was able to stabilize the model in 7.4161s as against 7.5162s when using the conventional trial-and-error LQR method. This showed a convergence of the solution space using both approaches with the LQR (mCAFAC) having a more optimal time-to-solution.
TABLE OF CONTENTS
DEVELOPMENT OF AN IMPROVED CULTURAL ARTIFICIAL FISH SWARM ALGORITHM WITH CROSSOVER
DECLARATION ii
CERTIFICATION iv
DEDICATION v
ACKNOWLEDGEMENT vi
ABSTRACT viii
LIST OF TABLES xv
LIST OF FIGURES xi
LIST OF ABBREVIATIONS xvi
CHAPTER ONE:INTRODUCTION
1.1 Background on Heuristics Optimization 1
1.2 Background on Optimal Control Theory 3
1.3 Aim and Objectives 5
1.4 Statement of Problem 6
1.5 Methodology 7
1.6 Significant Contributions 9
1.7 Theis Organization 9
CHAPTER TWO:REVIEW OF FUNDAMENTAL CONCEPTS
2.1 Introduction 10
2.2 Review of Fundamental Concepts on Heuristic Methods 10
2.2.1 Artificial fish swarm algorithm 10
2.2.2 Cultural algorithm 16
2.2.3 Genetic algorithm 24
2.2.4 Particle swarm optimization 26
2.2.5 Artificial bee colony optimization algorithm 28
2.2.6 Standard optimization test functions 34
2.2.6.1 Ackley function 34
2.2.6.2Cosine-Mixture function 35
2.2.6.3 DeJongF4 function 35
2.2.6.4 Expfun function 35
2.2.6.5 Griewangk function 36
2.2.6.6 Hyperelliptic function 36
x
2.2.6.7Levy and Montelvo first function 36
2.2.6.8 Levy and Montelvo second function 37
2.2.6.9 Neumaier3 function 37
2.2.6.10 Rastrigin function 37
2.2.6.11 Rosenbrock function 38
2.2.6.12 Sal Function 38
2.2.6.13 Schwefel function 39
2.2.6.14 Schaffer function 39
2.2.6.15 Sphere function 40
2.2.6.16 Bukin N.6 function 40
2.2.7 Determination of optimal values of weighting matrices in LQR problems 40
2.2.7.1 Design choice for determination of LQR weighting matrices 42
2.3 REVIEW OF SIMILAR WORKS 44
CHAPTER THREE: METHODS AND MATERIALS
3.1 Introduction 53
3.2 Modified artificial fish swarm algorithm 53
3.2.1 Modified preying behaviour 53
3.2.2 Modified swarming behaviour 54
3.2.3 Modified chasing behaviour 54
3.3 Modified Cultural Artificial Fish Swarm Algorithm with Crossover 57
3.3.1 mCAFAC Knowledge adjustment 57
3.4 Design Choices for the mCAFAC Influence Function 58
3.4.1 mCAFAC_Ns: mCAFAC Using normative knowledge 58
3.4.2 mCAFAC_Sd: mCAFAC using situational knowledge 60
3.4.3 mCAFAC_NsSd: mCAFAC using normative knowledge and situational knowledge 62
3.4.4 mCAFAC_NsNd: mCAFAC using normative knowledge for step size, visual distance and the direction of evolution 64
3.5 Recombination Operator 66
3.6 Determination of Weighting Matrices Using mCAFAC 68
3.6.1quadruple inverted pendulum stabilization 69
CHAPTER FOUR: RESULTS AND DISCUSSIONS
4.1 Introduction 75
4.2 Visualization of the Optimization Test Function 75
4.2.1 Ackley function 75
4.2.2 CM function 76
4.2.3 DeJongF4 function 76
xi
4.2.4 Expfun function 77
4.2.5 Griewangk function 77
4.2.6 Hyperelliptic function 78
4.2.7 Levy and Montelvo first function 78
4.2.8 Levy and Montelvo second functions 79
4.2.9 Neumaier3 function 79
4.2.10 Rastrigin test function 80
4.2.11 Rosenbrock test fuction 80
4.2.12 Sal test function 81
4.2.13 Schwefel test function 81
4.2.14 Schaffer test function 82
4.2.15 Sphere test function 82
4.2.16 Bukin N.6 test function 83
4.3 Performance Evaluation of Proposed AFSA Algorithms 83
4.3.1 Performance evaluation of AFSA (With and Without Inertial Weight) 83
4.3.2 Performance evaluation of mCAFAC_Ns using normative knowledge. 85
4.3.3 Performance evaluation of mCAFAC_Sd using situational knowledge 86
4.3.4 Performance evaluation of mCAFAC_NsSd using situational knowledge. 86
4.3.5 Performance evaluation of mCAFAC_NsNd using situational knowledge. 87
4.3.6 Performance evaluation of artificial bee colony (ABC) algorithm 88
4.4 Parameter Settings for the Proposed Algorithm 89
4.5 Artificial Bee Colony Parameters 90
4.6 Computer System Specification 90
4.7 Application of the Proposed Controller for Optimal Determination of Controller Parameters 91
CHAPTER FIVE: CONCLUSION AND RECOMMENDATIONS
5.1 Introduction 96
5.2 Summary of Findings 96
5.3 Conclusion 97
5.3 Limitations 6
5.4 Recommendations for Further Work 7
REFERENCES 98
APPENDIX A1
m-FILE Code of AFSA. 105
APPENDIX A2
m-FILE for Artificial Bee Colony (Abc) Algorithm 109
APPENDIX B1
xii
CHAPTER ONE
INTRODUCTION
1.1 Background on Heuristics Optimization
Optimization is a subject that deals with the problem of minimizing or maximizing a certain function in a finite dimensional space over a subset of that space, which is usually determined by functional inequalities (Wang & Li, 2015). During the past century, optimization has been developed into a mature field that includes many branches, such as linear conic optimization, convex optimization, global optimization, discrete optimization, etc. Each of such branches has a sound theoretical foundation and is featured by an extensive collection of sophisticated algorithms and software. Optimization, as a powerful modelling and problem solving methodology, has a broad range of applications in management science, industry and engineering (Nashat et al., 2012)
There is no known single optimization method available for solving all optimization problems. Several Optimization Algorithms have been developed in recent years. These Algorithms includes, Artificial Fish Swarm Algorithm (AFSA) (Li, 2002), Artificial Bee Colony Optimization (ABC) (Karaboga, 2005), Particle Swarm Optimization (PSO) (Eberhart & Kennedy, 1995), Genetic Algorithm (GA) (Holland, 1959), Ant Colony Optimization (ACO) (Dorigo, 1996), Fire-Fly Algorithm (FFA) (Yang, 2010), Bacterial Foraging Algorithm (BFA) (Passino, 2002) and Cultural Algorithm (CA) (Reynolds, 1994).
Some of these optimization methods mimicking evolution, animal behaviour, rules of natural ecology and mechanisms of human culture in nature were developed in order to solve certain categories of complicated scientific, Social and engineering design problems (Chung, 1997):
i) Weak problems, problems with little or no domain knowledge
ii) Non-deterministic Polynomial (NP) complete problems
2
iii) Problems for which a near optimal solution can be acceptable
iv) Problems with non-smooth (discontinuous; not-differentiable) and noisy search space.
v) Problems whose environments are uncertain and/or dynamic
This research considers artificial fish swarm optimization, a relatively recent addition to the field of natural computational intelligence that has elements inspired by the social behaviours of natural swarms of fish. Since its introduction in 2002, AFSA has found widespread application in complex optimization domains, and is currently a major research topic, offering an alternative to the more established evolutionary computational techniques that may be applied in many of the same domains.
The AFSA algorithm was first introduced by Li Xiao Lei (Li et al., 2002)and its basic idea was inspired by simulation of the social behaviour of fish(Li et al., 2002). It is based on the natural process of group communication to share individual knowledge when a group (Swarm) of fish search for food, although all fish do not know where the best food source is. But from the nature of the social behaviour, if any member can find out a desirable path to go, the rest of the members will follow suit quickly (Neshat et al., 2012). AFSA is modelled using the three (Preying, Swarming and Chasing) basic behaviour of fish. In this algorithm, each fish swarms through the multidimensional search space and adjusts its position in every step with its own experience and the experience of neighbouring fishes toward an optimum solution by the entire swarm (Li, 2002). Its next behaviour depends on its current state and its local environmental state (including the quality of the question solutions at present and the states of nearby companions).
AFSA possess similar attractive features of genetic algorithm (GA) such as independence from gradient information of the objective function, the ability to solve complex nonlinear
3
high dimensional problems. Moreover, they can achieve faster convergence speed and require few parameters to be adjusted. The system is started first in a set of randomly generated potential solutions, and then performs the search for the optimum solution one interactively (Zhang et al. 2006). Similar to human evolution processes, the evolution of AFSA can be represented in form of Cultural Evolution Process (CEP).
Cultural Algorithms were initially developed by Reynolds (Reynolds, 1994) in order to model the evolution of the cultural component of an evolutionary computational system over time as it accumulates experience. The cultural algorithm framework offers a mechanism supporting the dual inheritance system characterizing both the human culture at the macro evolutionary level, and individual phenotypic evolution at the micro evolutionary level (Chung, 1997). It also provides a framework in which knowledge acquired at the cultural level is isolated and exploited to accelerate the problem solving process. This research focuses on modifying the AFSA, using the cultural algorithm knowledge to accelerate the problem solving process during evolution of AFSA.
1.2 Background on Optimal Control Theory
Optimal control theory is a mathematical optimization method which is an extension of the calculus variation with numerous applications in control engineering (Ata & Coban, 2015). Verifying the control signals that will cause a process to meet the desired physical constraints and also optimization (maximization or minimization) of some performance criteria are the main objectives of optimal control system (Das et al., 2013). A special case of the general nonlinear optimal control problem where the cost function is quadruple and the system dynamics are described by a set of linear differential equations is a linear quadruple optimal control problem (Schildbach et al., 2015).
4
One of the challenging control and benchmark problems in the field of complex non-linear
control system is the swinging of an inverted pendulum. Stabilizing and control of such an
unstable system has been a major subject of research for control engineers. A cart-driven
inverted pendulum has a structure where the pendulum is hinged to the cart via a pivot and
only the cart is actuated (Boubaker, 2013). The motion of the pendulum has to be controlled
by moving the cart back and forth within a limited movement of the cart. The linearized
quadruple inverted pendulum (QIP) adopted in this research is obtained from the unpublished
M.Sc work of Abdullahi Mohammed(Abdullahi, 2014). Figure 1.1 shows the free diagram of
a typical QIP inverted pendulum.
P1
P2
P3
P4
Figure 1.1: Free Body Diagram of Quadruple Inverted Pendulum (QIP)
Where P1, P2, P3 and P4 are the first, second, third and fourth pendulum respectively of the
QIP of Figure 1.1.
5
Linear Quadruple Regulator (LQR) optimal controllers have been predominantly used for the control of such movement as inverted pendulum. The critical design parameters for the LQR are the weighting matrices (Q and R) in the cost function and are normally selected by the designer(Hamidi, 2012). The other parameters, the state and input matrices (A and B), are obtained from the state model of the system. Hence, even though the LQR is an optimal scheme, the method of selecting Q and R is not optimal.
1.3 Aim and Objectives
The aim of this research is to develop an improved artificial fish swarm optimization algorithm based on knowledge in cultural algorithm and crossover operator called modified Cultural Artificial Fish Swarm Algorithm with Crossover (mCAFAC). An inertial weight selection was introduced such that the algorithm can adaptively select its parameters when searching for global solution. The objectives of the research are as follows:
i) Development of the improved artificial fish swarm optimization algorithm, mCAFAC, using knowledge in culture algorithm, Inertia Weight and genetic crossover operator. These modifications should not significantly complicate the algorithm but should improve its convergence speed, its robustness and its ability to escape local minima.
ii) Evaluation of the performance of the algorithm using sixteen well-known test functions (such as: Ackley, Dejongf4, Schwefel etc.).
iii) Validation of the performance of the algorithm by comparison of the results in item ii) with those obtained using standard AFSA and Artificial Bee Colony (ABC) Algorithm.
6
iv) Application of the mCAFAC to determine the weighting matrices (Q and R) of Linear Quadruple Regulator (LQR). This is validated using the Quadruple Inverted Pendulum (QIP) model.
1.4 Statement of Problem
The AFSA can search for global optimum effective, and has an adaptive ability for search space. The individual behaviour is to search for local optimum, therefore avoiding individual premature becomes difficult due to slow convergence speed at later stage, a lot of Artificial Fish (AF) performs invalid search which increases the computation time and decreases precision accuracy. In this case, artificial fish can be stuck into local optima when dealing with multi-modal optimization problems. Parameters such as visual distance and step size have demonstrated great influence on the performance of the algorithm. When the visual distance is large, the AFSA has strong global searching ability and when the visual is small, the AFSA has strong local searching ability.Similarly the bigger the step size, the faster the convergence speed and the smaller the step the slower the convergence speed. In order to combat these shortcomings, a modified cultural artificial fish swarm algorithm with inertia weight and crossover operator is developed.
1.5Scope and Limitations
The limitations of this research work are highlighted as follows:
i) This research work did not consider negative cultural knowledge.
ii) This research work did not consider other form of cultural knowledge (such as: Domain, Topographical and Historical knowledge)
7
iii) This research work did not consider the improvement on artificial bee colony algorithm
5.4 Recommendations for Further Work
The following possible areas of further work are recommended for consideration for future research:
1. Other types of Cultural knowledge such as Historical, Topographical or Domain knowledge can be considered as alternative source of belief space structure instead of the Normative and/or Situational.
2. Modelling cultural based versions of other heuristic algorithms such as Artificial Bee Colony (ABC), FireFly Algorithm (FFA), Bacterial Foraging algorithm (BFA), Cuckoo Search Algorithm (CSA), etc. can be considered.
3. The effect of negative cultural knowledge can also be investigated.
4. Hybridization of AFSA with other heuristic optimization algorithms such as Artificial Bee Colony (ABC), FireFly Algorithm (FFA), Bacterial Foraging algorithm (BFA), Cuckoo Search Algorithm (CSA), etc. can be considered.
5. The algorithm can be applied to areas such as image processing, data clustering, WSN deployment power system stability analysis, constrained and unconstrained optimization problems etc.
1.5 Methodology
The methodology adopted for this research involves developing the artificial fish swarm algorithm using Matlab 2013Rb Control/Optimization toolboxes, then both situational and normative knowledge in cultural algorithm was used to guide the evolution, which will then
8
be use to initialize the population of the proposed improved algorithm. The steps of the proposed algorithm are highlighted as follows:
1. Initialize the population of artificial fish, which shall be N number of fish in D dimension.
2. Develop the AFSA algorithm as described in Figure 1.1.
a. Preying Behaviour
b. Swarming Behaviour
c. Chasing Behaviour
3. Knowledge (Situational and Normative) in cultural algorithm is used to guide the evolution of AFSA.
4. Inertial weight selection is introduced, such that the algorithm can adaptively select its own parameters during evolution.
5. Crossover criterion is set to judge whether the algorithm falls into local optima or not.
6. Four Variation of Modified Cultural Artificial Fish Swarm Algorithm are developed, which include:
a) mCAFAC_Ns.
b) mCAFAC_Sd.
c) mCAFAC_NsSd
d) mCAFAC_NsNd
7. The Modified algorithm is validated using a total of sixteen optimization test functions (e.g. Ackley, Cosine Mixture, Rastrigirn etc.)
8. The performance of the modified algorithm is compared with that of the Artificial Bee Colony (ABC) algorithm.
9. Finally, the Algorithm is also used to determine the weighting matrices of the LQR controller used for the quadruple inverted pendulum (QIP) model.
9
1.6 Significant Contributions
A lot of research works have been done on improving the precession accuracy and convergence speed of Artificial Fish Swarm Algorithm. Many researches have also been conducted on different area of its application. The significant contributions of this research work are as follows:
i. Development of a modified Cultural Artificial Fish Swarm Algorithm with Crossover (mCAFAC) and inertial weight with particular emphasis on visual distance and step size. This has added adaptive capabilities to the standard AFSA
ii. Four variants of the mCAFAC using different configurations of cultural knowledge were developed and validated on several test functions. All the variants (mCAFAC_Ns, mCAFAC_Sd, mCAFAC_NsSd and mCAFAC_NsNd) outperformed the standard AFSA by 18.75%, 6.25%, 56.25% and 6.25% respectively
iii. mCAFAC was used to obtain the optimal weighting matrices (Q and R) of Linear Quadruple Regulator (LQR) controller, which are critical in stabilizing and optimally controlling systems. This was validated using the QIP as a case study and the values obtained using the settling time as a metric. The LQR (mCAFAC) settled the QIP in 7.4161s as against 7.5162s obtained using the LQR (conventional trial-and-error method)
1.7 Thesis Organization
The general introduction has been presented in Chapter One. The rest of the chapters are structured as follows: Detail review of related literatures and relevant fundamental concept
10
about AFSA, CA, PSO, GA, ABC and LQR is carried out in Chapter Two. In-depth approach and relevant mathematical models describing the modification of an improved cultural artificial fish swam algorithm with crossover alongside the application LQR weighting matrices determination and QIP stabilization analysis were presented in Chapter Three. The analysis, performance and discussion of the result were analysed in Chapter Four. Conclusion and recommendations makes up the 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»
