# A Population and Interval Constraint Propagation Algorithm for Multi-objective Optimization

Vincent Barichard, Jin-Kao Hao

<figure><img src="image_1.png" /></figure>

## To cite this version:

Vincent Barichard, Jin-Kao Hao. A Population and Interval Constraint Propagation Algorithm for Multi-objective Optimization. The Fifth Metaheuristics International Conferences, Aug 2003, Kyoto, Japan. hal-04031144

HAL Id: hal-04031144

https://univ-angers.hal.science/hal-04031144

Submitted on 15 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
0pt0pt
# A Population and Interval Constraint Propagation Algorithm for Multi-objective Optimization

Vincent Barichard*

Jin-Kao Hao*

*LERIA - Faculty of Sciences - University of Angers
2, Boulevard Lavoisier, 49045 Angers Cedex 01, France
{Vincent.Barichard,Jin-Kao.Hao}@info.univ-angers.fr

## 1 Introduction

The multi-objective combinatorial optimization problems aim to model real world problems that involve many criteria and constraints. In this context, the optimum solution searched is not a single value but a set of good compromises or “trade-offs” that all satisfy the constraints.

A constrained continuous multi-objective problem (CCMO) can be defined as follows:

$$ \text{CCMO} \begin{cases} \min & f_i(\vec{x}) & i = 1, \dots, o \\ \text{s.t.} & C_l(\vec{x}) \ge 0 & l = 1, \dots, m \\ & \vec{x} \in \mathbb{R}^n \end{cases} $$

where $n$ is the number of variables, $\vec{x}$ is a decision vector, $o$ the number of objectives and $m$ the number of constraints of the problem.

Over the past few years, a number of evolutionary algorithms have been developed for multi-objective optimization problems [8, 6, 9, 7, 10, 2] showing promising results.

Unfortunately, when the constraints become difficult to satisfy, or when the feasible objective space is not connected, multi-objective evolutionary algorithms hardly converge to the whole Pareto optimal front. Furthermore, these algorithms don't give any bounds of the optimal front.

In this paper, we present PICPA, the “Population and Interval Constraint Propagation Algorithm” which is able to produce high quality approximate solutions while giving guaranteed bounds for the Pareto optimal front. These bounds allow us to know whether the heuristic solutions are close to or far away from the optimal front. PICPA combines “Interval Constraint Propagation” (ICP) techniques [1, 3] with evolutionary concepts (population and Pareto selection process). Experimental evaluations of PICPA on some well known test problems show its effectiveness.

Kyoto, Japan, August 25–28, 2003
## 2 Population and Interval Constraint Propagation Algorithm (PICPA)

The concept of population is very suitable in a multi-objectives context. Indeed, as the Pareto optimal front is most of the time a set of solutions, each individual of the population can hopefully become a particular solution of the Pareto optimal front. As a result, the whole population will be an approximation of the targeted Pareto optimal front.

In this section, we present the *PICPA* algorithm which combines interval constraint propagation with a population.

### 2.1 A new dominance relation definition

*PICPA* uses a new dominance relation: the Point with Set dominance (PS-dominance). The PS-Dominance is based on the classical “point to point” dominance relation.

**Definition 1 (PS-Dominance)** *For any vector $\vec{x}$ and any vector set $\{\vec{y}\}, |\{\vec{y}\}| > 0$:*

$\vec{x} \text{ PS-equals } \{\vec{y}\}, \text{ iff } \forall \vec{y} \in \{\vec{y}\} : \vec{x} \text{ equals } \vec{y}$

$\vec{x} \text{ PS-dominates } \{\vec{y}\}, \text{ iff } \forall \vec{y} \in \{\vec{y}\} : \vec{x} \text{ dominates } \vec{y}$

$\vec{x} \text{ is PS-dominated by } \{\vec{y}\}, \text{ iff } \forall \vec{y} \in \{\vec{y}\} : \vec{x} \text{ is dominated by } \vec{y}$

$\vec{x} \text{ is PS-non-dominated by } \{\vec{y}\}, \text{ otherwise}$

The time complexity of the PS-Dominance is in $O(n \times |\{\vec{y}\}|)$ as we have to test $\vec{x}$ with each element of $\{\vec{y}\}$.

Afterwards, we use $[y]$ to denote any interval of $\mathbb{R}$ and $[\vec{y}]$ to denote any *interval vector* of $\mathbb{R}^n$. Furthermore, an *interval vector* of $\mathbb{R}^n$ is also called a box in $\mathbb{R}^n$. So, we can use the PS-Dominance relation between any *decision vector* $\vec{x}$ of $\mathbb{R}^n$ and any box $[\vec{y}]$ of $\mathbb{R}^n$. In this case, the time complexity of the PS-Dominance is in $O(n)$. Indeed, we only need to test the dominance between $\vec{x}$ and the point located at the bottom left corner of $[\vec{y}]$.

