Abstract: This study implements three basic local search heuristics: hill climbing (i.e., random descent), simulated annealing and multi-start simulated annealing. The aim is to investigate the performance of these heuristics compared to the state of art literatures. To achieve this, this study used a common software interface (the HyFlex frame work), that are designed to enable the development, testing and comparison of iterative general-purpose heuristic search algorithms. To evaluate the performance of these heuristics, the algorithms are tested on one dimensional bin packing instances using simple move operator. Results demonstrated that hill climbing heuristic outperforms other approaches in all tested instances. This indicates that simple local search is more effective in solving one dimensional bin packing problems when the searcher is allowed to run in a short time.
INTRODUCTION
Many real-world problems fall in the class of NP-hard problems (Cook, 1971). In other words, the problem is difficult to solve for optimality in a reasonable time. A good practical example is the problem of one dimensional bin packing problem.
Hence, many researchers have developed variants of efficient heuristic methods to deal with large real-world problem instances. Heuristics (or meta-heuristics) often provide good solutions to NP-hard problems in a reasonable short time, but they cannot guarantee to find the optimal solution. Metaheuristics attempt to provide a non problem-specific optimisation algorithm which explores a search space in a guided manner in order to quickly find (near-) optimal solutions (Blum et al., 2008) for a list of accepted definitions for metaheuristic.
Researchers implemented a wide variety of different metaheuristics approaches such as Simulated Annealing (Dowsland et al., 2007) (modelling a physical cooling process), Ant Colony Optimisation (Dorigo and Gambardella, 1997) (mimicking the way a collection of ants finds a short way to a food source) and Genetic Algorithms (Reeves and Rowe, 2002) (implementing the biological process of gene mutation and recombination). Researchers usually refine their heuristic and often attempt to demonstrate their superiority over the state of art. However, the ”No free lunch” theorems stated that no algorithm can work well over divers set of problems (Wolpert and Macready, 1997). Therefore, the meta-heuristic need to be revised to solve a new problem.
The performance of simple iterative improvement local search (such as hill climbing for maximisation problems or descent heuristic in minimisation problems), that iteratively search for better quality solution and only accept improved solutions, is in general unsatisfactory (Blum et al., 2008). The quality of the solution found in local optimum is heavily depends on the starting point of the local search. A simple strategy to overcome this is, by iteratively restart the local search at different starting points, which may randomly generated. However, their performances are still far away from being satisfactory (Schreiber and Martin, 1999).
Therefore, this work attempt to further investigate the performance of three basic local search heuristics: simple descent (hill climbing), simulated annealing and multi-start simulated annealing.
THE HyFlex FRAME WORK
HyFlex (Hyper-heuristics Flexible framework) (Ochoa et al., 2012) is a Java object oriented framework for the development and comparison of different iterative general-purpose heuristic search algorithms. HyFlex provides a software interface between the problem specific components and the domain independent algorithm components. The aim is to support researchers in their efforts to develop generally applicable search heuristics. Therefore, future researchers can focus in the design of intelligent and adaptable cross-domain search controllers.
At the highest level, the framework consists of two abstract classes: ProblemDomain and HyperHeuristic. HyFlex can be used to implement both population-based and single based metaheuristics/hyper-heuristics. Indeed, it provides six combinatorial optimisation problems with real-world instances data. These are: maximum satisfiability (MAX-SAT), one-dimensional bin packing, permutation flow shop, personnel scheduling, traveling salesman problems and capacitated vehicle routing problems.
Each domain includes 10 training instances from different sources and a number of problem-specific local search (basic) heuristics of the types. Each HyFlex domain module encapsulates the problem model and the data structure for encoding a candidate solution. It has:
| • | A routine to initialise randomised solutions |
| • | An objective function for evaluating the quality of solutions and |
| • | A set of varied instance data sets from different sources |
HyFlex also has various set of low level heuristics, which are classified into four groups:
| • | Mutational or pertubation heuristics: These induce a small modification to the current solution |
| • | Ruin-recreate (destruction-construction) heuristics: They operate by randomly destroying part of the solution and then rebuilding it using a greedy or constructive procedure. These heuristics are considered as large neighbourhood structures. They are different from the mutational heuristics, in that they can incorporate problem specific construction heuristics to rebuild the solutions |
| • | Hill-climbing (simple descent) heuristics: Operate by iteratively perturbing an incumbent solution, accepting improving, until a local optimum is found or a stopping condition is met. They differ from mutational heuristics in that they incorporate an iterative improvement process |
| • | Crossover heuristics: Widely used in evolutionary approaches, crossover or recombination heuristics that take two solutions and combine them to produce an offspring solution |
Finally, HyFlex provides two control parameters β (intensity of mutation) and β (depth of search), than is used to control the behavior of the heuristics. The precise functioning of the parameters depends on the specific heuristic and problem domain. The value for α and β are between ‘0’ and ‘1’. Details discussion on HyFlex can be referred by Ochoa et al. (2012).
HyFlex provides an opportunity to modify some of the heuristics in an informed manner. It is possible to increase or decrease the perturbation effect of a mutational heuristic. In addition to that, it is also allowed to change the depth of the search for local search heuristics.
ONE DIMENSIONAL BIN PACKING PROBLEMS
One dimensional packing problem is an NP-hard problem. It consists of a set of pieces that must be packed into the fewest number of bins. This problem has a set of items of a fixed weight and a set of bins of fixed capacity. The packing process must consider these constraints (hard constraint):
| • | Each item must be assigned to one bin only |
| • | The total weight of items in each bin must be less or equal to the bin capacity |
The aim is to minimise to the number of used bins. A mathematical formulation for the fitness of the classical one dimensional bin packing problem is shown in Eq. (1) (Martello and Toth, 1990):
| (1) |
Subject to:
where, xij is 1 indicates that piece j is packed into bin i, or otherwise xij is 0; yi is 1 if a bin i contains some pieces, ‘0’ otherwise. n is the number of available bins (and also the number of pieces).
We used five instances of one dimensional packing problem currently available in the 2011 HyFlex software (Table 1). The set of initial solutions are generated as follows:
| • | Generate a random sequence of items |
| • | Pack them one by one into the first bin into which they will fit “first fit heuristic” |
| • | Evaluate he quality of solution using Eq. 2 (Hyde et al., 2010) |
To evaluate the fitness of the solution, this work employs an alternative fitness function to the number of bins as in equation (2) suggested by Hyde et al. (2010):
| (2) |
where, n is the number of bins, fullnessi is the sum of all the pieces in bin i and C is the bin capacity. This will avoid large plateaus in the search space around the best solutions.
LOCAL SEARCH HEURISTICS
This study implemented three basic local search heuristics. These are:
| • | Hill Climbing/simple descent (HC): The heuristic choose the first improving neighbour that is better than the current solution. Then, an improving neighbour is immediately selected to replace the current solution. The neighbour is randomly evaluated. The heuristic terminate when there is no improved neighbours for certain iteration or when the termination criterion is met |
| • | Simulated annealing (SA): SA is a stochastic algorithm that probabilistically accepts some worse solutions to escape from local optimum. It begins by randomly or heuristically generates an initial solution (or the initial solution is given). Then, the search starts with a high initial temperature to allow diversification at early search. For each iteration, the temperature is gradually reduced to restrict the acceptance of low quality solution (intensification) and will end when it reach zero or nearly zero temperature (or when termination criterion is met). In each iteration, a neighbour of the current solution is randomly generated. The ‘qualities’ of the two solutions (the current, f (so) and neighbor solution, f (s’)) are compared (δ = f (s')-f (s0)). A decision is made whether the new solution should be accepted. An improved solution is always accepted. However, in order to escape from the local optimum, a worse solution will probabilistically accepts that depends on SA acceptance criterion (where if the generated random number is less than e¯δ/T and T is the current temperature) (Talbi, 2009) |
| • | Multistart-Simulated Annealing: It combines the advantages of SA and multi-start hill climbing strategies. When the temperature is high, the SA acceptance criteria tend to perform a drastic search in the solution space to seek the solutions and there is a high probability that SA may accept worse solutions and quickly trapped in bad local optimum. Thus, SA that aspires to obtain (near) global optima typically requires some form of diversification to escape from local optimality. Without such diversification, SA may be restricted in a small area of the solution space, losing the possibility of finding a better local optimum (that might be a global optimum). The multi-start hill climbing strategy can provide an effective way of avoiding the search being trapped in local optimum. Therefore, the combination of the advantages of SA and the multi-start hill climbing strategy in escaping from local optimality may provide the rationale for developing a multi-start simulated annealing (MSA) heuristic. In this work, the SA temperature is restarted when it cannot find an improved solution for a certain number consecutive iterations. The temperature is reset to the value that the SA started trapped in local optimum |
| Table 1: | One dimensional bin packing instances |
EXPERIMENTAL SETUP AND RESULTS
The experiments were conducted using the five test instances of one dimensional bin packing problem currently available in the 2011 HyFlex software. As stated in CHeSC rules, the execution time is used as stopping condition, which is determined by the benchmark software provided by CHeSC organizer (Ochoa et al., 2012). Thus, ten runs was performed for each instances and terminated after ten minutes runs. For all tested approaches (HC, SA, MSA), this work only use a simple pertubation heuristic that is a simple swap, where two different pieces are selected at random and swapped them if there is a space and if it will produce an improvement in fitness (available in Hyflex software). The parameter setup used in this experiment is set based on the recommendation in the literature (Table 2).
This study reported the best (minimum), average and the worst (maximum) quality of solution obtained by HC, SA and MSA out of ten runs (Table 3).
| Table 2: | Parameter setup for HC, SA and MSA |
| Table 3: | Results of five instances bin packing problems tested on HC, SA and MSA (minimum, maximum and average quality of solutions out of 10 runs) |
| Bold value indicate the best quality values among them Min, max and avg. refer to the minimum, maximum and average quality of the solutions (out of 10 runs). All the values for max, min and avg indicate the quality of the solution | |
| Table 4: | Results of five instances bin packing problems tested on HC, SA and MSA (best quality solutions out of 10 runs) comparing to the top five hyper-heuristics |
| Ave. Overall: The overall average for instances; Bold value indicate the best quality values among them. All the values for max, min and avg indicate the quality of the solution, HC: Hill Climbing, SA: Simulated Annealing, MSA: Mutistart-Simulated Annealing, AdapHH: An adaptive hyper-heuristic for CHeSC 2011. VNS-TW: A variable neighborhood search-based hyperheuristic for cross-domain optimization problems in CHeSC 2011 competition, ML: A Hyper-heuristic for the CHeSC 2011. PHUNTER: Pearl Hunter: A Hyper-heuristic that Compiles Iterated Local Search Algorithms, EPH: An Evolutionary Programming Hyper-heuristic with Co-evolution for CHeSC'11 | |
For example, in instance 1, the quality of the best solution obtained by HC is 0.007, whilst SA and MSA managed to obtained the solution with quality value 0.064 and 0.046, respectively. Results demonstrated that in term of solution quality, HC out performed SA and MSA in all instances (where the best, average and the worst quality solution obtained by HC are better than SA and MSA).
To further evaluate the performance of HC, SA and MSA, these heuristics are compared with the top five hyper-heuristic methods from CHeSC competition (AdapHH, VNS-TW, ML, PHUNTER and EPH) (Ochoa et al., 2012) based on the quality of the best solution (Table 4). The results demonstrate that, out of 5 instances, HC outperformed the top five hyperheuristic methods on 3 instances (Instance 1, Instance 4 and Instance 5) and being inferior on 2 instances (Instance 2 and Instance 3). It is observed that HC managed to produce new best results for 3 instances, that is for Instance 1, Instance 4 and Instance 5, HC managed to obtain the best solution with quality of 0.007, 0.024 and 0.000, respectively. In average, HC is superior to the top five hyper-heuristic methods from CHeSC competition (based on Ave. Overall).
CONCLUSION
This study had implemented three basic local search heuristics (hill climbing, simulated annealing and multi-start simulated annealing) to solve the one dimensional bin packing problems. Five test instances of one dimensional bin packing problem currently available in the 2011 HyFlex software were used to evaluate the performance of these local search heuristics. Results indicated that hill climbing manage to find good quality solutions in a short run. This is due to its simplicity and perhaps at early stage there are many unexplored neighbours. Whilst, other advanced heuristics are computational expensive (compared to hill climbing) and therefore spend more time to explore the search at the early search. However, the advanced heuristics may perform well if the running time is expanded. This shows that the intelligent mechanism in advanced metaheuristic approaches give negative effect to the performance of the metaheuristic at the early search time.
ACKNOWLEDGMENTS
The authors wish to thank Ministry of Higher Education for supporting this study under the FRGS Research Grant Scheme (FRGS/1/2012/SG05/ UKM/02/11).