INTRODUCTION
Many realworld problems fall in the class of NPhard 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 realworld problem instances. Heuristics (or metaheuristics)
often provide good solutions to NPhard problems in a reasonable short time,
but they cannot guarantee to find the optimal solution. Metaheuristics attempt
to provide a non problemspecific 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 metaheuristic
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 multistart simulated annealing.
THE HyFlex FRAME WORK
HyFlex (Hyperheuristics Flexible framework) (Ochoa et
al., 2012) is a Java object oriented framework for the development and
comparison of different iterative generalpurpose 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 crossdomain
search controllers.
At the highest level, the framework consists of two abstract classes: ProblemDomain
and HyperHeuristic. HyFlex can be used to implement both populationbased and
single based metaheuristics/hyperheuristics. Indeed, it provides six combinatorial
optimisation problems with realworld instances data. These are: maximum satisfiability
(MAXSAT), onedimensional 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 problemspecific 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 
• 
Ruinrecreate (destructionconstruction) 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 
• 
Hillclimbing (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 NPhard 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):
Subject to:
where, x_{ij} is 1 indicates that piece j is packed into bin i, or
otherwise x_{ij} is 0; y_{i} 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):
where, n is the number of bins, fullness_{i} 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 (s_{o}) and neighbor solution,
f (s’)) are compared (δ = f (s')f (s_{0})). 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) 
• 
MultistartSimulated Annealing: It combines the advantages of SA
and multistart 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
multistart 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 multistart hill climbing strategy in escaping
from local optimality may provide the rationale for developing a multistart
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 hyperheuristics 

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: MutistartSimulated Annealing, AdapHH: An adaptive hyperheuristic
for CHeSC 2011. VNSTW: A variable neighborhood searchbased hyperheuristic
for crossdomain optimization problems in CHeSC 2011 competition, ML: A
Hyperheuristic for the CHeSC 2011. PHUNTER: Pearl Hunter: A Hyperheuristic
that Compiles Iterated Local Search Algorithms, EPH: An Evolutionary Programming
Hyperheuristic with Coevolution 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 hyperheuristic methods from CHeSC competition (AdapHH,
VNSTW, 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 hyperheuristic
methods from CHeSC competition (based on Ave. Overall).
CONCLUSION
This study had implemented three basic local search heuristics (hill climbing,
simulated annealing and multistart 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).