# Construction Example for Algebra System Using  Harmony Search Algorithm

Authors: FangAn Deng; Shouheng Tuo; Longquan Yong; Tao Zhou
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The construction example of algebra system is to verify the existence of a complex algebra system, and it is a NP-hard problem. In this paper, to solve this kind of problems, firstly, a mathematical optimization model for construction example of algebra system is established. Secondly, an improved harmony search algorithm based on NGHS algorithm (INGHS) is proposed to find as more solutions as possible for the optimization model; in the proposed INGHS algorithm, to achieve the balance between exploration power and exploitation power in the search process, a global best strategy and parameters dynamic adjustment method are present. Finally, nine construction examples of algebra system are used to evaluate the optimization model and performance of INGHS. The experimental results show that the proposed algorithm has strong performance for solving complex construction example problems of algebra system.


---

## Body

## 1. Introduction

Algebra system is one of the broad parts of mathematics, together with number theory, geometry, and analysis. It has wide applications in astronomy, biology, construction, computer science, and so on. Many scientific researchers focus on its studies. However, with the rapid development of science and technology, more and more complex algebra systems emerge in large numbers, so the algebra system researchers meet a lot of difficult problems. One of them is to construct appropriate examples for the algebra system so as to prove the existence of the algebra system. This is because there is the tremendous computing workload to construct appropriate examples that are satisfied with the operations of the algebra system. In the current study of algebra system, the construction examples of algebra system are often manually achieved. However, for a multielement complex algebra system, the construction examples are very difficult. In order to understand the construction example of algebra system better, we introduce its construction by an example ofN(2,2,0) algebra system.Above all, we begin this section by introducing a simplified definition ofN(2,2,0) algebra system [1, 2].Definition 1.
AnN(2,2,0) algebra is a system (S,*,Δ,0) where S is nonempty set, 0 is a constant element of S, and * and Δ are two binary operations on S, obeying the following axioms. For all x,y,z∈S,(F1)
x*(yΔz)=z*(x*y),(F2)
(xΔy)*z=y*(x*z),(F3)
0*x=x.
For Definition1, there are two works for researchers to do.(1)
Give some examples to prove the existence of this algebra.(2)
How many solutions are satisfying the three conditions (F1), (F2), and (F3) simultaneously?Example 2.
LetS={a1,a2,…,an} be a finite set of distinct elements. We define operations * and Δ by the following equations, respectively:(1)*a1a2⋯ana1x11x12⋯x1na2x21x22⋯x2n⋯anxn1xn2⋯xnn(2)Δa1a2⋯ana1y11y12⋯y1na2y21y22⋯y2n⋯anyn1yn2⋯ynn
In (1) and (2), ai*aj=xij∈S, aiΔaj=yij∈S(i=1,2,…,n;j=1,2,…,n).
Next we consider(F1)
ai*(ajΔak)=ak*(ai*aj)⇔ai*(yjk)=ak*(xik),(F2)
(aiΔaj)*ak=aj*(ai*ak)⇔(yij)*ak=aj*(xik)⇔ai*(yjk)=ak*(xik),(F3)
a1*ai=ai⇔x1i=ai,where i=1,2,…,n; j=1,2,…,n; k=1,2,…,n.For this algebra system, researchers hope to construct some examples that satisfy the conditions (F1), (F2), and (F3) and to prove the existence of the algebra. However, the calculated amount of this work is so large that computing cost is typically high. Like Example 2, each variable xij or yij  (i=1,2,…,n;j=1,2,…,n) can take n different values (a1,a2,…,an); the combinatorial number with the repetition for all xij and yij is n2n2. Obviously it is a NP-hard problem. It will result in the combination blast when the dimension increases. So the enumeration method can hardly be used to construct an example for the algebra system (S,*,Δ,0).Therefore, for this kind of NP-hard problem, this paper proposes an intelligent metaheuristic algorithm to get a set of(x11,x12,…,x1n;…;xn1,xn2,…,xnn) and (y11,y12,…,y1n;…;yn1,yn2,…,ynn) quickly that satisfy conditions (F1), (F2), and (F3).


## 2. The Optimization Model ofN(2,2,0) Algebra System

For the construction example of anN(2,2,0) algebra system, we can consider it as an optimized constraint satisfaction problem (OCSP) that satisfies conditions (F1), (F2), and (F3). Then it can be solved by the intelligent optimization algorithm.To predigest the solving process and promote its practicability, we turn this problem into nonconstrained optimization problem. The optimization model is as follows:(3)min⁡⁡FX,Y=∑i=1n∑j=1n∑k=1nf1ai,aj,ak+f2ai,aj,ak+f3ai,
where
(4)X=x11,x12,…,x1n;…;xn1,xn2,…,xnnisalgebraS,*,0;Y=y11,y12,…,y1n;…;yn1,yn2,…,ynnisalgebraS,Δ,0;
for any ai, aj, and ak  (i=1,2,…,n;j=1,2,…,n;k=1,2,…,n) in S={a1,a2,…,an},
(5)ai*aj=xij∈S,aiΔaj=yij∈S,f1(ai,aj,ak)=0,ai*ajΔak=ak*ai*aj1,ai*ajΔak≠ak*ai*aj,f2ai,aj,ak=0,aiΔaj*ak=aj*ai*ak1,aiΔaj*ak≠aj*ai*ak,f3ai=0,0*ai=ai1,0*ai≠ai.The functionsf1, f2, and f3 are to transform the constraint satisfaction problem to a nonconstraint optimization problem by adding the penalty factors. When f1, f2, and f3 meet conditions (F1), (F2), and (F3), respectively, the objective values of each functions are 0; otherwise, a penalty factor 1 is as the objective value.For this problem, there are multiple solutions that meet conditions (F1), (F2), and (F3). Therefore, sometimes researchers hope to get as many solutions as possible. To resolve the multisolution problem, we introduce tube table (tube table: TT) to store the obtained solutions and to avoid duplication of solutions. The definite means are as follows:
(6)f4X=0X∉TTnX∈TT,
where TT is the tube table. f4 is defined as a penalty function. If X is not in tube table TT, f4 is equal to 0. Otherwise, f4 is assigned a penalty value n.Under this condition, the objective function can be expressed as(7)min⁡⁡FX,Y=∑i=1n∑j=1n∑k=1nf1ai,aj,ak+f2ai,aj,ak+f3ai+f4X.It is clear that, for this optimization problem, the objective value of optimal solution ismin⁡⁡F*=0.In order to solve the nonconstrained optimization problem, we propose a new harmony search (HS) algorithm which is a big improvement for classical HS algorithm [1] and NGHS [3] method. We called it improved NGHS (INGHS).


