% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%
\usepackage{graphicx,color}
\usepackage{array}
\usepackage{amssymb}
\usepackage{amsmath}
%
\begin{document}
%
\frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
\mainmatter              % start of the contributions
%
\title{Circular representations of a valued preference matrix}
%
\titlerunning{Circular representations}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Karim Lidouh \and Yves De Smet \and Minh Tuan Huynh}
%
\authorrunning{Karim Lidouh et al.}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Karim Lidouh, Yves De Smet, Minh Tuan Huynh}
%
\institute{Universit\'{e} Libre de Bruxelles,\\
Department of Computer and Decision Engineering,\\
Brussels, Belgium}

\maketitle              % typeset the title of the contribution

\begin{abstract}
In this paper we propose a model for the graphical representation of valued preference matrices. These are obtained from multicriteria outranking methods such as for instance ELECTRE or PROMETHEE. As a consequence, they are often known to be non-symmetric, making two-dimensional representations seldom possible. An optimization model is defined and a particle swarm optimization algorithm is used to solve it. Validation is based on artificial tests. Finally, an illustrative example is given.
\end{abstract}
%
\section{Introduction}
\label{sec:intro}
%
It is common knowledge that problems involving several conflicting criteria are ill-defined \cite{Vincke92,Roy96}. The ranking of alternatives is not an obvious task since a given action is seldom better than others on all the criteria. As a consequence, finding a solution that is simultaneously optimal for every considered point of view is utopian in practice.

Therefore, many authors insist on the fact that multicriteria methods do not allow to solve a problem but only support an individual or a group of individuals during the decision process. The main challenge is thus to provide adequate tools dedicated to this decision aid activity. Among them, graphical representations are especially appreciated by end users.

In this paper, we propose a particular graphical representation of valued preference matrices. These can be obtained for instance by applying the outranking method PROMETHEE \cite{Brans02,Bouyssou06} but are not restricted to it. In section \ref{sec:model}, we describe the underlying model. Section \ref{sec:algo} presents the algorithm that was used. Artificial tests are performed in section \ref{sec:tests} and an illustrative example is presented in section \ref{sec:illustr}.

