In this work, a novel genetic algorithm (GA) is proposed for the design of multiplierless finite impulse response (FIR) filters with high filter order and wide coefficient wordlength. GA mimics the nature evolution to optimize complicated problems and in theory optimum solutions can be obtained with infinite computation time. However, in practical filter design problem, when the filter specification is stringent, requiring high filter order and wide coefficient wordlength, GA often fails to find feasible solutions, because the discrete search space thus constructed is huge and majority of the solution candidates therein can not meet the specification. In the proposed GA, the discrete search space is partitioned into smaller ones. Each of the small space is constructed surrounding an optimum continuous solution with a floating passband gain. This increases the chances for the GA to find feasible solutions, but not sacrificing the coverage of the search space. In addition, the search in the multiple spaces can run in parallel, and thus the computation time for the design of filters under consideration reduces significantly. Design examples show that the proposed GA outperforms existing algorithms dealing with the similar problems.