## 3. Classical Harmony Search (HS) and NGHS

Classical harmony search (HS) is derivative-free metaheuristic algorithm [4, 5]. It mimics the improvisation process of music players and attains the ideal harmony by adjusting the HM. HS algorithm has the same feature as genetic algorithm (GA).  The HS algorithm is good at identifying the new regions of the searching space in a reasonable time; however, it has difficulties performing a local search for numerical applications [3, 6–8].So, several variants of HS have been proposed to improve the performance of the HS algorithm [3, 6–14], such as local-best harmony search algorithm with dynamic subpopulations (DLHS) [6], self-adaptive global best harmony search algorithm (SGHS) [7], intelligent tuned harmony search (ITHS) [8] algorithm, and exploratory power of the harmony search (EHS) [3] algorithm. In addition, Zou et al. presented a novel global harmony search algorithm for unconstrained problems (NGHS) [9, 10]. The literature [11] presents the recent advances in HS algorithm. Tuo and Yong proposed HSTL methods for large scale optimization problem and presented an improved harmony search with chaos (HSCH) [12], as well as other variants [13–15] of HS and some applications [16–19] of HS.Consider an optimization model as follows:(8)min⁡fX,X=x1,x2,…,xDsubject  toxi∈xiL,xiU,i=1,2,…,D,
where f(X) is the optimization objective function, X is the solution vector that consists of D decision variables xi(i=1,2,…,D), and [xiL,xiU] is feasible range of values for decision variable xi.In the HS algorithm,X represents the harmony and f(X) denotes the melody of harmony X. HS uses three rules (memory consideration, pitch adjustments, and randomization) to optimize the harmony memories (HM) composed of HMS harmony vectors.


### 3.1. The Classical Harmony Search (HS) Algorithm

The steps in the procedure of classical harmony search algorithm are as follows.Step 1 (initialize the harmony memory).
The harmony memory (HM) consists of HMS harmony vectors. Each harmony vector is generated from a uniform distribution in the feasible space, as(9)xij=xiL+r·xiU-xiL,i=1,2,…,D;j=1,2,…,HMS,
where D and HMS represent the number of decision variables and the size of harmony memory, respectively, and r denotes a uniform distribution random number between 0 and 1, as
(10)HM=X1X2⋮XHMS=x11x21⋯xD1x12x22⋯xD2⋮⋮⋮⋮x1HMSx2HMS⋯xDHMS.Step 2 (improvise a new harmony via three rules).
There are three rules that can be used to improvise a new harmony vectorXnew.
(a) Memory Consideration. A decision variable value of the harmony vector will be adopted by choosing from the harmony memory with probability HMCR.
(b) Pitch Adjustment. Get a component randomly from an adjacent value of one decision variable of a harmony vector with probability PAR.
(c) Random Generation. Generate a component randomly in the feasible region with probability 1-HMCR.
The improvisation procedure of a new harmony vector works as Algorithm2.
A trial harmony vectorXnew is generated in Step 2. Next, in Step 3, it will be decided whether to survive.Step 3 (select operator).
Get the worst harmony vectorXworst from the HM (see Algorithm 1).Algorithm 1
If fitness
(
X
new
) is better than fitness (Xworst)  then
Xworst=Xnew; (Xworst is the worst harmony vector in HM).
EndIfAlgorithm 2:The improvisation procedure of new harmony vector by HS.
For  i=1 to D  do
If  rand(0, 1) < HMCR then
xinew=xij,j∈U{1,2,…,HMS}
If  rand(0, 1) < PARthen
xinew=xinew±rand()×FW(i); //FW: fretwidth
xinew=min⁡(max⁡(xinew,xiL),xiU)
Endif
Else
xinew=xiL+(xiU-xiL)×rand()
Endif
End ForStep 4 (check stopping criterion).
If the stopping criterion (maximum function evaluation times: maxFEs) is satisfied, computation is terminated. Otherwise, Steps2 and 3 are repeated.


### 3.2. The NGHS Algorithm

In the novel global harmony search (NGHS) algorithm [9], three significant parameters, harmony memory considering rate (HMCR), fret width (FW), and pitch adjusting rate (PAR), are excluded from NGHS and a random selection rate (pm) is included in the NGHS. In Step 3, NGHS works as Algorithm 3, where xibest and xiworst, respectively, represent indexes of the best harmony and the worst harmony in HM. rand(0,1) is a uniformly generated random number in [0,1], and it should set parameter pm=2/D for the 0-1 knapsack problem and set parameter pm=0.01~0.1 for continuous optimal problem.Algorithm 3:The NGHS modifies improvisation step.
For  i=1 to  D  do
xir=2×xibest-xiworst
xir=min⁡(max⁡(xir,xiL),xiU)
xinew=xiworst+rand(0,1)×(xir-xiworst).
Ifrand(0,1)≤pm %random mutation
xinew=xiL+(xiU-xiL)×rand(0,1)
EndIf
EndFor


### 3.3. The Proposed HS Method

