=Paper=
{{Paper
|id=Vol-1353/paper_02
|storemode=property
|title=The Hunch Factor: Exploration into Using Fuzzy Logic to Model Intuition in Particle Swarm Optimization
|pdfUrl=https://ceur-ws.org/Vol-1353/paper_02.pdf
|volume=Vol-1353
|dblpUrl=https://dblp.org/rec/conf/maics/Coffman-Wolph15
}}
==The Hunch Factor: Exploration into Using Fuzzy Logic to Model Intuition in Particle Swarm Optimization==
https://ceur-ws.org/Vol-1353/paper_02.pdf
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.