In this paper, we introduce an design of fuzzy relation-based fuzzy neural networks with multi-output. Fuzzy relation-based fuzzy neural networks comprise the network structure generated by dividing the entire input space. The premise part of the fuzzy rules of the network reflects the relation of the division space for the entire input space and the consequent part of the fuzzy rules expresses three types of polynomial functions such as constant, linear, and modified quadratic. For the multi-output structure the neurons in the output layer were connected with connection weights. The learning of fuzzy neural networks is realized by adjusting connections of the neurons both in the consequent part of the fuzzy rules and in the output layer, and it follows a back-propagation algorithm. In addition, in order to optimize the network, the parameters of the network such as apexes of membership functions, learning rate and momentum coefficient are automatically optimized by using real-coded genetic algorithm. Two examples are included to evaluate the performance of the proposed network.