# PAPR Reduction of OFDM Signals by Novel Global Harmony Search in PTS Scheme

Authors: Hojjat Salehinejad; Siamak Talebi
Journal: International Journal of Digital Multimedia Broadcasting
 (2012)

---

## Abstract

The orthogonal frequency division multiplexing (OFDM) modulation technique is one of the key strategies for multiuser signal transmission especially in smart grids and wind farms. This paper introduces an approach for peak-to-average power ratio (PAPR) reduction of such signals based on novel global harmony search (NGHS) and partial transmit sequence (PTS) schemes. In PTS technique, the data block to be transmitted is partitioned into disjoint subblocks, which are combined using phase factors to minimize PAPR. The PTS requires an exhaustive search over all combinations of allowed phase factors. Therefore, with respect to the fast implementation and simplicity of NGHS technique, we could achieve significant reduction of PAPR.


---

## Body

## 1. Introduction

Orthogonal frequency division multiplexing (OFDM) is an attractive technology for high-bit-rate transmission in wireless communications and has been widely adopted in different communication applications such as smart grid communication systems and offshore wind farms (OWFs) for data transmission between wind turbines [1]. However, some challenging issues still remain unsolved in design of such systems. One critical problem is large peak-to-average power ratio (PAPR) of the transmitted signals, which requires power amplifiers with a large linear range. Therefore, the OFDM receiver’s detection is very sensitive to the nonlinear devices [2].Over the past decade, various PAPR reduction techniques have been proposed in the literature [2]. One type of PAPR reduction methods is the probabilistic scheme; such as partial transmit sequence (PTS) technique that is based on combining signal subblocks which are phase-shifted by constant phase factors [3]. Another probabilistic scheme is selective mapping (SLM) in which multiple sequences with the lowest PAPR are transmitted [2]. PTS technique can get side information, which is needed to be sent at the same time and is able to achieve sufficient PAPR reduction [3]. However, the continuous search complexity of the optimal phase combination increases exponentially with the number of subblocks. Suboptimal PTS methods are of interest in the literature [4]. The iterative flipping PTS (IPTS) in [5] has linearly proportional computational complexity to the number of subblocks. A systematic procedure for the minimum error probability to look for and form the optimal precoding matrices is proposed in [6]. In exhaustive search of phase factors, the computational complexity increases exponentially with the number of the subblocks. Therefore, a scheme is proposed in [7] by utilizing the correlation among the candidate signals generated in PTS. In [8], two phase weighting methods with low computational complexity for PTS, namely grouping phase weighting (GPW) and recursive phase weighting (RPW), are proposed. These methods focus on simplifying the computation for candidate sequences.The conventional PTS scheme requires an exhaustive searching over all combinations of allowed phase factors [7, 8]. Optimization algorithms, and particularly bioinspired approaches, due to their low computational complexities and fast implementation, have attracted many attentions in recent years in major OFDM drawbacks. Some examples are a suboptimal PTS algorithm based on particle swarm optimization (PSO) [9]; an intelligent genetic algorithm (GA) for PAPR reduction [10]; cross entropy (CE) approach for sign-selection in PAPR [11]; artificial bee colony (ABC) algorithm for larger PTS subblocks [12]; harmony search algorithm (HSA) in [13] that could reduce the PAPR simply and efficiently.In this paper, we propose a suboptimal phase optimization scheme, which can efficiently reduce the PAPR of the OFDM signals, based on a modified global harmony search (GHS) algorithm [14], called novel global harmony search (NGHS) algorithm [14]. This algorithm is analogous with the music improvisation process, where a musician continue to polish the pitches in order to obtain better harmony. We show that this scheme can achieve a superb PAPR reduction performance, while keeping its efficient and simple structure.This paper is organized as follows. In Section2, we shortly review harmony search principals. In Section 3, the OFDM is briefly introduced and the PAPR problem is formulated. The proposed NGHS-PTS approach is then discussed in Section 4. In Section 5, performance of the proposed algorithm is evaluated and discussed. Finally, the paper is concluded in Section 6.


## 2. A Survey on Harmony Search and Further Developments

