Wed PM: discussion write up time …

Continuing to write up the PSO discussion. A framework is certainly there now — should hopefully have more flesh ont he bones after tomorrow, and then should be a ac ase of tidying it up into a suitable state at a later stage.

Tomorrow planning to look that the the1.pdf file in the PSO directoy — should be good.

NB notes from Will re: potential flocking models:

• Second Life 3d environment
• Microsoft Robotics lab

Thursday PM: notes to self …

REREAD

• Data Clustering with Particle Swarms
• A Distributed Particle Swarm Optimization Algorithm for Swarm Robotic Applications
• EVOLVING BEHAVIORS FOR A SWARM OF UNMANNED AIR VEHICLES

PRINT

• IMMUNE, SWARM, AND EVOLUTIONARY ALGORITHMS PART I BASIC MODELS
• IMMUNE, SWARM, AND EVOLUTIONARY ALGORITHMS PART 11 PHILOSOPHICAL COMPARISONS
• In Search of the Essential Particle Swarm

SEARCH

• OPTIMISATION Semantic web

2

Thursday PM: finals throes of collected materials …

• RUSSELL C. EBERHART, & YUHUI SHI,
  • Special Issue on Particle Swarm Optimization
  • IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 8, NO. 3, JUNE 2004
  • It has been reported that the global version of PSO converges fast, but with potential to converge to a local minimum, while the local version of PSO might have more chances to find better solutions slowly.
  • It is also found by some researchers that PSO with small neighborhoods might perform better on complex problems, while PSO with large neighborhoods would perform better for simple problems. Generally, each neighborhood structure has its strengths and weaknesses. It works better on one kind of problem, but worse on another kind of problem.
• NB remember to look at Rui Mendes PhD thesis for details on optimisation / optimization
• See p58 of the Rui Mendes Thesis for details on application if required
• Shi, Y. and Eberhart, R. C. (1998a). Empirical study of particle swarm optimization. In Evolutionary Programming VII, pages 591600. — for a list of optimisation test functions

2

Wednesday PM: finishing off the discussion work …

From the remains of vitually all articles (few tailenders to go through tomorrow AM):

• Comparison of Different Heuristic Optimization Methods for Near-Field Antenna Measurements
• Jesús Ramón Pérez and José Basterrechea, Member, IEEE
• IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, VOL. 55, NO. 3, MARCH 2007
• PSO demonstrates greater computational effiency cf. GA, Simplex Algorithm and Simmulated Annealing
• UCI Repository of Machine Learning Databases, “On line Datsets”,
• http://www.ics.uci.edu/~mlearn/MLSummary.html
• Evolving High-Performance Evolutionary Computations for Space Vehicle Design
• Gerry Dozier, Win Britt, Michael P. SanSoucie, Patrick V. Hull, Michael L. Tinker, Ron Unger, Steve Bancroft, Trevor Moeller, Dan Rooney
• 2006 IEEE Congress on Evolutionary Computation
• Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada
• July 16-21, 2006
• The GAs had better performances than all of the PSOs when allowing fewer than 1000 evaluations. However, when the number of allowable evaluations was increased to 1500, the micro-GAs and the PSO using the star topology had similar performances. The PSOs that used the ring and random topologies were the worst performers overall.
• Floorplanning Based on Particle Swarm Optimization
• Tsung-Ying Sun, Member, IEEE, Sheng-Ta Hsieh, Student Member, IEEE, Hsiang-Min Wang and Cheng-Wei Lin
• Proceedings of the 2006 Emerging VLSI Technologies and Architectures (ISVLSI’06)
• PSO exhibits the ability of searching the solution space more efficiency than Simulated Annealing, Furthermore, PSO can save more computation time for finding an acceptable solution.
• Stochastic Optimization Techniques for Economic Dispatch with Combined Cycle Units
• F. Gao, Student Member, IEEE, and G. B. Sheble, Fellow, IEEE
• 9th International Conference on Probabilistic Methods Applied to Power Systems
• KTH, Stockholm, Sweden – June 11-15, 2006
• PS and EP can be more appropriate than GA if solution space is well defined such as Case 1, for both of two utilize previous global information.  Particle swarms balances local and global searching, displaying more advantages.  On the other hand, if solution space highly skewed and tortuous, the previous global information may be wrong and mislead the searching procedure in particles swarms and evolutionary programming.  Thus, genetic algorithms may outweigh evolutionary programming and particle swarms.

Wednesday AM: Discussion work …

NB Applications of Evolutionary Computation in Electric Power Systems has intro to optimisation

• Bio-inspired Algorithms for the Design of Multiple Optimal Power System Stabilizers: SPPSO and BFA
  • Tridib K. Das and Ganesh K. Venayagamoorthy
  • 1-4244-0365-0/06/$20.00 (c) 2006 IEEE
  • The Small Population based Particle Swarm Optimization (SPPSO) however is found to be superior to the Bacterial Foraging Algorithm (BFA) both in number of fitness evaluations, the convergence speed and damping performances.
