Modular Abstract Self-learning Tabu Search (MASTS) : metaheuristic search theory and practice

MASTS is an extensible, feature rich, software architecture based on tabu search (TS), a metaheuristic that relies on memory structures to intelligently organize and navigate the search space. MASTS introduces a new methodology of rule based objectives (RBOs), in which the search objective is replaced with a binary comparison operator more capable of expressing a variety of preferences. In addition, MASTS supports a new metastrategy, dynamic neighborhood selection (DNS), which “learns” about the search landscape to implement an adaptive intensification-diversification strategy. DNS can improve search performance by directing the search to promising regions and reducing the number of required evaluations. To demonstrate the flexibility and range of capabilities, MASTS is applied to two complex decision problems in conservation planning and groundwater management. As an extension of MASTS, ConsNet addresses the spatial conservation area network design problem (SCANP) in conservation biology. Given a set of possible geographic reserve sites, the goal is to select which sites to place under conservation to preserve unique elements of biodiversity. Structurally, this problem resembles the NP-hard set cover problem, but also considers additional spatial criteria including compactness, connectivity, and replication. Modeling the conservation network as a graph, ConsNet uses novel techniques to quickly compute these spatial criteria, exceeding the capabilities of classical optimization methods and prior planning software. In the arena of groundwater planning, MASTS demonstrates extraordinary flexibility as both an advanced search engine and a decision aid. In House Bill 1763, the Texas state legislature mandates that individual Groundwater Conservation Districts (GCDs) must work together to set specific management goals for the future condition of regional groundwater resources. This complex multi-agent multi-criteria decision problem involves finding the best way to meet these goals considering a host of decision variables such as pumping locations, groundwater extraction rates, and drought management policies. In two separate projects, MASTS has shaped planning decisions in the Barton Springs/Edwards Aquifer Conservation District and Groundwater Management Area 9 (GMA9). The software has been an invaluable decision support tool for planners, stakeholders, and scientists alike, allowing users to explore the problem from a multicriteria perspective.