In this section, we proposed a new harmony search algorithm which is improved based on classical HS algorithm and NGHS method, so we call the proposed algorithm INGHS.Since the HS algorithm origination, it has been applied to many practical optimization problems. However, for large scale optimization problems, classical HS has slow convergence and low precision, which is due to the fact that because a new decision variable value in harmony memory (HM) can be generated only by using pitch adjustment and randomization strategies during the search procedure, the memory consideration rule is only used to adjust the existing decision variable values according to the harmony memory (HM). Thus HS can maintain a strong performance of exploration, but not a good performance of exploitation, and, in the later stage of search, it is characterized by slow convergent. Therefore, for solving the large scale optimization problem, the key is to balance the global exploration performance and the local exploitation ability.Because the construction example of the algebra is a large scale high-dimensional optimization problem, to achieve the most satisfactory optimization performance by applying the HS algorithm to a given problem, we adopt four optimization strategies and dynamical parameter control method to balance the global exploration power and the local exploitation ability.It is of very importance between the convergence and the diversity in order to improve the efficiency of the search. In the classical HS algorithm, a new harmony is generated in Step2. After the selecting operation in Step 3, the population variance may increase or decrease. With a high population variance, the diversity and exploration power will increase, and in the same time the convergence and the exploitation power will decrease accordingly. Conversely, with a low population variance, the convergence and the exploitation power will increase [8]; the diversity and the exploration power will decrease. So it is significant how to keep the balance between the convergence and the diversity. Classical HS algorithm loses its ability easily at the later evolution process [3], because of improvising a new harmony from HM with a high HMCR and local adjusting with PAR. And HM diversity decreases gradually from the early iteration to the last. However, in HS algorithm, a low HMCR employed will increase the probability (1-HMCR) of random select in search space; the exploration power will improve, but the local search ability and the exploitation accuracy cannot be improved by the single pitch adjusting strategy.To overcome the inherent weaknesses of HS, in this section, we present INGHS method to construct example for algebra. The INGHS algorithm works as Algorithm4 and Figure 1.Algorithm 4:The pseudocode of the proposed algorithm INGHS.
Xnew=Xworst %%% worst is the index of the worst harmony in HM
For
i
=
1
to D
Ifrand(0, 1)  <Pm
% Random playing: randomly select any pitch within bounds
xinew=Round(xiL+(xiU-xiL)×rand(0,1))
Else
Ifrand(0, 1)  <  HMCR
% Memory considering: randomly select a note stored in HM
xinew=xia;a∈U(1,2,…,HMS)
Ifrand(0, 1)  <  PAR
% Pitch adjusting: randomly adjust the pitch slightly
xinew=Round(xinew±rand(0,1)×FW(i))
EndIf
ElseIfrand(0, 1)  <  NGP %
xr=Round(2xibest-xiworst)
xinew=Round(xiworst+rand(0,1)×(xr-xiworst))
EndIf
EndIf
EndFor % Finished improvising a new harmonyFigure 1
The flow chart of the proposed algorithm.In Algorithm4, to resolve the discrete optimization problems, the function Round(x) is used to round each element of x to the nearest integer.(1) Novel Global (NG) Best Strategy. In NGHS algorithm, the novel global best strategy is very effective to explore the global best solution. So, in the proposed method, the novel global best strategy is adopted (see Algorithm 5), where the best and worst, respectively, represent indexes of the best harmony and the worst harmony in HM.Algorithm 5
Ifrand(0, 1) < NGP (NGP is the rate of choosing the novel global best strategy)
xr=Round(2xibest-xiworst)
xinew=Round(xiworst+rand(0,1)×(xr-xiworst))
End(2) Parameters Dynamically Changed. To balance the exploration and exploitation power of the INGHS algorithm efficiently, HMCR, PAR, FW, and NGP parameters are dynamically adapted to a suitable range with the increase of generations. Equation (11) shows the dynamic change of HMCR, PAR, and NGP, respectively,
(11)HMCR=HMCRmin⁡+HMCRmax⁡-HMCRmin⁡×tTmax⁡,NGP=NGPmin⁡+NGPmax⁡-NGPmin⁡×tTmax⁡3,PAR=PARmax⁡-PARmax⁡-PARmin⁡×tTmax⁡(see [8]).It can be seen that the parameter HMCR gradually increased fromHMCRmin⁡ to HMCRmax⁡ linearly and the parameter NGP increased with low velocity in the early stage and it increased sharply in the final stage. That is because, in the beginning, in order to explore the global optimal solution, the harmony consideration rules and NG strategies are carried out with a smaller probability, and, in later stage, INGHS methods begin to focus on the local exploitation that needs a high probability to employ the NG strategy and harmony consideration rules. The benefits of doing so can get more opportunities to reinforce the global exploration by strengthening disturbance in the early stage and can acquire high precision solution by carrying local intensification search in the later stage. For the same reason, FW is decreased gradually in order to reduce perturbation step size step by step, and the variation of PAR from 0.55 to 0.3 is to reduce the probability of pitch adjustment.


### 3.4. The Construction Example forN(2,2,0) Algebra System with the Proposed HS Method

For anN(2,2,0) algebra system, there are multiple solutions that meet the conditions. Sometimes we need to obtain multiple solutions. So we adopt the proposed HS algorithm and tube table technology to resolve the multisolution problem. Its flow chart is as shown in Figure 2 and in Pseudocode 1.Pseudocode 1
SetTTas empty
For  L=1 to Max Loop times (ML)
Run the proposed HS algorithm to get a best solutionXnew;
If the objective function value F(Xnew)==0
PutXnew into tube table TT.
EndIf
EndForFigure 2
The flow chart for construction example of algebra system based on INGHS algorithm.


### 3.5. Effect of Parameters HMCR and NGP on INGHS Performance

In this section, we determine the effect of parametersHMCRmax⁡, HMCRmin⁡, NGPmax⁡, and NGPmin⁡ on the performance of the proposed algorithm INGHS. The experiments are investigated for algebra system (S,*,Δ,0), where S={a,b,c,d,e,f,g}.(1) Investigation for
N
G
P
max
⁡
and
N
G
P
min
⁡
(initialize
H
M
C
R
max
⁡
=
0.9, HMCRmin⁡=0.6). Let NGPmin⁡ change from 0.1 to 0.6; then, for each NGPmin⁡, let NGPmax⁡=0.5 to 1. So there are 6×6=36 pairs of parameters (NGPmin⁡, NGPmax⁡). For each pair of parameters (NGPmin⁡, NGPmax⁡), we execute the proposed algorithm (INGHS) S4  (74=2401) times and then record the number of solutions obtained. The result is shown in Figure 3.Figure 3
Variation of number of solutions with change inNGPmax⁡ and NGPmin⁡.(2) Investigation for
H
M
C
R
max
⁡
and
H
M
C
R
min
⁡
(initialize
N
G
P
max
⁡
=
0.5, NGPmin⁡=0.15). Let HMCRmin⁡=0.2 to 0.7 and let HMCRmax⁡=0.5 to 1, respectively. For each pair of parameters (HMCRmin⁡, HMCRmax⁡), the proposed algorithm INGHS is performed S4  (74=2401) times and then we record the number of solutions obtained. The number of solutions obtained is shown in Figure 4.Figure 4
Variation of number of solutions with change inHMCRmax⁡ and HMCRmin⁡.It can be seen from Figure3 that most solutions can be obtained when NGPmin⁡=0.2 and NGPmax⁡=0.5. From Figure 4, we find that most solutions are found when HMCRmin⁡=0.6 and HMCRmax⁡=0.9.From the above, the proposed algorithm has better performance when it is set asHMCRmin⁡=0.6, HMCRmax⁡=0.9, NGPmin⁡=0.2, and NGPmax⁡=0.5.