• Boundary Conditions in Particle Swarm Optimization Revisited
  • Shenheng Xu and Yahya Rahmat-Samii
  • IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, VOL. 55, NO. 3, March 2007
  • It is up to the user to choose the most suitable boundary condition according to one’s a priori knowledge of the specific problem.
• Proceedings of the 39th Hawaii International Conference on System Sciences – 2006
  • Comparison of Artificial Life Techniques for Market Simulation
  • Feng Gao, Student Member, IEEE, G. Gutierrez-Alcaraz, Member, IEEE, and
  • Gerald B. Sheble, Fellow, IEEE
  • EP (Evolutionary Programming) and PS can be more appropriate than GA if solution space is well defined, for both of them utilize previous global information. Furthermore, PS balances local and global searching, displays more advantages. However more operations are needed.  On the other hand, if solution space is highly skewed and tortuous, the previous global information may be wrong and mislead the searching procedure in PS and EP. Thus, GA will outweigh EP and PS in the
  • case.
  • The gradient of PS contains more information compared with GA and EP. Individual particle has a memory of its own optimal value, k i Pbest . All particles share a common knowledge, i.e. k i Gbest , the optimal value until current generation. All of particles move within a solution space according to historical global & local best solutions.
  • EP makes use of a Gaussian random perturbation term to update each generation. All of the candidates’ updating directions form an n-dimension random vector. EP does not apply local information; however each generation does share a common knowledge implicitly. The mutation factor phi-k is proportional to the ratio between the best profit and individual profits up to now. The bigger the ratio between the best profit and individual profits, i.e. individual profits is far from the best one, the greater is the change in X(sub_i)(super k+1) as compared to X(sub_i)(super_k) and vice versa.
  • The “gradient” of GA employs neither global nor local historical information. Crossover and mutation operators bring in new sense of change in direction through the use of a random alteration of solution value. Therefore it is necessary to apply simulation to measure the expected “gradient” of GA.

2

Wednesday AM: Discussion work …

NB Applications of Evolutionary Computation in Electric Power Systems has intro to optimisation

• Bio-inspired Algorithms for the Design of Multiple Optimal Power System Stabilizers: SPPSO and BFA
• Tridib K. Das and Ganesh K. Venayagamoorthy
• 1-4244-0365-0/06/$20.00 (c) 2006 IEEE
• The Small Population based Particle Swarm Optimization (SPPSO) however is found to be superior to the Bacterial Foraging Algorithm (BFA) both in number of fitness evaluations, the convergence speed and damping performances.
• Boundary Conditions in Particle Swarm Optimization Revisited
• Shenheng Xu and Yahya Rahmat-Samii
• IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, VOL. 55, NO. 3, March 2007
• It is up to the user to choose the most suitable boundary condition according to one’s a priori knowledge of the specific problem.
• Proceedings of the 39th Hawaii International Conference on System Sciences – 2006
• Comparison of Artificial Life Techniques for Market Simulation
• Feng Gao, Student Member, IEEE, G. Gutierrez-Alcaraz, Member, IEEE, and
• Gerald B. Sheble, Fellow, IEEE
• EP (Evolutionary Programming) and PS can be more appropriate than GA if solution space is well defined, for both of them utilize previous global information. Furthermore, PS balances local and global searching, displays more advantages. However more operations are needed.  On the other hand, if solution space is highly skewed and tortuous, the previous global information may be wrong and mislead the searching procedure in PS and EP. Thus, GA will outweigh EP and PS in the
• case.
• The gradient of PS contains more information compared with GA and EP. Individual particle has a memory of its own optimal value, k i Pbest . All particles share a common knowledge, i.e. k i Gbest , the optimal value until current generation. All of particles move within a solution space according to historical global & local best solutions.
• EP makes use of a Gaussian random perturbation term to update each generation. All of the candidates’ updating directions form an n-dimension random vector. EP does not apply local information; however each generation does share a common knowledge implicitly. The mutation factor phi-k is proportional to the ratio between the best profit and individual profits up to now. The bigger the ratio between the best profit and individual profits, i.e. individual profits is far from the best one, the greater is the change in X(sub_i)(super k+1) as compared to X(sub_i)(super_k) and vice versa.
• The “gradient” of GA employs neither global nor local historical information. Crossover and mutation operators bring in new sense of change in direction through the use of a random alteration of solution value. Therefore it is necessary to apply simulation to measure the expected “gradient” of GA.

Wednesday AM: Discussion work …

NB Applications of Evolutionary Computation in Electric Power Systems has intro to optimisation