%
\section{The Model}
\label{sec:model}
%
Let $A = \{a_1, a_2, ..., a_n\}$ be a set of $n$ alternatives that are evaluated on a set of $q$ criteria denoted by $F = \{f_1, f_2, ..., f_q\}$. Without loss of generality, we may assume that these criteria have to be maximized. Let $\Pi$ be a valued preference matrix built on the basis of all the pair-wise comparisons of elements belonging to $A$. More precisely, $\Pi(a_i,a_j)=1$ will denote that $a_i$ is strictly preferred to $a_j$ while $\Pi(a_i,a_j)=0$ will denote that $a_i$ is not strictly preferred to $a_j$.  We assume that elements from the matrix $\Pi$ are such that:
\begin{equation}
\label{eq:equ1}
\left\{ \begin{array}{l}
      \Pi(a_i,a_j) \geq 0 \\
      \Pi(a_i,a_j) + \Pi(a_j,a_i) \leq 1.
   \end{array}
\right.
\end{equation}

One way to compute such a matrix is to use the PROMETHEE method \cite{Brans02,Bouyssou06}. At first, the differences between any pair of alternatives are computed for a given criterion $f_k$:
\begin{equation}
\label{eq:equ2}
d_k(a_i,a_j) = f_k(a_i) - f_k(a_j).
\end{equation}

Then, this difference is transformed into a preference degree denoted $\Pi_k(a_i,a_j)$ degree using a non-decreasing function $Pk: \Re \rightarrow [0,1]$:
\begin{equation}
\label{eq:equ3}
\Pi_k(a_i,a_j) = P_k[d_k(a_i,a_j)].
\end{equation}

Finally, a global preference degree is computed by aggregating these uni-criteria degrees:
\begin{equation}
\label{eq:equ4}
\Pi(a_i,a_j) = \overset{q}{\underset{k=1}{\sum}} w_k \Pi_k(a_i,a_j).
\end{equation}

Where $w_k$ represents the weight associated to criterion $f_k$. Without loss of generality, we assume that $w_k>0$ and $\overset{q}{\underset{k=1}{\sum}}w_k=1$.

Graphical tools are key elements to analyze problems involving multiple dimensions. They offer a convenient way to structure them and to lower their complexity. Traditional statistical approaches such as boxplots, piecharts, scatter plots, principal component analysis (PCA), ... are commonly used by practitioners during the decision process. However none of the methods really take into account the multicriteria nature of the problem. In other words, they do not incorporate the fact that the criteria have to be optimized and have to be interpreted with regard to the decision maker's preferences. To our knowledge, only a few approaches have been proposed to visualize multicriteria problems. For instance, in the PROMETHEE methodology, the GAIA method \cite{Brans94} is based on a PCA applied on the matrix of unicriterion net flow scores. It allows to bring information about conflicting and redundant criteria or alternatives and indicates regions where the best compromise solution is lying. We do think that this research area still needs to be explored.

As already stressed, the aim of this contribution is to propose a graphical representation of the   matrix. When matrices are symmetric, the isotonic representation method can be used \cite{Dattorro06}. The underlying idea of this approach is to find the coordinates of the $n$ points in a space of dimension $l$ such that the distances between the pairs of elements are equal to the values of the matrix.

Due to the multicriteria context, $\pi$ matrices are seldom symmetric. Moreover, the distance notion does not take into account the fact that criteria have to be optimized. Therefore, a new approach has to be developed.

First we start with the representation of two elements. The concept of circular representation is the following: the elements $a_i$ and $a_j$ will be placed on a circle the radius of which is equal to $[\Pi(a_i,a_j) + \Pi(a_j,a_i)]/(2\pi)$. This will lead to a perimeter of $[\Pi(a_i,a_j) + \Pi(a_j,a_i)]$. A clock-wise interpretation of the circle is the following: the arc from $a_i$ to $a_j$ is equal to $\Pi(a_i,a_j)$ and the arc from $a_j$ and $a_i$ is equal to $\Pi(a_j,a_i)$. As a consequence, two elements such that $\Pi(a_i,a_j) \simeq \Pi(a_j,a_i) \simeq 0$ are superposed. The graphical interpretation is thus consistent with the fact that they are indifferent. Figure \ref{fig:circillust} illustrates different preference settings.
\begin{figure}[htb]
	\centering
	\begin{minipage}{6.5cm}
		\begin{minipage}{2.5cm}
		$\Pi=\begin{pmatrix}
    	0 & 0.5\\
    	0.5 & 0
		\end{pmatrix}$:
		\end{minipage}\hfill
		\begin{minipage}{4cm}
		\centering
		\includegraphics[scale=0.75]{figs/illustr1.pdf}
		\end{minipage}
	\end{minipage}
	
	\begin{minipage}{6.5cm}
		\begin{minipage}{2.5cm}
		$\Pi=\begin{pmatrix}
    	0 & 0.9\\
    	0.1 & 0
		\end{pmatrix}$:
		\end{minipage}\hfill
		\begin{minipage}{4cm}
		\centering
		\includegraphics[scale=0.75]{figs/illustr2.pdf}
		\end{minipage}
	\end{minipage}
	
%	\begin{minipage}{6.5cm}
%		\begin{minipage}{2.5cm}
%		$\Pi=\begin{pmatrix}
%    	0 & 0\\
%    	0.4 & 0
%		\end{pmatrix}$:
%		\end{minipage}\hfill
%		\begin{minipage}{4cm}
%		\centering
%		\includegraphics[scale=0.75]{figs/illustr3.pdf}
%		\end{minipage}
%	\end{minipage}
	\caption{Circular representation of two different preference settings}
	\label{fig:circillust}
\end{figure}

It is obvious to notice that such a representation is always possible when only two alternatives are considered. When more actions are taken into account, a two dimensional representation does not perfectly correspond to the $\Pi$ matrix. Let $p(a_i,a_j)$ be the length of the arc going from $a_i$ to $a_j$ for a given circular representation. Our aim is to find the circular representation that will be as close as possible to the $\Pi$ matrix. More formally, we want to find the circular representation such that:
\begin{equation}
\label{eq:equ5}
min \overset{n}{\underset{i=1}{\sum}}\overset{n}{\underset{j=1}{\sum}} [\Pi(a_i,a_j) - p(a_i,a_j)]^2.
\end{equation}

An empirical approach based on particle swarm optimization  is used to solve this problem.

%
\section{The Algorithm}
\label{sec:algo}
%
Different approaches can be considered to solve the model presented in the previous section. As a first attempt, we have chosen to apply a Particle Swarm Optimization (PSO) \cite{Diosan06,Poli08} algorithm which is generally well performing for continuous optimization problems. Of course other heuristics could be considered but this goes beyond the scope of this contribution. Our main focus remains to present an original view of a preference matrix.

To solve our problem using the PSO approach we will have to define the variables of our search space. There will be two sets of variables:
\begin{itemize}
	\item Positioning variables $(x_i,y_i)$: These variables define the position of an action $i$ (where $i=1,2,...,n$). There will be $2n$ variables in this set. As two actions will ever be separated by a maximum distance of $1/2\pi$, we can reduce the search space for these variables. To make the implementation easier, we will allow each variable to be in $[\frac{-1}{2\pi},\frac{1}{2\pi}]$ even though we could reduce the space to a disc of diameter $1/2\pi$.
	\item Variables defining the circles $k_{ij}$: A single variable per pair of actions will be enough to define the preference circle once the coordinates of action $i$ and $j$ are chosen (where $i=1,2,...,n-1$ and $j=i+1,...,n$). The number of variables of this set will be $C^n_2$.
\end{itemize}

%Explication de k_ij
Figure \ref{fig:vark} shows how the variable $k_{ij}$ defines a circle for two actions  $i$ and $j$ whose coordinates are known. We consider the chord between the two actions and the normal line that cuts it in the middle. On this line, $k_{ij}$ will give us the position of the circle's center. Since this circle can only have a perimeter of 1 at most, as described in Section \ref{sec:model}, $k_{ij}$ will only have values in $[0,\frac{1}{2\pi}]$ if $\Pi(a_i,a_j) \geq \Pi(a_j,a_i)$ and in $[\frac{-1}{2\pi},0]$ if $\Pi(a_i,a_j) < \Pi(a_j,a_i)$.

\begin{figure}[htb]
	\centering
		\includegraphics{figs/vark.pdf}%[scale=0.75]
	\caption{Variable $k_{ij}$ defining the circle for two actions}
	\label{fig:vark}
\end{figure}

Figure \ref{fig:compl-rep} gives an example of representation obtained using the previously described algorithm. The example involved 6 actions with randomly generated preferences. The color of the arcs indicates the difference between their length and the preference that they are meant to represent. Table \ref{tab:error} gives a legend of the colors and the range of error symbolized by them.
%Exemple de résultat
\begin{figure}[htb]
	\centering
		\includegraphics{figs/compl-rep.pdf}%[scale=0.75]
	\caption{Complete circular representation of a problem}
	\label{fig:compl-rep}
\end{figure}

\begin{table}[htb]
	\centering
		\begin{tabular}{lc}
			\hline
			Color & Range of error \\
			\hline
			Red & $0.1 <$ error\\
			Blue & $0.01 <$ error $< 0.1$\\
			Green & $0.001 <$ error $< 0.01$\\
			Yellow & error $< 0.0001$\\
			\hline
		\end{tabular}
	\caption{Error ranges on the representation}
	\label{tab:error}
\end{table}

Studying the evolution of the mean error gave us an understanding of how effective particle swarm optimization can be for this kind of problems. We can see in Figure \ref{fig:evol-err} that no matter where the algorithm starts, the error drops tremendously during the first iterations before stabilizing itself after about 20000 evaluations of the objective function. This behavior can be explained by three possible situations \cite{Clerc02,Clerc06}:
\begin{itemize}
	\item Convergence: all the particles have converged towards the same position and are stuck in the same local or global minimum.
	\item Divergence: the particles fail in finding a good solution. They keep moving yet the error of the best solution found does not change.
	\item Stagnation: the particles have assembled in two or more separated positions that act as attractive poles for the particles near them. The movements of the particles are influenced by the different local minima but the particles cannot escape from the current situation.
\end{itemize}

%Comportement de l'algo
\begin{figure}[htb]
	\centering
		\includegraphics{figs/evol-err.pdf}%[scale=0.75]
	\caption{Evolution of the mean error with each evaluation of the objective function}
	\label{fig:evol-err}
\end{figure}

By observing the kinetic energy of the particle we can see if these are still in movement when the error stabilizes or if they are still looking for a better solution far from the best one discovered. We can also display the volume of the swarm of particles to see if these are dispersed or if they are concentrated around a single solution. Figure \ref{fig:ecin-vol} shows the evolution of these two measures while the algorithm is solved. It indicates that both the kinetic energy and the volume of the swarm reach zero, meaning that the algorithm has converged towards a single best solution.

\begin{figure}[htb]
	\centering
		\includegraphics{figs/ecin-vol.pdf}%[scale=0.75]
	\caption{Evolution of the kinetic energy and the volume of the swarm}
	\label{fig:ecin-vol}
\end{figure}

%
\section{Some Empirical Tests}
\label{sec:tests}
%
Using empirical tests on artificial matrices we tried to optimize the parameters chosen for our algorithm. The parameters that we chose to modify for the tests were the following:
\begin{itemize}
	\item The number of particles $N$: initially set at 20, we suspected the number had to be increased to broaden our coverage of the search space.
	\item The size of the neighborhood $K$: initially of 3 particles. A higher number would speed the propagation of good solutions to the other particles \cite{Mohais05}.
	\item A parameter $\gamma$ that defines the movement equations of the particles.
\end{itemize}
We tried to find the values that allowed us to improve the algorithm in terms of speed and accuracy when searching for representations of attainable matrices (i.e. matrices that can have a perfect representation).

To evaluate the different parameter settings, several indicators were considered:
\begin{itemize}
	\item The mean error on all arcs of the representation $\mu_{error}$.
	\item The standard deviation of the mean error $\sigma_{error}$: giving the robustness of the performance for a high number of executions.
	\item The success rate of the algorithm $\tau$: indicating the proportion of executions that yielded an acceptable representation.
	\item The speed of convergence $\mu_{conv}$: in number of iterations before a stable representation is found.
	\item The standard deviation of the speed of convergence $\sigma_{conv}$.
\end{itemize}

After some tests where we appreciated the effects of modifying the parameters, we obtained a configuration that improved the results significantly. Table \ref{tab:param-res} summarizes the results obtained with an initial and the last configurations. We found out that increasing the number of particles improved the results until a number of 300 to 600. As for the other parameters, using a ring neighbourhood with 3 particles and a $\gamma$ of $2.15$ seemed to produce the best output.

\begin{table}[htb]
	\centering
		\begin{tabular}{|l|c|c|}
			\hline
			Parameters & $N=20$ & $N=300$ \\
			 & $K=3$ & $K=3$\\
			 & $\gamma=2.01$ & $\gamma=2.15$\\
			\hline
			Indicators & $\mu_{error}=0.1058$ & $\mu_{error}=0.000858$\\
			 & $\sigma_{error}=0.0109$ & $\sigma_{error}=0.0015$\\
			 & $\tau=0\%$ & $\tau=59\%$\\
			 & $\mu_{conv}=192,460$ & $\mu_{conv}=68,877$\\
			 & $\sigma_{conv}=55,182$ & $\sigma_{conv}=8,951$\\
			\hline
		\end{tabular}
	\caption{Quality of results with two configurations}
	\label{tab:param-res}
\end{table}

%
\section{An Illustrative Example}
\label{sec:illustr}
%
The example we will use to illustrate our model is taken from the multicriteria literature: a power plant localization problem described by Brans et al. \cite{Brans02}. In that example, 6 alternatives are evaluated using the PROMETHEE and GAIA methods. The preference matrix we obtain for it is the following:
\begin{equation}
\label{eq:equ10}
\Pi=\begin{pmatrix}
        0  &  0.296  &  0.25   &  0.268  &  0.1    &  0.185\\
    0.463  &      0  &  0.689  &  0.334  &  0.296  &  0.5  \\
    0.235  &  0.18   &      0  &  0.334  &  0.055  &  0.43 \\
    0.398  &  0.506  &  0.305  &      0  &  0.224  &  0.212\\
    0.444  &  0.515  &  0.486  &  0.379  &      0  &  0.448\\
    0.286  &  0.399  &  0.25   &  0.431  &  0.133  &      0
\end{pmatrix}
\end{equation}

When carefully studying this matrix, we can see that it cannot be exactly represented by a 2-dimensional arrangement. This can be easily demonstrated by showing that the triangle inequality is not verified for most sets of 3 actions from our problem:
\begin{equation}
\label{eq:equ11}
|l(a,b)-l(a,c)| \leq l(a,c) \leq l(a,b)+l(b,c)
\end{equation}
where $l(a,b)$ represents the length of the chord between actions $a$ and $b$.

Using our swarm particle optimization algorithm we can obtain a complete circular representation as in Figure \ref{fig:compl-rep} or limit ourselves to the arcs that give us the most interesting information. The following matrix contains the net flow (or global score) of the 6 actions in our problem:
\begin{equation}
\label{eq:equ12}
\phi=\begin{pmatrix}
   -0.1454\\
    0.0772\\
   -0.1492\\
   -0.0202\\
    0.2928\\
   -0.0552
\end{pmatrix}.
\end{equation}

By comparing the net flows, we can see that the best alternative is action 5. Figure \ref{fig:compo5} shows a circular representation of the preferences for action 5 as well as the error on each arc. The color of the arcs indicates the error in length of the arc as already explained in Table \ref{tab:error}. As the only colors present are yellow and blue, we are sure that this representation is reliable.
\begin{figure}[htb]
	\centering
		\includegraphics{figs/compo5.pdf}%[scale=0.75]
	\caption{Circular representation of the preferences for action 5}
	\label{fig:compo5}
\end{figure}

On the circular representation in Figure \ref{fig:compo5} we also have a representation of the net flow as small colored disks that are blue when the net flow is positive and red otherwise. The size of the disks indicates the absolute value of the net flow. This additional information allows us to quickly detect which action is the next best one in the ranking as well as compare its behavior with regard to the best one. However action 5's higher net flow makes it by far the most interesting option. This assumption is further reinforced by the length of the blue arcs leaving action 5 in comparison to the red ones.

When considering action 1 on Figure \ref{fig:compo1}, we can remark that even though the action is globally considered as one of the worst, it is highly preferred to action 3 and is reasonably preferred to actions 2 and 4. Another interesting information is the big size of the circle between actions 1 and 2, indicating that the two actions are clearly differenciated (i.e. the sum of their respective preferences is close to 1) whereas actions 1 and 3 are more similar (i.e. the sum of their preferences has a lower value).

\begin{figure}[htb]
	\centering
	\begin{minipage}{11.5cm}
		\begin{minipage}{6.5cm}
		\centering
			\includegraphics{figs/compo1.pdf}%[scale=0.75]
		\end{minipage}\hfill
		\begin{minipage}{4.5cm}
		$\begin{pmatrix}
       0  &  \textcolor{blue}{0.30}   &  \textcolor{blue}{0.25}  &  \textcolor{blue}{0.27}  &  \textcolor{blue}{0.10}   &  \textcolor{blue}{0.19}\\
    \textcolor{red}{0.46}  &     0  &  0.69  &  0.33  &  0.30  &  0.50\\
    \textcolor{red}{0.24}  &  0.18  &     0  &  0.33  &  0.06  &  0.43\\
    \textcolor{red}{0.40}  &  0.51  &  0.31  &     0  &  0.22  &  0.21\\
    \textcolor{red}{0.44}  &  0.52  &  0.49  &  0.38  &     0  &  0.45\\
    \textcolor{red}{0.29}  &  0.40  &  0.25  &  0.43  &  0.13  &     0
		\end{pmatrix}$
		\end{minipage}
	\end{minipage}
	\caption{Circular representation of the preferences for action 1}
	\label{fig:compo1}
\end{figure}

Considering only one action at a time we are actually looking at a representation of the row and column of that action in the matrix $\Pi$. The elements considered are highlighted in the matrix of Figure \ref{fig:compo1} for action 1. This graphical representation allows us to quickly identify remarkable properties that would have taken us much more time to discover when simply looking at the corresponding numbers. As the cognitive effort of the decision maker has been reduced when analyzing a given preference matrix, they can afford to analyze more situations making it likely to take better decisions.

%
\section{Conclusion}
\label{sec:conclu}
%
In this paper we described a new model to graphically represent valued preference matrices using circles. However this model cannot be used in all cases to accurately represent problems with more than two actions. Therefore we make use of particle swarm optimization to find a representation as close as possible to a given matrix. The developed algorithm is tested on several cases and its parameters are optimized to find better solutions. We also considered different variants of particle swarm optimization such as attractive-repulsive optimization \cite{Murphy04} but the best results were obtained using the classical approach. Finally, an example was used to illustrate potential uses for the model such as the analysis of individual actions of a decision problem or the understanding of the relations between two of them.

Further work involves additional testing of the algorithm on different problems and the use of other optimization means to find more accurate representations. In particular, we could compute the theoretical minimum error of a given matrix and try to reach it using the algorithm. Or further analyze the search space to improve the way the algorithm explores it.

\nocite{Huynh09}
\bibliographystyle{splncs}
\bibliography{latex8}
\clearpage

\end{document}
