Keywords

1 Introduction

Optimization problems require complex and optimal solutions because they relate to distribute limited basic resources. To resolve these problems it means improving the lives of poor people directly and enabling the growth of businesses, for example: resources related to social welfare, reaction by natural disasters, medical distribution capabilities. For these reasons the optimization generates a wide area of research in the sciences of Operations Research and Computer.

In the last decades bio-inspired algorithms have called the attention of researchers, in particular the heuristic Particle Swarm Optimization, which is based the behavior of some species: Bugs, fish, felines. These species use the collective intelligence to reach specific objectives guided by some community member. This paper is focused on studying the heuristic based on the behavior of domestic cats to solve a classical problem the Set Covering Problem (SCP).

2 Multi Objective

Decision problems involves multiple evaluation criteria and generally they are in conflict. To resolve a multi objective problem it required to optimize multiple criteria simultaneously. Exists a wide variety of cases in our society, for example: vehicle route optimization, environmental problems, allocation of medical resources. The solution to multi-objective optimization problem it is presented by a set of feasible solutions, and the best of them define a set of non-dominated solutions, this set we will call Front. Formally the multi objective problem is defined as:

$$\begin{aligned} min\;\;\;z(x)\;=\;[z_1(x),z_2(x),z_3(x),z_4(x),.....,z_M(x)] \end{aligned}$$
(1)

The goal consists in minimizing a function z with M components with a vector variable x = (\(x_1\), . . . , \(x_n\)) in a universe U, i.e., A solution u dominates v if u performs at least as well as v across all the objectives and performs better than v in at least one objective.

2.1 Objective Space

The dimensions of the target area corresponding to the number of functions to optimize. In this single-objective problem is one-dimensional space, since each decision vector corresponds to only a scalar number. In multi-objective problems, this is multi-dimensional space, where each dimension corresponds to each objective function to be optimized.

2.2 Pareto Dominance

If we have two candidate solutions u and v from U, vector z(u) is said to dominate vector z(v) denoted by: z(u) \(\prec \) z(v), if and only if,

$$\begin{aligned} z_i(u)\;\le \;z_i(v),\;\;\;\;\;\;\;\forall \;i\;\in \;\{1,......,M\} \end{aligned}$$
(2)
$$\begin{aligned} z_i(u)\;\le \;z_i(v),\;\;\;\;\;\;\;\exists \;i\;\in \;\{1,......,M\} \end{aligned}$$
(3)

If solution u is not dominated by any other solution, then u is declared as a Non Dominated or Pareto Optimal Solution. There are no superior solutions to the problem than u, although there may be other equally good solutions (3).

3 Set Covering Problem

SCP is defined as a fundamental problem in Operations Research and often described as a problem of coverage of m-rows n-columns of a binary matrix by a subset of columns to a minimum cost [1]. It is one of Karp’s 21 NP-complete problems. This is the problem of covering the rows of an m-row, n column, zero-one m x n matrix \(a_{ij}\) by a subset of the columns at minimal cost. Formally, the problem can be defined as:

Defining \(x_j\) = 1 if column j with cost \(c_j\) is in the solution and \(x_j\) = 0 otherwise

$$\begin{aligned} \textit{Minimize}\, \ Z = \sum _{j=1}^n c_j x_j \;\;\;\;\;\;\;\; j\in \{ 1, 2, 3, ... , n \} \end{aligned}$$
(4)

Subject to:

$$\begin{aligned} \sum _{j=1}^n a_{ij} x_j \ge 1 \;\;\;\;\;\;\;\; i\in \{ 1, 2, 3, ... , m \} \end{aligned}$$
(5)
$$\begin{aligned} x_j = \{0,1\} \end{aligned}$$
(6)

This definition contains a one fitness function, there is just one objective to be optimized. We study the case for two objective functions, using meta heuristic Cat Swarm Optimization (CSO) and using position vector of ones and zeros. A complete case study of SCP using CSO was done Pontificia Universidad Cátolica de Valparaíso [2].

3.1 Set Covering Problem Bi Objective (SCPBO)

This work focuses on solving the SCP with two fitness functions, i.e., textit M = 2. To ensure the fitness functions have opposed criteria the second cost vector will be transposed the first, therefore the definition will be:

$$\begin{aligned} c_2\;=\;(c_1)^t \end{aligned}$$
(7)
$$\begin{aligned} min\;\;\;z(x)\;=\;[z_1(x),z_2(x)] \end{aligned}$$
(8)
$$\begin{aligned} \textit{Minimize}\, \ Z_1 = \sum _{j=1}^n c^1_j x_j \;\;\;\;\;\;\;\; j\in \{ 1, 2, 3, ... , n \} \end{aligned}$$
(9)
$$\begin{aligned} \textit{Minimize}\, \ Z_2 = \sum _{j=1}^n c^2_j x_j \;\;\;\;\;\;\;\; j\in \{ 1, 2, 3, ... , n \} \end{aligned}$$
(10)

Subject to:

$$\begin{aligned} \sum _{j=1}^n a_{ij} x_j \ge 1 \;\;\;\;\;\;\;\; i\in \{ 1, 2, 3, ... , m \} \end{aligned}$$
(11)

4 Cat Swarm Optimization CSO

Some species of felines shows similar behavior when they are hunting, commonly hunt in packs, some of them remain on alert and others run after their prey. They work with a common purpose, the prey. The CSO was introduced was in 2016 original version of CSO by Chu, Tsai, and Pan. They observed the behavior of the cats and modeled their behavior. Based on their studies they suggested that cats have two modes of behavior:

  1. (a)

    Seeking mode: Cat spends most of the time when they are awake on resting. While they are resting, they move their position carefully and slowly.

  2. (b)

    Tracing mode: cats change their position according to its own velocities for every dimension.

These states have been mathematically modeled y both sets of cats are used to reach a goal, that is, hunt prey. The position of each cat represent a solution set, has position and velocity for each dimension and a fitness value. Additionally a flag is used to identify whether the cat is in seeking mode or tracing mode. [3, 4] have shown that the CSO performs better than PSO with respect to convergence speed and residual mean square error, but it requires higher computation time.

4.1 Algorithm

The CSO algorithm works with a set of parameters that configure the behavior of the pack:

  • NC: Number of population or pack cats

  • MR: Mixture Rate that defines number of cats mode, this parameter must be chosen between 0 and 1. Define what percentage of cats are in seeking mode and tracing mode

Both group works with a reaches its optimal solution. The flowchart of this algorithm is shown in Fig. 1 and the and a description of the actions are outlined below.

Fig. 1
figure 1

Experimental workflow

Full size image
  1. (a)

    Randomly initialize the position of cats in D-dimensional space i.e. \(X_{id}\) representing position of i th cat in d th dimension.

  2. (b)

    Randomly initialize the velocity of cats i.e. \(V_{id}\).

  3. (c)

    According to MR, cats are randomly picked from the population and their flag is set to seeking mode, and for others the flag is set to tracing mode.

  4. (d)

    Evaluate both objective function for each cat.

  5. (e)

    Store the position of the cats representing non-dominated solutions in the archive.

  6. (f)

    If ith cat is in seeking mode, apply the cat to the seeking mode process, otherwise apply it to the tracing mode process. Check the termination condition, if satisfied, terminate the program. Otherwise repeat steps c to e.

4.2 Seeking Mode

The seeking mode corresponds to a global search technique in the search space of the optimization problem. A term used in this mode is seeking memory pool (SMP). It is the number of copies of a cat produced in seeking mode.

There are four essential factors in this mode: seeking memory pool (SMP), seeking range of the selected dimension (SRD), counts of dimension to change (CDC), and self-position considering (SPC).

  • SMP is used to define the size of seeking memory for each cat. SMP indicates the points explored by the cat. This parameter can be different for different cats.

  • SRD declares the mutation ratio for the selected dimensions.

  • CDC indicates how many dimensions will be varied.

  • SPC is a Boolean flag, which decides whether current position of cat

The steps involved in this mode are:

  1. (a)

    Create T (=SMP) copies of j th cat i.e. \(Y_kd\) where (\(1 \le k \le T\)) and (\(1 \le d \le D\)). D is the total number of dimensions.

  2. (b)

    Apply a mutation operator to \(Y_k\).

  3. (c)

    Evaluate the fitness of all mutated copies.

  4. (d)

    Update the contents of the archive with the position of those mutated copies which represent non dominated solutions.

  5. (e)

    Pick a candidate randomly from T copies and place it at the position of jth cat.

4.3 Tracing Mode [4]

