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), power dominating set problem, machine scheduling, clique partition and minimum weighted vertex cover. Additionally, the FSS has been adapted for bi-objective optimization and a matheuristic setting. 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, vocabulary building, and consistent chains from tabu search, and relates closely to the matheuristic POPMUSIC paradigm. The idea of observing a solution as a set of elements has also been used in the ant colony optimization algorithm.

Method outline

The FSS algorithm begins by initializing a population of solutions using GRASP, then employs a learning mechanism to generate fixed sets. These fixed sets are iteratively utilized in an enhanced randomized greedy algorithm, which incorporates a predefined selection of elements into each newly generated solution. Each new solution undergoes a local search to improve its quality. Apart from implementing the corresponding GRASP algorithm, several building blocks are necessary for FSS implementation.

Greedy algorithm and local search

The initial building blocks of the FSS are the same as for the GRASP. The first one is a greedy algorithm that can be randomized. The second one is a local search that can be applied to solutions generated in this way. The greedy algorithm should also be adapted to be able to generate solutions containing a pre-selected set of elements. A straightforward example of a greedy algorithm for the minimum vertex cover problem, using a preselected set of elements, might look like this: Rather than starting with an empty set as the initial partial solution, the algorithm begins with a predetermined fixed set.

Ground set

The next step is to use a ground set based formulation of the combinatorial optimization problem of interest. More precisely, any problem solution $S$ must be represented as a subset derived from a ground set of elements $G$. It should be noted that this type of formulation should be possible for any combinatorial optimization problem. For example, in the case of the TSP, defined on a graph, the ground set is the set of all edges. In the case of the minimum vertex cover problem, the ground set is the set of all vertices of the graph.

Generation of fixed sets

The third building block involves defining a method for generating multiple fixed sets $F$ from a population of solutions ${\mathcal {P}}$. This method should generate sets that contain elements that frequently occur in high quality solution. This method should be able to control the size of the fixed set ($|F|$). When integrating a fixed set $F$ into the randomized greedy algorithm, it must be capable of producing a feasible solution of equal or superior quality to those in the current population of solutions ${\mathcal {P}}$. In the following text the method for generating such fixed sets is given.

Let ${\mathcal {P}}_{n}=\{S_{1},S_{2},..,S_{n}\}$ represent the set of $n$ best (based on the objective function) solutions generated in previous steps. A base solution $B$ is a randomly selected solution from these best $n$ solutions. If a fixed set $F$ satisfies $F\subseteq B$, it can potentially generate a feasible solution of at least the same quality as $B$, and $F$ can include any number of elements from $B$. The objective is for $F$ to contain elements that frequently appear across a collection of high-quality solutions. In relation, let us define ${\mathcal {P}}_{kn}$ as the set of $k$ randomly selected solutions from the $n$ best ones, $P_{n}$.

Using these building blocks it is possible to define a function $Fix(B,{\mathcal {P}}_{kn},Size)$ for generating a fixed set $F\subseteq B$ that consists of $Size$ elements of the base solution $B=\{e_{1},e_{2},...,e_{l}\}$ that most frequently occur in the set of test solutions $P_{kn}$. Let use define the function $C(e,S)$, for an element $e\in G$ and a solution $S\subset G$ , which is equal to $1$ if $e\in S$ and $0$ otherwise. We can define a function that counts the number of occurrences of an element $e$ in the elements of the set ${\mathcal {P}}_{kn}$ using the function $C(e,S)$ as follows.

$$O(e,{\mathcal {P}}_{kn})=\sum _{S\in {\mathcal {P}}_{kn}}C(e,S)\qquad \qquad (1)$$

Now, we can define $Fix(B,P_{kn},Size)$ as the set of $Size$ elements $e\in B$ that have the largest value of $O(e,{\mathcal {P}}_{kn})$. A graphical illustration of the method for generating fixed sets can be seen in following figure.

