Particle Swarm Optimization (PSO) is a powerful biologybased optimization search strategy. This paper explores the addition of intuition into the PSO algorithm to improve the speed and number of iterations required to find solutions to the problem. This intuition will be modeled using a fuzzy variable called the Hunch Factor. It will act as memory for the system and influence the choices of the algorithm. Thus, allowing the algorithm to make more human-like decisions. This paper is an early exploration into the hunch factor via several experiments of the hunch factor with a simple optimization problem.
L. Zadeh introduced the concept of fuzzy logic as an
expansion of Boolean logic in his monumental paper entitled
“Fuzzy Sets”
Particle Swarm Optimization (PSO) is considered to be a highly successful and widely used problem-solving method and a subfield of swarm intelligence (Kennedy and Eberhart 2001). PSO is a biology-based optimization search strategy. It uses multiple independent particles to search the solution space of a given optimization problem. In PSO each individual particle stores the current candidate solution and refines the solution during the execution of the algorithm. PSO was based on the social behavior of animals and insects that regularly exist in groups.
Copyright held by the author.
The hunch factor supplies a human “hunch-like” element into the decision-making processes of the PSO algorithm. The hunch factor, represented by a membership function, is used to represent the innate ability of the system to derive guesses that influence the decisions made by the system. Additionally, the hunch acts as a fuzzy learning component for the algorithm since the hunch is continually altered during PSO execution. The hunch factor was first introduced in the author’s dissertation (Coffman-Wolph 2013).
Particle Definition # of particles # of iterations Init Particles Find Neighbors
Init Best
PSO
Velocity New Location
Fitness Update Neighbors
Update Best
Best Global Solution
The Particle Swarm Optimization (PSO) algorithm used in this paper is based on the original written by Kennedy and Eberhart (Kennedy and Eberhart 2001). The algorithm is a simple biology-inspired mathematical algorithm containing three main functions: fitness, velocity, and new location. Each of the three functions is processed on each particle individually until either the number of iterations is complete or a target value is reached. The fitness function determines how “good” the current candidate solution is, the velocity function determines the direction and speed the particle should head during the next iteration, and the new location function uses the velocity and previous location information to find the next candidate solution. Figure 1 provides the basic flowchart for the PSO algorithm.
Each particle has the following elements: • xi: A candidate solution • viold: Previous calculated velocity • pi: Particle’s best solution so far • Ni: List of neighbors • pn: Neighbor’s best solution, nεNi
The fitness equation is always problem dependent. However, it will always be a method for the evaluation of the candidate solution information. The number of variables in the equation(s) equals the size of the candidate solution vector. Any problem that can be formulated into an optimization problem can be used as a fitness function for the PSO.
The velocity function determines both the direction and speed the particle should move to form the next candidate solution. The velocity is calculated for each element of the candidate solution using the following formula:
vi = α * viold + φ1r()*(pi - xi) + φ2r()*(pn* - xi) where: • α = Inertia [0,1] • φ1 = Learning factor 1 • φ2 = Learning factor 2 • [φ1 + φ2 = 4] • r() = Random number function [0,1] • xi: Current position/candidate solution of particle i • viold: Previous calculated velocity • pi: Particle’s best solution so far • pn: Neighbor’s best solution, nεNi
The new location function updates the particle’s candidate solution. It uses the values calculated by the velocity function. The equation can be problem specific. The general equation for finding the new location for particle i is as follows:
xi = xi + vi where: • xi: Current position/candidate solution of particle i • vi: Calculated velocity
The nearest neighbors are calculated using the traditional distance equation. The neighbor list is part of the initial start up calculations. Additionally, the calculations are rerun and updated after an iteration of the algorithm (i.e., all the particles have been updated). The distance equation is as follows:
distance= xo-‐nx0 2+…+ (xn-‐nxn)2 where: • xi: Current position/candidate solution of particle i • nxi: Current position/candidate solution of neighbor particle ni
As stated earlier the hunch factor is represented by a membership function. It is used to represent the innate ability of the system to derive guesses that influence the decisions made by an algorithm. The hunch provides memory for the system and acts as a learning element. The hunch membership function is updated during runtime with information gained during the run of the algorithm. Specifically for the PSO, the hunch will be updated for every particle each iteration of the algorithm.
The hunch factor will be applied directly to the velocity function and, thus, influence the values of the next candidate solution. Basically, the hunch factor will be an additional factor to the direction and speed the particle will move in based on previous history of either the particle and/or all the particles (depending on the experiment set). 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.5 1
The hunch factor is stored as a fuzzy value and represented by a membership function. For simplicity, the hunch factor will be represented by a triangle membership function for these experiments. It is a fuzzy value and will be treated as such (i.e., storage and manipulation) during the execution of the algorithm. The hunch factor will be defuzzified and applied to the non-fuzzy velocity function calculation. (Defuzzification, in this case, will be based on the center of mass for the membership function).
To illustrate this concept, we can compare this to the childhood game of hot and cold. A group of players are attempting to find an object within a given room based on a leader calling out hot and cold to various players as they move around the room. The players begin by wanding around the room at random. As a player get positive reinforcement (i.e., warmer) they move in that postive direction until they get negative reinforcement (i.e., colder) and they change their path. The hunch factor is the accumulation of the warmer and colder clues received throughout the game and, thus, use the entire history instead of just the previous limited information. The hunch factor assists in speeding up the processes to finding the correct solution.
After each iteration of the PSO algorithm and for each particle, the difference between the old fitness value and the new fitness value is used to alter the hunch accordingly. If the new fitness value is greater than the old fitness value, then the hunch is altered in a positive manner - the width of the membership function is decreased and the height increased. If the new fitness value is less than the old value, then the opposite changes are made to the hunch. The magnitude of the difference between the values is also taken into consideration.
As stated, the hunch factor is applied to the velocity function. This allows the hunch factor to alter the speed and direction of the particle. The velocity function is, therefore, altered slightly from the original provided in the PSO algorithm. The following shows the altered velocity formula: vi = h * α * viold + (φ1r()*(pi - xi) + φ2r()*(pn* - xi)) where: • h = hunch factor value • α = Inertia [0,1] • φ1 = Learning factor 1 • φ2 = Learning factor 2 • [φ1 + φ2 = 4] • r() = Random number function [0,1] • xi: Current position/candidate solution of particle i • viold: Previous calculated velocity • pi: Particle’s best solution so far • pn: Neighbor’s best solution, nεNi
In this paper, several hunch factor experiments will be carried out. One set of experiments will be focused on the number of hunch factors considered: one global hunch factor vs. a hunch factor specific to an individual particle. Another set of experiments will focus on the level of influence the hunch factor has on the velocity function. The final set of experiments will focus on the manipulation of the hunch factor during the runtime of the function.
As mentioned in an earlier section, the preliminary hunch research began in the author’s dissertation (CoffmanWolph 2013). In this work, a single global hunch factor was maintained for the system. This simple hunch factor showed some promise in positively influencing the system. This first experiment directly expands on the original experiment. Thus, experiment #1 will compare the results of having a global hunch factor for the system with individual hunch factors associated with specific particles. The membership functions will be constant and the update methods will be exactly the same, just the number of hunch factors will be different.
The hunch factor is applied directly to the velocity equation calculation. Initially, the hunch factor is simply applied to the velocity as an additional factor. In this experiment the hunch factor will be applied at various partial levels and compared directly to the unaltered full hunch application. Additionally, the hunch factor will be moved from the first term of the velocity equation (i.e., the old velocity or the old information) to the second and third terms of the velocity equation (i.e., the best solutions seen by the particle and neighboring particles or the new information) to observe the effects.
The final set of experiments will focus on the manipulation of the hunch factor. In the first two experiments, the hunch factor will be manipulated in a very simple manner. If the fitness value improves, the hunch factor height will be increased by 25 percent and width be decreased by 10 percent. If the fitness value does not improve, the hunch factor height will be decreased by 25 percent and width increased by 10 percent.
In experiment #3 the hunch factor height and width will be increased/decreased using various percentages. Also, the positive and negative influences will not remain consistent (i.e., more “punishment” for wrong, less “reward” for correct). The combinations that will be tried are as follows: • Height and width 10% increase/decrease • Height 10% increase when correct, 20% decrease when incorrect, width 10% increase/decrease • Height and width 10% increase when correct, 20% decrease when incorrect • Height 20% increase when correct, 10% decrease when incorrect, width 10% increase/decrease • Height and width 20% increase when correct, 10% decrease when incorrect
For demonstration purposes in this paper, a simple optimization problem is used. This problem is defined as follows (Hillier and Lieberman 1990):
Maximize Z = 2x0 * x1 + 2x1 – x02 – 2x12 where x0 and x1 ≥ 0
The programming code for the PSO was written in Java. The testing environment is as follows: Eclipse SDK 4.2.1 using Java version 1.6 on a MacBook Pro running OS X version 10.8.2 with 3 GHz Intel Core i7.
The following sections cover the results of the three experiments outlined in detail earlier in this paper. Experiment #1 dealt with the difference between having a single global hunch factor versus a hunch factor tailored to each particle. Experiment #2 dealt with how the hunch factor was applied to the velocity equation. Experiment #3 explored various manipulations of the hunch factor during runtime.
The following data was collected during various runs for all three experiments with the simple optimization problem provided earlier.
100 particles, 1000 iterations PSO
Time
Fitness 1124 1162 1140 0.8542 0.8669 0.9777 PSO, Multi Hunch 1060 0.8778 Figure 3: Data for 100 particles, 1000 iterations 100 particles, 2000 iterations
Fitness 21070 20780 21060
As stated earlier, experiment #1’s focus was to compare the effects of having one global hunch factor for the PSO verses having a hunch factor for each particle. The following diagrams demonstrate the various results found for each test problem and various test cases (i.e., various particle and iteration sizes).
The analysis of the results begins by focusing on increasing the number of iterations. Figure 12 shows that there was negligible difference in execution time for just the PSO, the PSO with one hunch factor, and the PSO with a separate hunch factors for each particle. Figure 13 shows the average fitness values found for the PSO, the PSO with 1 hunch factor, and the PSO with a separate hunch factor for each particle.
As can be observed in Figure 12, when dealing with the standard PSO, as the number of iterations increases, the fitness value improves. However, when the global hunch factor is added to the PSO system, the hunch performs extremely well at lower iterations and becomes un-effective as the number of iterations increases. The system with individual hunch factors for each particle follows a pattern similar to the standard PSO system, but also demonstrates a performance issue with high iterations similar to the global hunch PSO system. However, it should be observed that both systems with the hunch outperformed the standard PSO in terms of fitness at low iteration values.
Figure 14 and Figure 15 demonstrate the effects of the number of hunch factors as the number of particles increases (while the number of iterations is held constant). Figure 14 (as with Figure 6) shows that the execution time is negligibly affected by the addition of the hunch into the system. Figure 15 illustrates the changes in the fitness value with the addition of the hunch. It can be observed, that overall the hunch (single global or multiple) is less effective as the number of particles increases. However, at low number of iterations, either system with the hunch out performs the standard PSO.
0" 1" 2" 3" 4" 5"
Experiment #2 consists of two experiments. The first experiment is the level (i.e., percentage) of effect the hunch has on the velocity function. Figures 16 and 17 illustrate the results of these different levels. The second experiment 5000" 4500" 4000" 3500" 3000" 2500" 2000" 1500" 1000" 500" 0" PSO"Time"" PSO"1"Hunch" PSO"Mul6"Hunch" PSO%Fitness% PSO%1%Hunch% PSO%Mul;%Hunch% 100"p,"1000"it" 200"p,"1000"it" 300"p,"1000"it" 100%p,%1000%it% 200%p,%1000%it% 300%p,%1000%it%
1% focuses on the difference between applying the hunch to the “old information” vs. the “new information” and can be observed in Figures 18 and 19. ranges of the hunch were overall not successful. However, high percentages of the hunch were successful in both 1000 and 4000 iterations. Applying only a percentage of the hunch into the velocity calculation had interesting results as seen in Figures 16 and 17. The “normal” mode was 100% (i.e., the point on the far right). Applying only a portion of the hunch was successful in the runs of 1000 and 4000 iterations. Middle
From Figures 18 and 19, it can be observed that the application of the hunch to either the old information or new information has very little effect on the fitness values found as the iteration size increased. However, as Figure 1" 2" 3" 4" 0% 20% 40% 60% 80% 100% 120% 19 illustrates, the term of the velocity equation where the hunch was applied affects the results as the number of particles increases. The hunch on the new information matches the pattern for the PSO without the hunch. Overall the hunch being applied to the old information produces better fitness values. Experiment #3 consisted of 5 test cases of various manipulations of the hunch factor. The test cases are as follows: • Case #1: Height and width 10% increase/decrease • Case #2: Height 10% increase when correct, 20% decrease when incorrect, width 10% increase/decrease • Case #3: Height and width 10% increase when correct, 20% decrease when incorrect • Case #4: Height 20% increase when correct, 10% decrease when incorrect, width 10% increase/decrease • Case #5: Height and width 20% increase when correct, 10% decrease when incorrect Test case #4: Height 20% increase when correct, 10% decrease when incorrect, width 10% increase/decrease. This test case used positive reinforcement. When the particle was moving in the correct direction, the hunch was increased more. However, if it was moving in an incorrect direction, less hunch manipulation occurred (i.e., less punishment).
The hunch factor has been shown in the experiment results of the previous section to have promise. These are simply the preliminary and exploratory results using a very simple optimization problem. The hunch factor works extremely well with smaller number of particles and fewer iterations. The hunch factor, is thus, best suited for assisting particles in finding the general area within the search space. (The hunch factor has either no effect or slight negative effect when honing in on a solution). Thus, the hunch could possibly make an excellent addition to an algorithm designed to find “good” starting points for other optimization algorithms that require such starting points.
Additionally, it can be observed that the hunch factor should be applied to the portion of the velocity function that contains the previous information. It would be helpful to use either the full hunch factor or a fraction of the hunch factor when determining the velocity and, thus, the next possible solution. The single global hunch should be manipulated using positive reinforcement.
The work done in this paper focuses on a specific optimization problem and provides only the beginning of exploration into the use of the hunch. Given these preliminary results, the next step would be to expand to other problem sets – with larger and more varied problems. Although the extra computation for the hunch factor is small and should not cause a hindrance when expanding to larger problems, more experimentation is needed to verify that conclusion. Additionally, it would be interesting to experiment further with various membership functions and not just a simple triangle membership function for the hunch factor representation. Another step would be to move to a completely fuzzy algorithm version of the PSO (Coffman-Wolph 2013a and Coffman-Wolph 2013b) and run these same experiments with the hunch factor. The hunch factor showed great promise when using a small numbers of particles and less iterations – something that could be further explored. In particular the application of using the hunch factor when trying to find starting points for other optimization algorithms.
The author would like to thank the reviews for their helpful suggestions. Coffman-Wolph, S. 2013. Fuzzy Search Strategy Generation for Adversarial Systems using Fuzzy Process Particle Swarm Optimization, Fuzzy Patterns, and a Hunch Factor. Ph.D. diss., Department of Computer Science, Western Michigan University, Kalamazoo, MI.
Coffman-Wolph, S. and Kountanis, D. 2013a. Fuzzy Process Particle Swarm Optimization. In the Proceedings of the 43rd Southeastern Conference on Combinatorics, Graph Theory, & Computing. Winnipeg: Utilitas Mathematica Pub. Inc. Coffman-Wolph, S. and Kountanis, D. 2013b. A general framework for the fuzzification of algorithms. In the Proceedings of the 4th biennial Michigan Celebration of Women in Computing (MICWIC 2013).
Hillier, F. S., and Lieberman, G. J. 1990. Introduction to Operations Research. McGraw-Hill.
Kennedy, J., and Eberhart, R. C. 2001. Swarm Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, Inc