Titre :	Bi-objective modeling and optimization by greedy stochastic algorithm
Type de document :	document électronique
Auteurs :	Hayet Dahmri, Auteur ; Bouamama, Salim, Directeur de thèse
Editeur :	Sétif:UFA1
Année de publication :	2024
Importance :	1 vol (119 f.)
Format :	29 cm
Langues :	Anglais (eng)
Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Multi-objective combinatorial optimization Stochastic algorithms Greedy heuristic Minimum weight minimum connected dominating set problem
Index. décimale :	004 - Informatique
Résumé :	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.
Note de contenu :
Côte titre :	DI/0083

Bi-objective modeling and optimization by greedy stochastic algorithm [document électronique] / Hayet Dahmri, Auteur ; Bouamama, Salim, Directeur de thèse . - [S.l.] : Sétif:UFA1, 2024 . - 1 vol (119 f.) ; 29 cm.
Langues : Anglais (eng)

Catégories :	Thèses & Mémoires:Informatique
Mots-clés :	Multi-objective combinatorial optimization Stochastic algorithms Greedy heuristic Minimum weight minimum connected dominating set problem
Index. décimale :	004 - Informatique
Résumé :	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.
Note de contenu :
Côte titre :	DI/0083