NDLI: A VNS-based hyper-heuristic with adaptive computational budget of local search

Content Provider	IEEE Xplore Digital Library
Author	Ping-Che Hsiao Tsung-Che Chiang Li-Chen Fu
Copyright Year	2012
Description	Author affiliation: Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, R.O.C. (Ping-Che Hsiao) \|\| Department of Computer Science and Information Engineering, National Taiwan Normal University, Taipei, Taiwan, R.O.C. (Tsung-Che Chiang) \|\| Department of Electrical Engineering and Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, R.O.C. (Li-Chen Fu)
Abstract	Hyper-heuristics solve problems by manipulating low-level domain-specific heuristics. The aim is to raise the level of generality of the algorithm to solve problems in different domains. In this paper we propose a hyper-heuristic based on Variable Neighborhood Search (VNS), which consists of two main steps: shaking and local search. Shaking disturbs solutions, and then local search seeks for the local optima. In our algorithm, we propose a mechanism to adjust the computational budget of local search periodically based on the search status. We also use a dynamically-sized population to store good solutions during the search process. Performance of the proposed algorithm is compared with four benchmark algorithms by four kinds of problems, Max-SAT, bin packing, flow shop scheduling, and personnel scheduling. Our algorithm finds the best solutions for around 90% of the tested instances.
Starting Page	1
Ending Page	8
File Size	1256077
Page Count	8
File Format	PDF
ISBN	9781467315104
e-ISBN	9781467315098
e-ISBN	9781467315081
DOI	10.1109/CEC.2012.6252969
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-10
Publisher Place	Australia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Search problems Heuristic algorithms Personnel Job shop scheduling Educational institutions Algorithm design and analysis chesc hyper-heuristic variable neighborhood search local search intensity tabu search adaptive control hyflex cross-domain heuristic search challenge
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in