# ارزیابی عملکرد هماهنگی الگوریتم جستجوی پیشرفته برای بهینه سازی عددی:جستجوی ملودی (MS)

کد مقاله | سال انتشار | مقاله انگلیسی | ترجمه فارسی | تعداد کلمات |
---|---|---|---|---|

10552 | 2013 | 21 صفحه PDF | سفارش دهید | 15890 کلمه |

**Publisher :** Elsevier - Science Direct (الزویر - ساینس دایرکت)

**Journal :** Engineering Applications of Artificial Intelligence, Volume 26, Issue 4, April 2013, Pages 1301–1321

#### چکیده انگلیسی

Melody Search (MS) Algorithm as an innovative improved version of Harmony Search optimization method, with a novel Alternative Improvisation Procedure (AIP) is presented in this paper. MS algorithm mimics performance processes of the group improvisation for finding the best succession of pitches within a melody. Utilizing different player memories and their interactive process, enhances the algorithm efficiency compared to the basic HS, while the possible range of variables can be varied going through the algorithm iterations. Moreover, applying the new improvisation scheme (AIP) makes algorithm more capable in optimizing shifted and rotated unimodal and multimodal problems than the basic MS. In order to demonstrate the performance of the proposed algorithm, it is successfully applied to various benchmark optimization problems. Numerical results reveal that the proposed algorithm is capable of finding better solutions when compared with well-known HS, IHS, GHS, SGHS, NGHS and basic MS algorithms. The strength of the new meta-heuristic algorithm is that the superiority of the algorithm over other compared methods increases when the dimensionality of the problem or the entire feasible range of the solution space increases.

#### مقدمه انگلیسی

