Studies Of Bio-inspired Optimization Algorithm Based On Positive Feedback Mechanism

In recent years, by simulating natural ecosystem, there emerges a large number of intelligent bionic algorithms for solving complex optimization problems, such as genetic algorithm, par-ticle swarm optimization algorithm, ant colony algorithm, artificial immune algorithm and firefly algorithm, etc These algorithms have similar features-the behavior of each individual is simple and random, while these individuals can collaborate with each other to complete a series of complex tasks. These intelligent optimization algorithms have a wide range of appli-cations, especially in the engineering design, resource allocation, survival plan, transportation and so on. According to recent studies, an primitive organism, Physarum polycephalum. shows a great intelligent in path optimization and network design. Studies found that Physarum polycephalum can solve a maze in the process of feeding and construct a tubular network which is comparable to the real Tokyo rail network in terms of efficiency, cost, and fault tolerance. This kind of intelligent organism has attracted lots of attention from researchers.At present, many algorithms and models are proposed to analyze and simulate the in-telligent behavior of Physarum polycephalum. In this paper, we mainly focus on a adaptive mathematical model, Physarum Solver. In Physarum Solver, the flow of liquid in its con-structed tubes is assumed firstly for Poiseuille’s law. Then, this model takes conductivity as a way to measure the thickness of each tube quantitatively. More importantly, an evolution equation is provided to simulate the positive feedback mechanism between the internal flow of tubes and conductivity-the larger the conductivity is, the greater the internal flow is; the greater the internal flow, the larger the conductivity. Otherwise, the opposite is true. Based on this positive feedback mechanism, Physarum Solver is biologically modeled and has shown a lot of intelligence. However, there are also some disadvantages as follows:(a) In Physarum Solver, the most important steps of the internal iteration in Physarum Solver is to solve the stress equations of Kirchhoff. The computational complexity of solving the Kirchhoff equa-tions is n3, where n is the number of nodes of a strong-connected network; (b) The original Physarum Solver can only be applied to solve shortest path problem in undirected graphs; (c) It requires the global structure information of graphs for Physarum Solver to build Kirchhoff equations, which limits its application scope; (d) Physarum Solver takes Kirchhoff equations to compute node pressure, which brings the disadvantage of not being able to process infor-mation independently. This also means Physarum Solver is difficult to be dealt with the form of parallel computing.At first, this paper analyzes the inner positive optimization mechanism of Physarum Solver. Then, we extend this model to deal with graphs with multi-source and multi-sink. Then, we extend this model to solve the classical transportation problems and generalized transportation problems in directed graphs. Based on positive feedback mechanism between internal flow of tubes and conductivity, we firstly propose a brand-new energy propagation model to solve a series of practical optimization problems, including transportation problem, maze, shortest path tree problem, dynamic shortest path tree problem and maximal flow problem.In this paper, the main works include the following aspects:(1) Introduction of Physarum SolverFirst, we take a famous experiment of Physarum polycephalum-solving a maze-to explicitly introduced and explain the core optimization mechanism of its mathematical mod-el Physarum-Solver. Last, both Physarum Solver and this improved algorithm Directed Physarum Solver are introduced.(2) Modification of Physarum Solver to solve Transportation problemsThe original Physarum Solver has not been applied to the case of graphs with multi-source multi-sink. Therefore, we try to extend the positive feedback optimization mechanism to work under graphs with more than one source and sink. As demonstrated by experi-ments, the modified model can effectively solve balanced transportation problem, unbalanced transportation problem and generalized transportation problem.(3) A novel energy propagation modelTraditional Physarum Solver is not capable of relying on local information to solve short-est path problem and can’t be possessed in parallel computing. Inspired by same basic laws in physics, we put forward an abstract energy propagation law. Besides, a particle with a unit of energy can be stored temporally on the node. Thanks to this special assumption, the updat-ing of energy flow can be obtained by using the information of its adjacent nodes. Based on optimization mechanism, experiments demonstrate the proposed energy propagation model can find the shortest path in a maze.(4) Application of energy propagation model to solve some optimization problemsThe energy propagation model is initially proposed to solve a maze. We try to extend to the cases of multi-source multi-sink and one-source multi-sink. As demonstrated by experi-ments, this model can be extended and applied to solve transportation problem, shortest path tree problem. What’s more, we use this model to select routes in wireless sensor networks, especially in dynamic wireless sensor networks.(5) A preliminary method of solving maximum flow problem based on energy propagation modelThere are still a lot of ways of applying positive feedback mechanism to solve optimization problems. In this paper, we propose a preliminary model to solve maximum flow problem: first, we build a virtual path between a source node and a sink node and let most of flux flow among this virtual path; By using positive feedback mechanism, flow will gradually converge to the original network and finally the maximum flow will be obtained when the flow is steady.