### 2.2 Representation of the search and objective space

In most of the population-based algorithms, an individual or configuration of the population is a decision vector, each variable of which being given a single value. Under this representation, each individual corresponds to a particular point in the objective space.

In our approach, each individual is also a vector, but each variable is now represented by an *interval* instead of a single value. Consequently, each individual of the population corresponds now to a box $[\vec{x}]$ of $\mathbb{R}^o$ ($o$ is the number of objectives of the problem) in the objective space.
<figure><img src="image_3.png" /><figcaption>Figure 1: A Pareto selection sample.</figcaption></figure>

## 2.3 Pareto selection of boxes

Consider a set of individuals represented as introduced in Section 2.2. We ensure that all the feasible configurations are contained in the sub-paving described by the population. As a consequence, the Pareto optimal front is also enclosed by the population.

In order to remove the individuals which do not contain any solution of the Pareto optimal front, we apply the following Pareto selection procedure:

1. Try to instantiate all the individuals of the population with bounded local search effort.

2. Apply the PS-Dominance relation 2.1 to remove the individuals which are dominated by another instantiated individual.

At this stage, we get a reduced population of individuals, and we ensure that the union of these boxes (or individuals) contains the whole Pareto optimal set (see 1).

## 2.4 The PICPA algorithm

PICPA uses a population of variable size whose maximum is a parameter to be fixed. PICPA starts with a single individual $[\vec{x}]$ where each variable $x_i$ is initialized with its interval (value domain). We suppose that each variable is locally consistent. If this is not the case, a first ICP process may be applied to reach a fix point. Clearly this individual corresponds to a box of $\mathbb{R}^o$ and contains the Pareto optimal front.

Let $[\vec{f}]$ be this box. Take an objective $f_i$ and bisect its value interval $[f_i]$. Such a bisection triggers two applications of the ICP process to contract variable intervals on the individual $[\vec{x}]$, leading to two new individuals $[\vec{x}']$ and $[\vec{x}'']$. These individuals replace the parent individual. These two individuals are composed of reduced intervals and correspond thus to two reduced boxes $[\vec{f}']$ and $[\vec{f}'']$ of $\mathbb{R}^o$. This “bisection-contraction” process continues until the number of individuals in the population reaches its allowed maximum. Notice that if any variable domain is reduced to the empty set by the ICP process, the underlying individual will be not inserted into the population.
Once the population reaches its full size, an instantiation process will try to create a complete feasible instantiation for each $[\vec{x}]$. That is, a particular value of the interval will be searched for each individual which satisfies the problem constraints. The feasible point obtained by this instantiation process will be used to eliminate dominated individuals by applying PS-dominance. Since this stage may require a huge processing time, *PICPA* uses a *search effort* parameter as a stop criterion to stop the instantiation process. Thus, after this stage, some individuals will be completely instantiated, leading to a real vector $\vec{x}$ while others remain uninstantiated. Notice that the result of this instantiation is recorded in a separate data structure and the individuals in the current population will not be altered.

Once this instantiation process is applied to all the individuals of the current population, we execute a Pareto selection mechanism (cf. section 2.3) to eliminate dominated individuals from the population. Since the population is reduced, we start again the above “bisection-contraction” process to extend the population to its maximal size.

**Algorithm 1** Skeleton of the *PICPA* algorithm.

* Initialize the population with a single locally consistent individual

* While $0 < |Population| < MaxPopulationSize$ do

* While $0 < |Population| < MaxPopulationSize$ do

1. Select an individual (parent) and bisect it according to one objective, leading to two distinct individuals (children)

2. Contract the children

3. Update the population:

(a) Remove the father

(b) Add the locally consistent children

EndWhile

* Potential instantiation of each individual

* PS-Dominance selection process

EndWhile

## 2.5 Experimental results

*PICPA* has been tested on a number of well-known benchmarks of the literature, including both constrained and unconstrained problems. We show in this section the experimental result on one test problem. Given the deterministic nature of *PICPA*, the quality of solutions of *PICPA* can be directly assessed with respect to the final bounds found. To show its practical performance however, we contrast the results of *PICPA* with those of *NSGA-IIc* [4]<fnref n="1" />. Notice that the version of the *NSGA-IIc* algorithm used here gives better results than those given in [4]. For these experiments, the following parameter settings are used:

* for *NSGA-IIc*, we used the settings given in [5], i.e. simulated binary crossover with $n_c = 20$ and the polynomial mutation operator with $n_m = 20$. A crossover probability

<footnote n="1">¹downloadable at: http://www.iitk.ac.in/kangal/soft.htm</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: Simulation results on CTP8.</figcaption></figure>