### 2.1. Harmony Search Algorithm

The musical process of searching for a perfect state of harmony has inspired researches to propose HSA as a metaheuristic optimization method [15]. An interesting analogous between the HSA and real musical instruments adjustment is the optimization solution vector and the harmony in music, respectively. Also the musician’s improvisations are analogous to local and global search schemes in optimization methods. An advantage of HSA is the use of stochastic random search based on harmony memory considering and pitch adjustment rates, instead of the need for an initial value as well as few mathematical requirements. According to [14, 15], a typical HSA is consisted of 5 steps which are as follows.Step 1 (initialization).
This step consists of defining the objective function, system parameters, decision variables, and the corresponding boundaries. Typically, an optimization problem can be defined as minimizingf(x) subject to xiL≤xi≤xiUfor i=1,2,…,Nwhere xiLand xiUare the lower and upper bounds for decision variables. The HSA parameters are the harmony memory size (HMS) or the number of solution vectors in harmony memory, harmony memory considering rate (HMCR), distance bandwidth (bw), pitch adjusting rate (PAR), and the number of improvisations K, or stopping criterion. Value of K is the same as the total number of function evaluations.Step 2 (HM initialization).
All the solution vectors (sets of decision variables) are stored in the harmony memory (HM). Its initial HM is randomly selected in[xiL,xiU] for  i=1,2,…,Nby
(1)xij=xiL+(q×(xiU-xiL)),j=1,2,…,HMS,
where qis a random number with uniform distribution in [0,1].Step 3 (new harmony improvisation).
This step generates a new harmonyxinew. To do so, a uniform random number r1is generated uniformly in  [0,1]. If r1 is less than HMCR, xinewis generated by memory consideration and otherwise, xinew is achieved by a random selection. As an example, an HMCR of 0.75 designates that the HS algorithm will choose the decision variable value from the historically stored values in the HM with the probability of 75% or from the entire possible range with a 25% probability. If xinewis produced by the memory consideration, then it will undergo a pitch adjustment. The pitch adjustment rule is defined as
(2)xinew=xinew±(r×bw),
where r is a uniform random number in [0,1].Step 4 (HMrefreshing).
The HM is updated after generation ofxinew. If the fitness of the improvised harmony vector xnew=(x1new,x2new,…,xNnew)is better than that of the worst harmony, the worst harmony in the HM will be replaced with xnew and becomes a new member of the HM.Step 5 (stop criterion).
Thenew harmony improvisation and HMrefreshing steps are repeated until the maximum number of improvisations, K, is met.


### 2.2. Improved Harmony Search Algorithm

After fundamental presentation of the HS in 2001, Mahdavi et al. proposed an improved version of the HSA, called improved harmony search (IHS) algorithm later in 2007, [16]. The key modifications of this improvement are regarding PAR and bw, which are updated dynamically as
(3)PAR(k)=PARmin+(PARmax-PARminK)k,bw(k)=bwmaxexp(ln(bwmin/bwmax)K)k,
where k and K are current number of improvisations and maximum number of improvisations, respectively. The key property of IHS is its approach for generating of new solution vectors that enhances accuracy and convergence rate of harmony search.The key difference between IHS and traditional HS method is in the way of adjusting PAR and bw. To improve the performance of the HS algorithm and eliminate the drawbacks lies with fixed values of PAR and bw, IHS algorithm uses variables PAR and bw in improvisation step. The traditional HS algorithm employs a fixed value of PAR and bw for specific purposes. In the HS method PAR and bw values are adjusted in initialization step and are fixed throughout the algorithm. These parameters are of great importance in optimum adjustment of optimized solution vectors and can be potentially useful in adjusting convergence rate of algorithm to optimal solution. Therefore, fine adjustment of these parameters is of great interest [14]. Combination of small PAR and large bw values results in low performance of the algorithm as well as more number of iterations to find optimum solution. Small values of bw in the final generations can adjust tuning of solution vectors. However, in beginning generations bw must have a large value to in order to have a rise in diversity of solution vectors. On the other side, large PAR values in combination with small bw values mostly result in best solutions in final generations, in which algorithm converged to optimal solution vector [14].


