Bin packing problem is a constrained optimization problem with a huge search space due to large combinations. Bin packing problem has a wide range of applications in multiple fields. This paper presents harmony search algorithm with different initialization and adaptive PAR strategies for solving bin packing problem. The proposed Harmony search (HS) variations tests two partial feasible initialization strategies for bin packing problem. The paper presents adaptive PAR strategies for better exploration and exploitation of HS algorithm. The PAR values are tuned in every iteration. Improved initialization strategy, population initialization after premature convergence and adaptive PAR leads to the better exploration of harmony search algorithm for bin packing problem. The performance of variations are tested over 120 benchmark instances with 100 and 200 objects with varying complexities. The results show that improved HS performs better than basic HS with respect to best, mean, convergence rate. The performance of algorithms is tested with varying harmony memory size and harmony memory considering rate. Results show that variation in these two parameter values has less effect on performance of improved versions.