Method for particle swarm optimization with random walk

摘要

Described is a method for particle swarm optimization (PSO) utilizing a random walk process. A plurality of software agents is configured to operate as a cooperative swarm to locate an optimum of an objective function. The method described herein comprises two phases. In a first phase, the plurality of software agents randomly explores the multi-dimensional solution space by undergoing a Brownian motion style random walk process. In a second phase, the velocity and position vectors for each particle are updated probabilistically according to a PSO algorithm. By allowing the particles to undergo a random walk phase, the particles have an increased opportunity to explore their neighborhood, land in the neighborhood of a true optimum, and avoid prematurely converging on a sub-optimum. The present invention improves on what is currently known by increasing the success rate of the PSO algorithm in addition to reducing the required computation.

主权项

1. A system implementing particle swami optimization, the system comprising one or more processors that are configured to perform operations of:
operating a plurality of software agents as a cooperative swarm to locate an optimum of an objective function, wherein each agent is assigned an initial velocity vector to explore a multi-dimensional solution space, where each agent is configured to perform at least one iteration, the iteration being a search in the multi-dimensional solution space for the optimum of the objective function, where each agent keeps track of a first position vector representing a current best solution yi that the agent has identified, and a second position vector used to store the current global best solution yg among all agents; wherein in a first phase, the plurality of software agents randomly explore the multi-dimensional solution space utilizing a random walk process to locate, the optimum of the objective function; wherein in a second phase that follows the first phase, the velocity and position vectors for a particle i are updated probabilistically to locate the optimum of the objective function; wherein in the first phase, each agent is driven by a random force according to the following:v->i⁡(t+1)=w⁢v->i⁡(t)+c0⁢q->0⁡(t)x->i⁡(t+1)=x->i⁡(t)+χ⁢v->i⁡(t+1),wherein for t≧1, yi and yg and are computed according to:y->i⁡(t+1)={x->i⁡(t+1),if⁢⁢J⁡(x->i⁡(t+1))>J⁡(y->i⁡(t))y->i⁡(t),otherwise⁢⁢y->g⁡(t+1)=arg⁢⁢maxy->i⁢J⁡(y->i⁡(t+1)),where {right arrow over (xi)}(t) is a position vector and {right arrow over (vi)}(t) is a velocity vector at an iteration t of an i-th agent, w is a momentum constant that prevents premature convergence of the agents, x is a constriction factor which influences the convergence of the agents, c0 is a constant, q0(t) is a vector with the same dimension as {right arrow over (vi)} or {right arrow over (xi)} with a set of uniformly distributed random components in [−1.0, 1.0] drawn on each iteration, wherein the current best yi and the global best yg computed in the first phase are used as an initial current best yi and global best yg in the second phase;
wherein the first phase runs for a predetermined number of iterations prior to initiation of the second phase; and wherein the plurality of software agents converge at a position in the multi-dimensional solution space representing an optimum of the objective function, wherein the objective function is J({right arrow over (y)}g).