### 2.3. Novel Global Harmony Search Algorithm

In 2010, Zou et al. proposed the NGHS algorithm. In this approach, a genetic mutation probabilitypmis considered, which modifies the new harmony improvisation step of the HS such that the new harmony mimics the global best harmony in the HM. In fact, it works instead of the HMCR and PAR as in Pseudocode 1. In this procedure, the terms “best” and “worst” are the indexes of the global best harmony and the worst harmony in HM, respectively. The parameters r and rand()are all uniformly random generated numbers in  [0,1]. After improvisation, the NGHS replaces the worst harmony xworst in HM with the new harmony xnew even if xnew is worse than xworst [14].Pseudocode 1:New harmony vector generation procedure of NGHS in pseudocode.
Initialize New Harmony Vector Generation
For each i∈[1,N]
stepi=|xibest-xiwrost|
xinew=xibest±r×stepi
If  U(0,1)≤pm
xinew=xiL+∥r∥×(xiU-xiL), where  r~U(0,1)
End
End
End New Harmony Vector Generation


## 2.1. Harmony Search Algorithm

The musical process of searching for a perfect state of harmony has inspired researches to propose HSA as a metaheuristic optimization method [15]. An interesting analogous between the HSA and real musical instruments adjustment is the optimization solution vector and the harmony in music, respectively. Also the musician’s improvisations are analogous to local and global search schemes in optimization methods. An advantage of HSA is the use of stochastic random search based on harmony memory considering and pitch adjustment rates, instead of the need for an initial value as well as few mathematical requirements. According to [14, 15], a typical HSA is consisted of 5 steps which are as follows.Step 1 (initialization).
This step consists of defining the objective function, system parameters, decision variables, and the corresponding boundaries. Typically, an optimization problem can be defined as minimizingf(x) subject to xiL≤xi≤xiUfor i=1,2,…,Nwhere xiLand xiUare the lower and upper bounds for decision variables. The HSA parameters are the harmony memory size (HMS) or the number of solution vectors in harmony memory, harmony memory considering rate (HMCR), distance bandwidth (bw), pitch adjusting rate (PAR), and the number of improvisations K, or stopping criterion. Value of K is the same as the total number of function evaluations.Step 2 (HM initialization).
All the solution vectors (sets of decision variables) are stored in the harmony memory (HM). Its initial HM is randomly selected in[xiL,xiU] for  i=1,2,…,Nby
(1)xij=xiL+(q×(xiU-xiL)),j=1,2,…,HMS,
where qis a random number with uniform distribution in [0,1].Step 3 (new harmony improvisation).
This step generates a new harmonyxinew. To do so, a uniform random number r1is generated uniformly in  [0,1]. If r1 is less than HMCR, xinewis generated by memory consideration and otherwise, xinew is achieved by a random selection. As an example, an HMCR of 0.75 designates that the HS algorithm will choose the decision variable value from the historically stored values in the HM with the probability of 75% or from the entire possible range with a 25% probability. If xinewis produced by the memory consideration, then it will undergo a pitch adjustment. The pitch adjustment rule is defined as
(2)xinew=xinew±(r×bw),
where r is a uniform random number in [0,1].Step 4 (HMrefreshing).
The HM is updated after generation ofxinew. If the fitness of the improvised harmony vector xnew=(x1new,x2new,…,xNnew)is better than that of the worst harmony, the worst harmony in the HM will be replaced with xnew and becomes a new member of the HM.Step 5 (stop criterion).
Thenew harmony improvisation and HMrefreshing steps are repeated until the maximum number of improvisations, K, is met.


## 2.2. Improved Harmony Search Algorithm

