Multi-Objective Genetic Algorithm (MOGA) is a new approach for association rule mining in the market-basket type databases. Finding the frequent itemsets is the most resource-consuming phase in association rule mining, and always does some extra comparisons against the whole database. This paper proposes a new algorithm, Cluster-Based Multi-Objective Genetic Algorithm (CBMOGA) which optimizes the support counting phase by clustering the database. Clusters are based on the number of items in each transaction. Experiments on two different market-basket type databases show that the CBMOGA outperforms the MOGA.