In this paper, β-Hill Climbing algorithm, the recent local search-based meta-heuristic, are tailored for Sudoku puzzle. β-Hill Climbing algorithm is a new extended version of hill climbing algorithm which has the capability to escape the local optima using a stochastic operator called β-operator. The Sudoku puzzle is a popular game formulated as an optimization problem to come up with exact solution. Some Sudoku puzzle examples have been applied for evaluation process. The parameters of the β-Hill Climbing is also studied to show the best configuration used for this game. β-Hill Climbing in its best parameter configuration is able to find solution for Sudoku puzzle in 19 iterations and 2 seconds.
In this paper, alternative selection mechanisms in the bat-inspired algorithm for global optimization problems are studied. The bat-inspired algorithm is a recent swarm-based intelligent system which mimics the echolocation system of micro-bats. In the bat-inspired algorithm, the bats randomly fly around the best bat locations found during the search so as to improve their hunting of prey. In practice, one bat location from a set of best bat locations is selected. Thereafter, that best bat location is used by local search with a random walk strategy to inform other bats about the prey location. This selection mechanism can be improved using other natural selection mechanisms adopted from other advanced algorithms like Genetic Algorithm. Therefore, six selection mechanisms are studied to choose the best bat location: global-best, tournament, proportional, linear rank, exponential rank, and random. Consequently, six versions of bat-inspired algorithm are proposed and studied which are global-best bat-inspired algorithm (GBA), tournament bat-inspired algorithm (TBA), proportional bat-inspired algorithm (PBA), linear rank bat-inspired algorithm (LBA), exponential rank bat-inspired algorithm (EBA), and random bat-inspired algorithm (RBA). Using two sets of global optimization functions, the bat-inspired versions are evaluated and the sensitivity analyses of each version to its parameters studied. Our results suggest that there are positive effects of the selection mechanisms on the performance of the classical bat-inspired algorithm which is GBA. For comparative evaluation, eighteen methods are selected using 25 IEEE-CEC2005 functions. The results show that the bat-inspired versions with various selection schemes observing the “survival-of-the-fittest” principle are largely competitive to established methods.
The multi-reservoir systems optimization problem requires defining a set of rules to recognize the water amount stored and released in accordance with the system constraints. Traditional methods are not suitable for complex multi-reservoir systems with high dimensionality. Recently, metaheuristic-based algorithms such as evolutionary algorithms and local search-based algorithms are successfully used to solve the multi-reservoir systems. β-hill climbing is a recent metaheuristic local search-based algorithm. In this paper, the multi-reservoir systems optimization problem is tackled using β-hill climbing. In order to validate the proposed method, four-reservoir systems used in the literature to evaluate the algorithm are utilized. A comparative evaluation is conducted to evaluate the proposed method against other methods found in the literature. The obtained results show the competitiveness of the proposed algorithm.
β-hill climbing; optimization; multi-reservoir operation; partially and fully constrained; local search-based heuristic method.
Maximum Satisfiability problem is an optimization variant of the Satisfiability problem (SAT) denoted as MAX-SAT. The aim of this problem is to find Boolean variable assignment that maximizes the number of satisfied clauses in the Boolean formula. In case the number of variables per clause is equal or greater than three, then this problem is considered NP-complete. Hence, many researchers have developed techniques to deal with MAX-SAT. In this paper, we investigate the impact of different hybrid versions of binary harmony search (HS) algorithm on solving MAX 3-SAT problem. Therefore, we propose two novel hybrid binary HS algorithms. The first hybridizes Flip heuristic with HS, and the second uses Tabu search combined with Flip heuristic. Furthermore, a distinguished feature of our proposed approaches is using an objective function that is updated dynamically based on the stepwise adaptation of weights (SAW) mechanism to evaluate the MAX-SAT solution using the proposed hybrid versions. The performance of the proposed approaches is evaluated over standard MAX-SAT benchmarks, and the results are compared with six evolutionary algorithms and three stochastic local search algorithms. The obtained results are competitive and show that the proposed novel approaches are effective.
Maximum satisfiability problem; harmony search; local search; 3SAT problem; MAX-SAT problem.
This paper proposes a hybrid harmony search algorithm (HHSA) for solving the highly constrained nurse rostering problem (NRP). The NRP is a combinatorial optimization problem tackled by assigning a set of shifts to a set of nurses; each has specific skills and work contract, to a predefined rostering period according to a set of constraints. The harmony search is a metaheuristic approach, where the metaheuristics are the most successful methods for tackling this problem. In HHSA, the harmony search algorithm is hybridized with the hill climbing optimizer to empower its exploitation capability. Furthermore, the memory consideration operator of the HHSA is modified by replacing the random selection scheme with the global-best concept of particle swarm optimization to accelerate its convergence rate. The standard dataset published in the first international nurse rostering competition 2010 (INRC2010) was utilized to evaluate the proposed HHSA. Several convergence scenarios have been employed to study the effects of the two HHSA modifications. Finally, a comparative evaluation against twelve other methods that worked on the INRC2010 dataset is carried out. The experimental results show that the proposed method achieved five new best results, and 33 best published results out of 69 instances as achieved by other comparative methods.
Metaheuristic; Harmony search; Nurse rostering; Hill climbing; Particle swarm optimization.
In this paper, the update process of harmony search (HS) algorithm is modified to improve its concept of diversity. The update process in HS is based on a greedy mechanism in which the new harmony solution, created in each generation, replaces the worst individual in the population, if better. This greedy process could be improved with other updates mechanisms in order to control the diversity perfectly. Three versions of HS have been proposed: (1) Natural Proportional HS ; (2) Natural Tournament HS; (3) Natural Rank HS. These three HS versions employed the natural selection principle of the ‘‘survival of the fittest’’. Instead of replacing the worst individual in population, any individual can be replaced based on certain criteria. Four versions of economic loading dispatch (ELD) problems with valve point have been used to measure the effect of the newly proposed HS versions. The results show that the new HS versions are very promising for ELD domain. This claim is proved based on the comparative evaluation process where the new HS versions are able to excel the state-of-the-art methods in almost ELD problems used.
Economic dispatch; Valve point; Harmony search algorithm; Natural update process; Optimization
Krill Herd (KH) algorithm is a class of nature-inspired algorithm, which simulates the herding behavior of krill individuals. It has been successfully utilized to tackle many optimization problems in different domains and found to be very efficient. As a result, the studies has expanded significantly in the last 3 years. This paper presents the extensive (not exhaustive) review of KH algorithm in the area of applications, modifications, and hybridizations across these fields. The description of how KH algorithm was used in the approaches for solving these kinds of problems and further research directions are also discussed.
Krill Herd algorithm; Swarm intelligence algorithms; Nature-inspired algorithms; Metaheuristics
For decades, image enhancement has been considered one of the most important aspects in computer science because of its influence on a number of fields including but not limited to medical, security, banking and financial sectors. In this paper, a new gray level image (edge preserving) enhancement method called the harmony search algorithm (HSA) is proposed. HSA is a recently introduced population-based algorithm stemmed by the musical improvisation process when a group of musicians play the pitches of their instruments seeking for pleasing harmony. Tremendous successful stories of HSA application to a wide variety of optimization problems have been passed on at a large scale. In order to evaluate the proposed HSA-based image enhancement method, 14 standard images from the literature are used. For comparative evaluation, the results of the 14 enhanced image produced by HSA are compared with two classical image enhancement methods (i.e., Histogram Equalization algorithm and Image Adjacent algorithm) and two advanced methods (i.e., genetic algorithm and particle swarm optimization). It is note worthy that all these methods employed the same criteria ( number of edges in an gray scaled images, summation intensity of edges detected using a Sobel filter and entropy measure) in order to evaluate their results. The HSA almost achieves the best results in comparison with the other classical and advanced image enhancement algorithms. Due to such achievements, we believe that the proposed method is very promising and has a potential to provide a substantial addition to the image enhancement domain.
Harmony Search; Image enhancement; Optimization; Intelligent Agent.
Recently, due to the huge growth of web pages, social media and modern applications, text clustering technique has emerged as a significant task to deal with a huge amount of text documents. Some web pages are easily browsed and tidily presented via applying the clustering technique in order to partition the documents into a subset of homogeneous clusters. In this paper, two novel text clustering algorithms based on krill herd (KH) algorithm are proposed to improve the web text documents clustering. In the first method, the basic KH algorithm with all its operators is utilized while in the second method, the genetic operators in the basic KH algorithm are neglected. The performance of the proposed KH algorithms is analyzed and compared with the k-mean algorithm. The experiments were conducted using four standard benchmark text datasets. The results showed that the proposed KH algorithms outperformed the k-mean algorithm in term of clusters quality that is evaluated using two common clustering measures, namely, Purity and Entropy.
krill herd algorithm; web text document clustering; evolutionary computing; global optimization.
This paper proposes a tournament-based harmony search (THS) algorithm for economic load dispatch (ELD) problem. The THS is an efficient modified version of the harmony search (HS) algorithm where the random selection process in the memory consideration operator is replaced by the tournament selection process to activate the natural selection of the survival-of-the-fittest principle and thus improve the convergence properties of HS. The performance THS is evaluated with ELD problem using five different test systems: 3-units generator system; two versions of 13-units generator system; 40-units generator system; and large-scaled 80-units generator system. The effect of tournament size (t) on the performance of THS is studied. A comparative evaluation between THS and other existing methods reported in the literature are carried out. The simulation results show that the THS algorithm is capable of achieving better quality solutions than many of the well-popular optimization methods.
Economic load dispatch
Harmony search algorithm
The nurse rostering problem (NRP) is a combinatorial optimization problem tackled by assigning a set of shifts to a set of nurses, each has specific skills and work contract, to a predefined rostering period according to a set constraints. The metaheuristics are the most successful methods for tackling this problem. This paper proposes a metaheuristic technique called a hybrid artificial bee colony (HABC) for NRP. In HABC, the process of the employed bee operator is replaced with the hill climbing optimizer (HCO) to empower its exploitation capability and the usage of HCO is controlled by hill climbing rate (HCR) parameter. The performance of the proposed HABC is evaluated using the standard dataset published in the first international nurse rostering competition 2010 (INRC2010). This dataset consists of 69 instances which reflect this problem in many real-world cases that are varied in size and complexity. The experimental results of studying the effect of HCO using different value of HCR show that the HCO has a great impact on the performance of HABC. In addition, a comparative evaluation of HABC is carried out against other eleven methods that worked on INRC2010 dataset. The comparative results show that the proposed algorithm achieved two new best results for two problem instances, 35 best published results out of 69 instances as achieved by other comparative methods, and comparable results in the remaining instances of INRC2010 dataset.
Artificial bee colony
Nurse rostering problem
Harmony search (HS) algorithm is a recent meta-heuristic algorithm that mimics the musical improvisation concepts. This algorithm has been widely used for solving optimization problems. Moreover, many modifications in this algorithm have been carried out in order to improve the performance of the search. Island model is a structured population mechanism used in evolutionary algorithms to preserve the diversity of the population and thus improve the performance. In this paper, the island model concepts are embedded into the main framework of HS algorithm to improve its convergence properties where the new method is refer to as island HS (iHS). In the proposed method, the individuals in population are distributed into separate sub-population named (islands). Then the breeding loop is separately involved in each island. After specific generations, a number of individuals run an exchange through a process called migration. This process is performed to keep the diversity of population and to allow islands to interact with each other. The experimental result using a set of benchmark function shows that the island model context is crucial to the performance of iHS. Finally the sensitivity analysis and the comparative study for iHS prove the efficiency of the island model.
Artificial bee colony algorithm(ABC) is proposed as a new nature-inspired algorithm which has been successfully utilized to tackle numerous class of optimization problems belongs to the category of swarm intelligence optimization algorithms. The major focus of this paper is to show that ABC could be used to generate good solutions when adapted to tackle the nurse rostering problem (NRP). In the proposed ABC for the NRP, the solution methods is divided into two phases. The first uses a heuristic ordering strategy to generate feasible solutions while the second phase employs the usage of ABC algorithm in which its operators are utilized to enhance the feasible solutions to their optimality. The proposed algorithm is tested on a set of 69 problem instances of the dataset introduced by the First International Nurse Rostering Competition 2010 (INRC2010). The results produced by the proposed algorithm are very promising when compared with some existing techniques that worked on the same dataset. Further investigation is still necessary for further improvement of the proposed algorithm.
Artificial Bee Colony Algorithm
Swarm Intelligence Method
This article presents a Hybrid Artificial Bee Colony (HABC) for uncapacitated examination timetabling. The ABC algorithm is a recent metaheuristic population-based algorithm that belongs to the Swarm Intelligence technique. Examination timetabling is a hard combinatorial optimization problem of assigning examinations to timeslots based on the given hard and soft constraints. The proposed hybridization comes in two phases: the first phase hybridized a simple local search technique as a local refinement process within the employed bee operator of the original ABC, while the second phase involves the replacement of the scout bee operator with the random consideration concept of harmony search algorithm. The former is to empower the exploitation capability of ABC, whereas the latter is used to control the diversity of the solution search space. The HABC is evaluated using a benchmark dataset defined by Carter, including 12 problem instances. The results show that the HABC is better than exiting ABC techniques and competes well with other techniques from the literature.
Artificial Bee Colony algorithm
examination timetabling problem
University course timetabling is concerned with assigning a set of courses to a set of rooms and timeslots according to a set of constraints. This problem has been tackled using metaheuristics techniques. Artificial bee colony (ABC) algorithm has been successfully used for tackling uncapaciated examination and course timetabling problems. In this paper, a novel hybrid ABC algorithm based on the integrated technique is proposed for tackling the university course timetabling problem. First of all, initial feasible solutions are generated using the combination of saturation degree (SD) and backtracking algorithm (BA). Secondly, a hill climbing optimizer is embedded within the employed bee operator to enhance the local exploitation ability of the original ABC algorithm while tackling the problem. Hill climbing iteratively navigates the search space of each population member in order to reach a local optima. The proposed hybrid ABC technique is evaluated using the dataset established by Socha including five small, five medium and one large problem instances. Empirical results on these problem instances validate the effectiveness and efficiency of the proposed algorithm. Our work also shows that a well-designed hybrid technique is a competitive alternative for addressing the university course timetabling problem.
Artificial bee colony
Hyper-heuristic (HH) is a higher level heuristic to choose from a set of heuristics applicable for the problem on hand. In this paper, a Harmony Search-based Hyper-heuristic (HSHH) approach is tested in solving nurse rostering problems (NRP). NRP is a complex scheduling problem of assigning given shifts to a given nurses. We test the proposed method by using the First International Nurse Rostering Competition 2010 (INRC2010) dataset. Experimentally, the HSHH approach achieved comparable results with the comparative methods in the literature.
Nurse Rostering Problems
Harmony Search ALgorithm
In this paper, a Harmony Search-based Hyper-heuristic (HSHH) approach is proposed for tackling examination timetabling problems. In this approach, the harmony search algorithm will operate as a high level of abstraction which intelligently evolves a sequence of low level heuristics. This sequence is a combination of improvement heuristics which consist of neighborhood structure strategies. The proposed approach is tested using the examination timetabling tracks in Second International Timetabling Competition (ITC-2007) benchmarks. Experimentally, the HSHH approach can achieve comparable results with the comparative methods in the literature.
The selection methods of population-based metaheuristics provide the driving force to generate good solutions. These selection methods select the individuals with a higher fitness to be members of the population in the next iteration correspond to the natural rule of Darwin’s principle survival-of-the-fittest. Harmony search algorithm is a population-based metaheuristic, which mimicking the musical improvisation process where a group of musicians play the pitches of their musical instruments seeking for a pleasing harmony. It improvises the new harmony based on three rules: memory consideration, random consideration, and pitch adjustment. In this paper, we investigate the replacement of the original random selection of memory consideration with a set of selection methods in order to speed-up the convergence. These selection methods include tournament, proportional, and liner rank of Genetic Algorithm, and Global-best of Particle Swarm Optimization. The proposed harmony search with the different memory consideration selection methods evaluated using standard dataset published in the first International Nurse Rostering Competition INRC2010. Nurse rostering problem is a combinatorial optimization problem tackled by assigning a set of nurses with different skills to a set of shifts over predefined scheduling period. Experimentally, the tournament memory consideration selection method achieved the best rate of convergence as well as the best results in comparison with the other memory consideration selection methods.
Structured population in evolutionary algorithms (EAs) is an important research track where an individual only interacts with its neighboring individuals in the breeding step. The main rationale behind this is to provide a high level of diversity to overcome the genetic drift. Cellular automata concepts have been embedded to the process of EA in order to provide a decentralized method in order to preserve the population structure. Harmony search (HS) is a recent EA that considers the whole individuals in the breeding step. In this paper, the cellular automata concepts are embedded into the HS algorithm to come up with a new version called cellular harmony search (cHS). In cHS, the population is arranged as a two-dimensional toroidal grid, where each individual in the grid is a cell and only interacts with its neighbors. The memory consideration and population update are modified according to cellular EA theory. The experimental results using benchmark functions show that embedding the cellular automata concepts with HS processes directly affects the performance. Finally, a parameter sensitivity analysis of the cHS variation is analyzed and a comparative evaluation shows the success of cHS.
In this paper, the Harmony Search Algorithm (HSA) is proposed to tackle the Nurse Rostering Problem (NRP) using a dataset introduced in the First International Nurse Rostering Competition (INRC2010). NRP is a combinatorial optimization problem that is tackled by assigning a set of nurses with different skills and contracts to different types of shifts, over a predefined scheduling period. HSA is an approximation method which mimics the improvisation process that has been successfully applied for a wide range of optimization problems. It improvises the new harmony iteratively using three operators: memory consideration, random consideration, and pitch adjustment. Recently, HSA has been used for NRP, with promising results. This paper has made two major improvements to HSA for NRP: (i) replacing random selection with the Global-best selection of Particle Swarm Optimization in memory consideration operator to improve convergence speed. (ii) Establishing multi-pitch adjustment procedures to improve local exploitation. The result obtained by HSA is comparable with those produced by the five INRC2010 winners’ methods.
This paper presents an analysis of some selection methods used in memory consideration of Harmony search (HS) Algorithm. The selection process in memory consideration entails selecting the value of the decision variable from any solution in the Harmony memory (HM). Quite recently, there has been a tendency to adopt novel selection methods that mimic the natural phenomena of the ‘survival of the fittest’ to replace the random selection method in memory consideration. Consequently, the value of decision variable selected using memory consideration is chosen from the higher promising solutions in HM. The adopted selection methods include: proportional, tournament, linear rank, and exponential rank. It has been demonstrated that experimenting with any of these methods in memory consideration directly affects the performance of HS. However, the success of these methods is based on choosing the optimal parameter value of each. The wrong parameter settings might affect the balance between exploration and exploitation of the search space. Accordingly, this paper studies the effect of the selection method parameters in order to show their effect on HS behavior. The evaluation is conducted using standard mathematical functions used in the literature for HS adoptions. The results suggest that the optimal setting of the selection method parameters is crucial to improve the HS performance.
The post-enrolment course timetabling is concern with assigning a set of courses to a set of rooms and timeslots according to the set of constraints. The problem has been tackled using metaheuristic techniques. Artificial Bee Colony (ABC) algorithm has been successfully used for tackling uncapaciated examination and curriculum based course timetabling problems. In this paper ABC is modified for post-enrolment course timetabling problem. The modification is embedded in the onlooker bee where the multiswap algorithm is used to replace its process. The dataset established by Socha including 5 small, 5 medium and one large dataset are used in the evaluation of the proposed technique. Interestingly, the results obtained is highly competitive when compared with those previously published techniques.
Artificial Bee Colony
University Course Timetabling
Harmony search (HS) algorithm is a recent evolutionary algorithm which mimics the musical improvisation process. It has been successfully applied to a wide range of combinatorial optimization problems. Office-Space-Allocation (OSA) is the process of distributing given limited spaces to given resources in accordance with given constraints: hard and soft. Hard constraints are mandatory to satisfy while the soft constraints are desired but not absolutely essential. The main aim is to find a solution with the least violations of soft constraints while the hard constraints are satisfied and the best usage of spaces is achieved. In this paper, HS is modified and adapted for OSA. The modification includes two HS operators: i) memory consideration where the global-best concept of Particle Swarm Optimization is borrowed and employed; and ii) the pitch adjustment has been designed to be as a local search agent with three effective neighbourhood structures. The proposed Modified Harmony Search Algorithm (MHSA) is evaluated using three datasets from Nottingham and Wolverhampton universities. Interestingly, MHSA obtained two new best results, and a competitively comparable result for the third dataset.
In this paper, a Hybrid Harmony Search Algorithm (HHSA) is presented for Nurse Rostering Problem (NRP) using the dataset proposed by the First International Nurse Rostering Competition (INRC2010). NRP is tackled by assigning daily shifts to nurses with different skills and working contracts, subject to hard and soft constraints. Harmony Search Algorithm (HSA) is a recent evolutionary computing technique, mimicking the musical improvisation process where a group of musicians play the pitches of their musical instruments. Recently, HSA has been used for NRP, with promising results. This paper extends HSA to HHSA by adding two powerful concepts to HSA: (i) hybridization with hill climbing optimizer to improve the exploitation ability, and (ii) hybridization with global-best concept of particle swarm optimization to improve the speed of convergence. The proposed HHSA is evaluated against a dataset provided by INRC2010. The results show that it is a powerful technique for INRC2010 dataset. A comparative analysis with five competitive methods is conducted. HHSA outperforms the other competitive methods in three instances and obtained the best results in 29 others out of 69 instances. The efficiency of our method lends further support to the previous theory based on hybridizing the local search within evolutionary computing technique for hard combinatorial optimization problems.
In this paper we proposed a Harmony Search-based Hyper-heuristic (HSHH) method for examination timetabling problems. The Harmony Search Algorithm (HSA) is a relatively new metaheuristic algorithm inspired by the musical improvisation process. The Hyper-heuristic is a new trend in optimization that uses a high level heuristic selected from a set of low-level heuristic methods. Examination timetabling is a combinatorial optimization problem which belongs to NP-hard class in almost all of its variations. In HSHH approach, the HSA will operate at a high level of abstraction which intelligently evolves a sequence of improvement low-level heuristics to use for examination timetabling problem. Each low-level heuristics represents a move and swap strategies. We test the proposed method using ITC-2007 benchmark datasets that has 12 de facto datasets of different complexity and size. The proposed method produced competitively comparable results.
Examination Timetabling Problems
Harmony Search Algorithm
Artificial Bee Colony Algorithm (ABC) is nature-inspired metaheuristic, which imitates the foraging behavior of bees. ABC as a stochastic technique is easy to implement, has fewer control parameters, and could easily be modify and hybridized with other metaheuristic algorithms. Due to its successful implementation, several researchers in the optimization and artificial intelligence domains have adopted it to be the main focus of their research work. Since 2005, several related works have appeared to enhance the performance of the standard ABC in the literature, to meet up with challenges of recent research problems being encountered. Interestingly, ABC has been tailored successfully, to solve a wide variety of discrete and continuous optimization problems. Some other works have modified and hybridized ABC to other algorithms, to further enhance the structure of its framework. In this review paper, we provide a thorough and extensive overview of most research work focusing on the application of ABC, with the expectation that it would serve as a reference material to both old and new, incoming researchers to the field, to support their understanding of current trends and assist their future research prospects and directions. The advantages, applications and drawbacks of the newly developed ABC hybrids are highlighted, critically analyzed and discussed accordingly.
Artificial Bee Colony Algorithms
Swarm Intelligence Algorithms
Recently, common selection schemes used in harmony search algorithm (HSA) are altered in memory consideration operation to imitate the natural selection principle of survival of the fittest. The selection schemes adopted include: random, proportional, tournament, and linear rank. In this paper, these selection schemes are analysed in order to evaluate their effect on the performance of HSA. The analysis considers takeover time and convergence rate to measure the effectiveness of each selection scheme. Furthermore, a scaled proportional selection scheme is proposed to replace the proportional selection scheme to overcome its shortcoming with negative fitness values. To study the effect of these different selection schemes we use eight global optimisation functions with different characteristics. An experimental evaluation show that linear rank selection provides the highest convergence speed and highest takeover time. On the other hand, scaled proportional selection provides the slowest convergence speed and slowest takeover time. This indicates the effect of the type of the selection method used in memory consideration in takeover time and convergence rate.
harmony search algorithm HSA,
evolutionary algorithms EA
Harmony search (HS) algorithm is relatively a recent metaheuristic optimization method inspired by natural phenomenon of musical improvisation process. despite its success, the main drawback of harmony search are contained in its tendency to converge prematurely due to its greedy selection method. This probably leads the harmony search algorithm to get stuck in local optima and unsought solutions owing to the limited exploration of the search space. The great deluge algorithm is a local search-based approach that has an efficient capability of increasing diversity and avoiding the local optima. This capability comes from its flexible method of accepting the new constructed solution. The aim of this research is to propose and evaluate a new variant of HS. To do so, the acceptance method of the great deluge algorithm is incorporated in the harmony search to enhance its convergence properties by maintaining a higher rate of diversification at the initial stage of the search process. The proposed method is called Harmony Search Great Deluge (HS-GD) algorithm. The performance of HS-GD and the classical harmony search algorithm was evaluated using a set of ten benchmark global optimization functions. In addition, five benchmark functions of the former set were employed to compare the results of the proposed method with three previous harmony search variations including the classical harmony search. The results show that HS-GD often outperforms the other comparative approaches.
Selection is a vital component used in Evolutionary Algorithms (EA) where the fitness value of the solution has influence on the evolution process. Normally, any efficient selection method makes use of the Darwinian principle of natural selection (i.e., survival of the fittest). Harmony search (HS) is a recent EA inspired by musical improvisation process to seek a pleasing harmony. Originally, two selection methods are used in HS: (i) memory consideration selection method where the values of the decision variables are randomly selected from the population (or solutions stored in harmony memory (HM)) to generate a new harmony, and (ii) selecting a new solution in HM whereby a greedy selection is used to update the HM. The memory consideration selection, the focal point of this paper, is not based on natural selection principle which draws heavily on random selection. In this paper, novel selection schemes which replace the random selection scheme in memory consideration are investigated, comprising global-best, fitness-proportional, tournament, linear rank and exponential rank. The proposed selection schemes are individually altered and incorporated in the process of memory consideration and each adoption is realized as a new HS variation. The performance of the proposed HS variations are evaluated and a comparative study is conducted. The experimental results using benchmark functions show that the selection schemes incorporated in memory consideration directly affect the performance of HS algorithm. Finally, a parameter sensitivity analysis of the proposed HS variations is analyzed.
Harmony search algorithm
In this paper, a hybridization of Harmony Search Algorithm (HSA) with a greedy shuffle move is proposed for Nurse Rostering Problem (NRP). NRP is a combinatorial optimization problem that is tackled by assigning a set of nurses with different skills and contracts to different types of shifts, over a pre-determined scheduling period. HSA is a population-based method which mimics the improvisation process that has been successfully applied for a wide range of optimization problems. The performance of HSA is enhanced by hybridizing it with a greedy shuffle move. The proposed method is evaluated using a dataset defined in first International Nurse Rostering Competition (INRC2010). The hybrid HSA obtained the best results of the comparative methods in four datasets.
Harmony Search Algorithm (HSA)
Nurse Rostering Problem (NRP)
This paper presents an artificial bee colony algorithm (ABC) for Education Timetabling Problem (ETP). It is aimed at developing a good-quality solution for the problem. The initial population of solutions was generated using Saturation Degree (SD) and Backtracking Algorithm (BA) to ensure the feasibility of the solutions. At the improvement stage in the solution method, ABC uses neighbourhood structures iteratively within the employed and onlooker bee operators, in order to rigorously navigate the UTP search space. The technique was evaluated using curriculum-based course timetabling (CB-CTT) and Uncapacitated Examination Timetabling Problem (UETP) problem instances. The experimental results on UETP showed that the technique is comparable with other state-of-the-art techniques and provides encouraging results on CB-CTT.
Artificial Bee Colony (ABC)
Artificial Bee Colony (ABC) algorithm is among the most effective nature-inspired algorithms for solving the combinatorial optimization problems. In this paper, ABC is adopted for university examination timetabling problems (UETP) using a defacto dataset established by Carter et al. (1996). ABC has three main operators that drive the search toward the global minima: employed bee, onlooker bee, and scout. For UETP, the employed bee and onlooker bee operators are manipulated to be workable where three neighborhood structures are employed: move, swap and Kempe chain. The effect of these neighborhood structures on the behaviour of ABC for UETP is studied and analyzed in this paper. The experimental design is intentionally made with various convergence cases of different neighborhood structure. The result suggests that the ABC combined with the three neighborhood structures is an effective method for UETP. Comparative evaluation with previous methods is also provided. The results produced by the proposed method are competitive in comparison with state of the art methods. Theoretically, this study contributes to the examination timetabling community through an ABC template which is both efficient and flexible for UETP.
artificial bee colony
examination timetabling problem
Office-Space-Allocation problem is a distribution of a set of limited spaces to a set of resources subject to two types of constraints: hard and soft. Hard constraints must be fulfilled while the soft constraints to be satisfied as much as possible. The quality of the solution is determined based on satisfaction of the soft constraints and the best usage of spaces. The harmony search algorithm (HSA) is a population-based metaheuristic inspired by a musical improvisation process. At each iteration, three operators are used to generate the new harmony: memory consideration, random consideration, and pitch adjustment. In this paper, we modify the memory consideration operator to select from the best solution in the population during the search. HSA is evaluated by using three datasets from Nottingham, and Wolverhampton universities. Experimentally, the HSA obtained new results for two datasets, and a comparable result for the third dataset.
This research article presents an Artificial Bee Colony algorithm for solving timetabling problems, with emphasis on curriculum-based course timetabling. An attempt was made to solve these problems via an approach broken down into two parts; first, Saturation Degree (SD) was used to ensure feasible solution, where the hard constraints were satisfied. In the second part, Artificial Bee Colony Algorithm (ABC) was used to improve the results obtained. The algorithm produced good results, though they were not better when compared to those already reported in the literature because ABC easily gets stuck in the local optimal solution. When properly modified through the hybridization of local search-based algorithms, this approach could boost ABC to perform better, to solve timetabling problems in general.
Curriculum Based Course Timetabling
Artificial Bee Colony
Nature Inspired Algorithm
In this paper, a Harmony Search Algorithm (HSA) is adapted for Nurse Rostering Problem (NRP). HSA is a global optimization method derived from a musical improvisation process which has been successfully tailored for several optimization domains. NRP is a hard combinatorial scheduling problem of assigning given shifts to given nurses. Using a dataset established by International Nurse Rostering Competition 2010 of sprint dataset that has 10-early, 10-late, 10-hidden, and 3-hint. The proposed method achieved competitively comparable results.
The Artificial Bee Colony Algorithm (ABC) is an emerging nature-inspired, metaheuristic optimisation algorithm. In this paper, an improved ABC algorithm is proposed for tackling Curriculum-Based Course Timetabling Problem (CBCTT). The first phase of the solution in the proposed technique uses a combinations of Saturation Degree (SD) and Backtracking Algorithm (BA) to guarantee a feasible timetabling, where all hard constraints are satisfied. The second phase involves the addition of new neighbourhood structures to the basic ABC algorithm, in order to further enhance its performance. The results obtained by the use of the improved ABC algorithm (IABC) shows that the performance is better than the original ABC when used for CB-CTT. Even though the results produced by the IABC in the present experiment is close to the average reported for the top five competitors, it is however, still not comparatively superior to the best results already reported in the literature. In conclusion, the results of this experiment suggest that IABC is capable of solving timetabling problems, although further work is necessary to overcome the related challenges which it still faces.
Curriculum Based Course Timetabling
Artificial Bee Colony Algorithm
Nature Inspired Algorithm
In this research an adaption of Harmony Search Algorithm (HSA) for Nurse Scheduling Problem (NSP) is presented. Nurse scheduling problem is a task of assigning shifts to nurses for the duties that have to carry out. The difficulty of handling this problem is due to the high number of constraints to be satisfied. Thus, we are proposing an adaptation of HSA i.e. a new population-based metaheuristic algorithm that mimics the musical improvisation process which has been successfully applied for wide range of optimisation problems. The performance of HSA is evaluated using datasets established by International Nurse Rostering Competition 2010 (INRC2010). The results obtained were compared with the best results reported in the competition. The results show that the proposed method can compete well in comparison with those reported results.
This research article presents the adaption of the Artificial Bee Colony algorithm for solving timetabling problems, with particular focus on the curriculum-based course timetabling that formed part of the competition track 3 of the 2nd International Timetabling Competition in 2007 (ITC-2007). An attempt to solve these problems was made via an approach broken down into two parts; first, Saturation Degree (SD) was used to ensure a feasible solution, where the hard constraints are satisfied. Secondly, Artificial Bee Colony Algorithm was used to further improve the results obtained. The algorithm produced very good results, though they were not comparatively better than those previously reported in the literature due to the fact that the algorithm easily gets stuck in the local optimal solution. With proper modification and hybridizing local search-based algorithms this approach could make the algorithm perform better on timetabling problem in general.
Curriculum Based Course Timetabling
Artificial Bee Colony Algorithm
Nature Inspired Algorithms