After fundamental presentation of the HS in 2001, Mahdavi et al. proposed an improved version of the HSA, called improved harmony search (IHS) algorithm later in 2007, [16]. The key modifications of this improvement are regarding PAR and bw, which are updated dynamically as
(3)PAR(k)=PARmin+(PARmax-PARminK)k,bw(k)=bwmaxexp(ln(bwmin/bwmax)K)k,
where k and K are current number of improvisations and maximum number of improvisations, respectively. The key property of IHS is its approach for generating of new solution vectors that enhances accuracy and convergence rate of harmony search.The key difference between IHS and traditional HS method is in the way of adjusting PAR and bw. To improve the performance of the HS algorithm and eliminate the drawbacks lies with fixed values of PAR and bw, IHS algorithm uses variables PAR and bw in improvisation step. The traditional HS algorithm employs a fixed value of PAR and bw for specific purposes. In the HS method PAR and bw values are adjusted in initialization step and are fixed throughout the algorithm. These parameters are of great importance in optimum adjustment of optimized solution vectors and can be potentially useful in adjusting convergence rate of algorithm to optimal solution. Therefore, fine adjustment of these parameters is of great interest [14]. Combination of small PAR and large bw values results in low performance of the algorithm as well as more number of iterations to find optimum solution. Small values of bw in the final generations can adjust tuning of solution vectors. However, in beginning generations bw must have a large value to in order to have a rise in diversity of solution vectors. On the other side, large PAR values in combination with small bw values mostly result in best solutions in final generations, in which algorithm converged to optimal solution vector [14].


## 2.3. Novel Global Harmony Search Algorithm

In 2010, Zou et al. proposed the NGHS algorithm. In this approach, a genetic mutation probabilitypmis considered, which modifies the new harmony improvisation step of the HS such that the new harmony mimics the global best harmony in the HM. In fact, it works instead of the HMCR and PAR as in Pseudocode 1. In this procedure, the terms “best” and “worst” are the indexes of the global best harmony and the worst harmony in HM, respectively. The parameters r and rand()are all uniformly random generated numbers in  [0,1]. After improvisation, the NGHS replaces the worst harmony xworst in HM with the new harmony xnew even if xnew is worse than xworst [14].Pseudocode 1:New harmony vector generation procedure of NGHS in pseudocode.
Initialize New Harmony Vector Generation
For each i∈[1,N]
stepi=|xibest-xiwrost|
xinew=xibest±r×stepi
If  U(0,1)≤pm
xinew=xiL+∥r∥×(xiU-xiL), where  r~U(0,1)
End
End
End New Harmony Vector Generation


## 3. OFDM System and PAPR Formulation

The OFDM input data block is denoted as the vector[X0,X1,…,XN-1], where N is number of subcarriers. Each symbol in X is one subcarrier of {f0,f1,….,fN-1}. These subcarriers are orthogonal and independently modulated using quadrature phase-shift keying (QPSK) or quadrature amplitude modulation (QAM), that is, fn=n/NT for n=0,1,…,N-1, where T is the duration of a symbol  Xnin  X. The complex envelope of the transmitted OFDM signal in one symbol period is given by
(4)x(t)=1N∑n=0N-1Xn·ej2πfnt,0≤t≤NT.However, most systems use discrete time signals in which the OFDM signal in expressed as(5)x(k)=1N∑n=0N-1Xn·ej2πnk/NL,k=0,1,…,NL-1,
where Lis the oversampled factor. To capture the peaks, it is shown in [1] that the oversampled factor L≥4is sufficient to get accurate PAPR results. The PAPR of the transmitted signal, x(k), in (2) is defined as
(6)max|x(t)|2E[|x(t)|2],k=0,1,…,NL-1,
where E[·]is the expected value operator.It is known that the complementary cumulative distribution function (CCDF) of PAPR can be used to estimate the bounds for the minimum number of redundancy bits required to identify the PAPR sequences and evaluate the performance of any PAPR reduction schemes. The CCDF of the PAPR denotes the probability that the PAPR of a data block exceeds a given threshold and is denoted as(7)PAPR>PAPR0,
where PAPR0 is considered as the PAPR threshold.


## 4. NGHS-PTS Approach