## 3.1. The Classical Harmony Search (HS) Algorithm

The steps in the procedure of classical harmony search algorithm are as follows.Step 1 (initialize the harmony memory).
The harmony memory (HM) consists of HMS harmony vectors. Each harmony vector is generated from a uniform distribution in the feasible space, as(9)xij=xiL+r·xiU-xiL,i=1,2,…,D;j=1,2,…,HMS,
where D and HMS represent the number of decision variables and the size of harmony memory, respectively, and r denotes a uniform distribution random number between 0 and 1, as
(10)HM=X1X2⋮XHMS=x11x21⋯xD1x12x22⋯xD2⋮⋮⋮⋮x1HMSx2HMS⋯xDHMS.Step 2 (improvise a new harmony via three rules).
There are three rules that can be used to improvise a new harmony vectorXnew.
(a) Memory Consideration. A decision variable value of the harmony vector will be adopted by choosing from the harmony memory with probability HMCR.
(b) Pitch Adjustment. Get a component randomly from an adjacent value of one decision variable of a harmony vector with probability PAR.
(c) Random Generation. Generate a component randomly in the feasible region with probability 1-HMCR.
The improvisation procedure of a new harmony vector works as Algorithm2.
A trial harmony vectorXnew is generated in Step 2. Next, in Step 3, it will be decided whether to survive.Step 3 (select operator).
Get the worst harmony vectorXworst from the HM (see Algorithm 1).Algorithm 1
If fitness
(
X
new
) is better than fitness (Xworst)  then
Xworst=Xnew; (Xworst is the worst harmony vector in HM).
EndIfAlgorithm 2:The improvisation procedure of new harmony vector by HS.
For  i=1 to D  do
If  rand(0, 1) < HMCR then
xinew=xij,j∈U{1,2,…,HMS}
If  rand(0, 1) < PARthen
xinew=xinew±rand()×FW(i); //FW: fretwidth
xinew=min⁡(max⁡(xinew,xiL),xiU)
Endif
Else
xinew=xiL+(xiU-xiL)×rand()
Endif
End ForStep 4 (check stopping criterion).
If the stopping criterion (maximum function evaluation times: maxFEs) is satisfied, computation is terminated. Otherwise, Steps2 and 3 are repeated.


## 3.2. The NGHS Algorithm

In the novel global harmony search (NGHS) algorithm [9], three significant parameters, harmony memory considering rate (HMCR), fret width (FW), and pitch adjusting rate (PAR), are excluded from NGHS and a random selection rate (pm) is included in the NGHS. In Step 3, NGHS works as Algorithm 3, where xibest and xiworst, respectively, represent indexes of the best harmony and the worst harmony in HM. rand(0,1) is a uniformly generated random number in [0,1], and it should set parameter pm=2/D for the 0-1 knapsack problem and set parameter pm=0.01~0.1 for continuous optimal problem.Algorithm 3:The NGHS modifies improvisation step.
For  i=1 to  D  do
xir=2×xibest-xiworst
xir=min⁡(max⁡(xir,xiL),xiU)
xinew=xiworst+rand(0,1)×(xir-xiworst).
Ifrand(0,1)≤pm %random mutation
xinew=xiL+(xiU-xiL)×rand(0,1)
EndIf
EndFor


## 3.3. The Proposed HS Method

