Ant Colony Optimization in Vertex Coloring (Tuklas Vol. 13, No. 5 - Jan. 14, 2012)

ANT COLONY OPTIMIZATION IN VERTEX COLORING

Advances in science and technology are not always driven by human genius alone. Sometimes, inspiration can be obtained from the other creatures around us which, in their own little worlds, are experts. This was what happened with Daniel Costa and Alain Hertz when they developed a graph coloring method based on the behavior of ants. They presented this method in the 1997 article "Ants can colour graphs" in The Journal of the Operational Research Society.

Preliminaries: The Vertex Coloring Problem
A graph is a set of vertices (or nodes) together with a set of edges (lines or arcs) that each connect two vertices. In particular, a simple graph is a graph where there is only at most one edge between two vertices and that has no loops (edges that begin and end on the same vertex). Some examples are given below.

Figure 1: (a) A simple graph. (b) A non-simple graph.

Furthermore, the vertex coloring problem (also popularly known as the graph coloring problem) aims to obtain the minimum number of colors required to color the vertices of a (simple) graph in such a way that no two vertices have the same color.

Figure 2: Optimal coloring of a graph.

For small graphs, the vertex coloring problem is easy; in general, this problem is considered to be difficult. Most developments revolve around what we call heuristics which generate sub-optimal solutions only, i.e., solutions that might not be the best but are considered to be good. Among these heuristics are constructive methods that color each vertex while trying to keep the number of colors used as small as possible.

The Behavior of Real Ants
In 1991, Alberto Colorni, Marco Dorigo and Vittorio Maniezzo introduced in their paper "Distributed optimization by ant colonies" an optimization algorithm that is based on the observations of real ants in the environment. This algorithm is now called Ant Colony Optimization.
Ant colony optimization is inspired by the observation that a colony of ants have the tendency to move along an organized path. This self-organizing behavior of ants is due to a chemical substance called a pheromone that they leave on their trails when they move from one place to another. The general term for this indirect communication done by altering the environment is stigmergy. For ants, stigmergy is done using trail pheromones.
Ants that encounter a path with a high pheromone deposit are more likely to choose that path over other available paths. This process of choosing paths biased by trail pheromones allow for a group of ants to converge on a single path as observed in natural situations.
What is interesting is that ants usually converge on the shortest path between their source and destination. A simple explanation for this is that over time, the trail pheromone starts to evaporate which reduces the trail's attractive strength. Because long paths allow for more pheromone evaporation, pheromone density becomes higher on shorter paths than longer ones. In turn, the shortest path becomes more attractive until all the ants converge on it.

Figure 3: Ants converge on the shortest path.

Ant Colony Optimization
The idea behind ant colony optimization is to use artificial ants (called agents) that are also capable of indirect communication or what we can call artificial stigmergy. However, the agents have additional capabilities that real ants do not have. These additional capabilities are 

1. the ability to determine the quality of solutions,
2. deposit amount of pheromones based on solution quality,
3. and access to colony-wide information, in particular, the best solution obtained so far.

The premise that a real ant colony might not converge on the shortest path makes ant
colony optimization a probabilistic algorithm, or a heuristic.

Ant Colony Optimization in Vertex Coloring
Costa and Hertz called the ant algorithm for the vertex coloring problem ANTCOL. The ANTCOL algorithm uses a \colony" of arti cial ants to color the vertices of the graph. ANTCOL can be outlined as follows:

1. Each virtual ant from the colony will color the graph using a known constructive heuristic. When they obtain a solution, each will record the quality of the solution (i.e. a better solution is one with fewer colors used).

2. Based on the quality of the solution obtained, each virtual ant will place virtual pheromones on each pair of vertices. If two non-adjacent vertices have the same color, then pheromones will be placed on that pair through a virtual matrix. Here, pheromones are used to reinforce the desirability of coloring two non-adjacent vertices with the same color.

3. Each virtual ant accesses the colony-wide information to determine which pairs of non-adjacent vertices are desirable to be colored using the same color. With this new information, each ant repeats step 1.

Performing several rounds of ANTCOL will most likely return an optimal coloring of the graph given.

This evolutionary technique and its successors are important because coloring the vertices of a graph has various applications in real life situations such as scheduling, allocation and even recreational activities like Sudoku.

ABOUT THE AUTHOR:
Mark Tolentino is an Assistant Instructor at the Ateneo de Manila University. He is currently on leave, taking his Ph.D. in Mathematics at the same university.

REFERENCES:

Colorni, Alberto, Marco Dorigo and Vittorio Maniezzo. "Distributed optimization by ant colonies." Proceedings of the First European Conference on Arti cial Life Paris. Ed. P Bourgine FJ Varela. Cambridge, Massachussetts: MIT/Press/Bradford Books, 1991. 134-142.
Costa, Daniel and Alain Hertz. "Ants can colour graphs." The Journal of the Operational Research Society 48.3 (1997): 295-305.
Dorigo, Marco and Thomas Stutzle. Ant colony optimization. Cambridge: MIT Press, 2004.

