The Comparison Between Lofti-Cerveny-Weitz Method and Local Search Genetic Algorithmfor Completion of Maximally Diverse Grouping Problem

摘要

Maximally Diverse Grouping Problem(MDGP) consists of grouping a set of M elements into Ggroups. The diversity of the elements in each group ismaximized. The MDGP problem is one of the mostcomplex computational problems today. It is the NP-HardProblem. The Lofti-Cerveny-Weitz (LCW) method is avariation of the Lofti-Cerveny (LC) method. It explainsthat the search for element j is not limited to group g.LCW considers all groups when searching for j elementexcept element i is located. Genetic algorithm is anintelligent optimization technique based on simulations ofbiological evolution. ZP Fan explains GA-based heuristicsteps combined with Local Search for MDGP. TheMDGP case of this study is at the ITERA dormitory. Itdivided into several attributes. They are regional origin,study programs, economics, religion and academic skills.Moreover, they were classified into groups and everygroup consisted of four students. Fitness value iscalculated by adding up all the distance of students ineach group. Student distance is obtained by using theEuclidian distance formula at the distance of the fivestudent attributes. The result of this study showed that thefitness value using the Lorent-Cerveny-Weitz method washigher than the local search Genetic algorithm. Itexplained that male dormitory were 0.0066 and0.0011% for female dormitory. The computation time ofLorent-Cerveny-Weitz Method was longer than the localsearch Genetic algorithm. It explained that maledormitory were 684 and 660% for female dormitory inlonger duration.