Bacterial Foraging Optimization Algorithm And Its Application Study

Optimization problems are widespread in social life,engineering practice,and scientific research,and solving optimization problems is of great practical significance and scientific value.Swarm intelligence is an effective technology to solve complex optimization problems,and is currently a hotspot in the modern optimization field.As a new swarm intelligence method,bacterial foraging optimization(BFO)has been sucessfully applied to some fields.However,there are two deficiencies in the study on BFO.Firstly,the theoretical researches are relatively less,and all make analysis specific to one-dimensional objective functions.Secondly,the existing application researches mostly focus on the single objective function optimization problems and pay less attention on complex optimization problems.To address the two above deficiencies in the study on BFO,this thesis focuses on the following five innovative points from three levels including the theoretical research,function optimization,and discrete optimization:1.In the theoretical research,the stability analysis of the chemotaxis mechanism in BFO is extended to multi-dimensional objective functions from one-dimensional objective functions.At first,the dynamic system model about the chemotaxis mechanism over the multi-dimensional objective function is created,and two necessary conditions for ensuring convergence of the chemotaxis mechanism are pointed out through theoretical analysis on the dynamic system model.Then the dynamic system model over the multi-dimensional case is proved to be stable using the Laypunov stability theorem.The experimental results on two typical function optimization problems establishes the effectiveness of the two necessary conditions.2.To aimed at the problem of single objective function optimization,a bacterial foraging optimization algorithm based on the adaptive chemotaxis and conjugation strategies is proposed.This algorithm first initializes each bacterial individual into a real vector in solution space and evaluates each individual based on the objective function value.Then it performs adaptive chemotaxis,conjugation,reproduction,and elimination and dispersal mechanisms to complete the optimization processes of individual solutions.The adaptive chemotaxis mechanism adopts two new strategies: the uniform step size and the standard basis vector direction.The uniform step size is adaptively adjusted based on the evolutionary generations and the information of global best individual,which effectively avoid the imbalance of the local search and global search caused by the fixed step size of BFO.The standard basis vector direction may obviate calculating an random unit vector and could effectively get rid of interfering with each other between different dimensions when updating an individual solution.As a new biological mechanism simulated,the conjugation mechanism helps each bacterial individual to exchange information with other individuals,which overcomes the shortcoming of lack of communication in BFO.At last the experimental results on standard test functions and real-world problems demonstrate the excellent performance of this algorithm in terms of solution quality and computation efficiency compared with multiple swarm intelligence optimization algorithms.3.To aimed at the problem of multi-objective function optimization,a multi-objective bacterial foraging algorithm based on archive strategy is proposed.This algorithm first initializes each bacterial individual into a real vector in solution space and evaluates each individual based on the Pareto dominant concept.Then it sets internal and external bacterial populations.The internal bacterial population performs adaptive chemotaxis,conjugation,reproduction,and elimination and dispersal mechanisms to complete the optimization processes of individual solutions.The external bacterial population(i.e.,archive)stores the elite solutions(non-dominanted solutions)previously found in the optimization process of the internal bacterial population,and utilizes the crowding distance to maintain its diversity.Whenever the internal bacterial population carries out one chemotaxis process,the external bacterial population will update its individuals.At last the experimental results on standard test functions confirm that the non-dominated solutions obtained by this algorithm can satisfactorily approach the optimal non-dominated solutions and distributes uniformly compared with classical algorithms.4.To aimed at the problem of Bayesian network structural learning,a learning algorithm based on bacterial foraging optimization is proposed.This algorithm first initializes each bacterial individual into a Bayesian network with less arcs and uses the K2 score metric to evaluate each individual.Then for completing the optimization processes of individual solutions,it performs chemotaxis,reproduction,and elimination and dispersal mechanisms to constantly search Bayesian networks with higher K2 scores.At last the experimental results on multiple standard datasets demonstrate that the Bayesian network learned by this algorithm has a higher K2 score and smaller structural difference compared with different kinds of algorithms.5.To aimed at the problem of detecting functional modules in a protein-protein interaction network,a detection algorithm based on bacterial foraging optimization is proposed.This algorithm fist initializes each bacterial individual into a functional module partition based on a random walk behavior and uses the modularity metric to evaluate each individual.Next for completing the optimization processes of individual solutions,it performs chemotaxis,conjugation,reproduction,and elimination and dispersal mechanisms to constantly search functional module partitions with higher modularity.Then it utilizes two post-processing operators to refine the preliminary module partition obtained in the optimization process.At last the experimental results on public datasets demonstrate that this algorithm is able to more effectively detect functional modules with biological significance compared with various algorithms.The above research work in this thesis,on the one hand perfects the basic theoretical system of BFO and laid a more solid theoretical basis for its application on different optimization problems,on the other hand expands the application fields of BFO and provides new approaches for some complex optimization problems.Therefore,the researches of this thesis not only have the theoretical significance,but also the practical value.