Um Algoritmo Híbrido para o Problema da Clique Máxima / A Hybrid Algorithm for the Maximum Clique Problem

Murilo Oliveira Machado, Thiago Soares Marques, Elizabeth Ferreira Gouvea Goldbarg, Marcos Cesar Gouvea Goldbarg

Abstract


Este artigo apresenta um algoritmo que realiza a hibridização entre a meta-heurística Simulated Anneling e uma Lista Tabu para resolver o problema da clique máxima. O algoritmo foi avaliado mediante os resultados obtidos para o banco de instâncias do Centro de matemática discreta e ciência da computação teórica (DIMACS). O algoritmo consegue processar um total de 83% das instâncias em menos de 2 minutos e obtém o valor ótimo para 74,6%. Os resultados mostraram-se promissores em contraste com as observações realizadas na literatura. Em comparação com o resultado recente publicado, a média da solução do algoritmo aqui apresentado foi estritamente melhor em 52,11% e empataram em 21,1% das instâncias.


Keywords


Problema da Clique Máxima, Simulated Anneling, Lista Tabu, Algoritmos Híbridos

References


KARP, R. M. Reducibility among combinatorial problems. In:. Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, and sponsored by the Office of Naval Research, Mathematics Program, IBM World Trade Corporation, and the IBM Research Mathematical Sciences Department. Boston, MA: Springer US, 1972.

p. 85–103. ISBN 978-1-4684-2001-2. doi.org/10.1007/978-1-4684-2001-2 9i.

TOMITA, E.; SEKI, T. An efficient branch-and-bound algorithm for finding a maximum clique. In: CALUDE, C. S.; DINNEEN, M. J.; VAJNOVSZKI, V. (Ed.). Discrete Mathematics and Theoretical Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. p. 278–289. ISBN 978-3-540-45066-5.

WU, Q.; HAO, J.-K. A review on algorithms for maximum clique problems. European Journal of Operational Research, v. 242, n. 3, p. 693 – 709, 2015. ISSN 0377-2217. Disponı́vel em: hhttp://www.sciencedirect.com/science/ article/pii/S0377221714008030i.

Li, X. et al. A distributed transmission scheduling algorithm for wireless networks based on the ising model. In: 2018 IEEE Statistical Signal Processing Workshop (SSP). [S.l.: s.n.], 2018. p. 6–10. ISSN null.

DOUIK, A. et al. A Tutorial on Clique Problems in Communications and Signal Processing. 2018.

DOUIK, A. et al. Delay reduction in multi-hop device-to-device communication using network coding. IEEE Transactions on Wireless Communications, PP, 09 2014

CHO, S.; BYUN, H. A space-time graph optimization approach based on maximum cliques for action detection. IEEE Transactions on Circuits and Systems for Video Technology, v. 26, n. 4, p. 661–672, April 2016. ISSN 1558-2205.

WONG, S. W. et al. Modeling tumor progression via the comparison of stage-specific graphs. Methods, v. 132, p. 34 –41, 2018. ISSN 1046-2023. Comparison and Visualization Methods for High-Dimensional Biological Data.

CHAPUIS, G. et al. Finding maximum cliques on a quantum annealer. In: Proceedings of the Computing Frontiers Conference. New York, NY, USA: Association for Computing Machinery, 2017. (CF’17), p. 63–70. ISBN 9781450344876.doi.org/10.1145/3075564.3075575i.

PELOFSKE, E.; HAHN, G.; DJIDJEV, H. Solving large maximum clique problems on a quantum annealer. In: FELD, S.; LINNHOFF-POPIEN, C. (Ed.). Quantum Technology and Optimization Problems. Cham: Springer International Publishing, 2019. p. 123–135. ISBN 978-3-030-14082-3.

CAVIQUE L.; REGO, C. T. Estruturas de vizinhança e procura local no problema da clique máxima. Investigação Operacional, v. 22, p. 1–18, 2002.

JOHNSON, D. J.; TRICK, M. A. Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. USA: American Mathematical Society, 1996. ISBN 0821866095.

BATTITI, R.; PROTASI, M. Reactive local search for the maximum clique problem 1. Algorithmica, Springer, v. 29, n. 4, p. 610–637, 2001.

KATAYAMA, K.; HAMAMOTO, A.; NARIHISA, H. An effective local search for the maximum clique problem. Information Processing Letters, v. 95, n. 5, p. 503 – 511, 2005. ISSN 0020-0190.

PULLAN, W.; MASCIA, F.; BRUNATO, M. Cooperating local search for the maximum clique problem. Journal of Heuristics, Springer, v. 17, n. 2, p. 181–199, 2011.

ASSAD, A.; DEEP, K. A heuristic based harmony search algorithm for maximum clique problem. OPSEARCH, v. 55, n. 2, p. 411–433, Jun 2018. ISSN 0975-0320.

PARDALOS, P.; XUE, J. The maximum clique problem. Journal of Global Optimization, v. 4, p. 301–328, 04 1994.

BOMZE, I. M. et al. The maximum clique problem. In: . Handbook of Combinatorial Optimization: Supplement Volume A. Boston, MA: Springer US, 1999. p. 1–74. ISBN 978-1-4757-3023-4.

