[ca] En aquest treball presentem una proposta algorítmica basada en l'Artificial Bee Colony per al problema dels nodes crítics, anomenada ABCCNP. El problema dels nodes crítics en xarxes (en anglès the Critical Node Problem -CNP-) és un conegut problema d'optimització combinatòria NP-complet que ha atret molta atenció investigadora recentment degut al seu gran nombre d'aplicacions en el món real. Essencialment, el problema tracta de trobar un subconjunt de com a molt k nodes, l'eliminació dels quals degrada al màxim la connectivitat entre parells de nodes del graf resultant. Nombrosos autors han proposat solucions per al CNP en la literatura fent ús d'algorismes exactes, algorismes greedy i conegudes metaheurístiques com el Simulated Annealing, Variable Neighborhood Search, etc. Recentment, s'han presentat molts estudis exitosos que han donat solució a desafiadors problemes d'optimització fent ús de tècniques metaheurísitques de Swarm Intelligence inspirades en el comportament col·lectiu de societats d'animals. Un exemple és l'algorisme d'Artificial Bee Colony que s'inspira en el comportament de cerca d'aliment dels eixams naturals d'abelles mel·líferes. En aquest estudi adaptem l'algorisme base d'ABC per al CNP proposant dos avançats algorismes de construcció de fonts d'alimentació i de cerca local, fent ús d'un conjunt de paràmetres de control per obtenir el millor balanç entre exploració i explotació de solucions. La qualitat de l'ABCCNP és avaluada sobre un conegut conjunt d'instàncies de xarxes aleatòries i comparada amb els altres algorismes de l'estat de l'art. Els resultats obtingut demostren que es tracta d'una solució molt competitiva en molts aspectes.

[en] In this paper we present an algorithmic approach based on the Artificial Bee Colony for the critical node problem, called ABCCNP. The Critical Node Problem (CNP) is a well-known NP-complete combinatorial optimisation problem that has attracted a lot of research attention recently due to the large number of real-world applications. The problem is about finding a subset of at most k nodes, whose deletion maximally degrades the connectivity between pairs of nodes in the resulting graph. Numerous authors have proposed solutions for the CNP in the literature using exact algorithms, greedy algorithms and some wellknown metaheuristics like Simulated Annealing, Variable Neighborhood Search, etc. Recently, many successful studies have been presented solving challenging optimisation problems using Swarm Intelligence metaheuristic techniques that are inspired by the collective behaviour of animal societies. One example is the Artificial Bee Colony algorithm that is specifically inspired by the foraging behaviour of natural honeybees. In this study, we adapt the base ABC algorithm for the CNP by proposing two advanced algorithms for the construction of food sources and local foraging, making use of a set of control parameters to obtain the best balance between exploration and exploitation. The quality of ABCCNP is evaluated on a set of random network instances and compared with other state-of-the-art algorithms. The results obtained show that it is a very competitive solution in many aspects.