The PTS is one of the most significant techniques due its worthy performance in terms of PAPR reduction [17]. The idea is to generate several alternative OFDM signals by multiplying every original data sub-block with different phase rotation vectors. In the next step, the generated signal based on the minimum PAPR is selected to be transmitted, and its corresponding phase rotation vectors for subblocks are denoted as optimal phase rotation combination [17]. Therefore, parts of subcarriers are occupied to transmit the optimal phase rotation combination as side information to recover the original data at the receiver [17].The known sub-block partitioning methods for PTS scheme can be classified into three categories [3] which are adjacent partition, interleaved partition, and pseudorandom partition. The PTS technique that uses the pseudorandom partition has better PAPR performance than employing the other two partition methods [9].


### 4.1. Ordinary PTS Technique

In a typical OFDM system, with PTS approach for PAPR reduction, the input data block inXis partitioned into  Mdisjoint subblocks. The subblocks are combined to minimize the PAPR in the time domain, which are represented by the vectorsXm for m=1,2,…,Mas shown in Figure 1 [3]. Therefore, we can have
(8)X=∑m=1MXm,
where  Xm=[Xm,0,Xm,1,…,Xm,N-1]Tfor 1≤m≤M.Figure 1
PTS techniques block diagram.TheL-times oversampled time domain signal of Xmis denoted as  xm=[xm,0,xm,1,…,xm,N-1]T, where xmfor  m=1,2,…,Mis obtained by taking IDFT of length NL on  Xm, concatenated with N(L-1) zeros. These are called the partial transmit sequences. These partial sequences are independently rotated by phase factors  bm=ejθm, where θm∈[0,2π]for  m=1,2,…,M. The set of the phase factor is defined as a vector b=[b1,b2,…,bM]T. The time-domain of OFDM signal after combining is expressed as(9)x′(b)=∑i=1Mbixi,
wherex′(b)=[x1′(b),x2′(b),…,xNL′(b)]T. The PTS technique target is to find an optimal phase weighted combination to minimize the PAPR value. Minimization of PAPR is related to the minimization of
(10)Max|xk′(b)|,0≤k≤NL-1.In general, the selection of phase factors is confined to a set with a finite number of elements to reduce the search complexity. The set of allowed phase factors is written as(11)P={ej2πl/w∣l=0,1,…,W-1},
where W is the number of allowed phase factors. We can fix a phase factor without any performance loss. There are only M-1free variables to be optimized and hence WM-1different phase vectors are searched to find the global optimal phase factor. The search complexity increases exponentially with the number of sub-blocks M.


### 4.2. NGHS in PTS

