The Hunch Factor: Exploration into Using Fuzzy Logic to Model Intuition in Particle Swarm Optimization Stephany Coffman-Wolph West Virginia University Institute of Technology 405 Fayette Pike, Montgomery, West Virginia 25136 sscoffmanwolph@mail.wvu.edu Abstract The hunch factor supplies a human “hunch-like” ele- Particle Swarm Optimization (PSO) is a powerful biology- ment into the decision-making processes of the PSO algo- based optimization search strategy. This paper explores the rithm. The hunch factor, represented by a membership addition of intuition into the PSO algorithm to improve the function, is used to represent the innate ability of the sys- speed and number of iterations required to find solutions to tem to derive guesses that influence the decisions made by the problem. This intuition will be modeled using a fuzzy variable called the Hunch Factor. It will act as memory for the system. Additionally, the hunch acts as a fuzzy learning the system and influence the choices of the algorithm. Thus, component for the algorithm since the hunch is continually allowing the algorithm to make more human-like decisions. altered during PSO execution. The hunch factor was first This paper is an early exploration into the hunch factor via introduced in the author’s dissertation (Coffman-Wolph several experiments of the hunch factor with a simple opti- 2013). mization problem. PSO Particle Definition Background # of particles # of iterations Velocity L. Zadeh introduced the concept of fuzzy logic as an ex- Best pansion of Boolean logic in his monumental paper entitled New Location Global Init Particles “Fuzzy Sets” (Zadeh 1965). Fuzzy logic is a set of rules Solution and techniques for dealing with logic beyond a two-value Fitness (yes/no, on/off, true/false) system. Therefore, fuzzy logic, Find Neighbors on a basic level, is an abstraction of traditional, two-value Update Neighbors logic. Thus, fuzzy logic mimics a more human like ap- proach to decision making. Fuzzy logic differs from tradi- Init Best Update Best tional mathematical sets because it allows for an overlap of values between fuzzy sets. Figure 1: PSO Flowchart Particle Swarm Optimization (PSO) is considered to be a highly successful and widely used problem-solving method The PSO Algorithm and a subfield of swarm intelligence (Kennedy and Eber- The Particle Swarm Optimization (PSO) algorithm used in hart 2001). PSO is a biology-based optimization search this paper is based on the original written by Kennedy and strategy. It uses multiple independent particles to search Eberhart (Kennedy and Eberhart 2001). The algorithm is a the solution space of a given optimization problem. In PSO simple biology-inspired mathematical algorithm containing each individual particle stores the current candidate solu- three main functions: fitness, velocity, and new location. tion and refines the solution during the execution of the al- Each of the three functions is processed on each particle gorithm. PSO was based on the social behavior of animals individually until either the number of iterations is com- and insects that regularly exist in groups. plete or a target value is reached. The fitness function de- termines how “good” the current candidate solution is, the Copyright held by the author. 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 Nearest Neighbors Calculation information to find the next candidate solution. Figure 1 The nearest neighbors are calculated using the traditional provides the basic flowchart for the PSO algorithm. distance equation. The neighbor list is part of the initial start up calculations. Additionally, the calculations are re- Particles run and updated after an iteration of the algorithm (i.e., all Each particle has the following elements: the particles have been updated). The distance equation is • xi: A candidate solution as follows: • viold: Previous calculated velocity distance=   xo -­‐nx0 2 +…+  (xn -­‐nxn )2   • pi: Particle’s best solution so far where: • xi: Current position/candidate solution of particle i • Ni: List of neighbors • nxi: Current position/candidate solution of neighbor par- • pn: Neighbor’s best solution, nεNi ticle ni Fitness Function The fitness equation is always problem dependent. Howev- The Hunch Factor er, it will always be a method for the evaluation of the can- As stated earlier the hunch factor is represented by a mem- didate solution information. The number of variables in the bership function. It is used to represent the innate ability of equation(s) equals the size of the candidate solution vector. the system to derive guesses that influence the decisions Any problem that can be formulated into an optimization made by an algorithm. The hunch provides memory for the problem can be used as a fitness function for the PSO. system and acts as a learning element. The hunch member- ship function is updated during runtime with information Velocity Function gained during the run of the algorithm. Specifically for the The velocity function determines both the direction and PSO, the hunch will be updated for every particle each it- speed the particle should move to form the next candidate eration of the algorithm. solution. The velocity is calculated for each element of the The hunch factor will be applied directly to the velocity candidate solution using the following formula: function and, thus, influence the values of the next candi- vi = α * viold + φ1r()*(pi - xi) + φ2r()*(pn* - xi) date solution. Basically, the hunch factor will be an addi- where: tional factor to the direction and speed the particle will • α = Inertia [0,1] move in based on previous history of either the particle • φ1 = Learning factor 1 and/or all the particles (depending on the experiment set). • φ2 = Learning factor 2 • [φ1 + φ2 = 4] 0.6   • r() = Random number function [0,1] 0.5   • xi: Current position/candidate solution of particle i 0.4   • viold: Previous calculated velocity 0.3   • pi: Particle’s best solution so far 0.2   • pn: Neighbor’s best solution, nεNi 0.1   New Location Function 0   The new location function updates the particle’s candidate 0   0.5   1   solution. It uses the values calculated by the velocity func- tion. The equation can be problem specific. The general Figure 2: Initial Hunch Factor equation for finding the new location for particle i is as fol- lows: Hunch Factor Representation xi = xi + vi where: The hunch factor is stored as a fuzzy value and represented • xi: Current position/candidate solution of particle i by a membership function. For simplicity, the hunch fac- • vi: Calculated velocity tor will be represented by a triangle membership function for these experiments. It is a fuzzy value and will be treat- ed as such (i.e., storage and manipulation) during the exe- cution of the algorithm. The hunch factor will be defuzzi- fied and applied to the non-fuzzy velocity function calcula- tion. (Defuzzification, in this case, will be based on the Experiments center of mass for the membership function). To illustrate this concept, we can compare this to the In this paper, several hunch factor experiments will be car- childhood game of hot and cold. A group of players are at- ried out. One set of experiments will be focused on the tempting to find an object within a given room based on a number of hunch factors considered: one global hunch fac- leader calling out hot and cold to various players as they tor vs. a hunch factor specific to an individual particle. move around the room. The players begin by wanding Another set of experiments will focus on the level of influ- around the room at random. As a player get positive ence the hunch factor has on the velocity function. The fi- reinforcement (i.e., warmer) they move in that postive nal set of experiments will focus on the manipulation of the direction until they get negative reinforcement (i.e., colder) hunch factor during the runtime of the function. and they change their path. The hunch factor is the accumulation of the warmer and colder clues received Experiment #1: Number of Hunch Factors throughout the game and, thus, use the entire history As mentioned in an earlier section, the preliminary hunch instead of just the previous limited information. The hunch research began in the author’s dissertation (Coffman- factor assists in speeding up the processes to finding the Wolph 2013). In this work, a single global hunch factor correct solution. 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 ex- Hunch Factor Manipulation periment. Thus, experiment #1 will compare the results of After each iteration of the PSO algorithm and for each par- having a global hunch factor for the system with individual ticle, the difference between the old fitness value and the hunch factors associated with specific particles. The new fitness value is used to alter the hunch accordingly. If membership functions will be constant and the update the new fitness value is greater than the old fitness value, methods will be exactly the same, just the number of hunch then the hunch is altered in a positive manner - the width of factors will be different. the membership function is decreased and the height in- creased. If the new fitness value is less than the old value, Experiment #2: Hunch Factor and Velocity then the opposite changes are made to the hunch. The The hunch factor is applied directly to the velocity equa- magnitude of the difference between the values is also tak- tion calculation. Initially, the hunch factor is simply ap- en into consideration. plied to the velocity as an additional factor. In this exper- iment the hunch factor will be applied at various partial levels and compared directly to the unaltered full hunch The Velocity Function with Hunch Factor application. Additionally, the hunch factor will be moved As stated, the hunch factor is applied to the velocity func- from the first term of the velocity equation (i.e., the old ve- tion. This allows the hunch factor to alter the speed and di- locity or the old information) to the second and third terms rection of the particle. The velocity function is, therefore, of the velocity equation (i.e., the best solutions seen by the altered slightly from the original provided in the PSO algo- particle and neighboring particles or the new information) rithm. The following shows the altered velocity formula: to observe the effects. vi = h * α * viold + (φ1r()*(pi - xi) + φ2r()*(pn* - xi)) where: Experiment #3: Hunch Factor Manipulation • h = hunch factor value The final set of experiments will focus on the manipulation • α = Inertia [0,1] of the hunch factor. In the first two experiments, the hunch • φ1 = Learning factor 1 factor will be manipulated in a very simple manner. If the • φ2 = Learning factor 2 fitness value improves, the hunch factor height will be in- creased by 25 percent and width be decreased by 10 per- • [φ1 + φ2 = 4] cent. If the fitness value does not improve, the hunch fac- • r() = Random number function [0,1] tor height will be decreased by 25 percent and width in- • xi: Current position/candidate solution of particle i creased by 10 percent. • viold: Previous calculated velocity In experiment #3 the hunch factor height and width will • pi: Particle’s best solution so far be increased/decreased using various percentages. Also, • pn: Neighbor’s best solution, nεNi the positive and negative influences will not remain con- sistent (i.e., more “punishment” for wrong, less “reward” for correct). The combinations that will be tried are as fol- lows: • Height and width 10% increase/decrease 100 particles, 2000 iterations • Height 10% increase when correct, 20% decrease when Time Fitness incorrect, width 10% increase/decrease • Height and width 10% increase when correct, 20% de- PSO 2233 0.8576 crease when incorrect PSO, Hunch New 2381 0.8850 • Height 20% increase when correct, 10% decrease when PSO, Hunch Old 2246 0.9806 incorrect, width 10% increase/decrease • Height and width 20% increase when correct, 10% de- PSO, Multi Hunch 2209 0.9199 crease when incorrect Figure 4: Data for 100 particles, 2000 iterations 100 particles, 3000 iterations Testing Problem Time Fitness For demonstration purposes in this paper, a simple optimi- PSO 3328 0.9690 zation problem is used. This problem is defined as follows (Hillier and Lieberman 1990): PSO, Hunch New 3362 0.7806 Maximize Z = 2x0 * x1 + 2x1 – x02 – 2x12 PSO, Hunch Old 3350 0.9636 where x0 and x1 ≥ 0 PSO, Multi Hunch 3225 0.9309 Figure 5: Data for 100 particles, 3000 iterations Testing Environment 100 particles, 4000 iterations The programming code for the PSO was written in Java. The testing environment is as follows: Eclipse SDK 4.2.1 Time Fitness using Java version 1.6 on a MacBook Pro running OS X PSO 4507 0.9629 version 10.8.2 with 3 GHz Intel Core i7. PSO, Hunch New 4642 0.9392 PSO, Hunch Old 4659 0.9513 Results PSO, Multi Hunch 4222 0.9140 The following sections cover the results of the three exper- Figure 5: Data for 100 particles, 4000 iterations iments outlined in detail earlier in this paper. Experiment #1 dealt with the difference between having a single global 200 particles, 1000 iterations hunch factor versus a hunch factor tailored to each particle. Time Fitness Experiment #2 dealt with how the hunch factor was ap- PSO 6639 0.9236 plied to the velocity equation. Experiment #3 explored var- ious manipulations of the hunch factor during runtime. PSO, Hunch New 6794 0.9376 PSO, Hunch Old 6748 0.9203 Data Collected PSO, Multi Hunch 6369 0.9012 The following data was collected during various runs for Figure 6: Data for 200 particles, 1000 iterations all three experiments with the simple optimization problem provided earlier. 300 particles, 1000 iterations Time Fitness 100 particles, 1000 iterations PSO 21070 0.9274 Time Fitness PSO 1124 0.8542 PSO, Hunch New 20780 0.9706 PSO, Hunch New 1162 0.8669 PSO, Hunch Old 21060 0.9600 PSO, Hunch Old 1140 0.9777 PSO, Multi Hunch 20154 0.9480 Figure 7: Data for 300 particles, 1000 iterations PSO, Multi Hunch 1060 0.8778 Figure 3: Data for 100 particles, 1000 iterations 100, 1000 100, 4000 The analysis of the results begins by focusing on in- creasing the number of iterations. Figure 12 shows that Percentage (%) Fitness Fitness there was negligible difference in execution time for just 10 0.9837 0.958 the PSO, the PSO with one hunch factor, and the PSO with 20 0.8941 0.9697 a separate hunch factors for each particle. Figure 13 shows the average fitness values found for the PSO, the PSO with 30 0.9641 0.9259 1 hunch factor, and the PSO with a separate hunch factor 40 0.9870 0.9300 for each particle. 50 0.9152 0.9855 As can be observed in Figure 12, when dealing with the 60 0.9223 0.8685 standard PSO, as the number of iterations increases, the fitness value improves. However, when the global hunch 70 0.8756 0.9399 factor is added to the PSO system, the hunch performs ex- 80 0.9535 0.9560 tremely well at lower iterations and becomes un-effective 90 0.9541 0.9390 as the number of iterations increases. The system with in- dividual hunch factors for each particle follows a pattern 100 0.9777 0.9513 similar to the standard PSO system, but also demonstrates Figure 8: Data for Hunch % Applied a performance issue with high iterations similar to the global hunch PSO system. However, it should be observed PSO that both systems with the hunch outperformed the stand- PSO Fit- PSO Hunch ard PSO in terms of fitness at low iteration values. Set Up ness Hunch Old New Figure 14 and Figure 15 demonstrate the effects of the 100 p, 1000 it 0.8542 0.9777 0.8669 number of hunch factors as the number of particles in- 100 p, 2000 it 0.8576 0.9806 0.8850 creases (while the number of iterations is held constant). 100 p, 3000 it 0.9690 0.9636 0.7806 Figure 14 (as with Figure 6) shows that the execution time is negligibly affected by the addition of the hunch into the 100 p, 4000 it 0.9629 0.9513 0.9392 system. Figure 15 illustrates the changes in the fitness val- Figure 9: Data for Hunch Placement ue with the addition of the hunch. It can be observed, that overall the hunch (single global or multiple) is less effec- PSO tive as the number of particles increases. However, at low PSO Fit- PSO Hunch number of iterations, either system with the hunch out per- Set Up ness Hunch Old New forms the standard PSO. 100 p, 1000 it 0.8542 0.9777 0.8669 200 p, 1000 it 0.9236 0.9203 0.9376 5000" 300 p, 1000 it 0.9274 0.9600 0.9706 4500" Figure 10: Data for Hunch Placement 4000" 3500" Itera- Nor- Case Case Case Case Case 3000" PSO"Time"" tions mal #1 #2 #3 #4 #5 2500" PSO"1"Hunch" 2000" 1000 0.9777 0.9210 0.9282 0.9401 0.9659 0.9919 PSO"Mul6"Hunch" 1500" 2000 0.9806 0.9797 0.9683 0.7785 0.9871 0.9492 1000" 500" 3000 0.9636 0.9817 0.9535 0.9362 0.9684 0.9455 0" 4000 0.9513 0.9786 0.9759 0.9314 0.9856 0.9456 0" 1" 2" 3" 4" 5" Figure 11: Data for Hunch Test Cases Figure 12: Comparison of Execution Time (Time in Experiment #1 Results: Number of Hunch Factors Milliseconds vs. Iterations in 1000s) As stated earlier, experiment #1’s focus was to compare Experiment #2 Results: Hunch Factor and Veloci- the effects of having one global hunch factor for the PSO ty verses having a hunch factor for each particle. The follow- ing diagrams demonstrate the various results found for Experiment #2 consists of two experiments. The first ex- each test problem and various test cases (i.e., various parti- periment is the level (i.e., percentage) of effect the hunch cle and iteration sizes). has on the velocity function. Figures 16 and 17 illustrate the results of these different levels. The second experiment focuses on the difference between applying the hunch to ranges of the hunch were overall not successful. However, the “old information” vs. the “new information” and can be high percentages of the hunch were successful in both observed in Figures 18 and 19. 1000 and 4000 iterations. 1% 1% 0.98% 0.98% 0.96% 0.96% 0.94% PSO%Fitness% 0.94% 0.92% PSO%1%Hunch% 0.9% 0.92% PSO%Mul;%Hunch% 0.88% 0.9% 0.86% 0.88% 0.84% 0% 1% 2% 3% 4% 5% 0.86% 0% 20% 40% 60% 80% 100% 120% Figure 13: Comparison of Fitness Values (Fitness Value vs. Iterations in 1000s) Figure 16: Hunch Percentage Applied - 100 parti- cles, 1000 iterations (Fitness Value vs. Hunch Per- centage) 25000" 20000" 1% 0.98% 15000" 100"p,"1000"it" 0.96% 200"p,"1000"it" 0.94% 10000" 300"p,"1000"it" 0.92% 5000" 0.9% 0.88% 0" 0.86% 0" 1" 2" 3" 4" 0% 20% 40% 60% 80% 100% 120% Figure 14: Comparison of Execution Time (Time in Figure 17: Hunch Percentage Applied - 100 parti- Milliseconds vs. Particles in 100s) cles, 4000 iterations (Fitness Value vs. Hunch Per- centage) 1% 0.98% 0.96% 0.94% 100%p,%1000%it% 0.92% 200%p,%1000%it% 0.9% 300%p,%1000%it% 0.88% 0.86% 0.84% 0% 1% 2% 3% 4% Figure 15: Comparison of Fitness Values (Fitness Figure 18: Hunch Applied Old Information (Fitness Value vs. Particles in 100s) Value vs. Iterations in 1000s) Applying only a percentage of the hunch into the velocity From Figures 18 and 19, it can be observed that the ap- calculation had interesting results as seen in Figures 16 and plication of the hunch to either the old information or new 17. The “normal” mode was 100% (i.e., the point on the information has very little effect on the fitness values far right). Applying only a portion of the hunch was suc- found as the iteration size increased. However, as Figure cessful in the runs of 1000 and 4000 iterations. Middle 19 illustrates, the term of the velocity equation where the can be observed in Figure 21, of the 5 test cases, one test hunch was applied affects the results as the number of par- case stood out: #4. ticles increases. The hunch on the new information match- es the pattern for the PSO without the hunch. Overall the hunch being applied to the old information produces better fitness values. Figure 21: Hunch Test Case #4 (Fitness Value vs. It- erations) Test case #4: Height 20% increase when correct, 10% de- Figure 19: Hunch Applied New Information (Fitness crease when incorrect, width 10% increase/decrease. This Value vs. Particles in 100s) test case used positive reinforcement. When the particle was moving in the correct direction, the hunch was in- Experiment #3 Results: Hunch Factor Manipula- creased more. However, if it was moving in an incorrect tion direction, less hunch manipulation occurred (i.e., less pun- Experiment #3 consisted of 5 test cases of various manipu- ishment). lations of the hunch factor. The test cases are as follows: • Case #1: Height and width 10% increase/decrease Discussion and Concluding Remarks • Case #2: Height 10% increase when correct, 20% de- crease when incorrect, width 10% increase/decrease The hunch factor has been shown in the experiment results • Case #3: Height and width 10% increase when correct, of the previous section to have promise. These are simply 20% decrease when incorrect the preliminary and exploratory results using a very simple • Case #4: Height 20% increase when correct, 10% de- optimization problem. The hunch factor works extremely crease when incorrect, width 10% increase/decrease well with smaller number of particles and fewer iterations. • Case #5: Height and width 20% increase when correct, The hunch factor, is thus, best suited for assisting particles 10% decrease when incorrect 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 pos- 1$ sibly make an excellent addition to an algorithm designed 0.95$ to find “good” starting points for other optimization algo- Normal$ rithms that require such starting points. 0.9$ Additionally, it can be observed that the hunch factor Case$#1$ Case$#2$ should be applied to the portion of the velocity function 0.85$ Case$#3$ that contains the previous information. It would be helpful 0.8$ to use either the full hunch factor or a fraction of the hunch Case$#4$ factor when determining the velocity and, thus, the next 0.75$ Case$#5$ possible solution. The single global hunch should be ma- 0.7$ nipulated using positive reinforcement. 0$ 1000$ 2000$ 3000$ 4000$ 5000$ Figure 20: Hunch Test Cases (Fitness Value vs. It- Future Work erations) The work done in this paper focuses on a specific optimi- zation problem and provides only the beginning of explora- Figure 20 illustrates (using the data from Figure 11) the tion into the use of the hunch. Given these preliminary re- fitness value that resulted from the various test cases. As sults, 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 repre- sentation. 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 ex- periments 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 algo- rithms. Acknowledgments The author would like to thank the reviews for their helpful suggestions. References Coffman-Wolph, S. 2013. Fuzzy Search Strategy Generation for Adversarial Systems using Fuzzy Process Particle Swarm Opti- mization, Fuzzy Patterns, and a Hunch Factor. Ph.D. diss., De- partment 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 frame- work 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 Opera- tions Research. McGraw-Hill. Kennedy, J., and Eberhart, R. C. 2001. Swarm Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, Inc Zadeh, L.A. 1965. Fuzzy Sets. Information and Control 8: 338- 353.