OLYMPIAD CORNER

from the XXXIX Republic Competition of Mathematics in Macedonia Class I, 1999

Problem: The sum of three integers \(a, b\) and \(c\) is 0. Prove that \(2a^4+2b^4+2c^4\) is the square of an integer.

Solution: 
Let \(p(x) = x^3 + sx^2 + qx + r\) be a third degree polynomial having \(a, b\) and \(c\) as roots. Since \(s = -(a+b+c) = 0\), we can rewrite \(p(x) = x^3+qx+r\). Note also that \(ab+bc+ca = q\), a fact we will use later.

Since \(a, b\) and \(c\) are roots, \(p(a) = p(b) = p(c) = 0\) or \[ a^3 + qa + r = 0, \quad \quad \quad b^3 + qb + r = 0, \quad \quad \quad c^3 + qc + r = 0. \] Multiply each equation by \(2a, 2b\) and \(2c\) respectively. Then add. We have \[ \begin{align*} 2a(a^3+qa+r) + 2b(b^3+qb+r) + 2c(c^3+qc+r) &= 2a(0)+2b(0) + 2c(0) \\ 2(a^4+b^4+c^4) + 2q(a^2+b^2+c^2) + 2r(a+b+c) &= 0 \\ 2a^4+2b^4+ 2c^4 &= -2q(a^2+b^2+c^2) \end{align*} \] Now, note that \(0 = (a+b+c)^{2} = (a^{2}+b^{2}+c^{2}) + 2(ab+bc+ca)\). It follows that \[ a^{2}+b^{2}+c^{2} = -2(ab+bc+ca) = -2q. \] Therefore, \(2a^{4} + 2b^{4} + 2c^{4} = -2q(-2q) = (2q)^{2}\), so \(2a^{4} + 2b^{4} + 2c^{4}\) really is the square of an integer.

PROBLEMS

13. \(AB\) is a chord in a circle with center \(O\) and radius 52 cm. The point \(M\) divides the chord \(AB\) such that \(AM = 63\) cm and \(MB = 33\) cm. Find the length of \(OM\) in cm.
    
14. If \(a\) and \(b\) are positive real numbers such that \(a+b=1\), prove that \[ \left( a+\frac{1}{a} \right)^2 + \left( b+\frac{1}{b} \right)^2 \geq \frac{25}{2}.\]
15. For any non-negative integers \(m, n, p,\) prove that the polynomial \(x^{3m} + x^{3n+1}+x^{3p+2}\) has the factor \(x^2 + x + 1\).

We welcome readers to submit solutions to the problems posed below for publication consideration. Solutions must be preceded by the solver's name, school affiliation and year level. The deadline for submission is January 28, 2012. 

SOLUTIONS

(for December 3 and 10, 2011)

7. Evaluate\[ \frac{1}{(1+1)!} + \frac{2}{(2+1)!} + \ldots + \frac{n}{(n+1)!}, \] where \(n\) is any natural number.
   (solved by Ferdinand John S. Briones [MSHS], Emman Joshua B. Busto [PSHS - Main], Dianne Garcia [AA], Albert Jason Z. Olaya [PSHS - Main], Gerald M. Pascua [PSHS - Main] and Marisse T. Sonido [AA])
   
   
   SOLUTION: 
   Simply note that for \(1 \leq k \leq n\), we have \[ \frac{k}{(k+1)!} = \frac{k+1-1}{(k+1)!} = \frac{1}{k!} - \frac{1}{(k+1)!},\] Thus the original sum reduces to \[ 1 - \frac{1}{2!} + \frac{1}{2!} - \frac{1}{3!} + \ldots + \frac{1}{(n-1)!} - \frac{1}{n!} + \frac{1}{n!} - \frac{1}{(n+1)!} = 1 - \frac{1}{(n+1)!}. \]
8. Suppose that the incircle of \(ABC\) is tangent to the sides \(BC, CA, AB\) at \(D, E, F\) respectively. Prove that \[ EF^2 + FD^2 + DE^2 \leq \frac{s^2}{3},\] where \(s\) is the semiperimeter of \(ABC\). (Taken from Inequalities by Manfrino, Ortega, and Delgado)
   (solved by Ferdinand John S. Briones [MSHS])
   
   
   SOLUTION: 
   Let \(R\), \(r\) and \(s\) denote the circumradius, inradius and semiperimeter of triangle \(ABC\), respectively. Note that \(\text{area}(ABC)=\frac{abc}{4R}=sr\). We use the AM-GM inequality to obtain \[2s = a+b+c \geq 3\sqrt[3]{abc} = 3\sqrt[3]{4Rrs}. \] By manipulation and the fact that \(R \geq 2r\), we have \( 8s^3 \geq 27(4Rrs) \geq 27(8r^2s)\), giving us \(s \geq 3\sqrt{3}r\).
   Since the incircle of \(ABC\) is the circumcircle of \(DEF\), we can apply Leibniz's inequality to \(DEF\) and obtain \[ {EF}^2 + {FD}^2 + {DE}^2 \leq 9r^2, \] and combining with the previous inequality gives us the desired solution.