• Bio-inspired Algorithms for the Design of Multiple Optimal Power System Stabilizers: SPPSO and BFA
• Tridib K. Das and Ganesh K. Venayagamoorthy
• 1-4244-0365-0/06/$20.00 (c) 2006 IEEE
• The Small Population based Particle Swarm Optimization (SPPSO) however is found to be superior to the Bacterial Foraging Algorithm (BFA) both in number of fitness evaluations, the convergence speed and damping performances.
• Boundary Conditions in Particle Swarm Optimization Revisited
• Shenheng Xu and Yahya Rahmat-Samii
• IEEE TRANSACTIONS ON ANTENNAS AND PROPAGATION, VOL. 55, NO. 3, March 2007
• It is up to the user to choose the most suitable boundary condition according to one’s a priori knowledge of the specific problem.
• Proceedings of the 39th Hawaii International Conference on System Sciences – 2006
• Comparison of Artificial Life Techniques for Market Simulation
• Feng Gao, Student Member, IEEE, G. Gutierrez-Alcaraz, Member, IEEE, and
• Gerald B. Sheble, Fellow, IEEE
• EP (Evolutionary Programming) and PS can be more appropriate than GA if solution space is well defined, for both of them utilize previous global information. Furthermore, PS balances local and global searching, displays more advantages. However more operations are needed.  On the other hand, if solution space is highly skewed and tortuous, the previous global information may be wrong and mislead the searching procedure in PS and EP. Thus, GA will outweigh EP and PS in the
• case.
• The gradient of PS contains more information compared with GA and EP. Individual particle has a memory of its own optimal value, k i Pbest . All particles share a common knowledge, i.e. k i Gbest , the optimal value until current generation. All of particles move within a solution space according to historical global & local best solutions.
• EP makes use of a Gaussian random perturbation term to update each generation. All of the candidates’ updating directions form an n-dimension random vector. EP does not apply local information; however each generation does share a common knowledge implicitly. The mutation factor phi-k is proportional to the ratio between the best profit and individual profits up to now. The bigger the ratio between the best profit and individual profits, i.e. individual profits is far from the best one, the greater is the change in X(sub_i)(super k+1) as compared to X(sub_i)(super_k) and vice versa.
• The “gradient” of GA employs neither global nor local historical information. Crossover and mutation operators bring in new sense of change in direction through the use of a random alteration of solution value. Therefore it is necessary to apply simulation to measure the expected “gradient” of GA.

Tuesday AM: more discussion work …

