ENHANCING NSGA-II FOR MULTI-OBJECTIVE COMBINATORIAL OPTIMIZATION PROBLEMS

Abstract

Multi-objective combinatorial optimization problems (MOCOPs) represent a challenging class of optimization problems characterized by discrete decision spaces and the simultaneous optimization of multiple conflicting objectives. These problems have diverse applications across various fields that require practical decision-making, such as engineering, logistics, finance, and resource allocation. Unlike single-objective optimization, where a single-objective function is optimized, MOCOPs require finding solutions that represent trade-offs between competing objectives, known as Pareto-optimal solutions. The combinatorial nature of MOCOPs introduces further complexity as the number of possible combinations grows exponentially with the number of decision variables, which often resulting in computational intractability. Addressing these challenges requires robust optimization techniques that are capable of navigating complex decision spaces and balancing competing objectives effectively. The fast non-dominated sorting genetic algorithm (NSGA-II) proposed by Deb et al. in 2000 is a widely recognized multi-objective optimization algorithm (MOOA) in evolutionary computation, which offers a powerful engine for exploring search space and identifying Pareto-optimal solutions. While traditional NSGA-II has been extensively utilized in solving real-world MOCOPs, customizing NSGA-II for specific MOCOPs has proven more effective in handling their inherent complexities. Through refinement and customization tailored to various MOCOPs, NSGA-II is evolving into a premier tool for effectively addressing complex MOCOPs. Further, validating any new MOOA is tedious, requiring rigorous comparisons against state-of-the-art algorithms on real-world or standard benchmark problems, including MOCOPs. The process involves a comprehensive investigation of the developed algorithms across various performance metrics. This highlights the need for a research tool to facilitate fair performance assessment and consistency in comparing results. This thesis primarily aims to enhance the effectiveness of NSGA-II in addressing large-scale MOCOPs by developing more effective genetic operations, investigating efficient constraint handling, and addressing scalability challenges. Three diverse MOCOPs: Indian Premier League (IPL) squad selection, Web Service Location-Allocation Problem (WSLAP), and Bounded Single Depot Multiple Travelling Salesmen Problem (BSD-MTSP) have been selected for study to highlight the broader applicability of NSGA-II across different domains, including sports management, service computing, and logistics.The objectives of the thesis include reviewing NSGA-II modifications for diverse MOCOPs, developing enhanced NSGA-II variants for specific MOCOPs, and contributing to the field by developing a software tool for comparing various MOOAs. Based on this, the structure of the thesis is outlined as follows: Chapter 1 introduces the fundamental aspects of the thesis, including the basic definitions of MOCOPs, popular solution methods for MOCOPs, challenges in enhancing NSGA-II for MOCOPs, identified research gaps, research objectives, and thesis organization. Chapter 2 conducts a comprehensive review of NSGA-II modifications for various MOCOPs. This analysis provides insights into the existing adaptations of NSGA-II and evaluates their effectiveness and adaptability in the field of combinatorial optimization. Chapter 3 enhances NSGA-II for the IPL squad selection problem by proposing a new knapsack model that ensures precise player assessments, squad balance, and integration of star players. Two efficient binary and integer-coded NSGA-II variants are developed and validated against the state-of-the-art and other prominent algorithms on IPL 2020 players' data. The proposed methodology provides well-performing trade-off squads to franchises with improved decision-making capabilities for success. Chapter 4 refines NSGA-II to optimize the selection of locations for allocating web services, with a focus on improving the quality of service. This chapter aims to enhance internet performance by reducing delays and increasing data throughput while simultaneously reducing allocation costs for web service providers. The proposed model improves throughput while lowering cost, and the proposed NSGA-II variants outperform the compared algorithms in hypervolume, inverted generational distance (IGD), and computational time in 89% of instances. Chapter 5 proposed ACSEvo, a hybrid NSGA-II approach for BSD-MTSP, optimizing routes for multiple salesmen while balancing workload. By integrating NSGA-II with sweep line heuristic and Ant colony system, the chapter aims to achieve better solution quality, optimize resource utilization, reduce transportation costs, and improve delivery schedules in logistics. Chapter 6 presents a software tool designed for comparing various MOOAs on multiple problems or test instances, facilitating comprehensive evaluations through numerical and graphical outputs. The tool provides a systematic framework for conducting comparative analyses based on Pareto fronts, performance metrics, and statistical tests.Chapter 7 concludes the thesis by summarizing the key findings, discussing the contributions to the field, and outlining potential future research directions. In summary, this thesis contributes to advancing the multi-objective combinatorial optimization (MOCO) community by critically reviewing and enhancing NSGA-II for diverse MOCOPS. The developed NSGA-II variants are tailored to address real-world challenges, offering practical solutions to complex decision-making scenarios. Additionally, it provides a valuable tool for researchers to compare and evaluate MOOAs, facilitating further advancements in the field.