Back

Draft:Fixed set search

  • Comment: Possible COI issues. The majority of the sources appear to be written by the same author. Shadow311 (talk) 00:28, 24 April 2024 (UTC)


The fixed set search (FSS) is a metaheuristic that has been effectively applied to various combinatorial optimization problems, including the traveling salesman problem (TSP)[1], machine scheduling[2], clique partition[3], interconnected facility problem[4] and minimum weighted vertex cover[5]. Additionally, the FSS has been adapted for bi-objective optimization[5] and a matheuristic setting[6]. As a population-based metaheuristic integrating a local search, FSS is particularly effective for problems where local search methods excel. FSS enhances the Greedy randomized adaptive search procedure (GRASP) metaheuristic by adding a learning mechanism to it. The GRASP involves iteratively generating solutions using a randomized greedy algorithm and refining each of the solutions with a local search.

The FSS is inspired by the observation that high-quality solutions often share common elements. The core strategy of FSS is to identify these shared elements—termed the "fixed set"—and incorporate them into newly generated solutions. This approach focuses computational efforts on completing these partial solutions by "filling in the gaps." This concept draws on earlier metaheuristic strategies such as chunking[7] and vocabulary building[8]. The idea of observing a solution as a set of elements has also been used in the ant colony optimization and worm optimization[9] metaheuristics. Note that matheuristic techniques, such as Kernel Search[10] and Heuristic Concentration[11], employ a similar strategy of generating numerous solutions to identify common elements in high-quality ones.

  1. ^ Jovanovic, Raka; Tuba, Milan; Voß, Stefan (2019), Blesa Aguilera, Maria J.; Blum, Christian; Gambini Santos, Haroldo; Pinacho-Davidson, Pedro (eds.), "Fixed Set Search Applied to the Traveling Salesman Problem", Hybrid Metaheuristics, vol. 11299, Cham: Springer International Publishing, pp. 63–77, arXiv:1809.04942, doi:10.1007/978-3-030-05983-5_5, ISBN 978-3-030-05982-8, retrieved 2024-04-19
  2. ^ Jovanovic, Raka; Voß, Stefan (2021-10-01). "Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times". Applied Soft Computing. 110: 107521. doi:10.1016/j.asoc.2021.107521. ISSN 1568-4946.
  3. ^ Jovanovic, Raka; Sanfilippo, Antonio P.; Voß, Stefan (2023-08-16). "Fixed set search applied to the clique partitioning problem". European Journal of Operational Research. 309 (1): 65–81. doi:10.1016/j.ejor.2023.01.044. ISSN 0377-2217.
  4. ^ Lozano-Osorio, Isaac; Sánchez-Oro, Jesús; Martínez-Gavara, Anna; López-Sánchez, Ana D.; Duarte, Abraham (2023). "An Efficient Fixed Set Search for the Covering Location with Interconnected Facilities Problem". In Di Gaspero, Luca; Festa, Paola; Nakib, Amir; Pavone, Mario (eds.). Metaheuristics. Lecture Notes in Computer Science. Vol. 13838. Cham: Springer International Publishing. pp. 485–490. doi:10.1007/978-3-031-26504-4_37. ISBN 978-3-031-26504-4.
  5. ^ a b Jovanovic, Raka; Sanfilippo, Antonio P.; Voß, Stefan (2022-08-01). "Fixed set search applied to the multi-objective minimum weighted vertex cover problem". Journal of Heuristics. 28 (4): 481–508. doi:10.1007/s10732-022-09499-z. ISSN 1572-9397.
  6. ^ Jovanovic, Raka; Voß, Stefan (2024-02-12). "Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets". OR Spectrum. doi:10.1007/s00291-024-00746-2. ISSN 1436-6304.
  7. ^ Woodruff, David L (1998-04-16). "Proposals for chunking and tabu search". European Journal of Operational Research. 106 (2): 585–598. doi:10.1016/S0377-2217(97)00293-2. ISSN 0377-2217.
  8. ^ Sondergeld, Lutz; Voß, Stefan (1999), Voß, Stefan; Martello, Silvano; Osman, Ibrahim H.; Roucairol, Catherine (eds.), "Cooperative Intelligent Search Using Adaptive Memory Techniques", Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Boston, MA: Springer US, pp. 297–312, doi:10.1007/978-1-4615-5775-3_21, ISBN 978-1-4615-5775-3, retrieved 2024-05-10
  9. ^ Arnaout, Jean-Paul (2020-02-01). "A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times". Annals of Operations Research. 285 (1): 273–293. doi:10.1007/s10479-019-03138-w. ISSN 1572-9338.
  10. ^ Angelelli, Enrico; Mansini, Renata; Grazia Speranza, M. (2010-11-01). "Kernel search: A general heuristic for the multi-dimensional knapsack problem". Computers & Operations Research. Metaheuristics for Logistics and Vehicle Routing. 37 (11): 2017–2026. doi:10.1016/j.cor.2010.02.002. ISSN 0305-0548.
  11. ^ Rosing, K. E.; ReVelle, C. S. (1997-02-16). "Heuristic concentration: Two stage solution construction". European Journal of Operational Research. 97 (1): 75–86. doi:10.1016/S0377-2217(96)00100-2. ISSN 0377-2217.

Rich TVX News Network Site

Rich TVX News Network Info

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search