An improved society of hill-climbers and its application on batch process scheduling

ABSTRACT

Society of Hill-Climbers (SOHC) is a kind of powerful evolutionary optimization algorithm for a large range of problems. But the performance of the algorithm is sensitive to the mutation rate, which must be determined by the user based on the problem. In this study, the performance of SOHC with different mutation rate was evaluated on a series of large numerical problems and mutation rates robust for all the problems tested were identified. Then the algorithm was applied to an important type of optimization problem, the scheduling problem of batch process. The results show that SOHC is a very versatile and powerful method for solving the batch process scheduling problems and is superior to the widely used simulated annealing.

REFERENCES

• 1: William Millan , Andrew Clark , Ed Dawson, Boolean Function Design Using Hill Climbing Methods, Proceedings of the 4th Australasian Conference on Information Security and Privacy, p.1-11, April 07-09, 1999
• 2: Lourdes Peña Castillo , Stefan Wrobel, A comparative study on methods for reducing myopia of hill-climbing search in multirelational learning, Proceedings of the twenty-first international conference on Machine learning, p.19, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015334]
• 3: Sebag, M. and Schoenauer, M. A Society of Hill-Climbers. In Proceedings of 1997 IEEE International Conference on Evolutionary Computation. IEEE Press, 319--324, 1997.
• 4: Dozier G. V., Solving distributed asymmetric constraint satisfaction problems using an evolutionary society of Hill-Climbers. In The Proceedings of the 2003 Genetic and Evolutionary Computation Conference (GECCO '03), (Chicago, IL, July 12--16), 561--572.
• 5: Fu, S. G. and Dozier, G. V., Solving distributed Constraint Satisfaction Problems with an Ant-Like Society of Hill-Climbers. IC-AI, 2003, 263--269.
• 6: Dozier, G. V., Recurrent distributed constraint satisfaction, virtual constraints and meta evolutionary societies of Hill-Climbers. IC-AI, 2003, 276--284.
• 7: Dozier, G. V. and Rupela, V., Solving distributed asymmetric CSPs via a Society of Hill-Climbers. IC-AI, 2002, 949--953.
• 8: Temporel, A. and Kovacs, T., A heuristic hill climbing algorithm for Mastermind. In Proceedings of the 2003 UK Workshop on Computational Intelligence (UKCI-03), 2003, 189--196.
• 9: Ivana Ljubic , Günther R. Raidl, An Evolutionary Algorithm with Stochastic Hill-Climbing for the Edge-Biconnectivity Augmentation Problem, Proceedings of the EvoWorkshops on Applications of Evolutionary Computing, p.20-29, April 18-20, 2001
• 10: Bowei Xi , Zhen Liu , Mukund Raghavachari , Cathy H. Xia , Li Zhang, A smart hill-climbing algorithm for application server configuration, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988711]
• 11: Das H, Cummings P T and Le Van M D. Scheduling of serial multiproduct batch processes via simulated annealing. Comput Chem Eng, 1990, 14, 12, 1351--1362.
• 12: Ku H and Karimi I. An evaluation of simulated annealing for batch process scheduling. Ind. Eng. Chem. Res., 1991, 30, 1, 163--169.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
batch process, mutation rate, scheduling, simulated annealing, society of hill-climbers