The minimum PAPR for PTS problem is stated as(12)f(b)=max|x′(b)|2E[|x′(b)|2],
where f(b) must be minimized subject to
(13)b∈{ejφm}M
for  φm∈{2πk/W∣k=0,1,…,W-1}.To minimize (12), the NGHS approach works as follow.Step 1 (parameters initialization).
By consideringf(b)as the objective functions, NL is considered as the number of decision variables and K as the number of possible values for the discrete variables. The lower and upper bands of the discrete variables [biL,biU] are considered as [-1,1] for  i=1,…,NL. The HMS is considered as the number of solution vectors in the HM defined as
(14)HM=[b11b21⋯bNL1b12b22⋯bNL2⋮⋮⋱⋮b1HMSb2HMS⋯bNLHMS].
Each row of HM is a random solution for the optimization problem and then the value of the objective functionf(b)is computed for each harmony vector. The HMCR, PAR, and the maximum number of initialized searches (stopping criterion) are used to improve the solution vector. The HMCR and PAR parameters task is to help the algorithm find global and local enhanced solutions, respectively.Step 2 (new harmony improvisation).
The HM is improvised by generating a new harmony vectorb′=(b1′,b1′,…,bNL′)as in Pseudocode 2. In this procedure, the term binew=biL+∥r∥×(biU-biL), where r~U(0,1) is called the genetic mutation. In NGHS, the original structure of HS is changed by excluding the HMCR parameter and including a mutation probability  pm. The genetic mutation operation with a small probability is carried out for the worst harmony of HM after position updating. Therefore, it can enhance the capacity of escaping from the local optimum for the proposed algorithm. By a careful consideration, we can find that the role of pmis the same as 1-HMCR. Therefore, in this paper HMCR is used to emphasize that the original structure of harmony search is held and the improvisation step becomes as follows. In NGHS, new harmony is inclined to mimic the global best harmony in HM. In our approach, 1-HMCR determines the randomness of new harmony. Therefore, large HMCR results in premature convergence. To maintain the diversity of HM, HMCR must be small. But small HMCR decreases convergence velocity and also results in producing new harmonies which are infeasible.
In this paper, HMCR is adjusted close to one to produce feasible solutions and to have a good exploitation. After some evaluations, the algorithm may reach to a local solution and the adaptive stepstepigoes to zero. At this step, the algorithm is stagnated. Therefore, to prevent the stagnation, we generate a few harmonies randomly and replace them by the worse harmonies in the HM. The number of new random harmonies depends on the problem and the size of the HM. The new random harmonies cause increase of stepiand the algorithm starts new exploration to find a better solution.Pseudocode 2:New harmony vector generation procedure of proposed NGHS-PTS in pseudocode.
Initialize New Harmony Vector Generation Procedure
For each  i∈[1,NL]
If   U(0,1)≤HMCR
stepi=|bibest-biwrost|
binew=bibest±∥r∥×stepi, where    r~U(0,1)
binew=max(biL,min(biU,binew))
else
binew=biL+∥r∥×(biU-biL), where    r~U(0,1)
End
End
End New Harmony Vector Generation ProcedureFurthermore, after improvisation in the NGHS, the worst harmonybiwrostin HM will be replaced with the new harmony bineweven if binewis worse than  biwrost. This replacement is not good and it does not make the algorithm to converge. Therefore, in this paper, the worst harmony   biwrostin HM will be replaced with the new harmony binew if  binew is better than  biwrost.The reasonable design forstepi can guarantee that the algorithm has strong global search ability in the early stage of optimization and has strong local search ability in the late stage of optimization. Dynamically adjusted stepi keeps a balance between the global search and the local search. The genetic mutation operation is carried out for the worst harmony of harmony memory after updating position to prevent the premature convergence of the NGHS.In approaches using improved versions of harmony search such as IHS, the number of parameters is increased which is not good. It should be note that in order to get the optimum point by heuristic algorithms, the parameters of the algorithm must be tuned for the problem at hand. In NGHS the number of parameters is decreased, and our approach does not add any parameters to NGHS. Therefore it can be used for any problem easily.Step 3 (Update HM).
The newly generated harmony vector is evaluated in terms of the objective function value. If the objective function value for the new harmony vector is better than the objective function value for the worst harmony in the HM, then the new harmony is included in the HM and the existing worst harmony is excluded from the HM. In fact, the HM is sorted by the objective function value.Step 4.
Go to step two until termination criterion is satisfied. The current best solution is selected from the HM after the termination criterion is satisfied. This is the solution for the optimization problem formulated.


## 4.1. Ordinary PTS Technique

In a typical OFDM system, with PTS approach for PAPR reduction, the input data block inXis partitioned into  Mdisjoint subblocks. The subblocks are combined to minimize the PAPR in the time domain, which are represented by the vectorsXm for m=1,2,…,Mas shown in Figure 1 [3]. Therefore, we can have
(8)X=∑m=1MXm,
where  Xm=[Xm,0,Xm,1,…,Xm,N-1]Tfor 1≤m≤M.Figure 1
PTS techniques block diagram.TheL-times oversampled time domain signal of Xmis denoted as  xm=[xm,0,xm,1,…,xm,N-1]T, where xmfor  m=1,2,…,Mis obtained by taking IDFT of length NL on  Xm, concatenated with N(L-1) zeros. These are called the partial transmit sequences. These partial sequences are independently rotated by phase factors  bm=ejθm, where θm∈[0,2π]for  m=1,2,…,M. The set of the phase factor is defined as a vector b=[b1,b2,…,bM]T. The time-domain of OFDM signal after combining is expressed as(9)x′(b)=∑i=1Mbixi,
wherex′(b)=[x1′(b),x2′(b),…,xNL′(b)]T. The PTS technique target is to find an optimal phase weighted combination to minimize the PAPR value. Minimization of PAPR is related to the minimization of
(10)Max|xk′(b)|,0≤k≤NL-1.In general, the selection of phase factors is confined to a set with a finite number of elements to reduce the search complexity. The set of allowed phase factors is written as(11)P={ej2πl/w∣l=0,1,…,W-1},
where W is the number of allowed phase factors. We can fix a phase factor without any performance loss. There are only M-1free variables to be optimized and hence WM-1different phase vectors are searched to find the global optimal phase factor. The search complexity increases exponentially with the number of sub-blocks M.


