Bi-objective modeling and optimization by greedy stochastic algorithm
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Setif 1 University - Ferhat ABBAS , Faculty of Sciences
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.
Description
Les problèmes d’optimisation multi-objectif (POMs) nécessitent l’optimisation simul
tanée de divers objectifs souvent contradictoires. Ils ont de nombreuses applications
dans différents domainesscientifiques, notammentl’ingénierie, lecommerce, l’économie,
la logistique, etc. La plupart des MOPssontdesproblèmesNP-difficiles, ilestdonctrop
coûteux en termes de calcul de trouver une solution optimale exacte s’il en existe une.
Dans de telles situations, des méthodes stochastiques sont appliquées pour trouver
une solution quasi-optimale dans un temps de calcul raisonnable, plutôt que des ap
proches déterministes qui garantissent l’optimalité des solutions retournées mais dans
un temps exponentiel.
Dans cette thèse, nous traitons le problème d’optimisation bi-objectif appelé problème
de l’ensemble dominant connexe de cardinalité minimale et de poids minimale(MWM
CDS), qui cherche à minimiser à la fois la cardinalité et le poids total du problème bien
connu en théorie des graphes ; l’ensemble dominant connexe.
Trois algorithmes stochastiques gloutons sont proposés pour résoudre le problème
mentionné. Le premier, GSA, est un recuit simulé standard qui utilise une fonction
objective agrégée pour guider le processus de recherche. Le deuxième, I-NSGA-II,
représente une version améliorée du célèbre algorithme NSGA-II dans le domaine
de l’optimisation multi-objectifs. Le troisième, MGSA, est une nouvelle adaptation
multiobjectif de l’algorithme de recuit simulé basée sur la technique de Pareto. Dans
chacune de ces approches, une heuristique gloutonne est développée et utilisée pour
améliorer l’efficacité de la résolution de problème. Les résultats expérimentaux basés
sur plusieurs métriques de performance montrent que les algorithmes proposés sur
passent les méthodes actuelles de pointe.