In this section, we proposed a new harmony search algorithm which is improved based on classical HS algorithm and NGHS method, so we call the proposed algorithm INGHS.Since the HS algorithm origination, it has been applied to many practical optimization problems. However, for large scale optimization problems, classical HS has slow convergence and low precision, which is due to the fact that because a new decision variable value in harmony memory (HM) can be generated only by using pitch adjustment and randomization strategies during the search procedure, the memory consideration rule is only used to adjust the existing decision variable values according to the harmony memory (HM). Thus HS can maintain a strong performance of exploration, but not a good performance of exploitation, and, in the later stage of search, it is characterized by slow convergent. Therefore, for solving the large scale optimization problem, the key is to balance the global exploration performance and the local exploitation ability.Because the construction example of the algebra is a large scale high-dimensional optimization problem, to achieve the most satisfactory optimization performance by applying the HS algorithm to a given problem, we adopt four optimization strategies and dynamical parameter control method to balance the global exploration power and the local exploitation ability.It is of very importance between the convergence and the diversity in order to improve the efficiency of the search. In the classical HS algorithm, a new harmony is generated in Step2. After the selecting operation in Step 3, the population variance may increase or decrease. With a high population variance, the diversity and exploration power will increase, and in the same time the convergence and the exploitation power will decrease accordingly. Conversely, with a low population variance, the convergence and the exploitation power will increase [8]; the diversity and the exploration power will decrease. So it is significant how to keep the balance between the convergence and the diversity. Classical HS algorithm loses its ability easily at the later evolution process [3], because of improvising a new harmony from HM with a high HMCR and local adjusting with PAR. And HM diversity decreases gradually from the early iteration to the last. However, in HS algorithm, a low HMCR employed will increase the probability (1-HMCR) of random select in search space; the exploration power will improve, but the local search ability and the exploitation accuracy cannot be improved by the single pitch adjusting strategy.To overcome the inherent weaknesses of HS, in this section, we present INGHS method to construct example for algebra. The INGHS algorithm works as Algorithm4 and Figure 1.Algorithm 4:The pseudocode of the proposed algorithm INGHS.
Xnew=Xworst %%% worst is the index of the worst harmony in HM
For
i
=
1
to D
Ifrand(0, 1)  <Pm
% Random playing: randomly select any pitch within bounds
xinew=Round(xiL+(xiU-xiL)×rand(0,1))
Else
Ifrand(0, 1)  <  HMCR
% Memory considering: randomly select a note stored in HM
xinew=xia;a∈U(1,2,…,HMS)
Ifrand(0, 1)  <  PAR
% Pitch adjusting: randomly adjust the pitch slightly
xinew=Round(xinew±rand(0,1)×FW(i))
EndIf
ElseIfrand(0, 1)  <  NGP %
xr=Round(2xibest-xiworst)
xinew=Round(xiworst+rand(0,1)×(xr-xiworst))
EndIf
EndIf
EndFor % Finished improvising a new harmonyFigure 1
The flow chart of the proposed algorithm.In Algorithm4, to resolve the discrete optimization problems, the function Round(x) is used to round each element of x to the nearest integer.(1) Novel Global (NG) Best Strategy. In NGHS algorithm, the novel global best strategy is very effective to explore the global best solution. So, in the proposed method, the novel global best strategy is adopted (see Algorithm 5), where the best and worst, respectively, represent indexes of the best harmony and the worst harmony in HM.Algorithm 5
Ifrand(0, 1) < NGP (NGP is the rate of choosing the novel global best strategy)
xr=Round(2xibest-xiworst)
xinew=Round(xiworst+rand(0,1)×(xr-xiworst))
End(2) Parameters Dynamically Changed. To balance the exploration and exploitation power of the INGHS algorithm efficiently, HMCR, PAR, FW, and NGP parameters are dynamically adapted to a suitable range with the increase of generations. Equation (11) shows the dynamic change of HMCR, PAR, and NGP, respectively,
(11)HMCR=HMCRmin⁡+HMCRmax⁡-HMCRmin⁡×tTmax⁡,NGP=NGPmin⁡+NGPmax⁡-NGPmin⁡×tTmax⁡3,PAR=PARmax⁡-PARmax⁡-PARmin⁡×tTmax⁡(see [8]).It can be seen that the parameter HMCR gradually increased fromHMCRmin⁡ to HMCRmax⁡ linearly and the parameter NGP increased with low velocity in the early stage and it increased sharply in the final stage. That is because, in the beginning, in order to explore the global optimal solution, the harmony consideration rules and NG strategies are carried out with a smaller probability, and, in later stage, INGHS methods begin to focus on the local exploitation that needs a high probability to employ the NG strategy and harmony consideration rules. The benefits of doing so can get more opportunities to reinforce the global exploration by strengthening disturbance in the early stage and can acquire high precision solution by carrying local intensification search in the later stage. For the same reason, FW is decreased gradually in order to reduce perturbation step size step by step, and the variation of PAR from 0.55 to 0.3 is to reduce the probability of pitch adjustment.


## 3.4. The Construction Example forN(2,2,0) Algebra System with the Proposed HS Method

For anN(2,2,0) algebra system, there are multiple solutions that meet the conditions. Sometimes we need to obtain multiple solutions. So we adopt the proposed HS algorithm and tube table technology to resolve the multisolution problem. Its flow chart is as shown in Figure 2 and in Pseudocode 1.Pseudocode 1
SetTTas empty
For  L=1 to Max Loop times (ML)
Run the proposed HS algorithm to get a best solutionXnew;
If the objective function value F(Xnew)==0
PutXnew into tube table TT.
EndIf
EndForFigure 2
The flow chart for construction example of algebra system based on INGHS algorithm.


## 3.5. Effect of Parameters HMCR and NGP on INGHS Performance

In this section, we determine the effect of parametersHMCRmax⁡, HMCRmin⁡, NGPmax⁡, and NGPmin⁡ on the performance of the proposed algorithm INGHS. The experiments are investigated for algebra system (S,*,Δ,0), where S={a,b,c,d,e,f,g}.(1) Investigation for
N
G
P
max
⁡
and
N
G
P
min
⁡
(initialize
H
M
C
R
max
⁡
=
0.9, HMCRmin⁡=0.6). Let NGPmin⁡ change from 0.1 to 0.6; then, for each NGPmin⁡, let NGPmax⁡=0.5 to 1. So there are 6×6=36 pairs of parameters (NGPmin⁡, NGPmax⁡). For each pair of parameters (NGPmin⁡, NGPmax⁡), we execute the proposed algorithm (INGHS) S4  (74=2401) times and then record the number of solutions obtained. The result is shown in Figure 3.Figure 3
Variation of number of solutions with change inNGPmax⁡ and NGPmin⁡.(2) Investigation for
H
M
C
R
max
⁡
and
H
M
C
R
min
⁡
(initialize
N
G
P
max
⁡
=
0.5, NGPmin⁡=0.15). Let HMCRmin⁡=0.2 to 0.7 and let HMCRmax⁡=0.5 to 1, respectively. For each pair of parameters (HMCRmin⁡, HMCRmax⁡), the proposed algorithm INGHS is performed S4  (74=2401) times and then we record the number of solutions obtained. The number of solutions obtained is shown in Figure 4.Figure 4
Variation of number of solutions with change inHMCRmax⁡ and HMCRmin⁡.It can be seen from Figure3 that most solutions can be obtained when NGPmin⁡=0.2 and NGPmax⁡=0.5. From Figure 4, we find that most solutions are found when HMCRmin⁡=0.6 and HMCRmax⁡=0.9.From the above, the proposed algorithm has better performance when it is set asHMCRmin⁡=0.6, HMCRmax⁡=0.9, NGPmin⁡=0.2, and NGPmax⁡=0.5.


## 4. Computational Experiments and Results

In this section, we have tested the proposed algorithm over a set ofN(2,2,0) algebra system construction examples problems.


### 4.1. The Proposed Algorithm for Solving the Construction Examples of Algebra System