## 4.2. NGHS in PTS

The minimum PAPR for PTS problem is stated as(12)f(b)=max|x′(b)|2E[|x′(b)|2],
where f(b) must be minimized subject to
(13)b∈{ejφm}M
for  φm∈{2πk/W∣k=0,1,…,W-1}.To minimize (12), the NGHS approach works as follow.Step 1 (parameters initialization).
By consideringf(b)as the objective functions, NL is considered as the number of decision variables and K as the number of possible values for the discrete variables. The lower and upper bands of the discrete variables [biL,biU] are considered as [-1,1] for  i=1,…,NL. The HMS is considered as the number of solution vectors in the HM defined as
(14)HM=[b11b21⋯bNL1b12b22⋯bNL2⋮⋮⋱⋮b1HMSb2HMS⋯bNLHMS].
Each row of HM is a random solution for the optimization problem and then the value of the objective functionf(b)is computed for each harmony vector. The HMCR, PAR, and the maximum number of initialized searches (stopping criterion) are used to improve the solution vector. The HMCR and PAR parameters task is to help the algorithm find global and local enhanced solutions, respectively.Step 2 (new harmony improvisation).
The HM is improvised by generating a new harmony vectorb′=(b1′,b1′,…,bNL′)as in Pseudocode 2. In this procedure, the term binew=biL+∥r∥×(biU-biL), where r~U(0,1) is called the genetic mutation. In NGHS, the original structure of HS is changed by excluding the HMCR parameter and including a mutation probability  pm. The genetic mutation operation with a small probability is carried out for the worst harmony of HM after position updating. Therefore, it can enhance the capacity of escaping from the local optimum for the proposed algorithm. By a careful consideration, we can find that the role of pmis the same as 1-HMCR. Therefore, in this paper HMCR is used to emphasize that the original structure of harmony search is held and the improvisation step becomes as follows. In NGHS, new harmony is inclined to mimic the global best harmony in HM. In our approach, 1-HMCR determines the randomness of new harmony. Therefore, large HMCR results in premature convergence. To maintain the diversity of HM, HMCR must be small. But small HMCR decreases convergence velocity and also results in producing new harmonies which are infeasible.
In this paper, HMCR is adjusted close to one to produce feasible solutions and to have a good exploitation. After some evaluations, the algorithm may reach to a local solution and the adaptive stepstepigoes to zero. At this step, the algorithm is stagnated. Therefore, to prevent the stagnation, we generate a few harmonies randomly and replace them by the worse harmonies in the HM. The number of new random harmonies depends on the problem and the size of the HM. The new random harmonies cause increase of stepiand the algorithm starts new exploration to find a better solution.Pseudocode 2:New harmony vector generation procedure of proposed NGHS-PTS in pseudocode.
Initialize New Harmony Vector Generation Procedure
For each  i∈[1,NL]
If   U(0,1)≤HMCR
stepi=|bibest-biwrost|
binew=bibest±∥r∥×stepi, where    r~U(0,1)
binew=max(biL,min(biU,binew))
else
binew=biL+∥r∥×(biU-biL), where    r~U(0,1)
End
End
End New Harmony Vector Generation ProcedureFurthermore, after improvisation in the NGHS, the worst harmonybiwrostin HM will be replaced with the new harmony bineweven if binewis worse than  biwrost. This replacement is not good and it does not make the algorithm to converge. Therefore, in this paper, the worst harmony   biwrostin HM will be replaced with the new harmony binew if  binew is better than  biwrost.The reasonable design forstepi can guarantee that the algorithm has strong global search ability in the early stage of optimization and has strong local search ability in the late stage of optimization. Dynamically adjusted stepi keeps a balance between the global search and the local search. The genetic mutation operation is carried out for the worst harmony of harmony memory after updating position to prevent the premature convergence of the NGHS.In approaches using improved versions of harmony search such as IHS, the number of parameters is increased which is not good. It should be note that in order to get the optimum point by heuristic algorithms, the parameters of the algorithm must be tuned for the problem at hand. In NGHS the number of parameters is decreased, and our approach does not add any parameters to NGHS. Therefore it can be used for any problem easily.Step 3 (Update HM).
The newly generated harmony vector is evaluated in terms of the objective function value. If the objective function value for the new harmony vector is better than the objective function value for the worst harmony in the HM, then the new harmony is included in the HM and the existing worst harmony is excluded from the HM. In fact, the HM is sorted by the objective function value.Step 4.
Go to step two until termination criterion is satisfied. The current best solution is selected from the HM after the termination criterion is satisfied. This is the solution for the optimization problem formulated.