The tracing mode corresponds to a local search technique for the optimization problem. In this mode, the cat traces the target while spending high energy. The rapid chase of the cat is mathematically modeled as a large change in its position. Define position and velocity of ith cat in the D-dimensional space as \(X_i=(X_{i1},X_{i2},X_{i3} \ldots X_{iD})\) and \(V_i=(V_{i1},V_{i2},V_{i3} \ldots V_{iD})\) where (\(1 \le d \le D\)) represents the dimension. The global best position of the cat swarm is represented as \(X_g=(X_{g1},X_{g2}, X_{g3} \ldots X_{gD})\). The steps involved in tracing mode are:

  1. (a)

    Compute the new velocity of ith cat using (13)

    $$\begin{aligned} V_{id}\;=\,w\;*\;V_{id}\;+\;c\;*\;r\;*(X_{gd}\;-\;X_{id}) \end{aligned}$$
    (12)

    where

    • w = is the inertia weight

    • c = is the acceleration constant

    • r = is a random number uniformly distributed in the range [0, 1]

  2. (b)

    Compute the new position of ith cat using

    $$\begin{aligned} V_{id}\;=\,X_{gd}\;-\;X_{id} \end{aligned}$$
    (13)
  3. (c)

    If the new position of ith cat corresponding to any dimension goes beyond the search space, then the corresponding boundary value is assigned to that dimension and the velocity corresponding to that dimension is multiplied by \(-1\) to continue the search in the opposite direction.

  4. (d)

    Evaluate the fitness of the cats.

  5. (e)

    Update the contents of the archive with the position of those cats which represent no dominated vectors.

4.4 Flow Chart Diagram

The Fig. 1 shows the flow of processes to solve SCP-BO. The parameter that produces a greater quantity of solutions, is MR. It was determined experimentally, from 0.5 until 0.9. For this experiment we define an increment of 0.1

  1. (a)

    Initiate \(MR_p\) in min value (\(=0.5\))

  2. (b)

    Create the cat swam, N cats working to solve the problem

  3. (c)

    Define, randomly the position and velocity for each cat

  4. (d)

    Distribute the swarm in tracing and seeking mode based on MR

  5. (e)

    Check if the cat is feasible solution (Eq. 11). if the cat satisfies the restriction compute the fitness (Eqs. 9 and 10) and compare with the non dominated solutions in the archive

  6. (f)

    Update de solution file

  7. (g)

    If number iteration less than the max iteration continue work, goto step c

  8. (h)

    If \(MR_p\) less than max value MR, increment \(MR_p\) and go to step b

  9. (i)

    Calculate the pareto front from non domination file

5 Experimental Results

The BCSO was evaluated using the next features:

  1. (a)

    Using 4 of 65 Instances for set covering from OR-Library of Beasley [5]

  2. (b)

    MacBook Pro (13-inch, Mid 2012), CPU MacBook Pro (13-inch, Mid 2012), 16 GB 1333 MHz DDR3, OS X Yosemite, version 10.10.5

  3. (c)

    IDE: BlueJ version 3.1.5 (Java version 1.8.0_31)

The working conditions of the process were:

  1. (a)

    1.500 iterations for each varying from MR \(=0.5\) until MR \(=0.7\), using an increment 0.1

  2. (b)

    30 times each Beasly instance

  3. (c)

    The Optimal Pareto Front for each instance was obtained varying MR from 0.1 until 0.99 and determined by the union of fronts obtained MR

  4. (d)

    The parameters used BCO was obtained from [2, 4] and show in Tables 1 and 2

Table 1 Parameter values CSO
Full size table
Table 2 Experimental results: MAX, MIN, PROM, DESV in sec
Full size table

6 Conclusion

There are not published results on a SCP Bi Objective. We think the Pareto Front is quite promising considering just we varied only MR. We also believe varying the population of cats with the best value of MR, we will improve the results. In this first phase of our research we only work with MR parameters, however we think that using adaptive techniques for parameters: seeking memory pool (SMP), seeking range of the selected dimension (SRD), counts of dimension to change (CDC), and self-position considering, we improve our results.

The next step:

  1. (a)

    To use adaptive techniques for CSO parameters

  2. (b)

    To obtain a Pareto optimal front using GA and PSO algorithm

in this work an analysis of quality of results should be done using the metric of comparison. The hypervolume considers aspects of convergence and diversity in a particular front, which would be a good metric to evaluate our results [6].