Definition1 is chosen as the optimization objective algebra system. For Definition 1, we, respectively, set the following:(1)
S=a,b;(2)
S=a,b,c;(3)
S=a,b,c,d;(4)
S=a,b,c,d,e;(5)
S=a,b,c,d,e,f;(6)
S=a,b,c,d,e,f,g;(7)
S=a,b,c,d,e,f,g,h;(8)
S=a,b,c,d,e,f,g,h,i;(9)
S=a,b,c,d,e,f,g,h,i,j; n=Srepresents the number of setS,D=2n2.Then we use the proposed algorithm to construct the examples for the algebra system onS.In order to deal with the optimization problems easily, we replace the elementsa, b, c, d, e, f, g, h, i, and j with 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, respectively. So, for each S, the upper limit of variables about optimization problems is set as S and the lower limit is set as 1.


### 4.2. The Parameters Setting for Algorithms

In the experiment test, we set the following parameter values:Tmax⁡=500×D; for NGHS algorithm, HMS=10, pm=min⁡(0.01,2/D); for the proposed algorithm (INGHS), HMS=10, HMCRmax⁡=0.9,HMCRmax⁡=0.6, NGPmax⁡=0.55, NGPmin⁡=0.15, PARmax⁡=0.8, PARmin⁡=0.25, FWmax⁡=n/2, FWmin⁡=n/10, and pm=min⁡(0.01,2/D).Whenn=2 and n=3, there are 3 and 16 solutions for theN(2,2,0) algebra system, respectively. So we set max looping times (ML)=3 and 16, respectively. When n>3 and n<9, we do not know how many solutions are there for the algebra system. So we set ML=n4. However, with the increasing of n, there are much more solutions, and computer’s running time is very long. So we set ML=8000 and 5000 when n=9 and n=10.


### 4.3. The Experiment Results and Analysis

In order to evaluate the performance of the proposed algorithm INGHS, we compared its success rate of finding the solutions with HS, HSTL, and NGHS algorithms in the same conditions. The results are shown in Table1.Table 1
The success rate comparison of the proposed method with HS and NGHS algorithm.
n
The number of solutions
HS
HSTL
NGHS
INGHS
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
2
3
3
3
100.00%
3
3
100.00%
3
3
100.00%
3
3
100.00%
3
16
16
15
93.75%
16
16
100.00%
16
16
100.00%
16
16
100.00%
4
Unknown
256
127
49.61%
256
148
57.81%
256
127
49.61%
256
162
63.28%
5
Unknown
625
485
77.60%
625
600
96.00%
625
579
92.64%
625
601
96.16%
6
Unknown
1296
1016
78.40%
1296
1258
97.07%
1296
1243
95.91%
1296
1271
98.07%
7
Unknown
2401
1834
76.38%
2401
2212
92.13%
2401
2119
88.25%
2401
2217
92.34%
8
Unknown
4096
79
1.93%
4096
3364
82.13%
4096
3174
77.49%
4096
3383
82.59%
9
Unknown
8000
0
0.00%
8000
5763
72.04%
8000
4768
59.60%
8000
6151
76.89%
10
Unknown
5000
0
0.00%
5000
3451
69.02%
5000
3251
65.02%
5000
3749
74.98%WhenS={a,b}  (n=2), the solutions, as shown in (12a)–(12c), are obtained by using the proposed algorithm. And when S={a,b,c}  (n=3), the solutions obtained by INGHS method are shown in (13a)–(13p). For other instances (n>3), due to the existence of many solutions, we only present one solution for each instance. All is shown in (14)–(20).The first solution onn=2 is as follows:
(12a)*abaabbabΔabaaabbb
The second solution onn=2 is as follows:
(12b)*abaabbbaΔabaabbba
The third solution onn=2 is as follows:
(12c)*abaabbbbΔabaabbbbThe first solution onn=3 is as follows:
(13a)*abcaabcbbbbccbcΔabcaabcbbbbccbc
The second solution onn=3 is as follows:
(13b)*abcaabcbbbbcabcΔabcaababbbbccbc
The third solution onn=3 is as follows:
(13c)*abcaabcbbbbcbbbΔabcaabbbbbbccbb
The fourth solution onn=3 is as follows:
(13d)*abcaabcbabcccccΔabcaaacbbbccccc
The fifth solution onn=3 is as follows:
(13e)*abcaabcbbbbccbbΔabcaabcbbbbccbb
The sixth solution onn=3 is as follows:
(13f)*abcaabcbbbbccbaΔabcaabcbbbbccba
The seventh solution onn=3 is as follows:
(13g)*abcaabcbabccabcΔabcaabcbabccabc
The eighth solution onn=3 is as follows:
(13h)*abcaabcbbcbccbcΔabcaabcbbcbccbc
The ninth solution onn=3 is as follows:
(13i)*abcaabcbbbccbbcΔabcaabcbbbccbbc
The tenth solution onn=3 is as follows:
(13j)*abcaabcbcbcccbcΔabcaabcbcbcccbc
The eleventh solution onn=3 is as follows:
(13k)*abcaabcbbccccccΔabcaabcbbcccccc
The twelfth solution onn=3 is as follows:
(13l)*abcaabcbbbcccccΔabcaabcbbbccccc
The thirteenth solution onn=3 is as follows:
(13m)*abcaabcbbbccccbΔabcaabcbbbccccb
The fourteenth solution onn=3 is as follows:
(13n)*abcaabcbbacccccΔabcaabcbbaccccc
The fifteenth solution onn=3 is as follows:
(13o)*abcaabcbcccccccΔabcaaccbbcccccc
The sixteenth solution onn=3 is as follows:
(13p)*abcaabcbbcaccabΔabcaabcbbcaccabOne of the solutions onn=4 (S={a,b,c,d}) is as follows:
(14)*abcdaabcdbabcdcdccdddccdΔabcdaaaddbbbcccccccddddd
One of the solutions onn=5 (S={a,b,c,d,e}) is as follows:
(15)*abcdeaabcdebbbddbccdddcddddddeabcdeΔabcdeaabcdabbbddbccdddcddddddeebcde
One of the solutions onn=6 (S={a,b,c,d,e,f}) is as follows:
(16)*abcdefaabcdefbabcdefccccdccdddddddeeecdeefabcdefΔabcdefaaacdeabbbcdebccccdccdddddddeeecdeefffcdef
One of the solutions onn=7 (S={a,b,c,d,e,f,g}) is as follows:
(17)*abcdefgaabcdefgbabcdefgcabcdefgddeddefeededdefeffffffffgdeddefeΔabcdefgaaaaddfdbbbbeefeccccddfdddddddfdeeeeeefeffffffffggggeefe
One of the solutions onn=8 (S={a,b,c,d,e,f,g,h}) is as follows:
(18)*abcdefghaabcdefghbabcdefghcccccccccdddccccddeeeccefeefccccccccgabcdefghhabcdefghΔabcdefghaaacdecaabbbcdecbbcccccccccdddccccddeeecceceefffccfcffgggcdecgghhhcdechh
One of the solutions onn=9 (S={a,b,c,d,e,f,g,h,i}) is as follows:
(19)*abcdefghiaabcdefghibbbbbbbbbbccbcbeegbcddbbbbdbbdecbcbeegbcfabcdefghigbbbbbbbbbhbbbbbbbbbiabcdefghiΔabcdefghiaabcdcabbabbbbbbbbbbccbcbccbbcddbbbbdbbdeebebeebbeffbedefbbfggbgbggbbghhbbbbhbbhiibcdcibbi
One of the solutions onn=10 (S={a,b,c,d,e,f,g,h,i,j}) is as follows:
(20)*abcdefghijaabcdefghijbeeceeegeeeceeceeegeeeddecfeegeeeeeeceeegeeeffeceeegeeegeeceeegeeehhbceeegheeiieceeegeeejeeceeegeeeΔabcdefghijaaeedefehiebbeeeeeebeecccccccccccddeefeeeeeeeeeeeeeeeeeffeeeeeeeeeggggggggggghheeeeeeheeiieeeeeeeeejjeeeeeeeeeFrom Table1, it can be seen obviously that the success rate of all instances of the proposed method is higher than HS, HSTL, and NGHS.For instance,n=6,7,8,9, and 10, and Figures 5, 6, 7, 8, 9, and 10 show the convergence curves of three algorithms (HS, NGHS, and INGHS). It is evident from Figures 5–10 that the proposed algorithm is better than HS and NGHS for all instances. The convergence curve of the proposed algorithm can maintain falling until it finds the best solution. When n>6, the convergence curve of INGHS method falls faster than HS, HSTL, and NGHS algorithms, and it keeps declining actively until the best solution is found.The convergence curve and the box plot whenn=5.
(a)
(b)The convergence curve and the box plot whenn=6.
(a)
(b)The convergence curve and the box plot whenn=7.
(a)
(b)The convergence curve and the box plot whenn=8.
(a)
(b)The convergence curve and the box plot whenn=9.
(a)
(b)The convergence curve and the box plot whenn=10.
(a)
(b)


