Sailing speed performance is a crucial indicator that significantly affects the trafficability, efficiency, and tracking capability of autonomous sailing monohulls during marine science missions. Considering that the design of the hull and keel of an autonomous sailing monohull is usually a task-orientated and creative process, estimating speed performance by traditional velocity prediction programs (VPPs) based on empirical formulas and gradient solvers will lead to errors. This paper proposes a generalized VPP for helping designers assess the speed performance of their autonomous sailing monohulls. We designed an enhanced genetic algorithm (GA) solver to help the VPP converge quickly without a priori performance estimation. Furthermore, we propose an innovative neighbourhood information-based optimization (NIBO) strategy to accelerate and refine the solutions using adjacent states (external conditions with the same true wind speed (TWS) or true wind angle (TWA)) instead of culminating prediction by solving each state independently. We provide an application of the proposed VPP on our prototype as an example. Moreover, the numerical and experimental results show that the proposed VPP can serve as a practical design evaluation tool, especially in the early stages of design.