Nature is inspiring researchers to develop effective and powerful optimization methods (Karaboga and Akay, 2009). In the past, many optimization methods were adopted to solve various real-world optimization problems which were constrained by the complexities of non-linearity in the model formulation and affected by the increase in the number of constraints and decision variables (Kumar and Reddy, 2006). Nowadays evolutionary stochastic search methods are very popular for solving optimization problems in the research arena of computational intelligence (Karaboga and Basturk, 2007). The routine feature of meta-heuristic algorithms is the point that they often employ combinations of rules and randomness to imitate natural processes (Lee and Geem, 2005). Although the algorithms do not always ensure the global optimum solution, quite good results in a reasonable computation time are achieved. This is why many researchers have been eager to develop newer techniques and improve existing methods over the past years (Kumar and Reddy, 2006). Many meta-heuristic algorithms, such as genetic algorithm, particle swarm optimization, tabu search, ant colony optimization, bees' algorithm, artificial immune system and simulated annealing have been extensively employed for various science and engineering problems. One of the major disadvantages of these algorithms is the fact that most of the meta-heuristic algorithms are successful for solving some certain class of problems. Furthermore, in some cases, although the algorithms show superior performance on low dimensional problems, they cannot preserve their superior performance on high dimensional cases (Karaboga and Akay, 2009). The concepts of Genetic Algorithms (GAs) were originally explained by Holland (1975) and further developed by Goldberg (1989). GA-based algorithms are global search methods found on concepts from natural genetics and the Darwinian survival-of-the-fittest code. During the past two decades, GA has been studied extensively by many researchers to solve difficult and complicated real-world and engineering optimization problems. GAs are generally capable in finding good solutions in reasonable amounts of time. However, applying to harder and bigger problems increases the time required to find adequate solutions. Several papers, book chapters, special issues and books have surveyed GAs literature (e.g. Cheng et al., 1999, Coello et al., 2007 and Nicklow et al., 2010). Tabu Search (TS) as a gradient-descent search method with memory was originally suggested by Glover (1977). Details about tabu search can also be found in Glover, 1989 and Glover, 1990, Hertz et al. (1997) and Glover and Laguna (1997). In the TS method the solution space is explored by moving from a solution to the best solution in a subset of its neighborhood trough different iterations while, to avoid cycling, recently explored solutions are temporarily declared tabu or forbidden. Many different models based on TS have been developed to improve the efficiency of the algorithm and applied to solve optimization problems (e.g. Griinert, 2002, Glover and Kochenberger, 2003 and Gendreau, 2002). The Simulated Annealing (SA) algorithm has been modeled on the annealing of solids in nature. The SA initially, proposed by Kirkpatrick et al. (1983) as a method/tool for solving single objective combinatorial problems. However, recently there are many reports of SA applications in different fields of engineering problems containing continuous and discrete spaces (Suman and Kumar, 2006). An important approach which is based on ants behavior, called Ant Colony Optimization (ACO), proposed by Dorigo et al. (1991). The approach has been studied by many researchers, while several new variants have been proposed and applied to solve optimization problems in different areas. Numerous publications related with the applications of ACO models have been presented to the literature (Blum, 2005, Dorigo and Blum, 2005, Pedemonte et al., 2011 and Chandra Mohan and Baskaran, 2012). Inspired by the social behavior of the birds flocking or fish schooling, Kennedy and Eberhat (1995) introduced an evolutionary computational method named Particle Swarm Optimization (PSO) algorithm. PSO, similar to the other evolutionary computational algorithms like GA, is a population-based interactive method. As the most important swarm intelligence paradigms (Kennedy et al., 2001), PSO is popular and useful to solve various kinds of real-world optimization problems (Eberhart and Shi, 2001); however, a number of PSO variants have been developed to overcome some weaknesses which have restricted wider applications of the standard-PSO. Several survey papers regarding the PSO variants applications have been presented (Eberhart and Shi, 2004, Reyes-Sierra and Coello, 2006 and AlRashidi and El-Hawary, 2009). Artificial Bee Colony (ABC) presented by Karaboga (2005) inspired by the intelligent behavior of honey bees for seeking a quality food source in nature. The algorithm was originally proposed for solving numerical problems; however, the success of the algorithm as a single-objective optimizer has motivated researchers to extend its application to other study areas (Karaboga et al., 2012). Recently, a new meta-heuristic technique, namely Harmony Search (HS) algorithm has been proposed by Geem et al. (2001), which simulates the improvisation process of musicians. In HS algorithm, solution vectors correspond to the harmony in music and the local and global search schemes correspond to the musician's improvisations (Lee and Geem, 2005). HS is a stochastic search technique without the need of derivative information, and with reduced memory requirement. In comparison with other meta-heuristic methods, HS is computationally effective and easy to implement for solving various kinds of engineering optimization problems (Mahdavi et al., 2007 and Omran and Mahdavi, 2008). The algorithm is capable for identifying the high performance regions of solution space in a reasonable run time; however, it is not successful in performing local search in numerical optimization applications (Mahdavi et al., 2007). Moreover, in the case of problems with large space of decision variables, the likelihood of obtaining the global optimum is considerably reduced. Karaboga and Akay (2009) presented a comparative investigation of the performance of basic Harmony Search, Bees algorithms, and Artificial Bee Colony algorithm. It was concluded that HS algorithm is less efficient than the ABC in solving different optimization problems. The initial development of HS Algorithm was conducted by Geem (2000), during his Ph.D. studies. Design of water distribution networks was the main aim, while the study covered benchmark optimization, parameter estimation, and the traveling salesman problem (TSP) (Ingram and Zhang, 2009). Since then, a variety of HS models have been adopted to diverse field of problems, such as structural design, Sudoku puzzles, musical composition, medical imaging, heat exchanger design, course timetabling, web page clustering, robotics, water network design, dam scheduling, vehicle routing, energy system dispatch, cell phone network, satellite heat pipe design, and medical physics. There are several attempts to improve the performance of basic HS algorithm for enhancing solution accuracy and convergence rate, like Improved Harmony Search algorithm (IHS) (Mahdavi et al., 2007), global best Harmony Search algorithm (GHS) (Omran and Mahdavi, 2008), self-adaptive global best harmony search algorithm (SGHS) (Pan et al., 2010b), novel global harmony search (NGHS) (Zou et al., 2010). All improvements are categorized into two classes by Alia and Mandava (2011); the first one is improvement of HS in terms of parameter setting, and the second one is improvement in terms of hybridizing HS components with other meta-heuristic algorithms. Ingram and Zhang (2009) have classified various modifications of HS in seven categories and briefly explained each category. Geem et al. (2005), proposed a multiple pitch adjusting rate (PAR) strategy in solving the so called Generalized Oriented Problem. Using three PAR's for moving rates to the nearest, second nearest, and third nearest cities was proposed in their study. Mahdavi et al. (2007) developed an Improved HS algorithm, denoted as IHS, by introducing a method to dynamically adjust the algorithm computational parameters (i.e. PAR and bw). Their algorithm was applied to solve four engineering and four mathematical optimization problems. According to their comparative investigation between obtained results and those from other techniques in the literature, they remarked that the algorithm can find better solutions. Omran and Mahdavi (2008) presented a Global-best Harmony Search algorithm, (GHS) GHS algorithm, by borrowing the concepts from swarm intelligence. They studied the sensitivity of the HS parameters and compared the performance of HS, IHS and GHS on ten continuous optimization functions and six integer programming problems. Both IHS and GHS algorithms could find better solutions, compared with the basic HS algorithm. Coelho and Mariani (2009), proposed an improved harmony search (IHS) algorithm based on exponential distribution, for solving Economic Dispatch Problems, which updated the PAR parameter dynamically. The application of HS and IHS for solving thirteen thermal units of generation with the valve-point effects was reported there. Numerical results show that IHS the algorithm converged to more reasonable results compared with basic HS algorithm. Another new improvement to HS, named (DHS) which was inspired by mutation operator of Differential Evolution (DE) is proposed by Chakraborty et al. (2009). They replaced the pitch adjustment operation in basic HS with a mutation strategy borrowed from DE algorithm. Inspired by the local version of the particle swarm optimization algorithm, Pan et al. (2010a) proposed the local-best harmony search algorithm with dynamic subpopulations (DLHS) for solving the bound-constrained continuous optimization problems. In DLHS method the Harmony Memory (HM) is divided into many sub-harmony memories. New harmonies are independently generated in these small-sized sub-harmony memories, which are regrouped frequently by using a regrouping schedule. A recent variant of HS algorithm was proposed by Wang, Huang (2010). The model totally replaces bandwidth parameter (bw) parameter with a new concept based on using the maximal and minimal values in HM. While the search process is going on, PAR values are dynamically adapted using the modification proposed by Mahdavi et al. (2007). Kattan et al. (2010), applied HS for feed-forward artificial neural networks (ANN) training. They proposed a new stopping criterion that is based on the best-to-worst (BtW) harmony ratio in the current harmony memory, and applied the ratio within the existing improved version of HS (proposed by Mahdavi et al. 2007). They remarked that the modification is more proper for ANN training since parameters and termination depend on the quality of the obtained solutions (Alia and Mandava, 2011). A self-adaptive global best harmony search algorithm denoted as (SGHS), was proposed by Pan et al. (2010a) for solving continuous optimization problems. In SGHS, the algorithm parameters, Harmony Memory Considering Rate (HMCR) and PAR, are self-adaptive by a learning mechanism and bw bandwidth parameter (bw), is dynamically decreased with increasing the generation number. Numerical experiments revealed that SGHS algorithm is more effective in finding better solutions than HS, IHS and GHS algorithms. Zou et al. (2010) developed a novel global harmony search method, called NGHS, for solving unconstrained problems. A novel location updating strategy is designed which makes the algorithm easier to converge. The experimental results showed better performance for NGHS algorithm for solving most of unconstrained problems compared with other harmony search methods (i.e. HS, IHS, and SGHS). For enhancing the performance of HS, Al-Betar et al. (2010) proposed eight procedures instead of using one PAR value, to solve the Course Timetabling Problem, which were controlled by their certain PAR value ranges. There are several hybrid models of HS with other meta-heuristic methods in the literature. Alia and Mandava (2011) categorized this hybridization into two classes. The first class consists of models which are the integration of some components of the other meta-heuristic algorithms within HS, while the second class consists of methods which integrate some HS components within other meta-heuristic algorithms. More recently, inspired by basic concepts applied in HS algorithm, an innovative improved version of HS algorithm is presented by authors (Ashrafi and Dariane 2011). The algorithm named Melody Search (MS) is designed in accordance with the concept of melody instead of harmony. This algorithm is based on musical performance processes and interactive relations occurred between members of a group of musicians attempting to find better and better series of pitches within a melodic line. In such a group, the music players can improvise the melody differently and lead each other to achieve the best subsequence of pitches. Furthermore, a novel improvisation scheme is introduced and applied in this study through which the efficiency of the algorithm for solving shifted and rotated optimization problems would be increased. In order to demonstrate the performance of the proposed algorithm, MS with the novel improvisation scheme is applied to various benchmark problems and the results are compared with those of the basic HS, IHS, GHS, SGHS, NGHS and basic MS algorithms. The remaining of this paper is organized as follows: basic concepts of HS algorithm are explained in Section 2. Some variants of HS algorithms including IHS, GHS, SGHS and NGHS are briefly described in 3 and 4. describes the proposed MS algorithm, and the basic differences between HS and MS methods. Some experimental studies regarding numerical benchmark problems, along with their analysis and discussions are summarized in Section 5. Finally Section 6 provides a brief summary and conclusion.

#### نتیجه گیری انگلیسی

This paper introduced a novel improved version of Harmony Search optimization algorithm called Melody Search (MS). Principles of the new algorithm were described and similarities and differences were explained comparing with basic HS. Moreover, a novel alternative improvisation procedure (AIP) was proposed in this study. In order to demonstrate the performance of MS algorithm with the new improvisation scheme (AIP_MS), it was tested using eighteen high dimensional numerical well-known functions. The obtained results were compared with those of basic HS, IHS, GHS, SGHS, NGHS and basic MS algorithms. Based on the experimental results, it is concluded that the proposed algorithm is more effective in finding better solutions comparing with the aforementioned algorithms. Furthermore, the main advantage of AIP_MS algorithm is that the algorithm can better preserve the accuracy of the results comparing with other described methods in the case that the dimensionality of the problem or the entire feasible range of the search space is increased. Further research on issues, such as the investigation of the control parameters' effects on the performance of MS algorithm and the convergence speed of the algorithm in different conditions, is sought in our future research.