## 4.1. The Proposed Algorithm for Solving the Construction Examples of Algebra System

Definition1 is chosen as the optimization objective algebra system. For Definition 1, we, respectively, set the following:(1)
S=a,b;(2)
S=a,b,c;(3)
S=a,b,c,d;(4)
S=a,b,c,d,e;(5)
S=a,b,c,d,e,f;(6)
S=a,b,c,d,e,f,g;(7)
S=a,b,c,d,e,f,g,h;(8)
S=a,b,c,d,e,f,g,h,i;(9)
S=a,b,c,d,e,f,g,h,i,j; n=Srepresents the number of setS,D=2n2.Then we use the proposed algorithm to construct the examples for the algebra system onS.In order to deal with the optimization problems easily, we replace the elementsa, b, c, d, e, f, g, h, i, and j with 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, respectively. So, for each S, the upper limit of variables about optimization problems is set as S and the lower limit is set as 1.


## 4.2. The Parameters Setting for Algorithms

In the experiment test, we set the following parameter values:Tmax⁡=500×D; for NGHS algorithm, HMS=10, pm=min⁡(0.01,2/D); for the proposed algorithm (INGHS), HMS=10, HMCRmax⁡=0.9,HMCRmax⁡=0.6, NGPmax⁡=0.55, NGPmin⁡=0.15, PARmax⁡=0.8, PARmin⁡=0.25, FWmax⁡=n/2, FWmin⁡=n/10, and pm=min⁡(0.01,2/D).Whenn=2 and n=3, there are 3 and 16 solutions for theN(2,2,0) algebra system, respectively. So we set max looping times (ML)=3 and 16, respectively. When n>3 and n<9, we do not know how many solutions are there for the algebra system. So we set ML=n4. However, with the increasing of n, there are much more solutions, and computer’s running time is very long. So we set ML=8000 and 5000 when n=9 and n=10.


## 4.3. The Experiment Results and Analysis

