Sourab Mandal

and 2 more

This article draws inspiration from one of the most widely used Multi-objective Evolutionary Algorithms (MOEAs), known as the Elitist Non-dominated Sorting Genetic Algorithm (NSGA–II). This paper explores the possibility of a hardware implementation of the NSGA-II procedure to make a fast and dedicated multi-objective optimization in practice. The algorithm comprises two key components for converting a single-objective evolutionary algorithm into a multi-objective algorithm: a fast non-dominated sorting for achieving convergence and a crowding distance computation for maintaining a diverse yet indifferent solution set. The fast non-dominated sorting approach requires O(N^2) (N is the population size) and employs the concept of dominance to decompose population members in a multidimensional objective space into distinct non-dominated fronts. The primary objective of this study is to theoretically establish the inherent logical characteristics of dominance and indifference relations, along with their other comprehensive properties, so that the operation can be completed in a computationally fast manner. This involves examining their characteristics concerning reflexivity, symmetry, (semi-)transitivity, equivalence etc., through logical propositions and corresponding truth tables. The research concludes by proposing that the dominance relation can be represented as a logical ‘AND’ operation, while the indifference relation aligns with a logical ‘exclusive-OR’ (XOR) operation. Furthermore, this report logically establishes that both the dominance and indifference relations do not qualify as equivalence relations. The paper also offers a visual representation using a block diagram and a circuit diagram that vividly illustrates these relations, leading to a possible hardware implementation of dominance and indifference relations on chips.