Bi-objective modeling and optimization by greedy stochastic algorithm

Abstract

Multi-objective optimization problems (MOPs) involve the simultaneous optimization of multiple, often conflicting objectives, and have wide-ranging applications in fields such as engineering, business, economics, and logistics. Most MOPs are classified as NP-Hard, meaning that finding an exact optimal solution is computationally expensive and impractical for large instances. In such cases, stochastic methods are preferred, as they offer near-optimal solutions within a reasonable time, as opposed to exact methods, which guarantee optimal solutions but require exponentially longer runtimes.

This thesis addresses a bi-objective optimization problem known as the Minimum Weight Minimum Connected Dominating Set (MWMCDS) problem. The objective is to minimize both the number of nodes (cardinality) and the total weight of the connected dominating set (CDS) in a given graph, a well-known challenge in graph theory.

To tackle this problem, three greedy stochastic algorithms are proposed. The first, Greedy Simulated Annealing (GSA), applies the simulated annealing technique with an aggregated objective function to guide the search process. The second, Improved NSGA-II (I-NSGA-II), is an enhanced version of the widely used NSGA-II algorithm, specifically adapted for multi-objective optimization. The third algorithm, Multi-objective Greedy Simulated Annealing (MGSA), introduces a new multi-objective adaptation of simulated annealing based on Pareto optimization. In all three approaches, tailored greedy heuristics are integrated to boost the efficiency of the solution process.

Experimental results, based on several performance metrics, demonstrate that the proposed algorithms outperform existing state-of-the-art methods, achieving superior results in terms of both solution quality and computational efficiency.