## 5. Simulation Results

In this section, performance of NGHS-PTS versus CE [11], ABC-PTS [12], and HSA-PTS [13] is evaluated. We assume an OFDM system with 256 subcarriers (N=256) with 16-QAM modulation. The number of allowed phase factor is considered as W=2, since by increasing the W similar simulation results can be obtained while the performance will be better [12]. The transmitted signal is oversampled by a factor of 4 (L=4) and 100000 random OFDM symbols are generated to obtain the complementary cumulative density functions (CCDFs) of PAPR. The CCDF denotes the probability that the PAPR of a data block exceeds a given threshold and is expressed as
(15)CCDF(PAPR0)=Pr{PAPR>PAPR0}.The HMS is selected to be 20 and HMCR and the number of evaluations is set to 0.9 and 1000, respectively. In the simulations, parameters are set by trial and error for optimum algorithm performance.Performances of the under study algorithms are compared for different iteration numbers:It=20 and It=40 in Figure 2. When Pr(PAPR>PAPR0)=10-3, the PAPR of the original OFDM is 11.30 dB. The PAPR by the IPTS in [5] is 7.95 dB. The PAPR by the ABC-PTSs with iteration number 20 and 40 is approximately 6.847 dB and 6.717 dB and also the HSA-PTS provides approximately 6.828 dB and 6.66 dB for the iteration number 20 and 40 respectively. The GA-PTS with W=60, which is reported as the best condition for the GA approach in [10], is not better than above approaches except for the original one with the PAPR of about 8.75 dB. This is while the NGHS-PTS provides approximately 6.526 dB and 6.412 dB PAPRs for the iteration number 20 and 40, respectively. A closer look at the performance of algorithms for Pr(PAPR>PAPR0)=10-4 is presented in Figure 3. As it is demonstrated that the proposed NGHS algorithm with iteration number of could achieve OPTS for less than 0.1 dB of PAPR.Figure 2
PAPR reduction comparison for iteration numbers 20 and 40.Figure 3
Zoomed version of Figure2 around CCDF=10-4.To study performance of the approaches versus different number of iterations/generations, a simulation with 100 experiments is performed. This study compares PAPR convergence performance for an OFDM symbol, whereM=16  subblocks are generated by pseudorandom partition. Figure 4 shows simulation results of the under study methods on the mean of the best cost function values. As it is depicted in this figure, the NGHS-PTS has the least mean of best cost function value for all iterations. This is an advantage of this method versus other evolutionary approaches due to its less running cost.Figure 4
Mean of best cost function values.


## 6. Conclusion

The PAPR reduction problem for OFDM signals has received a great deal of attention recently, both in academia and industry. This issue attracted more attention after development of smart grid systems and the need for reliable multiuser communication. In the proposed NGHS-PTS algorithm, harmony search is performed to obtain better phase factor. Computer simulation shows that the algorithm offers improved performance in terms of complementary cumulative density function (CCDF) while reducing PAPR effectively. Compared to the existing PAPR reduction methods, the NGHS-PTS algorithm can get better PAPR reduction due to its simple structure and few parameters to adjust. Performance study of the proposed method demonstrates its feasibility and performance.



---

*Source: 940849-2012-12-06.xml*