• 2006 IEEE Congress on Evolutionary Computation
• A Distributed Particle Swarm Optimization Algorithm for Swarm Robotic Applications
• James M. Hereford, Member, IEEE
• In summary, the advantages of the PSO over other algorithms are that (a) it is computationally simple and efficient; (b) each agent only needs to know its own local information and the global best to compute the new position, so there is a minimal amount of data transfer among the agents; and (c) the results from all agents in the population are not required to form the next generation, so a centralized processor is not required.
• A New Optimizer Using Particle Swarm Theory
• Russell Eberhart  James Kennedy
• Particle swarm optimization can be used to solve many of the same kinds of problems as genetic algorithms (GAS) [6]. This optimization technique does not scffer, however, from some of GA’s difficulties; interaction in the group enhances rather than detracts from progress toward the solution. Further, a particle swarm system has memory, which the genetic algorithm does not have. Change in genetic populations results in destruction of previous knowledge of the problem, except when elitism is employed, in which case usually one or a small number of individuals retain their iidentities.” In particle swarm optimization, individuals who fly past optima are tugged to return toward them; knowledge of good solutions is retained by all particles.
• (Millonas comment) First is the proximity principle: the population should be ablc to carry out simple space and time computations.  Second is the quality principle: the population should be able to respond to quality factors in the environment.  Third is the principle of diverse response: the population should not commit its activities along excessively narrow channels Fourth is the principle of stability: the popularion should not change its mode of behavior every time the environment changes. Fifth is the principle of adaptability. the population must be able to change behavior mode when it’s worth the computational price.  Note that principles four and five are the opposite sides of the same coin. 
• The particle swarm optimization concept and paradigm presented in this paper seem to adhere to all five principles. Basic to the paradigm are n-dimensional space calculations carried out over a series of time steps. The population is responding to the quality factors pbest and gbest/lbset The allocation of responses between pbest and gbest/lbest ensures a diversity of response. The population changes its state (mode of behavior) only when gbest/lbest changes, thus adhering to the principle of stability. The population is adaptive because it does change when gbest/lbest changes.
• The neural-net application described in Section 3, for instance, showed that the particle swarm optimizer could train NN weights as effectively as the usual error backpropagation method.  The particle swarm optimizer has also been used to train a neural network to classify the Fisher Iris Data Set [3].  Again, the optimizer trained the weights as effectively as the backpropagation method 
• The particle swarm optimizer was compared to a benchmark for genetic algorithms in Davis [2]: the extremely nonlinear Schaffer f6 function. This function is very difficult to optimize, as the highly discontinuous data surface features many local optima. The particle swarm paradigm found the global optimum each run, and appears to approximate the results reported for elementary genetic algorithms in Chapter 2 of [2] in terms of the number of evaluations required to reach certain performance levels [6].
• Conceptually, it seems to lie somewhere between genetic algorithms and evolutionary programming. It is highly dependent on stochastic processes, like evolutionary programming. The adjustment toward pbest and gbest by the particle swarm oplirnizer is conceptually similar to the crossover operation utilized by genetic algorithms. It uses the concept of fitness, as do all evolutionary computation paradigms.
• Unique to the concept of particle swarm optimization is flying potential solutions through hyperspace, accelerating toward “better” solutions. Other evolutionary computation schemes operate directly on potential solutions which are represented as locations in hypcrspace. Much of the success of particle swarms seems to lie in the agents’ tendency to hurtle past their target. Holland’s chapter on the “optimum allocation of trials” [5] reveals the delicate balance between conscrvativc testing of known regions versus risky exploration of the unknown. It appears that the current version of the paradigm allocates trials nearly optimally
• The stochastic factors allow thorough search of spaces between regions that have been found to be relatively good, and the momentum effect caused by modifying the extant velocities rather than replacing them results in overshooting, or exploration of unknown regions of the problem domain.
• [2] L. Davis, Ed., Handbook of Genetic Algorithms.  Van Nostrand Reinhold, New York, NY, 1991.
• [3] R. A. Fisher, “The use of multiple measurements in taxonomic problems.” Annals of Eugenics, 7: 179-188, 1936. 
• [5] J. H. Holland, Adaptation in Natural and Artificial Systems, MIT Press, Cambridge, MA., 1992.
• [6] J. Kennedy and R. Eberhart, Particle swarm optimization.” Proc. IEEE International Conf. on Neural Networks (Perth, Australia), IEEE Service Center, Piscataway, NJ, 1995 (in press).
• Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007)
• An Investigation of Grinding Process Optimization via Evolutionary Algorithms
• T.S. Lee1, T.O. Ting2 and Y.J. Lin3
• Similar to GA, a PSO consists of a population refining its knowledge of the given search space.
• Each particle keeps track of its coordinates in the search space, which are associated with the best solution it has achieved so far. This value is known as pbest.
• In this work, three prominent evolution algorithms namely GA, DE and PSO are investigated for the grinding process optimization with the objective of maximizing the Maximum Removal Rate, MRR subject to some operating constraints. The similar constraints handling are applied to all the algorithms. From the numerical results, PSO methodology is superior in comparison with other optimization algorithms such as DE (Differential Evolution) or GA.

Monday AM: reviewing collated material for input into discussion …

Currently going through collated papers to collect input into discussion:

• A Comparative Study on Particle Swarm Optimization for Optimal Steady-State Performance of Power Systems
• John G. Vlachogiannis and Kwang Y. Lee, Fellow, IEEE
• IEEE TRANSACTIONS ON POWER SYSTEMS, VOL. 21, NO. 4, NOVEMBER 2006
• In such complex problems, the conventional OPF techniques are susceptible to be trapped in local minima, and the solution obtained will not be the optimal one.

• A Comparison of Algorithms for the Optimization of Fermentation Processes
• 2006 IEEE Congress on Evolutionary Computation
• Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada, July 16-21, 2006
• Rui Mendes Isabel Rocha Eug´enio C. Ferreira Miguel Rocha
• When solving a real world problem, the main concern is to have a tool that may be applied to the problem with as few fine-tuning as possible. We are mainly interested in the results and not in a thorough study about the algorithms involved.We do not wish to go through the cumbersome task of testing the valuation of all the parameters of these algorithms until we found a setting that is perfect for the problem at hand.

Currently looking at A Distributed Particle Swarm Optimization Algorithm for Swarm Robotic Applications …

Fiday: thoughts on discussion …

Today started thinking more about what to put into the discusision:

1. PSO computationally efficent search method
2. topology affects performance considerably
3. knowledge of the optimisation problem is required ahead of setting the PSO parameters
1. could PSO be used to optimise the settings of a PSO algorithm … ?
4. can get confused if it has to deal with really tortuous search landscapes, or if there are lots of local minima.

Also started to work through a resource found yesterday (link) (look at the1.pdf in \My Documents\PhD\Reports\PSOReport):

• look at the summary for overview of results
• would be a good idea to look at the information in section 5 about the Ackley function, and how PSO deals with it, in comparison with point 4 above
• the PSO section itself looks useful