of 0.9 and a mutation probability of 0.15 are chosen. The population size is set to 300 and the maximum number of generation to 1000.

• for *PICPA*, we set the population size to 1000 and the search effort to 0.2.

For these experiments, we used the test problem CTP8 presented in [5]. This problem, known to be difficult, is tunable by changing the function $g()$. We used a Rastrigin's function for $g()$.

$$
\text{CTP8} \left\{
\begin{array}{ll}
\text{Minimize} & f_1(x) = x_1 \\
\text{Minimize} & f_2(x) = g(x) - f_1(x) \\
\text{s.t.} & g(x) = 41 + x_2^2 - 10 \cos(4\pi x_2) + x_3^2 - 10 \cos(4\pi x_3) + \\
& \qquad x_4^2 - 10 \cos(4\pi x_4) + x_5^2 - 10 \cos(4\pi x_5) \\
& C_1(x) \equiv \cos(\frac{\pi}{10})(f_2(x) + 2) - \sin(\frac{\pi}{10})f_1(x) \ge \\
& \qquad 40 \times |\sin(\frac{\pi}{2} \times (\sin(\frac{\pi}{10})(f_2(x) + 2) + \cos(\frac{\pi}{10})f_1(x)))|^2 \\
& C_2(x) \equiv \cos(-\frac{\pi}{20})f_2(x) - \sin(-\frac{\pi}{20})f_1(x) \ge \\
& \qquad 40 \times |\sin(2\pi \times (\sin(-\frac{\pi}{20})f_2(x) + \cos(-\frac{\pi}{20})f_1(x)))|^6 \\
\text{and} & x_1 \in [0..1] \\
& x_{i,i>1} \in [-5..5]
\end{array}
\right.
$$

On this test problem, *NSGA-IIc* was run ten times and the best run was taken for our comparisons. As *PICPA* doesn't use any random value, only one run is required to get the result. Figure 2(a) shows the feasible search space, the corresponding disconnected Pareto optimal regions and the bounds obtained by *PICPA*. From figure 2(a), we see that the *PICPA* bounds are very precise. Figure 2(b) shows the solution sets by *NSGA-IIc* and *PICPA*. We observe that the solution set of *PICPA* has a quite similar coverage of the optimal front as that of *NSGA-IIc*.
## 3 Conclusions

In this paper, we presented *PICPA*, a new algorithm to solve continuous constrained multi-objective problems. *PICPA* combines interval constraint propagation with evolutionary concepts (population and selection). This algorithm has the desirable property of bounding the Pareto optimal front. Moreover, *PICPA* has only two parameters. Experimental evaluations of *PICPA* on some well-known test problems show its practical efficiency to find high quality approximation solutions and very tight bounds of the Pareto optimal front. Also, a new dominance relation called PS-Dominance was proposed which allows to compare a point to a set of points. We think this work fills in a gap of existing population-based methods for multi-objective optimization.

## References

[1] J.G. Cleary. Logical arithmetic. *Future Computing Systems*, 2(2):125-149, 1987.

[2] D.W. Corne and J.D. Knowles. M-paes: a memetic algorithm for multiobjective optimization. In *Proc. of the 2000 Congres on Evolutionary Computation*, pages 325-332, 2000.

[3] E. Davis. Constraint propagation with interval labels. *Artificial Intelligence*, 32(3):281-331, 1987.

[4] K. Deb and T. Goel. Controlled elitist non-dominated sorting genetic algorithms for better convergence. In *Proc. of Evolutionary Multi-Criterion Optimization*, pages 67-81, 2001.

[5] K. Deb, A. Pratap, and T. Meyarivan. Constrained test problems for multi-objective evolutionary optimization. In *Proc. of Evolutionary Multi-Criterion Optimization*, pages 284-298, 2001.

[6] C.M. Fonseca and P.J. Fleming. Genetic algorithms for multi-objective optimization: Formulation, discussion and generalization. In *Proc. of The Fifth International Conference on Genetic Algorithms*, pages 416-423, 1993.

[7] X. Gandibleux, N. Mezdaoui, and A. Freville. A multiobjective tabu search procedure to solve combinatorial optimization problems. In *Lecture Notes in Economics and Mathematical Systems*, volume 455, pages 291-300. Springer, 1997.

[8] D.E. Goldberg. Genetic algorithms for search, optimization, and machine learning. *Reading, MA: Addison-Wesley*, 1989.

[9] N. Srinivas and K. Deb. Multiobjective optimization using non dominated sorting in genetic algorithms. *Evolutionary Computation*, 2(3):221-248, 1994.

[10] E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. *IEEE Transactions on Evolutionary Computation*, 3:257-271, 1999.