A graphical illustration of the method for generating fixed sets for the minimum vertex cover problem. It is assumed that the fixed set is selected for the best $n=6$ solutions ($P_{6}$), $k=4$ test solutions ($P_{46}$) are used and the size of the fixed set is $Size=4$. On the left side each solution corresponds to the blue colored vertices. In the base solution ($B$) the values in the blue vertices are equal to the number of occurrences of these vertices in the set of test solutions (values of $C(e,P_{46})$). On the right side is the selected fixed set ($Fix(B,{\mathcal {P}}_{46},4)$), dashed blue vertices, is equal to $Size=4$ elements that occur the most frequently in the test set of solutions $P_{46}$.

Learning mechanism

The learning mechanism in the FSS is facilitated through fixed sets. To achieve this, the randomized greedy algorithm from the GRASP is adapted to incorporate preselected elements that must be included in newly generated solutions. We denote the solution generated with such an randomized greedy algorithm with a fixed (preselected) set of elements $F$ as $RGF(F)$.

In FSS, akin to GRASP, solutions are iteratively generated and subjected to local search. Initially, a population of solutions $P$ is created by executing $N$ iterations of the GRASP algorithm. This population is then used to randomly generate a fixed set $F$ of size $Size$, following the method outlined in the preceding section. $F$ is utilized to produce a new solution $S=RGF(F)$, upon which local search is applied. The population is expanded with these newly generated locally optimal solutions. This cycle continues until no new best solutions are discovered for an extended period, signifying stagnation. At this point, the size of the fixed set may be increased if stagnation persists. If the maximum allowed size is reached, the fixed set size resets to the minimum allowed value. This iterative process continues until a stopping criterion is met.

An essential aspect of the algorithm is defining the array of permissible fixed set sizes, tied to the fixed part of the solution. In our implementation, this array is defined as

$$Coefs[i]=1-{\frac {1}{2^{i}}}\qquad \qquad (2)$$

The size of fixed sets used is proportional to the base solution $B$, specifically $Coefs[i]|B|$ at the $i$-th level.

Algorithm

The FSS uses the following set of parameters:

• $N$ the number of iterations performed by the GRASP to generate the initial population of solutions
• The number of best solutions $n$, related to ${\mathcal {P}}_{n}$, that is considered in generating the fixed set.
• The number of test solutions $k$, related to ${\mathcal {P}}_{kn}$, used when generating the fixed set
• The number of iterations ($Stag$) without change to ${\mathcal {P}}_{n}$after which the FSS is considered stagnant.
• Parameters related to the randomization of the greedy algorithm

The FSS is best understood by observing its pseudocode.

Initialize Coefs
Coef = Coefs[1]
Generate initial population P using GRASP(N)
while (Not termination condition) do
    Set P_kn to random k elements of P_n
    Set B to a random solution in P_n
    F = Fix(B, P_kn, Coef*|B|)
    S = RGF(F)
    Apply local search to S
    P = P ∪ {S}
    if no change to P_n in Stag iterations then
        Coef = Coefs.Next
    end if
end while

The first step involves initializing the sizes of fixed sets using using (2), setting the current fixed set size, $Coef$, to its minimum value. The initialization stage proceeds by generating an initial population ${\mathcal {P}}$ through $N$ iterations of the basic GRASP algorithm.

Each iteration within the main loop comprises several steps. Initially, a random set of solutions, $P_{kn}$, is formed by selecting $k$ elements from $P_{n}$, and a random base solution, $B$, is chosen from the set $P_{n}$. Subsequently, the $Fix(B,P_{kn},Coef|B|)$ function is employed to create a fixed set, $F$. Using $F$, a new solution, $S=RGF(F)$, is generated utilizing the randomized greedy algorithm with preselected elements, followed by applying a local search to $S$. We then assess whether $S$ is the new best solution and include it in the set of generated solutions, ${\mathcal {P}}$. If stagnation is detected, $Coef$ is incremented to the next value in $Coefs$, with $Coef$ being the next larger element in the $Coefs$ array. If $Coef$ has already reached its maximum, we reset it to the smallest element in $Coefs$. This process continues until a termination criterion is met.

See also

See also: Ant colony optimization algorithms, Variable neighborhood search, and Greedy randomized adaptive search procedure