As a straightforward continuation of our previous work in this paper new memetic (combined evolutionary and gradient based) methods are proposed for constructing hierarchical-interpolative fuzzy rule bases in the frame of a supervised machine learning system modeling black box systems defined by input-output pairs. In this work the resulting hierarchical rule bases are constructed by using structure building Genetic and Bacterial Memetic Programming Algorithms, thus stochastic evolutionary optimization methods containing deterministic local search steps. Applying hierarchical-interpolative fuzzy rule bases has proved an efficient way of reducing the complexity of knowledge bases, whereas memetic techniques often ensure a relatively fast convergence in the learning process. The literature has highlighted the advantages of memetic methods against pure evolutionary algorithms, thus the combination of hierarchical-interpolative fuzzy rule bases with memetic techniques may form promising hierarchical-interpolative machine learning systems. © 2012 IEEE.