9. On the blackboard some student has written 17 natural numbers, and their units digits are inside the set \(\{0, 1, 2, 3, 4\}\). Prove that one can always select out 5 numbers from them such that their sum is divisible by 5. (China Mathematical Competitions for Secondary Schools, 2005)
   (solved by Ferdinand John S. Briones [MSHS])
   
   
   SOLUTION: 
   Group the 17 numbers into 5 sets according to their units digit. If each set contains at least one number, then taking a number from each set yields a sum whose units digit ends in 0, hence divisible by 5. If a particular set is empty, that means each set contains at least 4 numbers each with one set having 5 numbers, and these 5 numbers will yield our desired result. Two or more empty sets will yield the same result.
10. Let \(a, b, c\) be positive real numbers with \(abc = 8\). Prove that \[\frac{a-2}{a+1} + \frac{b-2}{b+1} + \frac{c-2}{c+1} \leq 0.\](Romania, 2008)
    (solved by Ferdinand John S. Briones [MSHS])
    
    
    SOLUTION: 
    We wish to show that \[ \begin{align*}
    \frac{a-2}{a+1} + \frac{b-2}{b+1} + \frac{c-2}{c+1} \leq 0 &\Leftrightarrow 3-3\left(\frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}\right) \leq 0 \\
    &\Leftrightarrow 1 \leq \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}. \end{align*} \] By substituting \(a = \frac{2x}{y}\), \(b = \frac{2y}{z}\), \(c = \frac{2z}{x}\) we have \[ \begin{align*} \frac{1}{a+1} + \frac{1}{b+1}+\frac{1}{c+1} &= \frac{1}{\frac{2x}{y} + 1}+\frac{1}{\frac{2y}{z} + 1}+ \frac{1}{\frac{2z}{x}+1} \\
    &= \frac{y}{2x+y} + \frac{z}{2y+z} + \frac{x}{2z+x} \\
    &= \frac{y^2}{2xy+y^2} + \frac{z^2}{2yz+z^2} + \frac{x^2}{2xz+x^2} \\
    &\geq \frac{(x + y + z)^2}{2xy+y^2 + 2yz+z^2 + 2xz+x^2} = 1, \end{align*} \] by the Cauchy-Schwarz inequality in Engel form.
    As an alternative, we can prove by contradiction. Suppose \[1 > \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1}.\] Simplifying, we have \[ \begin{align*} 1 &> \frac{1}{a+1} + \frac{1}{b+1} + \frac{1}{c+1} \\ &= \frac{(b+1)(c+1) + (a+1)(c+1) + (a+1)(b+1)}{(a+1)(b+1)(c+1)} \\ (a+1)(b+1)(c+1) &> (b+1)(c+1) + (a+1)(c+1) + (a+1)(b+1) \end{align*} \] which, after simplifying and using the fact that \(abc = 8\), yields \[ \frac{a+b+c}{3} < 2 = \sqrt[3]{abc}, \] which is false by the AM-GM inequality, hence the contradiction.
11. Let \(\{x\} = x - \left\lfloor x \right\rfloor\) denote the fractional part of \(x\). Prove that for every natural number \(n\), \[ \sum_{j=1}^{n^2} \left\{ \sqrt{j} \right\} \leq \frac{n^2 - 1}{2}.\](Russia, 1999)
    (solved by Ferdinand John S. Briones [MSHS])
    
    
    SOLUTION: 
    We prove via induction on \(n\). When \(n = 1\), the inequality holds. Assuming it is true for \(n\), we prove it is true for \(n+1\). Note that \(n < \sqrt{n^2 + i} < n+1\) for \(i = 1, 2, \ldots , 2n\), giving us  \[ \left\{ \sqrt{n^2 + i} \right\} = \sqrt{n^2+1} - n < \sqrt{n^2 + i + \left( \frac{i}{2n} \right)^2} - n = \frac{i}{2n}. \] Thus \[ \begin{align*}
    \sum_{j=1}^{(n+1)^2}\left\{\sqrt{j}\right\} &= \sum_{j=1}^{n^2}\left\{\sqrt{j}\right\}   + \sum_{j = n^2 +1}^{(n+1)^2} \left\{ \sqrt{j} \right\} \leq \frac{n^2 - 1}{2} + \frac{1}{2n} \sum_{i=1}^{2n}{i} \\
    &= \frac{(n+1)^2 -1}{2}.  \end{align*} \]
12. Show that there are infinitely many ordered integral pairs \((a,b)\) such that \(\frac{a^3+b^3}{a-b}\) is a perfect square. (Taken from A Primer for Mathematics Competitions by Hitchcock and Zawaira)
    (solved by Ferdinand John S. Briones [MSHS] and Gerald M. Pascua [PSHS - Main])
    
    
    SOLUTION: 
    Setting \(b = 0\), we have \[ \frac{a^3+b^3}{a-b} = \frac{a^3}{a} = a^2,\] which is always a perfect square for any integer \(a\), giving us the integral pair \( (a,0) \).