BUTENKO, S.; PARDALOS, P. M. Maximum Independent Set and Related Problems, with Applications. Tese (Doutorado)

— University of Florida, USA, 2003. AAI3120100.

BABEL, L.; TINHOFER, G. A branch and

bound algorithm for the maximum clique problem. Zeitschrift für Operations Research, v. 34, n. 3, p. 207–217, May 1990. ISSN 1432-5217.

FAHLE, T. Simple and fast: Improving a branch-and-bound algorithm for maximum clique. In: MÖHRING, R.; RAMAN, R. (Ed.). Algorithms — ESA 2002. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. p. 485–498. ISBN 978-3-540-45749-7.

SORIANO, P.; GENDREAU, M. Tabu search algorithms for the maximum clique problem. v. 26, 01 1994.

GENDREAU, M.; SORIANO, P.; SALVAIL, L. Solving the maximum clique problem using a tabu search approach. Annals of Operations Research, v. 41, n. 4, p. 385–403, Dec 1993. ISSN 1572-9338.

WU, Q.; HAO, J.-K. An adaptive multistart tabu search approach to solve the maximum clique problem. Journal of Combinatorial Optimization, v. 26, 07 2013.

SOLNON, C.; FENET, S. A study of aco capabilities for solving the maximum clique problem. Journal of Heuristics, v. 12, n. 3, p. 155–180, May 2006. ISSN 1572-9397.

HOMER, S.; PEINADO, M. Experiments with polynomial-time clique approximation algorithms on very large graphs. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, v. 26, p. 147–168, 1996.

DUAN, H. et al. Three-dimension path planning for ucav using hybrid meta-heuristic aco-de algorithm. Simulation Modelling Practice and Theory, v. 18, n. 8, p. 1104 – 1115,

ISSN 1569-190X. Modeling and Simulation for Complex System Development.

HOMBERGER, J.; GEHRING, H. A two-phase hybrid metaheuristic for the vehicle routing problem with time windows. European Journal of Operational Research, Elsevier, v. 162, n. 1, p. 220–238, 2005.

RIOS , B. H. O.; GOLDDARG, E. F. G.; Quesquén, G. Y. O. A hybrid metaheuristic using a corrected formulation for the traveling car renter salesman problem. In: 2017 IEEE Congress on Evolutionary Computation (CEC). [S.l.: s.n.], 2017. p. 2308–2314.

FERNANDES, I. F. d. C. Meta-heurı́sticas hı́bridas aplicadas ao problema da árvore geradora multiobjetivo. Dissertação (Mestrado) , Brasil, 2018.

CARRAGHAN, R.; PARDALOS, P. M. An exact algorithm for the maximum clique problem. Operations Research Letters, v. 9, n. 6, p. 375 – 382, 1990. ISSN 0167-6377.

FRIDEN, C.; HERTZ, A.; WERRA, D. de.Stabulus: A technique for finding stable sets in large graphs with tabu search. Computing, v. 42, n. 1, p. 35–44, Mar 1989. ISSN 1436-5057.

FLEURENT, C.; FERLAND, J. A. Genetic and hybrid algorithms for graph coloring. Annals of Operations Research, v. 63, n. 3, p. 437–461, Jun 1996. ISSN 1572-9338.

JAGOTA, A.; SANCHIS, L. A. Adaptive, restart, randomized greedy heuristics for maximum clique. Journal of Heuristics, v. 7, n. 6, p. 565–585, Nov 2001.

GROSSO, A.; LOCATELLI, M.; CROCE,

F. D. Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem. Journal of Heuristics, v. 10, n. 2, p. 135–152, Mar 2004. ISSN 1572-9397.

ORDÓÑEZ-GUILLÉN, N.; MARTÍNEZ-PéREZ, I. Heuristic search space generation for maximum clique problem inspired in biomolecular filtering. Journal of Signal Processing Systems, v. 83, 08 2015.

ZÜGE, A. P.; CARMO, R. On comparing algorithms for the maximum clique problem. Discrete Applied Mathematics, Elsevier, v. 247, p. 1–13, 2018.

BRÉLAZ, D. New methods to color the vertices of a graph. Communications of the ACM, ACM New York, NY, USA, v. 22, n. 4, p. 251–256, 1979.

ÖSTERGÅRD, P. R. A fast algorithm for the maximum clique problem. Discrete Applied

Mathematics, Elsevier, v. 120, n. 1-3, p. 197–207, 2002.

KONC, J.; JANEZIC, D. An improved branch and bound algorithm for the maximum clique problem. proteins,v. 4, n. 5, 2007.

TOMITA, E.; KAMEDA, T. An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. Journal of Global optimization,

Springer, v. 37, n. 1, p. 95–111, 2007.

TOMITA, E. et al. A simple and faster branch-and-bound algorithm for finding a maximum clique. In: SPRINGER. International Workshop on Algorithms and Computation.[S.l.], 2010. p. 191–203.

LÓPEZ-IBÁÑEZ, M. et al. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, v. 3, p. 43 – 58, 2016. ISSN 2214-7160.




DOI: https://doi.org/10.34117/bjdv6n6-275

Refbacks

  • There are currently no refbacks.