Proposed a new fuzzy nearest neighbor rule with two new parameters.Proposed two new cost functions working in fuzzy class membership space.Verified the model reliability using experiments on several data sets.Statistically compared with several fuzzy based nearest neighbor rules.Implemented on graphical processing units for the sake of speed up. This paper presents an improved version of the well-established k nearest neighbor (k-NN) and fuzzy NN (FNN), termed the multi-objective genetic-algorithm-modified FNN (MOGA-MFNN). The MFNN design problem is converted into a multi-modal objective maximization problem constrained by four objective functions. Thereafter, the associated parameter set of the MFNN and the feature attributes can be determined optimally and automatically via the non-dominated sorting genetic algorithm II. We introduce two new objective functions termed the Margin-I and Margin-II, which are used to improve the generalization capability of the MFNN for the unknown data, along with two existing performance functions: the geometric mean and the area under the receiver-operated characteristic curve for the training accuracy. Moreover, we proposed a novel data-dependent weight-assignment technique for local class membership functions of the MFNN. The technique enables the MFNN to determine its local neighbors adaptively through the MOGA algorithm. To expedite the classification, the MOGA-MFNN is implemented on a graphical processing unit (GPU), which significantly increases the computation speed. Furthermore, the local class-membership function of the MFNN can be computed in advance, rather than delaying it to the classification stage. This again can improve the classification speed. The MOGA-MFNN is evaluated on 20 datasets obtained from the repository of the University of California, Irvine (UCI). The experiments with rigorous statistical significance tests demonstrate that the proposed method performs competitively with the existing methods.