In this paper a family of new methods are proposed for constructing hierarchical-interpolative fuzzy rule bases in the frame of a fuzzy rule based supervised machine learning system modeling black box systems defined by input-output pairs. The resulting hierarchical rule base is constructed by using structure building pure evolutionary and memetic techniques, namely, Genetic and Bacterial Programming Algorithms and their memetic variants containing local search steps. Applying hierarchical-interpolative fuzzy rule bases is a rather efficient way of reducing the complexity of knowledge bases, whereas evolutionary methods (including memetic techniques) ensure a relatively fast convergence in the learning process. As it is presented in the paper, by applying a newly proposed representation schema these approaches can be combined to form hierarchical-interpolative machine learning systems. © 2012 World Scientific Publishing Company.