In order to evaluate the performance of the proposed algorithm INGHS, we compared its success rate of finding the solutions with HS, HSTL, and NGHS algorithms in the same conditions. The results are shown in Table1.Table 1
The success rate comparison of the proposed method with HS and NGHS algorithm.
n
The number of solutions
HS
HSTL
NGHS
INGHS
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
Max looping times(ML)
Success times
Success rate
2
3
3
3
100.00%
3
3
100.00%
3
3
100.00%
3
3
100.00%
3
16
16
15
93.75%
16
16
100.00%
16
16
100.00%
16
16
100.00%
4
Unknown
256
127
49.61%
256
148
57.81%
256
127
49.61%
256
162
63.28%
5
Unknown
625
485
77.60%
625
600
96.00%
625
579
92.64%
625
601
96.16%
6
Unknown
1296
1016
78.40%
1296
1258
97.07%
1296
1243
95.91%
1296
1271
98.07%
7
Unknown
2401
1834
76.38%
2401
2212
92.13%
2401
2119
88.25%
2401
2217
92.34%
8
Unknown
4096
79
1.93%
4096
3364
82.13%
4096
3174
77.49%
4096
3383
82.59%
9
Unknown
8000
0
0.00%
8000
5763
72.04%
8000
4768
59.60%
8000
6151
76.89%
10
Unknown
5000
0
0.00%
5000
3451
69.02%
5000
3251
65.02%
5000
3749
74.98%WhenS={a,b}  (n=2), the solutions, as shown in (12a)–(12c), are obtained by using the proposed algorithm. And when S={a,b,c}  (n=3), the solutions obtained by INGHS method are shown in (13a)–(13p). For other instances (n>3), due to the existence of many solutions, we only present one solution for each instance. All is shown in (14)–(20).The first solution onn=2 is as follows:
(12a)*abaabbabΔabaaabbb
The second solution onn=2 is as follows:
(12b)*abaabbbaΔabaabbba
The third solution onn=2 is as follows:
(12c)*abaabbbbΔabaabbbbThe first solution onn=3 is as follows:
(13a)*abcaabcbbbbccbcΔabcaabcbbbbccbc
The second solution onn=3 is as follows:
(13b)*abcaabcbbbbcabcΔabcaababbbbccbc
The third solution onn=3 is as follows:
(13c)*abcaabcbbbbcbbbΔabcaabbbbbbccbb
The fourth solution onn=3 is as follows:
(13d)*abcaabcbabcccccΔabcaaacbbbccccc
The fifth solution onn=3 is as follows:
(13e)*abcaabcbbbbccbbΔabcaabcbbbbccbb
The sixth solution onn=3 is as follows:
(13f)*abcaabcbbbbccbaΔabcaabcbbbbccba
The seventh solution onn=3 is as follows:
(13g)*abcaabcbabccabcΔabcaabcbabccabc
The eighth solution onn=3 is as follows:
(13h)*abcaabcbbcbccbcΔabcaabcbbcbccbc
The ninth solution onn=3 is as follows:
(13i)*abcaabcbbbccbbcΔabcaabcbbbccbbc
The tenth solution onn=3 is as follows:
(13j)*abcaabcbcbcccbcΔabcaabcbcbcccbc
The eleventh solution onn=3 is as follows:
(13k)*abcaabcbbccccccΔabcaabcbbcccccc
The twelfth solution onn=3 is as follows:
(13l)*abcaabcbbbcccccΔabcaabcbbbccccc
The thirteenth solution onn=3 is as follows:
(13m)*abcaabcbbbccccbΔabcaabcbbbccccb
The fourteenth solution onn=3 is as follows:
(13n)*abcaabcbbacccccΔabcaabcbbaccccc
The fifteenth solution onn=3 is as follows:
(13o)*abcaabcbcccccccΔabcaaccbbcccccc
The sixteenth solution onn=3 is as follows:
(13p)*abcaabcbbcaccabΔabcaabcbbcaccabOne of the solutions onn=4 (S={a,b,c,d}) is as follows:
(14)*abcdaabcdbabcdcdccdddccdΔabcdaaaddbbbcccccccddddd
One of the solutions onn=5 (S={a,b,c,d,e}) is as follows:
(15)*abcdeaabcdebbbddbccdddcddddddeabcdeΔabcdeaabcdabbbddbccdddcddddddeebcde
One of the solutions onn=6 (S={a,b,c,d,e,f}) is as follows:
(16)*abcdefaabcdefbabcdefccccdccdddddddeeecdeefabcdefΔabcdefaaacdeabbbcdebccccdccdddddddeeecdeefffcdef
One of the solutions onn=7 (S={a,b,c,d,e,f,g}) is as follows:
(17)*abcdefgaabcdefgbabcdefgcabcdefgddeddefeededdefeffffffffgdeddefeΔabcdefgaaaaddfdbbbbeefeccccddfdddddddfdeeeeeefeffffffffggggeefe
One of the solutions onn=8 (S={a,b,c,d,e,f,g,h}) is as follows:
(18)*abcdefghaabcdefghbabcdefghcccccccccdddccccddeeeccefeefccccccccgabcdefghhabcdefghΔabcdefghaaacdecaabbbcdecbbcccccccccdddccccddeeecceceefffccfcffgggcdecgghhhcdechh
One of the solutions onn=9 (S={a,b,c,d,e,f,g,h,i}) is as follows:
(19)*abcdefghiaabcdefghibbbbbbbbbbccbcbeegbcddbbbbdbbdecbcbeegbcfabcdefghigbbbbbbbbbhbbbbbbbbbiabcdefghiΔabcdefghiaabcdcabbabbbbbbbbbbccbcbccbbcddbbbbdbbdeebebeebbeffbedefbbfggbgbggbbghhbbbbhbbhiibcdcibbi
One of the solutions onn=10 (S={a,b,c,d,e,f,g,h,i,j}) is as follows:
(20)*abcdefghijaabcdefghijbeeceeegeeeceeceeegeeeddecfeegeeeeeeceeegeeeffeceeegeeegeeceeegeeehhbceeegheeiieceeegeeejeeceeegeeeΔabcdefghijaaeedefehiebbeeeeeebeecccccccccccddeefeeeeeeeeeeeeeeeeeffeeeeeeeeeggggggggggghheeeeeeheeiieeeeeeeeejjeeeeeeeeeFrom Table1, it can be seen obviously that the success rate of all instances of the proposed method is higher than HS, HSTL, and NGHS.For instance,n=6,7,8,9, and 10, and Figures 5, 6, 7, 8, 9, and 10 show the convergence curves of three algorithms (HS, NGHS, and INGHS). It is evident from Figures 5–10 that the proposed algorithm is better than HS and NGHS for all instances. The convergence curve of the proposed algorithm can maintain falling until it finds the best solution. When n>6, the convergence curve of INGHS method falls faster than HS, HSTL, and NGHS algorithms, and it keeps declining actively until the best solution is found.The convergence curve and the box plot whenn=5.
(a)
(b)The convergence curve and the box plot whenn=6.
(a)
(b)The convergence curve and the box plot whenn=7.
(a)
(b)The convergence curve and the box plot whenn=8.
(a)
(b)The convergence curve and the box plot whenn=9.
(a)
(b)The convergence curve and the box plot whenn=10.
(a)
(b)


## 5. Conclusions

This paper has investigated nine construction example problems of algebra system and converted the construction example problems into optimization problems. A novel harmony search algorithm (INGHS) is proposed to solve the problems. Global best strategy and dynamic parameters adjustment are employed in INGHS. The experimental results on 9 instances of algebra system demonstrate that the proposed algorithm is more effective than HS, HSTL, and NGHS algorithms. Further research will investigate the INGHS algorithm to solve the combinatorial optimization problems and some practical optimization problems.



---

*Source: 836925-2015-01-19.xml*