Using Shuffled Frog Leaping Algorithm to View Selection Problem Subject to Dual Constraints

摘要

This paper presents a shuffled frog leaping algorithm (SFLA) based solution to solve the View Selection Problem (VSP) subject to dual constraints, which is often used to accelerate data warehouse queries. Since VSP is both discrete and constrained, a greedy-repaired strategy under dual constraints is proposed to handle unfeasible solutions. This proposed solution also profits from a mutation strategy in order to improve the quality of solutions, particularly to avoid being trapped in local optima. Experimental results show that under different constraints combinations, SFLA is able to find a near-optimal feasible solution, with maximum error less than 1%. Comparisons with GA and PSO show that SFLA has better solution quality and faster convergence rate, and also scales with the problem size.