---
abstract: |
    Given an undirected graph $G$, the Minimum Sum Coloring problem (MSCP) is to find a legal assignment of colors (represented by natural numbers) to each vertex of $G$ such that the total sum of the colors assigned to the vertices is minimized.  This paper presents a memetic algorithm for MSCP based on a tabu search procedure with two neighborhoods and a multi-parent crossover operator.  Experiments on a set of 77 well-known DIMACS and COLOR 2002-2004 benchmark instances show that the proposed algorithm achieves highly competitive results in comparison with five state-of-the-art algorithms.  In particular, the proposed algorithm can improve the best known results for 17 instances.  We also provide upper bounds for 18 additional instances for the first time. 

    *Keywords*: Sum coloring, memetic algorithm, heuristics, combinatorial optimization
address: 'LERIA, Université d’Angers, 2 Boulevard Lavoisier, 49045 Angers, France'
author:
- Yan Jin
- 'Jin-Kao Hao'
- 'Jean-Philippe Hamiez'
date: 'March 13, 2013'
title: A memetic algorithm for the minimum sum coloring problem
---

,

,

Introduction {#Sec_Intro}
============

Let $G = (V, E)$ be a simple undirected graph (without loops) with vertex set $V = \{v_1, \ldots , v_n\}$ and edge set $E \subset V \times V$. A proper $k$-coloring $c$ of $G$ is a mapping $c: V \to \{1, \ldots, k\}$ such that $c(v_i) \neq c(v_j)~\forall \{v_i, v_j\} \in E$. A legal or proper $k$-coloring can also be defined as a partition of $V$ into $k$ independent sets or stables $V_1, \ldots, V_k$ such that $\forall u,v \in V_i$ $(i=1, \ldots, k), \{u,v\} \notin E$. The classical graph coloring problem (GCP) aims at finding a proper $k$-coloring with $k$ minimum.  This paper is dedicated to the NP-hard Minimum Sum Coloring Problem (MSCP) , which is closely related to GCP.  The objective of MSCP is to find a proper $k$-coloring which minimizes the sum of the colors assigned to the vertices.  This minimum is the chromatic sum $\Sigma(G)$ of $G$: $\Sigma(G)=\min_{c \in \mathcal{C}} f(c)$, with $\mathcal{C}$ the set of all proper $k$-colorings of $G$ (for all possible $k$ values) and $f(c) = \sum_{i=1}^n c(v_i)$, or $f(c) = \sum_{l=1}^k l|V_l|$ equivalently (where $|V_l|$ is the cardinality of $V_l$), the “coloring sum” of the proper $k$-coloring $c$. MSCP applications include VLSI design, scheduling, and resource allocation [@Malafiejski2004]. 

Considering the theoretical intractability of MSCP, a number of heuristic algorithms have been proposed to find suboptimal solutions, such as a parallel genetic algorithm , two greedy heuristics , a tabu search metaheuristic , a hybrid algorithm (HA) , an effective heuristic algorithm (EXSCOL) , a local search heuristic (MDS5) , and a breakout local search (BLS) .  To our knowledge, EXSCOL, HA, MDS5, and BLS are the state-of-the-art algorithms in the literature.  EXSCOL is based on extracting large disjoint independent sets and is particular effective for handling large graphs (with at least 500 vertices).  HA is a hybrid algorithm which combines a genetic algorithm with a surrogate constraint heuristic.  MDS5 is based on variable neighborhood search and iterated local search.  BLS combines local search with adaptive perturbation mechanisms to ensure the quality of solutions.  This paper introduces a Memetic Algorithm for the minimum Sum Coloring problem (MASC), which relies on three key components.  First, a double-neighborhood tabu search procedure is especially designed for MSCP (DNTS).  DNTS is based on a token-ring application of two complementary neighborhoods to explore the search space and a perturbation strategy to escape from local optima.  Second, a multi-parent crossover operator is used for solution recombination.  Basically, it tries to transmit large color classes from the parents to the offspring.  Finally, a population updating mechanism is devised to determine how the offspring solution is inserted into the population. 

We evaluate the performance of MASC on 77 well-known graphs from DIMACS and COLOR 2002-2004 graph coloring competitions (59 of them have been used previously for evaluating sum coloring algorithms).  The computational results show that MASC can frequently match the best known results in the literature for most of the 59 cases.  In particular, it improves the previous best solution for 17 graphs for which an upper bound is known.  For the additional 18 new graphs, we report computational results for the first time. 

The paper is organized as follows.  Next section describes the general framework and the components of our MASC memetic algorithm, including the population initialization, the crossover operator and the double-neighborhood tabu search procedure.  Detailed computational results and comparisons with five state-of-the-art algorithms are presented in Section \[Sec\_Results\].  Before concluding, Section \[Sec\_analysis\_MASC\] investigates and analyzes two key issues of the proposed memetic algorithm. 

MASC: A Memetic Algorithm for Minimum Sum Coloring {#Sec_Approach}
==================================================

A memetic algorithm is a population-based approach where the traditional mutation operator is replaced by a local search procedure .  Memetic algorithms are among the most powerful paradigms for solving NP-hard combinatorial optimization problems.  In particular, they have been successfully applied to the tightly related GCP . 

Our MASC algorithm is summarized in Algorithm \[Algo\_MASC\].  After population initialization, MASC repeats a series of generations (limited to $MaxGeneration$) to explore the search space which is defined by the set of all proper $k$-colorings ($k$ is not a fixed value, Section \[Search Space\]).  At each generation, two or more parents are selected at random (line 6) and used by the dedicated crossover operator to generate an offspring solution (line 7, Section \[subsec\_sol\_crossover\_operator\]).  The offspring solution is then improved by a double neighborhood tabu search (line 8, Section \[subsec\_sol\_TS\]).  If the improved offspring has a better sum of colors, it is then used to update the current best solution found so far (lines 9-10).  Finally, the population updating criterion decides whether the improved offspring will replace one existing individual of the population or not (line 12, Section \[subsec\_sol\_population\_update\]). 

**input**: A graph $G$ **output**: The minimum sum coloring $c_*$ found and its objectif $f(c_*)$ Population\_Initialization($P,p$) /\* Population $P$ has $p$ solutions, Sect.  \[subsec\_sol\_initial\_population\] \*/ $f_* \gets \min_{c \in P} f(c)$ /\* $f_*$ records the best objective value found so far \*/ $P' \gets \textrm{Selection}(P)$ /\* Select 2 or more parents at random for crossover \*/ $o \gets \textrm{Crossover}(P')$ /\* Crossover to get an offspring solution, Sect.  \[subsec\_sol\_crossover\_operator\] \*/ $o \gets \textrm{DNTS}(o)$ /\* Improve $o$ with the DNTS procedure, Sect.  \[subsec\_sol\_TS\]\*/ $f_* \gets f(o); c_*  \gets o$ Population\_Updating($P, o$) /\* Sect.  \[subsec\_sol\_population\_update\] \*/ $f_*, c_*$

Search Space and Evaluation Function {#Search Space}
------------------------------------

The search space explored by MASC is the set $\mathcal{C}$ of all *proper* $k$-colorings of $G$ ($k$ is not fixed).  For a given proper $k$-coloring $c$, its quality is directly assessed by the sum of colors $f(c) = \sum_{v \in V} c(v) = \sum_{l = 1}^k l|V_l|$.

Initial Population {#subsec_sol_initial_population}
------------------

Our algorithm begins with a population $P$ of $p$ feasible colorings.  This population can be obtained by any graph coloring algorithm that is able to generate different proper colorings for a graph.  In our case, we employ the well-known TABUCOL , more precisely its improved version introduced in .  For a given graph $G$, TABUCOL tries to find a proper $k$-coloring with $k$ as small as possible.  Given the stochastic nature of TABUCOL, we run it multiple times to obtain different $k$-colorings ($k$ may take different values).  Each resulting $k$-coloring is inserted into $P$ if it is not already present (discarded otherwise).  This process is repeated until $P$ is filled with $p$ different $k$-colorings. 

Crossover Operator {#subsec_sol_crossover_operator}
------------------

The crossover operator is an important component in a population-based algorithm.  It is used to generate one or more new offspring individuals to discover new promising search areas. 

MASC uses a multi-parent crossover operator, called MGPX, which is similar to the one introduced in as a variant of the well-known GPX crossover first proposed in for GCP (restricted to two parents).  MGPX generates only one offspring solution $o$ from $\alpha$ parents randomly chosen from $P$, where $\alpha$ varies from 2 to 4 according to $|V|$ and the best $k$-coloring found for GCP (see Eq.  \[EqNbParents\]).  Motivations for these $\alpha$ values can be found in . 

$$\alpha= \left \{ \begin{array} {ll}
2,   &   \textrm{if $|V| / k < 5$} \\
3,   &    \textrm{if $5 \le |V| / k \le 15$}\\
4,   &    \textrm{otherwise}
\end{array}  \right. 
\label{EqNbParents}$$

**input**: A set $P'$ of $\alpha$ parents randomly chosen from $P$ **output**: An offspring $o$ $\nu \gets 0$ /\* Counts the number of colored vertices in $o$ \*/ $\kappa \gets 0$ /\* Counts the number of colors used in $o$ \*/ $\varphi_j \gets 0~\forall c_j \in P'$ /\* To identify which parents are forbidden for color $\kappa$ \*/ $\kappa \gets \kappa + 1$ $P_\kappa \gets \{c_j \in P': \varphi_j < \kappa\}$ /\* Set of parents allowed for color $\kappa$ \*/ Let $V_*^j$ be a color class of maximum cardinality $\forall c_j \in P_\kappa$ $\nu \gets \nu + |V_*^j|$ $o(v) \gets \kappa$ Remove $v$ from $c_i~\forall c_i \in P'$ $\varphi_j \gets \kappa + \lfloor \alpha / 2 \rfloor$ /\* Forbid using $c_j \in P'$ for a few steps \*/ $o$

MGPX is summarized in Algorithm \[AlgoMGPX\].  It builds the color classes of the $o$ offspring one by one, transmitting as many vertices as possible from the parents at each step (for quality purpose) (lines 7-14).  Once a parent has been used for transmitting an entire color class to $o$, the parent is not considered for a few steps with the purpose of varying the origins of the color classes of $o$ (line 15).  This strategy avoids transmitting always from the same parent and introduces some diversity in $o$ .  Note that the offspring solution is always a proper $k$ coloring while the number of colors used by the offspring can be higher than those of the considered parents. 

A Double-Neighborhood Tabu Search for Sum Coloring {#subsec_sol_TS}
--------------------------------------------------

Local optimization is another important element within a memetic algorithm.  In our case, its role is to improve as far as possible the quality (i.e., the sum of colors) of a given solution returned by the MGPX crossover operator.  This is achieved by a Double-Neighborhood Tabu Search (DNTS) procedure specifically designed for MSCP (see Algorithm \[Algo\_tabu\]). 

DNTS uses two different and complementary neighborhoods $N_1$ and $N_2$ which are applied in a token-ring way [@GasperoSchaerf2006; @Luetal2011] to find good local optima (intensification) (lines 2-14).  More precisely, we start our search with one neighborhood (lines 6-9) and when the search ends with its best local optimum, we switch to the other neighborhood to continue the search while using the last local optimum as the starting point (lines 10-13).  When this second search terminates, we switch again to the first neighborhood and so on.  DNTS continues the exploration of each neighborhood $N_i$ ($i=1,2$) until $p_i$ ($i=1,2$) consecutive iterations fail to update the best solution found. 

This neighborhood-based intensification phase terminates if the best local optimum is not updated for $p_3$ consecutive iterations (line 14).  At this point, we enter into a diversification phase by triggering a perturbation to escape from the local optimum (line 15, Section \[subsec\_sol\_perturbation\_mechanism\]).  The DNTS procedure stops when a maximum number of iterations $p_4$ is met.  We explain below the two neighborhoods, the tabu list management and the perturbation mechanism. 

**Input**: Graph $G$, a $k$-coloring $c$ **Output**: the best improved $k$-coloring $c_* \leftarrow c$ $c$ $\leftarrow$ TS($N_1, c$)   /\* Tabu search with neighborhood $N_1$, Sect.  \[SectN2\] \*/ $c^* \leftarrow c$

$c$ $\leftarrow$ TS($N_2, c$)    /\* Tabu search with neighborhood $N_2$, Sect.  \[subsec\_sol\_one\_move\_tabu\] \*/ $c_* \leftarrow c$ $c \leftarrow$ Perturbation($c_*$)   /\* Search is stagnating, generate a new starting solution by perturbing the best $k$-coloring found so far, Sect.  \[subsec\_sol\_perturbation\_mechanism\] \*/

### $N_1$: A Neighborhood Based on Connected Components {#SectN2}

The first neighborhood $N_1$ can be described by the operator $Exchange(i,j)$. Given a proper $k$-coloring $c = \{V_1, \ldots, V_k\}$, operator $Exchange(i,j), (1 \le i \neq j \le k)$ swaps some vertices of a color class $V_i$ against some connected vertices of another color class $V_j$. Formally, let $G_{i, j}(c)$ be the set of all connected components of more than one vertex in the subgraph of $G$ induced by color classes $V_i$ and $V_j$ in a proper $k$-coloring $c$. In Figure \[fig\_chain\_swap\] (left) for instance, $G_{i, j}(c)$ is composed of two graphs (say $g_1$ and $g_2$): $g_1$ is the subgraph induced by $\{v_2, v_3, v_6, v_7, v_8\}$ and $g_2$ is induced by $\{v_4, v_5, v_9\}$.

  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
   ![ $N_1$: An illustrative example with two partial colorings ($c$ and $c'$ are restricted here to two $V_i$ and $V_j$ color classes)[]{data-label="fig_chain_swap"}](N2l.eps "fig:")   ![ $N_1$: An illustrative example with two partial colorings ($c$ and $c'$ are restricted here to two $V_i$ and $V_j$ color classes)[]{data-label="fig_chain_swap"}](N2r.eps "fig:")
                                                                                A proper $k$-coloring $c$                                                                                                                                                            A possible $c' \in N_1(c)$
  ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Neighborhood $N_1(c)$ is composed of the set $\mathcal{G}(c)$ of all possible elements in all the $G_{i, j}(c)$ sets: $\mathcal{G}(c) = \cup_{1 \le i < j \le k} G_{i, j}(c)$. In other words, $N_1(c)$ includes all the proper $k$-colorings that can be obtained from the current $k$-coloring $c$ by exchanging the vertices of a connected component induced by color classes $V_i$ and $V_j$. Figure \[fig\_chain\_swap\] shows an example where by exchanging the two sets of vertices $\{v_2, v_3\}$ and $\{v_6, v_7, v_8\}$ of connected component $g_1$ of the current $k$-coloring $c$ (left drawing), we obtain a neighboring $k$-coloring $c'$ (right drawing). 

### $N_2$: A Neighborhood Based on One-Vertex-Move {#subsec_sol_one_move_tabu}

The second neighborhood $N_2$ is conventional and is simpler than $N_1$. $N_2$ can be described by the operator $OneMove(v,i,j)$. Given a proper $k$-coloring $c = \{V_1, \ldots, V_k\}$, operator $OneMove(v,i,j), (1 \le i \neq j \le k)$ displaces one single vertex $v$ of a color class $V_i$ to another color class $V_j$ such that the resulting $k$-coloring remains proper.  For instance, from the current coloring $c$ of the left drawing of Figure \[fig\_chain\_swap\], moving vertex $v_1$ from $V_i$ to $V_j$ gives a neighboring solution.  Neighborhood $N_2(c)$ is composed of all the possible proper $k$-colorings by applying $OneMove(v,i,j)$ to the current $k$-coloring $c$. Like neighborhood $N_1$, the solutions of this second neighborhood are also proper $k$-colorings.  Moreover, the number of colors of the neighboring solutions remains the same as that of the current coloring. 

### Neighborhood Examination and Tabu List {#Neighborhood examination}

DNTS applies these two neighborhoods $N_1$ and $N_2$ in a token-ring way [@GasperoSchaerf2006; @Luetal2011].  The alternation between $N_1$ and $N_2$ is triggered when the current neighborhood is exhausted, i.e., when the current best solution cannot be further improved for a fixed number of consecutive iterations. 

During the exploration of a neighborhood, DNTS uses a tabu list to avoid short-term cycles.  Precisely, for the neighborhood $N_1$ defined by the operator $Exchange(i,j)$, when a set of vertices of a color class $V_i$ are exchanged with a set of vertices of another color class $V_j$, exchanges between $V_i$ and $V_j$ are forbidden for the next $TT$ iterations (called tabu tenure).  For the neighborhood $N_2$ defined by the operator $OneMove(v,i,j)$, when a vertex $v$ of a color class $V_i$ is displaced to another color class $V_j$, the vertex $v$ is forbidden to go back to $V_i$ for the next $TT$ iterations. 

In both cases, the tabu tenure $TT$ is determined simply by taking a random number from $\{0, \ldots k - 1\}$. Moreover, a forbidden $Exchange$ or $OneMove$ operation is always accepted if it leads to a neighboring solution better than the best solution found so far (this is called aspiration according to the tabu search terminology). 

As shown in Algorithm \[Algo\_tabu\], at each iteration of our DNTS, a best neighboring solution is selected among all the allowed solutions (from $N_1$ or $N_2$) to replace the current solution.  The tabu list is updated accordingly after each iteration. 

### The Perturbation Mechanism {#subsec_sol_perturbation_mechanism}

In addition to the basic diversification mechanism of the tabu list, our DNTS algorithm applies a stronger diversification strategy based on perturbations to escape deep local optima.  The perturbation is triggered when the current intensification phase cannot update the recorded best solution $c_*$ for $p_3$ consecutive iterations (see line 15, Algorithm \[Algo\_tabu\]).  In this case, the search is considered to be trapped in a deep local optimum and a strong diversification is needed to bring the search to a new search region.  To achieve this, we apply the following perturbation technique to modify the recorded best solution $c_*$ and then use this perturbed solution to initialize DNTS.  Suppose $c_*$ is composed of $k$ different color classes and let $V_l$ be the largest color class.  We introduce an additional color class $V_{k + 1}$ and then move randomly one third of the vertices of $V_l$ into $V_{k + 1}$. In order to prevent the subsequent search from coming back to $c_*$, $V_l$ and $V_{k + 1}$ are classified tabu and cannot take part of an $Exchange$ or a $OneMove$ operation for the next $TT$ iterations (see Section \[Neighborhood examination\]). 

Population Updating {#subsec_sol_population_update}
-------------------

The management of the population usually controls and balances two important factors in population-based heuristics: Quality and diversity. 

Quality can naturally be measured here using the coloring sum function ($f$).  The proper $k$-coloring $c_i$ is better than $c_j$ if $f(c_i) < f(c_j)$.

We use the following distance $H$ to estimate the diversity.  Given two coloring $c_i$ and $c_j$, $H_{i, j}$ is the number of vertices in $c_i$ and $c_j$ which have different colors: $H_{i, j} = |\{v \in V: c_i(v) \neq c_j(v)\}|$. A small $H_{i, j}$ value indicates a high similarity between $c_i$ and $c_j$. $H$ is also employed to measure how much diversity $H_{i, P}$ a particular $k$-coloring $c_i$ contributes to the entire population $P$: $H_{i, P} = \min_{j \neq i} H_{i, j}$. Again, a small (large) $H_{i, P}$ value indicates that $c_i$ adds a low (high) diversity to $P$.

In MASC, $f$ and $H$ are combined in a $s$ “score” function which is used to decide whether an offspring solution $o$ replaces an individual in the population $P$ or not: $s(c_i)=f(c_i)+e^{0.08|V|/H_{i,P}}~\forall c_i \in P$. Precisely we first add $o$ into $P$ and compute all $s(c_i)$. We then identify the worse configuration $c_w$ (i.e., $s(c_w)$ is maximum).  The replacement strategy applies the following rules:

Case 1

:   ($c_w$ is not $o$): Remove $c_w$ from $P$;

Case 2

:   ($c_w$ is $o$): Remove the second worse individual from $P$ with probability 0.2, and discard $o$ otherwise. 

Experimental Results {#Sec_Results}
====================

Our MASC approach was tested on a benchmark composed of 77 well-known graphs commonly used to report computational results for MSCP: 39 are part of the COLOR 2002–2004 competitions and the 38 others are known as “DIMACS” instances.  Most of these graphs are available on-line from <http://mat.gsia.cmu.edu/COLOR04>, except the 6 “flat” instances that can be retrieved from <http://mat.gsia.cmu.edu/COLOR/instances.html>.  The main characteristics of each graph appear in Tables \[table\_MASC\] and \[table\_MASC\_large\], see columns 1–4 (COLOR 2002–2004 instances are at the top of Table \[table\_MASC\] and DIMACS instances at the bottom): Name of the graph, order ($|V|$), size ($|E|$), and chromatic sum $\Sigma$ (or the best known upper bound when $\Sigma$ is unknown). 

MASC is programmed in C++ and compiled using GNU gcc on a PC with 2.7 GHz CPU and 4 Gb RAM.  Like many memetic algorithms, we use a small population of 10 individuals.  The values of the other parameters were determined empirically, see Table \[Parameter\_Settings\].  Notice that $MaxGenerations = 50$ is the stop condition that determines the running time of the algorithm.  The best results of our MASC algorithm will be made available at http://www.info.univ-angers.fr/pub/hao/masumcol.html. 

      Parameter                      Sect.                  Description                                                      Value
  ------------------ ------------------------------------- -------------------------------------------------------------- -------
        $p_1$                 \[subsec\_sol\_TS\]          Maximum number of non-improving moves for TS using $N_1$           500
        $p_2$                 \[subsec\_sol\_TS\]          Maximum number of non-improving moves for TS using $N_2$          1000
        $p_3$                 \[subsec\_sol\_TS\]          Maximum number of non-improving moves of TS for perturbation      4000
        $p_4$                 \[subsec\_sol\_TS\]          Maximum iterations of TS procedure                               10000
   $MaxGenerations$   \[subsec\_sol\_population\_update\]  Maximum number of generations                                       50

  : Settings of parameters[]{data-label="Parameter_Settings"}

Computational Results {#subsec_computational_results}
---------------------

Columns 6–10 in Table \[table\_MASC\] present detailed computational results of our MASC algorithm: Best result obtained ($\Sigma_*$) with the number of required colors ($k_*$), success rate (SR, percentage of runs such that $\Sigma_* \le \Sigma$), average coloring sum (Avg.),  standard deviation ($\sigma$), and average running time to reach $\Sigma_*$ ($t$, in minutes).  Column $k$ shows the chromatic number or its best upper bound (i.e., the smallest number of colors for which a $k$-coloring is ever reported).  Furthermore, a sign “–” in column 4 ($\Sigma$) indicates that the instance was never tested in literature for the sum coloring problem (there are 18 such cases).  The reported values are based on 30 independent runs (i.e., with different random seeds). 

  ----------------- ------- -------- -------------- -- ----- ----------------- ----- --------- ---------- -------
                                                                                                          
  Name                $|V|$    $|E|$       $\Sigma$      $k$   $\Sigma_*(k_*)$    SR      Avg.    $\sigma$     $t$
  myciel3                11       20             21        4             21(4)   1.0      21.0        0.0     0.0
  myciel4                23       71             45        5             45(5)   1.0      45.0        0.0     0.0
  myciel5                47      236             93        6             93(6)   1.0      93.0        0.0     0.0
  myciel6                95      755            189        7            189(7)   1.0     189.0        0.0     0.1
  myciel7               191     2360            381        8            381(8)   1.0     381.0        0.0     1.1
  anna                  138      986            276       11           276(11)   1.0     276.0        0.0     0.1
  david                  87      812            237       11           237(11)   1.0     237.0        0.0     0.1
  huck                   74      602            243       11           243(11)   1.0     243.0        0.0     0.0
  jean                   80      508            217       10           217(10)   1.0     217.0        0.0     0.0
  homer                 561     1629              -       10      **1123(12)**   1.0    1136.2        5.8    80.6
  queen5.5               25      160             75        5             75(5)   1.0      75.0        0.0     0.0
  queen6.6               36      290            138        7            138(8)   1.0     138.0        0.0     1.1
  queen7.7               49      476            196        7            196(7)   1.0     196.0        0.0     0.0
  queen8.8               64      728            291        9            291(9)   1.0     291.0        0.0    12.8
  queen9.9               81     2112              -       10       **409(10)**   0.3     410.5        1.2     1.2
  queen8.12              96     1368              -       12       **624(12)**   1.0     624.0        0.0     0.0
  games120              120      638            443        9            443(9)   1.0     443.0        0.0     0.5
  miles250              128      387            325        8            325(8)   1.0     325.0        0.0     0.4
  miles500              128     1170      $\le 709$       20       **705(20)**   1.0     705.0        0.0     1.0
  fpsol2.i.1            496    11654           3403       65          3403(65)   1.0    3403.0        0.0     8.7
  fpsol2.i.2            451     8691              -       30      **1668(30)**   1.0    1668.0        0.0     5.7
  fpsol2.i.3            425     8688              -       30      **1636(30)**   1.0    1636.0        0.0     7.0
  mug88\_1               88      146            178        4            178(4)   1.0     178.0        0.0     0.1
  mug88\_25              88      146            178        4            178(4)   1.0     178.0        0.0     0.2
  mug100\_1             100      166            202        4            202(4)   1.0     202.0        0.0     0.2
  mug100\_25            100      166            202        4            202(4)   1.0     202.0        0.0     0.3
  2-Insertions\_3        37       72             62        4             62(4)   1.0      62.0        0.0     0.0
  3-Insertions\_3        56      110             92        4             92(4)   1.0      92.0        0.0     0.0
  inithx.i.1            864    18707              -       54      **3676(54)**   1.0    3676.0        0.0     7.6
  inithx.i.2            645    13979              -       31      **2050(31)**   1.0    2050.0        0.0     4.4
  inithx.i.3            621    13969              -       31      **1986(31)**   1.0    1986.0        0.0     1.8
  mulsol.i.1            197     3925              -       49      **1957(49)**   1.0    1957.0        0.0     0.1
  mulsol.i.2            188     3885              -       31      **1191(31)**   1.0    1191.0        0.0     0.2
  mulsol.i.3            184     3916              -       31      **1187(31)**   1.0    1187.0        0.0     0.2
  mulsol.i.4            185     3946              -       31      **1189(31)**   1.0    1189.0        0.0     0.2
  mulsol.i.5            186     3973              -       31      **1160(31)**   1.0    1160.0        0.0     0.2
  zeroin.i.1            211     4100              -       49      **1822(49)**   1.0    1822.0        0.0     0.2
  zeroin.i.2            211     3541           1004       30          1004(30)   1.0    1004.0        0.0     0.1
  zeroin.i.3            206     3540            998       30           998(30)   1.0     998.0        0.0     0.1
  DSJC125.1             125      736            326        5            326(7)   0.7     326.6        0.9     4.4
  DSJC125.5             125     3891           1012       17          1012(18)   0.1    1020.0        3.9     3.5
  DSJC125.9             125     6961           2503       44          2503(44)   0.5    2508.0        5.6     1.9
  DSJC250.1             250     3218            973        8            974(9)   0.0     990.5        8.3    17.3
  DSJC250.5             250    15668           3219       28          3230(31)   0.0    3253.7       14.3    23.1
  DSJC250.9             250    27897   $\le 8\,286$       72      **8280(74)**   0.1    8322.7       22.3     5.6
  DSJC500.1             500    12458           2850       12          2940(14)   0.0    3013.4       28.3    50.4
  DSJC500.5             500    62624          10910       48         11101(53)   0.0   11303.5       73.9   202.5
  DSJC500.9             500   112437          29912      126        29994(126)   0.0   30059.1       31.6    90.9
  flat300\_20\_0        300    21375           3150       20          3150(20)   1.0    3150.0        0.0     0.0
  flat300\_26\_0        300    21633           3966       26          3966(26)   1.0    3966.0        0.0     0.8
  flat300\_28\_0        300    21695   $\le 4\,282$       28      **4238(30)**   0.1    4313.4       22.3   309.7
  le450\_5a             450     5714              -        5       **1350(5)**   1.0    1350.0        0.0     0.7
  le450\_5b             450     5734              -        5       **1350(5)**   1.0    1350.0        0.0     0.4
  le450\_5c             450     9803              -        5       **1350(5)**   1.0    1350.0        0.0     0.2
  le450\_5d             450     9757              -        5       **1350(5)**   1.0    1350.0        0.0     0.5
  le450\_15a            450     8168           2632       15          2706(19)   0.0    2742.6       13.8    41.3
  le450\_15b            450     8169           2642       15          2724(19)   0.0    2756.2       14.8    40.3
  le450\_15c            450    16680   $\le 3\,866$       15      **3491(16)**   1.0    3491.0        0.0    45.3
  le450\_15d            450    16750   $\le 3\,921$       15      **3506(17)**   1.0    3511.8        3.6    59.8
  le450\_25a            450     8260           3153       25          3166(27)   0.0    3176.8        4.4    39.2
  le450\_25b            450     8263           3366       25          3366(26)   0.1    3375.1        3.4    40.3
  le450\_25c            450    17343           4515       25          4700(31)   0.0    4773.3       25.2    75.3
  le450\_25d            450    17425           4544       25          4722(29)   0.0    4805.7       27.4    63.4
  ----------------- ------- -------- -------------- -- ----- ----------------- ----- --------- ---------- -------

  : Detailed computational results of MASC on the set of 39 COLOR 2002-2004 instances (upper part) and 24 DIMACS instances (bottom part)[]{data-label="table_MASC"}

From Table \[table\_MASC\], one observes that for the 25 cases of 39 COLOR 2002–2004 instances with known upper bounds (see top part of the table), MASC improves the best known upper bound for one instance (miles500) and equals the best known results for the other 24 graphs.  For the remaining 14 cases, we provide upper bounds for the first time.  Furthermore, MASC achieves robust results here since $\textrm{SR} = 1.0$ and $\sigma = 0.0$ for these graphs except two instances (homer and queen9.9).  The average running time of MASC ranges from less than one second to about 13 minutes except for the homer instance. 

For the set of 24 DIMACS instances (bottom part), the MASC algorithm improves the best known upper bound for 4 graphs (DSJC250.9, flat300\_28\_0, le450\_15c, and le450\_15d) and equals the best known results for 6 instances.  Unfortunately, MASC was unable to reach the best known results for the other 10 graphs (see lines where $\textrm{SR} = 0.0$).  For the four graphs which were not tested previously, we report upper bounds achieved for the first time.  The average running time is less than 76 minutes except for the DSJC500.5 and flat300\_28\_0 instances.  Finally, we notice that the number of colors needed to ensure the best sum coloring ($k_*$) can be larger than the chromatic number or its best upper bound ($k$). 

Comparisons With State-of-the-art Algorithms {#subsec_comparison_results}
--------------------------------------------

Table \[table\_many\_algorithms\] compares MASC with 5 recent effective algorithms that cover the best known results for the considered benchmark: EXSCOL , BLS , MDS5 , MRLF , and HA .  No averaged value appears in the table for HA, MDS5, and MRLF since this information is not given in .  Furthermore, “–” marks signal that some instances were not tested by some approaches. 

  ----------------- -------------- -- ------------ --------- ------ ------------ --------- ------------ ------------ ------------ ------------ ---------
                                                              MDS5          MRLF        HA                                                     
  Name                    $\Sigma$      $\Sigma_*$      Avg.           $\Sigma_*$      Avg.    $\Sigma_*$   $\Sigma_*$   $\Sigma_*$   $\Sigma_*$      Avg. 
  myciel3                       21              21      21.0                  21      21.0           21           21           21           21      21.0
  myciel4                       45              45      45.0                  45      45.0           45           45           45           45      45.0
  myciel5                       93              93      93.0                  93      93.0           93           93           93           93      93.0
  myciel6                      189             189     189.0                 189     196.6          189          189          189          189     189.0
  myciel7                      381             381     381.0                 381     393.8          381          381          381          381     381.0
  anna                         276             283     283.2                 276     276.0          276          277            –          276     276.0
  david                        237             237     238.1                 237     237.0          237          241            –          237     237.0
  huck                         243             243     243.8                 243     243.0          243          244          243          243     243.0
  jean                         217             217     217.3                 217     217.0          217          217            –          217     217.0
  queen5.5                      75              75      75.0                  75      75.0           75           75            –           75      75.0
  queen6.6                     138             150     150.0                 138     138.0          138          138          138          138     138.0
  queen7.7                     196             196     196.0                 196     196.0          196          196            –          196     196.0
  queen8.8                     291             291     291.0                 291     291.0          291          303            –          291     291.0
  games120                     443             443     447.9                 443     443.0          443          446          446          443     443.0
  miles250                     325             328     333.0                 327     328.8          325          334          343          325     325.0
  miles500               $\le 709$             709     714.5                 710     713.3          712          715          755      **705**     705.0
  fpsol2.i.1                  3403               –         –                   –         –         3403            –         3405         3403    3403.0
  mug88\_1                     178               –         –                   –         –          178            –          190          178     178.0
  mug88\_25                    178               –         –                   –         –          178            –          187          178     178.0
  mug100\_1                    202               –         –                   –         –          202            –          211          202     202.0
  mug100\_25                   202               –         –                   –         –          202            –          214          202     202.0
  2-Insertions\_3               62               –         –                   –         –           62            –           62           62      62.0
  3-Insertions\_3               92               –         –                   –         –           92            –           92           92      92.0
  zeroin.i.2                  1004               –         –                   –         –         1004            –         1013         1004    1004.0
  zeroin.i.3                   998               –         –                   –         –          998            –         1007          998     998.0
  DSJC125.1                    326             326     326.7                 326     326.9          326          352            –          326     326.6
  DSJC125.5                   1012            1017    1019.7                1012    1012.9         1015         1141            –         1012    1020.0
  DSJC125.9                   2503            2512    2512.0                2503    2503.0         2511         2653            –         2503    2508.0
  DSJC250.1                    973             985     985.0                 973     982.5          977         1068            –          974     990.5
  DSJC250.5                   3219            3246    3253.9                3219    3248.5         3281         3658            –         3230    3253.7
  DSJC250.9           $\le 8\,286$            8286    8288.8                8290    8316.0         8412         8942            –     **8280**    8322.7
  DSJC500.1                   2850            2850    2857.4                2882    2942.9         2951         3229            –         2940    3013.4
  DSJC500.5                  10910           10910   10918.2               11187   11326.3        11717        12717            –        11101   11303.5
  DSJC500.9                  29912           29912   29936.2               30097   30259.2        30872        32703            –        29994   30059.1
  flat300\_20\_0              3150            3150    3150.0                   –         –            –            –            –         3150    3150.0
  flat300\_26\_0              3966            3966    3966.0                   –         –            –            –            –         3966    3966.0
  flat300\_28\_0      $\le 4\,282$            4282    4286.1                   –         –            –            –            –     **4238**    4313.4
  le450\_15a                  2632            2632    2641.9                   –         –            –            –            –         2706    2742.6
  le450\_15b                  2642            2642    2643.4                   –         –            –            –            –         2724    2756.2
  le450\_15c          $\le 3\,866$            3866    3868.9                   –         –            –            –            –     **3491**    3491.0
  le450\_15d          $\le 3\,921$            3921    3928.5                   –         –            –            –            –     **3506**    3511.8
  le450\_25a                  3153            3153    3159.4                   –         –            –            –            –         3166    3176.8
  le450\_25b                  3366            3366    3371.9                   –         –            –            –            –         3366    3375.1
  le450\_25c                  4515            4515    4525.4                   –         –            –            –            –         4700    4773.3
  le450\_25d                  4544            4544    4550.0                   –         –            –            –            –         4722    4805.7
  ----------------- -------------- -- ------------ --------- ------ ------------ --------- ------------ ------------ ------------ ------------ ---------

  : Comparisons of MASC with five state-of-the-art sum coloring algorithms[]{data-label="table_many_algorithms"}

  -------- ---- -------- ------- -------
                                 
                  Better   Equal   Worse
  EXSCOL    36        12      16       8
  BLS       25         5      17       3
  MDS5      34         9      25       0
  MRLF      25        16       9       0
  HA        19        10       9       0
  -------- ---- -------- ------- -------

  : MASC vs. five state-of-the-art sum coloring algorithms[]{data-label="comparisons_other_algorithms"}

Since the reference algorithms give only results for a (small) subset of the considered benchmark, it is difficult to analyze the performance of these algorithms by statistical tests.  Hence, we compare the performance between MASC and these reference algorithms one by one and summarize the comparisons in Table \[comparisons\_other\_algorithms\].  The first column of Table \[comparisons\_other\_algorithms\] indicates the name of the reference heuristics, followed by the number $\#G$ of graphs tested by each algorithm and shown in Table \[table\_many\_algorithms\].  The last three columns give the number of times MASC reports a better, equal, or worse result compared to each reference algorithm. 

From Table \[comparisons\_other\_algorithms\], it can be observed that MASC obtains absolutely no worse results than MDS5, MRLF, and HA (see the last three lines).  Furthermore, MASC gets better results than these algorithms for 9, 16, and 10 instances respectively.  Our algorithm is also quite competitive with EXSCOL and BLS which are the most recent and effective methods since it obtains better or equivalent results for 28 and 22 graphs respectively.  MASC reaches worse results than EXSCOL and BLS only for 8 and 3 graphs respectively. 

Experiment on Large Graphs {#subsec_experiments_large}
--------------------------

We turn now our attention to the performance of our MASC algorithm to color large graphs with at least 500 vertices.  These large graphs are known to be quite difficult for almost all the existing sum coloring approaches except EXSCOL which dominates the other heuristics particularly on large graphs.  We show a new experiment with MACS applied to color 17 large graphs.  In this experiment, we run MASC 10 times on each graph under exactly the same condition as in Section \[subsec\_computational\_results\].  The only difference is that we use the solution of EXSCOL[^1] as one of MASC’s 10 initial solutions while the 9 other initial solutions are generated according to the procedure described in Section \[subsec\_sol\_initial\_population\].  With this experiment, we aimed to investigate two interesting questions.  Is it possible for MASC to improve the results of the powerful EXSCOL algorithm?  Does the initial population influence the performance of MASC?  The computational outcomes of this experiment are provided in Table \[table\_MASC\_large\]. 

  ----------------- ------- -------- ---------- -- ------------ ---------- -- ----- ----------------- ---------- ---------- -------
                                                                                                                            
  Name                $|V|$    $|E|$   $\Sigma$      $\Sigma_*$       Avg.       $k$   $\Sigma_*(k_*)$       Avg.    $\sigma$     $t$
  DSJC500.1             500    12458       2850            2850     2857.4       12      **2841(14)**     2844.1        3.2    28.9
  DSJC500.5             500    62624      10910           10910    10918.2       48     **10897(51)**    10905.8        4.6    73.3
  DSJC500.9             500   112437      29912           29912    29936.2      126    **28896(131)**    29907.8        5.8    59.0
  DSJC1000.1           1000    49629       9003            9003     9017.9       20      **8995(22)**     9000.5        3.0    70.7
  DSJC1000.5           1000   249826      37598           37598    37673.8       83     **37594(87)**    37597.6        1.2   200.4
  DSJC1000.9           1000   449449     103464          103464   103531.0      223       103464(231)   103464.0        0.0   125.9
  flat1000\_50\_0      1000   245000      25500           25500    25500.0       50         25500(50)    25500.0        0.0     0.1
  flat1000\_60\_0      1000   245830      30100           30100    30100.0       60         30100(60)    30100.0        0.0   114.6
  flat1000\_76\_0      1000   246708      37167           37167    37213.2       82        37167 (85)    37167.0        0.0     1.1
  latin\_sqr\_10        900   307350      42223           42223    42392.7       98    **41444(100)**    41481.5       19.1   101.2
  wap05                 905    43081      13680           13680    13718.4       50     **13669(51)**    13677.8        3.7     3.3
  wap06                 947    43571      13778           13778    13830.9       46     **13776(48)**    13777.8        0.6     4.1
  wap07                1809   103368      28629           28629    28663.8       46     **28617(50)**    28624.7        3.8    12.4
  wap08                1870   104176      28896           28896    28946.0       45     **28885(50)**    28890.9        3.2    15.1
  qg.order30            900    26100      13950           13950    13950.0       30     **12581(31)**    12641.3       45.7     4.2
  qg.order40           1600    62400      32800           32800    32800.0       40         32800(40)    32800.0        0.0    11.8
  qg.order60           3600   212400     110925          110925   110993.0       60    **109800(60)**   109800.0        0.0   290.6
  ----------------- ------- -------- ---------- -- ------------ ---------- -- ----- ----------------- ---------- ---------- -------

  : Results of MASC on 17 large graphs with at least 500 vertices[]{data-label="table_MASC_large"}

In Table \[table\_MASC\_large\], column 4 presents the best known result ($\Sigma$) in the literature, columns 5–6 present the best result ($\Sigma_*$) and the average coloring sum (Avg.)  of EXSCOL and columns 7–11 present detailed computational results of our MASC algorithm: Best result obtained ($\Sigma_*$) with the number of required colors ($k_*$), average coloring sum (Avg.),  standard deviation ($\sigma$), and average running time to reach $\Sigma_*$ ($t$, in minutes).  One notices that the values of columns 4 and 5 are identical.  This is because EXSCOL is the single approach in the literature able to attain these results. 

Table \[table\_MASC\_large\] shows that with the help of its search mechanism, our MASC algorithm is able to further improve the best known results of 12 instances (entries in bold).  This is remarkable given that no previous approach can even equal these results.  Moreover, if we contrast the results of the three DSJC500.$x$ graphs ($x=1,5,9$) reported in Tables \[table\_MASC\] and \[table\_MASC\_large\], it is clear that the initial population impacts directly MASC’s outcomes.  This indicates that the performance of MASC could be further improved by using a more powerful coloring algorithm to generate the initial solutions of its population. 

Analysis of MASC {#Sec_analysis_MASC}
================

In this section, we investigate the influence of two important ingredients of the proposed memetic algorithm, i.e., the multi-parent crossover operator and the combined neighborhood.  Experiments were based on 16 selected graphs of different types, for which some reference algorithms cannot achieve the best known results.  Hence, these selected instances can be considered to be difficult and representative. 

Influence of the Multi-parent Crossover Operator {#subsec_sol_influence_Crossover}
------------------------------------------------

For our memetic algorithm, it is relevant to evaluate the effectiveness of its crossover operator.  To verify this, we carry out experiments on the 16 selected graphs and run both MASC (using the MGPX crossover) and DNTS (without MGPX) for 30 times (with the same parameter $p_1$, $p_2$ and $p_3$ settings as defined in Table \[Parameter\_Settings\]).  The DNTS (without MGPX) starts with a single solution which is generated for MASC.  DNTS stops when a maximum number of $5 \times 10^5$ iterations in order to make sure that MASC and DNTS are given the same search effort.  The results are given in Table \[table\_MASC\_TS\]. 

From Table \[table\_MASC\_TS\], one notices that DNTS equals and improves respectively 5 and 3 best known results while MASC equals and improves respectively 5 and 11 best known results.  Furthermore, the last column *tt* (t-test) indicates whether the observed difference between MASC and DNTS is statistically significant when a 95% confidence t-test is performed in terms of the best result obtained ($\Sigma_*$).  The t-test indicates that MASC is statistically better than DNTS for 12 out of 16 cases except for the instances where DNTS can achieve the best known results ($\Sigma$).  These comparative results provide clear evidences that the MGPX crossover operator plays an important role in the MASC algorithm. 

  ---------------- -------------- -- ------------ -------- -- ------------ -------- --- --
                                                                                        
  Name                   $\Sigma$      $\Sigma_*$     Avg.       $\Sigma_*$     Avg.      
  anna                        276           *276*    276.0           *276*    276.0  N  
  queen6.6                    138           *138*    138.0           *138*    138.0  N  
  miles250                    325           *325*    325.0           *325*    325.0  N  
  miles500              $\le 709$         **705**    705.0         **705**    705.6  Y  
  DSJC125.1                   326           *326*    326.6           *326*    328.6  Y  
  DSJC125.5                  1012        **1012**   1020.0            1016   1029.8  Y  
  DSJC125.9                  2503        **2503**   2508.0            2506   2530.1  Y  
  DSJC250.1                   973         **974**    990.5             981    997.7  Y  
  DSJC250.5                  3219        **3230**   3253.7            3234   3301.7  Y  
  DSJC250.9          $\le 8\,286$        **8280**   8322.7            8321   8381.9  Y  
  flat300\_26\_0             3966          *3966*   3966.0          *3966*   3966.0  N  
  flat300\_28\_0     $\le 4\,282$        **4238**   4313.4            4303   4406.3  Y  
  le450\_15c         $\le 3\,866$        **3491**   3491.0        **3491**   3492.1  Y  
  le450\_15d         $\le 3\,921$        **3506**   3511.8        **3506**   3515.0  Y  
  le450\_25c                 4515        **4700**   4773.3            4749   4803.9  Y  
  le450\_25d                 4544        **4722**   4805.7            4784   4835.3  Y  
  ---------------- -------------- -- ------------ -------- -- ------------ -------- --- --

  : Comparative results of MASC and DNTS[]{data-label="table_MASC_TS"}

Influence of the Neighborhood Combination {#subsec_sol_influence_neighborhood_combination}
-----------------------------------------

The neighborhood is an important element that influences the local search procedure.  Our proposed algorithm relies on two different neighborhoods: $N_1$ (neighborhood based on connected components) and $N_2$ (neighborhood based on one-vertex-move) which are explored in a token-ring way (see Section \[subsec\_sol\_TS\]).  In this section, we investigate the interest of this combined use of the two neighborhoods.  For this purpose, we carried out experiments on the 16 selected graphs to compare the original Double-Neighborhood Tabu Search (DNTS) with two variants which uses only one neighborhood $N_1$ or $N_2$. We use below TS$_{N1}$ and TS$_{N2}$ to denote these two variants.  These three TS procedures (DNTS, TS$_{N1}$ and TS$_{N2}$) are run under the same stop condition, i.e. limited to $5 \times 10^5 $ iterations. 

We run 30 times these TS procedures to solve each of the 16 selected graphs and report the computational outcomes (the best and average results) in Table \[table\_Multi\_Single\].  One easily observes that DNTS obtains better or equal results compared to TS$_{N1}$ and TS$_{N2}$ for all the instances in terms of the best known result ($\Sigma_*$) and the average result (Avg.).  The t-test *$tt_i$* ($i = 1, 2$) in the last two columns confirms that with a 95% confidence level DNTS is slightly or significantly better than TS$_{N1}$ and TS$_{N2}$. This experiment demonstrates thus the advantage of the token-ring combination of the two neighborhoods compared to each individual neighborhood. 

  ---------------- ------------ -------- -- ------------ -------- -- ------------ -------- --- --- -- --
                                                                                                      
                     $\Sigma_*$     Avg.       $\Sigma_*$     Avg.       $\Sigma_*$     Avg.             
  anna                      276    276.0             282    285.8             276    276.0  Y    N    
  queen6.6                  138    138.0             138    138.4             138    138.0  Y    N    
  miles250              **325**    325.0             346    361.6             335    340.7  Y    Y    
  miles500              **705**    705.6             722    736.0             719    730.9  Y    Y    
  DSJC125.1             **326**    328.6             334    340.8             329    334.0  Y    Y    
  DSJC125.5            **1016**   1029.8            1031   1045.1            1020   1031.8  Y    N    
  DSJC125.9            **2506**   2530.1            2514   2557.6            2512   2538.3  Y    N    
  DSJC250.1             **981**    997.7            1004   1021.3            1022   1039.9  Y    Y    
  DSJC250.5            **3234**   3301.7            3271   3323.9            3260   3306.5  Y    N    
  DSJC250.9            **8321**   8381.9            8347   8405.6            8318   8387.5  Y    N    
  flat300\_26\_0           3966   3966.0            3966   3966.0            3966   3966.0  N    N    
  flat300\_28\_0       **4303**   4406.3            4347   4427.8            4332   4435.5  N    Y    
  le450\_15c           **3491**   3492.5            3503   3517.2            3508   3551.8  Y    Y    
  le450\_15d           **3506**   3515.0            3528   3538.5            3526   3568.2  Y    Y    
  le450\_25c           **4749**   4803.9            4828   4893.9            5005   5067.4  Y    Y    
  le450\_25d           **4784**   4835.3            4848   4907.0            5035   5119.1  Y    Y    
  ---------------- ------------ -------- -- ------------ -------- -- ------------ -------- --- --- -- --

  : Comparative results of the LS improvement method according to the neighborhood employed[]{data-label="table_Multi_Single"}

Conclusion {#Sec_Conclusion}
==========

In this paper, we presented a memetic algorithm (MASC) to deal with the minimum sum coloring problem (MSCP).  The proposed algorithm employs an effective tabu search procedure with a combination of two neighborhoods, a multi-parent crossover operator and a population updating mechanism to balance intensification and diversification. 

We assessed the performance of MASC on 77 well-known graphs from the DIMACS and COLOR 2002-2004competitions.  MASC can improve 17 best known upper bounds including 11 large and very hard graphs with at least 500 vertices while equaling 30 previous best results.  We also report upper bounds for the 18 remaining graphs for the first time.  Compared with five recent and effective algorithms which cover the best known results for the tested instances, our MASC algorithm remains quite competitive. 

Furthermore, we investigated two important components of the proposed algorithm.  The experiments demonstrate the relevance of the multi-parent crossover operator and the combined neighborhood for the overall performance of MASC. 

Acknowledgment {#acknowledgment .unnumbered}
==============

The work is partially supported by the RaDaPop (2009-2013) and LigeRo projects (2009-2013) from the Region of Pays de la Loire (France).  Support for Yan Jin from the China Scholarship Council is also acknowledged. 

[10]{} url \#1[`#1`]{}urlprefix

U. Benlic, J.-K. Hao, A study of breakout local search for the minimum sum coloring problem, in: L. Bui, Y. Ong, N. Hoai, H. Ishibuchi, P. Suganthan (eds.),  Simulated Evolution and Learning, vol.  7673 of Lecture Notes in Computer Science, Springer, Berlin / Heidelberg, Germany, 2012, pp.  128–137. 

H. Bouziri, M. Jouini, A tabu search approach for the sum coloring problem, Electronic Notes in Discrete Mathematics 36 (2010) 915–922. 

L, Di Gaspero, A. Schaerf, Neighborhood portfolio approach for local search applied to timetabling problems.  Journal of Mathematical Modeling and Algorithms 5(1) (2006) 65�-89. 

S. Douiri, S. Elbernoussi, New algorithm for the sum coloring problem, International Journal of Contemporary Mathematical Sciences 6 (2011) 453–463. 

P. Galinier, J.-K. Hao, Hybrid evolutionary algorithms for graph coloring, Journal of Combinatorial Optimization 3 (4) (1999) 379–397. 

F. Glover, M. Laguna, Tabu Search, Kluwer Academic Publishers, Dordrecht, The Nederlands, 1997. 

J.-P. Hamiez, J.-K. Hao, Scatter search for graph coloring, in: P. Collet, E. Lutton, M. Schoenauer, C. Fonlupt, J.-K. Hao (eds.),  Artificial Evolution, vol.  2310 of Lecture Notes in Computer Science, Springer, Berlin / Heidelberg, Germany, 2002, pp.  168–179. 

A. Helmar, M. Chiarandini, A local search heuristic for chromatic sum, in: L. [Di Gaspero]{}, A. Schaerf, T. Stützle (eds.),  Proceedings of the 9th Metaheuristics International Conference, 2011, pp.  161–170. 

A. Hertz, D. [de Werra]{}, Using tabu search techniques for graph coloring, Computing 39 (4) (1987) 345–351. 

Z. Kokosiński, K. Kwarciany, On sum coloring of graphs with parallel genetic algorithms, in: B. Beliczynski, A. Dzielinski, M. Iwanowski, B. Ribeiro (eds.),  Adaptive and Natural Computing Algorithms, vol.  4431 of Lecture Notes in Computer Science, Springer, Berlin / Heidelberg, Germany, 2007, pp.  211–219. 

E. Kubicka, The chromatic sum of graphs, Ph.D. thesis, Western Michigan University, USA (1989). 

E. Kubicka, A. Schwenk, An introduction to chromatic sums, in: Proceedings of the 17th ACM Annual Computer Science Conference, ACM Press, New York (NY) USA, 1989, pp.  39–45. 

Y. Li, C. Lucet, A. Moukrim, K. Sghiouer, Greedy algorithms for the minimum sum coloring problem, in: Logistique et Transports Conference, 2009. 

Z. Lü, J.-K. Hao, A memetic algorithm for graph coloring, European Journal of Operational Research 203 (1) (2010) 241–250. 

Z. Lü, J.-K. Hao, F. Glover.  Neighborhood analysis: a case study on curriculum-based course timetabling.  Journal of Heuristics 17(2) (2011) 97–118. 

M. Malafiejski, Sum coloring of graphs, in: M. Kubale (ed.),  Graph Colorings, vol.  352 of Contemporary mathematics, American Mathematical Society, New Providence (Rhode Island) USA, 2004, pp.  55–65. 

E. Malaguti, M. Monaci, P. Toth, A metaheuristic approach for the vertex coloring problem, INFORMS Journal on Computing 20 (2) (2008) 302–316. 

P. Moscato, C. Cotta, A gentle introduction to memetic algorithms, in: F. Glover, G. Kochenberger (eds.),  Handbook of Metaheuristics, vol.  57 of International Series in Operations Research and Management Science, chap.  5, Kluwer Academic Publishers, Dordrecht, The Nederlands, 2003, pp.  105–144. 

F. Neri, C. Cotta, P. Moscato (eds.),  Handbook of Memetic Algorithms, vol.  379 of Studies in Computational Intelligence, Springer, Berlin / Heidelberg, Germany, 2012. 

D. Porumbel, J.-K. Hao, P. Kuntz, An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring, Computers & Operations Research 37 (10) (2010) 1822–1832. 

Q. Wu, J.-K. Hao, An effective heuristic algorithm for sum coloring of graphs, Computers & Operations Research 39 (7) (2012) 1593–1600. 

[^1]: Available at <http://www.info.univ-angers.fr/pub/hao/exscol.html>
