Parallel Processing Letters Vol. 8 No. 4 (1998)549–560 \begin{matrix}c \\ ◯ \end{matrix} World Scientific Publishing Company

GENETIC PROGRAMMING TO DESIGN COMMUNICATION ALGORITHMS FOR PARALLEL ARCHITECTURES ^{∗}

F. COMELLAS^{†}, and G. GIMENEZ Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya Campus Nord, Edifici C3 08034 Barcelona, Catalonia, Spain

Received January 1997 Revised February 1998 Communicated by A. M. Farley

ABSTRACT

Broadcasting is an information dissemination problem in which a message originating at one node of a communication network (modeled as a graph) is to be sent to all other nodes as quickly as possible. This paper describes a new way of producing broadcasting schemes using genetic programming. This technique has proven successful by easily finding optimal algorithms for several well-known families of networks (grids, hypercubes and cycle connected cubes) and has indeed generated a new scheme for butterflies that improves the known upper bound for the broadcasting time of these networks.

Keywords: Broadcasting, genetic programming, butterfly graph

1 Introduction

There is considerable interest in the study of the propagation of information in interconnection networks. This research area is important because the ability of a network to effectively disseminate information is a good measure of the suitability of the network for parallel computing. Broadcasting is one of the most studied problems in communication networks and refers to the sending of a message from one node of the network to all the other nodes as quickly as possible, subject to the constraints that each call involves only two nodes, a node which already knows the message can only inform one of the nodes to which it is connected and each call requires one unit of time. Optimal broadcasting schemes are known for some simple topologies such as grids, hypercubes and cube connected cycles. For other networks that are considered good candidates to implement parallelism (butterflies, de Bruijn, Kautz, star graphs, etc.), there is still work in progress and no general technique is known to help in the design of communication algorithms that, very often, are found by inspection.

∗Part of this research was done while F.C. was visiting the School of Computing Science, Simon Fraser University, Burnaby, Canada. This work was supported with a grant from the Dirección General de Investigación Científica y Técnica, Ministerio de Educación y Ciencia, Spain (ref. PR95-179) and by the CICYT, Spain, under Project TIC94-0592 and the EU-HCM program ERBCHRX-CT920049.

†e-mail: comellas@mat.upc.es

On the other hand, in recent years we have seen the introduction of methods that may deal with difficult combinatorial problems and produce good solutions in a reasonable computational time. These methods include simulated annealing, neural networks, genetic algorithms, and more recently genetic programming. In this paper we show the ability of genetic programming to generate easily good communication schemes. The main aim of this paper is to provide a new computational tool for researchers looking for such schemes. The technique described here may be used to generate them automatically when, until now, they were produced by inspection. Therefore we do not focus on the analysis of the schemes produced, that in some cases may be extremely difficult, see [4].

The paper is organized as follows. The next section will introduce the notation and give some general definitions. Section 3 presents the genetic programming technique, based on genetic algorithms and in Section 4 we describe some details of the implementation considered. Finally, in Section 5, we present the results obtained and in Section 6 we suggest new possible applications.

2 Notation and Known Results

In this paper we will model a network using graphs. A graph, G = (V, A), consists of a non empty finite set V of elements called vertices and a set A of pairs of elements of V called edges. The number of vertices N = |G| = |V | is the order of the graph. If (x, y) is an edge of A, we say that x and y (or y and x) are adjacent. The degree of a vertex δ(x) is the number of vertices adjacent to x. The degree of G is Δ = max_{x∈V} δ(x). A graph is regular of degree Δ or Δ-regular if the degree of all vertices is Δ. The distance between two vertices x and y, d(x, y), is the number of edges of a shortest path between x and y, and its maximum value over all pairs of vertices, D = max_{x,y∈V} d(x, y), is the diameter of the graph.

A graph is vertex symmetric if its automorphism group acts transitively on its set of vertices. Loosely speaking we say that the graph looks the same from any vertex. The interest in vertex symmetric graphs comes from the fact that in the associated network each node is able to execute the same communication software without modifications and in this way these graphs may be considered for easy implementation of parallelism. We refer to [1] for other basic concepts in graph theory not defined here.

The topologies considered in this work are:

The directed 2-grid M_{m×n} = P_{m}□P_{n}: Let P_{m} and P_{n} be directed paths on m and n vertices. The 2-grid digraph, or mesh, is the cartesian product of those paths. It has m · n vertices, maximum degree 4 and minimum degree 2. Its diameter is D = m + n − 2. This is the only directed graph considered (in which the edges have a given direction) and also the only non vertex symmetric graph.

The 2-torus graph T_{m×n} = C_{m}□C_{n}: It is a 4-regular graph on m · n vertices arising from the cartesian product of the cycles C_{m} and C_{n}. Its diameter is D = ⌊\frac{m}{2}⌋ + ⌊\frac{n}{2}⌋.

The hypercube graph H_{k}: A hypercube H_{k} is a graph on N = 2^{k} vertices, each denoted by a k-bit binary number. Edges join vertices whose labels differ in precisely one bit. H_{k} is k-regular and has diameter D = k = log_{2} N.

The cube connected cycles graph CCC_{k}: This graph is a modification of the hypercube H_{k}, obtained by replacing each vertex by a cycle of k vertices. The order of the CCC_{k} is k2^{k}. The degree is three.

The butterfly graph BF_{k}: The butterfly graph has k2^{k} vertices labeled with a pair of numbers (l, x). l is called the level (0 ≤ l ≤ k − 1) and x = x_{0}x_{1} ⋯ x_{k−1} is a k-bit string. Each vertex (l, x) is connected by a straight edge to (l+1 (mod k), x) and by a cross edge to (l + 1 (mod k), x_{0} ⋯ x_{l−1}x̄_{l}x_{l+1} ⋯ x_{k−1}). BF_{k} has degree four and diameter ⌊\frac{3k}{2} ⌋.

Broadcasting in a graph is the process of spreading a message known initially by one vertex, subject to the following rules: The transfer of the message from one vertex to another (termed a call) takes one unit of time. A vertex can only call an adjacent vertex. A vertex can participate in at most one call per unit of time. A broadcast scheme is a formal description of that process.

Given a connected graph G and a vertex u, the broadcast time of u, denoted b(u), is the minimum number of time units required to broadcast a message originating at u. The broadcast time of the graph G is defined b(G) = max{b(u)|u ∈ G}. For any vertex u in a connected graph with |V | vertices, b(u) ≥ ⌈log_{2} |V |⌉, since during each time unit the number of vertices informed can at most double. For a vertex symmetric graph, the broadcast time is equal to the broadcast time of any of its vertices.

Optimal broadcasting algorithms are known, for example, for 2-grids (b(M_{m×n}) = m+n−2 = D), 2-torus (b(T_{m×n}) = D, if m and n are even and b(T_{m×n}) = D+1 otherwise), hypercubes (b(H_{k}) = D = log_{2} N) and cube connected cycles (b(CCC_{k}) = ⌈\frac{5k}{2} − 1⌉), see [4]. For some other networks the known broadcasting algorithms give only upper bounds on the broadcasting time. In [7], for example, the authors present a broadcasting algorithm for the butterfly network of dimension k that leads to an upper bound of 2k − 1 on the broadcasting time.

3 Genetic Algorithms and Genetic Programming

A general overview of genetic algorithms (GA) may be found in the article of Holland in Scientific American [6]. For a detailed introduction, with discussion of implementation issues, see Goldberg’s book [5].

In a classical genetic algorithm the starting point is a collection of solutions generated at random, known as a population. A suitable encoding of each solution in the population is used to compute its fitness through a cost function.

At each iteration a new population, or generation, is obtained by mating the best of the old solutions with one another. To create the next generation, new solutions are formed through reproduction, crossover and mutation. The solutions that will be considered for crossover are probabilistically selected according to the fitness values from the set that constitutes the current generation. This new population becomes the parent pool. In Goldberg’s approach a constant number of solutions are selected so that a fixed size population is maintained. Crossover creates two new child solutions from two solutions sampled from the parent pool. In this way, fitter parents have a better chance of producing children. This is done for the whole population. Children solutions are obtained by interchanging random parts of their parents. Some randomness is also introduced through the mechanism called mutation to ensure that the algorithms avoid getting stuck at local minima. Mutation changes selected parts of a solution. The crossover and mutation operations are done with fixed probabilities, thus ensuring that some solutions from the current generation will be kept in the new generation.

Once a new generation is created, the fitness of all solutions is evaluated and the best solution is recorded. The process is repeated until either the results stabilize or the optimal solution, when it can be identified, is reached.

The main aspects to decide are the representation of the solutions, the cost function and the crossover and mutation operators. Important parameters are the population size and the probabilities of crossover and mutation.

Numerous modifications have been made to the classical genetic algorithm, and certain variations appear to be more or less useful depending on the problem being optimized. One common version of the GA which has several advantages over the classical model is the steady-state GA . In this paradigm, a single population of individuals is maintained at any given time, and the reproduction operator is replaced by a selection operator that chooses which individuals to crossover. The newly created solutions are then returned to the single population by means of the replacement operator, which selects the individuals to be removed. The steadystate GA provides greater control over which individuals are removed from the population, and also requires substantially less computer memory to operate.

Genetic algorithms have been used successfully to solve combinatorial optimization problems related to network design such as the assignment problem for radio networks [2] and to solve planarization problems related to VLSI [3].

GA may evolve a large variety of structures, although the most frequently used are strings or lists. In particular, they have been used to evolve trees, representing programs or algorithms. John Koza, in 1987, considered a GA to evolve Lisp expressions and started using the term genetic programming to describe this method, see [8]. Lisp expressions, or S-expressions as are also known, have become the usual representation of solutions for GP. An S-expression consists of a function followed, or not, by arguments. Each argument is also an S-expression. A function in an expression is called a node. Functions with no arguments are called terminals. A special function, PROGn, is used to join together n other functions into a procedural program.

In our broadcasting schemes, for example, it is possible to represent “If the information has reached the node from an upper vertex, move it next using a cross link” as the following S-expression (IfProc Up MoveCross), where IfProc Up is a conditional function and MoveCross a terminal.

An important property of S-expressions is closure. It is possible to use an Sexpression as an argument of another and still have a valid S-expression. This fact facilitates the implementation of the crossover and mutation operators.

4 Implementation Details

To perform the experiments we adapted the GP software written by Andy Singleton and described in the February 1994 issue of BYTE [9]. The package is known as GPQUICK and version 2.1 was used. It consists of several modules written in C++ and it is publicly available for non commercial purposes from the author. A modified version, with an explanation of the changes made, is accessible on the WWW^{a}.

GPQUICK uses a steady state GA, tournament selection, three types of mutation, and subtree crossover. It uses tournament selection with a tournament size of six, and a kill tournament size of 2. It uses node mutation (switching a node for another node of the same arity), constant mutation (small adjustments to constant values) and shrink mutation (promote a sub-subtree to replace a subtree) 10% of the time each, a copy with reevaluation on new cases 10% of the time, and subtree crossover 70% of the time.

The package was adapted by modifying the file chrome.cpp and its header file and creating a new file specific for each graph (or family of graphs) considered. None of the original GA parameters of the package were changed (rates of mutation, crossing, etc.). In some runs params[pMaxExpr] and params[pInitExpr], that fix the maximum expression size in nodes and the maximum initial expression depth, were changed to bigger values to deal more easily with possible large expressions.

Functions and terminals: The graphical representation of a network very often suggested the choice of the function set and terminal set.

After preliminary experiments using conditional functions with parameters, and to speed the testing process, we decided to expand the number of conditional functions. For example, instead of using (IfProc param) with param one of { up, down, left, right} we use four different conditional functions: IfProc Up,

IfProc Down, IfProc Left and IfProc Right.

Fitness: To evaluate the fitness of a possible solution, it is executed on the graph. A broadcasting scheme is an inherently parallel process, but the program that tests it is sequential, so we may reach a situation in which two (or more) nodes could inform the same node at a given broadcasting step. We choose the option that the actual node that will transmit the message will be the node that received it first. On the other hand, the scheme is executed in the order that is written. Therefore it is possible to generate schemes containing conditional functions that will never be used. Fitness is calculated by counting the number of vertices reached by the algorithm penalized by its length (number of nodes of the corresponding S-expression). Each new vertex reached increases the fitness by T (an adjustable parameter). Each conditional function and the null action decreases the fitness by two. Other actions decrement it by four. Finally, connective functions do not affect the fitness value.

ahttp://www-mat.upc.es/~comellas/genprog/genprog.html

Some preliminary tests were compiled on a PC 486 under MS Windows 3.1 using Borland C++, but most of the results were obtained on Sun Sparc2 and HP Apollo 715 workstations with their standard ANSI C++ compilers. The CPU time to find an acceptable solution ranged from a few seconds -to find the optimal algorithm for a simple instance of the directed 2-grid- to around 10 hours –to obtain a new broadcasting scheme for butterflies (k = 7). The most time consuming task is the evaluation of the fitness of a given S-expression. A typical run found a solution after less than 60000 such evaluations were performed and typically between 10000 and 20000.

5 Results

5.1 Directed 2-grid

The first graph studied was the directed 2-grid. It was chosen for the simplicity of its known optimal broadcasting algorithm:

“The originating vertex (upper left of the grid) informs its horizontal neighbour at the first step and its vertical neighbour at the second.

Each node that is informed by a horizontal neighbour first informs its other horizontal neighbour and then its vertical neighbour.

If a node is informed by a vertical neighbour it informs its other vertical neighbour.” To find a broadcasting scheme for this directed graph, the function and

[figure]

Fig. 1: Directed 2-grid M(5, 5)

terminal sets were considered as follows:

Function set: {IfOri, IfProc Ver, IfProc Hor, If turn 0, If turn 1, Prog4,
     Prog3, Prog2, Prog1}
Terminal set: {MoveHor, MoveVer, Null}

With the M_{5×5} 2-grid, and running the system with a population of 500 individuals, a value of T=280 and after 12340 iterations (40” CPU time on an SPARCstation SLC) the following S-expression, with a fitness value of 6678, is found:

(Prog3 (IfOri      (Prog2  (If_turn_0 MoveHor)
                           (If_turn_1 MoveVer)))
       (IfProc_Hor (Prog3  (If_turn_0 MoveHor)
                           (If_turn_0 MoveVer)
                           (If_turn_1 MoveVer)))
       (IfProc_Ver (If_turn_0 MoveVer)))

This expression corresponds exactly to the known optimal broadcasting algorithm. Note that the function (If turn 0 MoveVert) is redundant and will never be used. More iterations should eliminate it.

The program also generates a visualization of the propagation of the information (for the solution), as shown in Figure 2.

step 0  step 1  step 2  step 3  step 4  step 5  step 6  step 7  step 8
0oooo   *1ooo   **2oo   ***3o   ****4   *****   *****   *****   *****
ooooo   ooooo   2oooo   *3ooo   **4oo   ***55   *****   *****   *****
ooooo   ooooo   ooooo   3oooo   *4ooo   **5oo   ***66   *****   *****
ooooo   ooooo   ooooo   ooooo   4oooo   *5ooo   **6oo   ***77   *****
ooooo   ooooo   ooooo   ooooo   ooooo   5oooo   *6ooo   **7oo   ***88

Fig. 2: Broadcasting in the directed 2-grid M_{5×5}

5.2 Toroidal grid

This graph is vertex symmetric, and the originating vertex may be chosen arbitrarily. We decided to put it at the upper left of the graphical representation.

The degree of the graph is four for any member of the family of graphs and therefore this is the number of possible movements for the information. Therefore we decided to use the following functions and terminals:

Function set: {IfOri, IfProc Up, IfProc Down, IfProc Right, IfProc Left,
    If turn 0, If turn 1, If turn 2, If turn 3, Prog6, Prog5, Prog4, Prog3,
    Prog2, Prog1}
Terminal set: {MoveUp, MoveDown, MoveRight, MoveLeft, Null}

Considering the graph T_{8×5} with a population of 800, T = 280, and after 23420 iterations we found this solution:

(Prog3 (Prog2 (IfProc_Down (Prog3 (If_turn_0 MoveUp)
                                 (If_turn_0 MoveLeft)
                                 (Prog3  (If_turn_0 MoveRight)
                                         (If_turn_1 MoveLeft)
                                         (If_turn_2 MoveRight))))
             (Prog3 (IfProc_Up (Prog3 (If_turn_0 MoveDown)
                                      (If_turn_0 MoveRight)
                                      (Prog3 (If_turn_0 MoveLeft)
                                             (If_turn_1 MoveLeft)
                                             (If_turn_2 MoveRight))))
                    (IfProc_Right (Prog3 (If_turn_0 MoveLeft)
                                         (If_turn_0 MoveDown)
                                         (Prog3 (If_turn_1 MoveDown)
                                                (If_turn_1 MoveUp)
                                                (If_turn_2 MoveUp))))
                    (IfOri        (Prog4 (If_turn_0 MoveRight)
                                       (If_turn_1 MoveLeft)
                                       (If_turn_2 MoveUp)
                                       (If_turn_3 MoveDown)))))
      (IfProc_Left (Prog3 (If_turn_0 MoveRight)
                          (If_turn_1 MoveUp)
                          (If_turn_2MoveDown)))
      (Prog2 (If_turn_0 MoveUp)
             (If_turn_1 MoveDown)))

We observe several redundancies that do not affect the performance of the algorithm. Again, the scheme corresponds to the known optimal algorithm for this family of graphs, that is: “If a vertex is informed by one of its vertical neighbours, it sends the message to its other vertical neighbour. Otherwise, it first sends the message to its other horizontal neighbour, then to its upper vertical neighbour, and finally to its lower vertical neighbour”.

  step 0         step 1         step 2         step 3         step 4
  0oooooooooo    *1ooooooooo    **2ooooooo2    ***3ooooo3*    ****4ooo4**
  ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo    44oooooooo4
  ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo
  ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo
  ooooooooooo    ooooooooooo    ooooooooooo    ooooooooooo    44ooooooooo
  ooooooooooo    ooooooooooo    ooooooooooo    33ooooooooo    **4oooooooo
  step 5         step 6         step 7         step8          step 9
  *****5o5***    ******6****    ***********    ***********    ***********
  **5oooooo5*    ***6oooo6**    ****7777***    ***********    ***********
  55oooooooo5    **6oooooo6*    ***7oooo7**    ****8888***    ***********
  55ooooooooo    **6ooooooo6    ***7ooooo7*    ****88oo8**    ******99***
  **5oooooooo    ***6oooooo6    ****77ooo7*    ******oo8**    ******99***
  ***5oooooo5    ****66ooo6*    ******oo7**    ******88***    ***********

Fig. 3: Broadcasting process in the graph T_{11×6}

5.3 Hypercube

Let 0 be the originator. For this family, the function set differ depending on the dimension of the graph (the degree increases with the dimension). On the other hand, due to the standard labeling of its vertices we decided to use functions and terminals based on the equivalent numerical value of each label.

As an example, for the hypercube of dimension k = 6 we consider:

Function set: {IfOri, IfProc Big, IfProc Small, If turn 0, If turn 1, If turn 2,
     If turn 3, If turn 4, If turn 5, Prog6, Prog5, Prog4, Prog3, Prog2, Prog1}
Terminal set: { MoveBig, MoveSmall, Null}

The scheme found is:

 (Prog2 (IfProc_Ori (Prog5 (If_turn_0 MoveBig)
                           (If_turn_1 MoveBig)
                           (If_turn_2 MoveBig)
                           (If_turn_3 MoveBig)
                           (Prog2 (If_turn_4 MoveBig)
                                  (If_turn_5 MoveBig))))
        (IfProc_Menor (Prog4 (If_turn_0 MoveBig)
                             (If_turn_1 MoveBig)
                             (If_turn_2 MoveBig)
                             (If_turn_3 MoveBig)
                             (If_turn_4 MoveBig))))

This solution is equivalent to the optimal broadcasting algorithm for the hypercube: “At step i, each informed vertex sends the message in dimension i, 1 ≤ i ≤ k.”

5.4 Cube-Connected-Cycles

For this graph we use the graphical representation of figure 4 in which each column of vertices corresponds to one of the cycles. This representation suggests the following set of functions and terminals:

[figure: 0; 1; 2; 000; 100; 010; 110; 001; 101; 011; 111]

Fig. 4: The cube connected cycles CCC_{3}

Function set: {IfOri, IfProc Up, IfProc Down, IfProc Trans, If turn 0, If turn 1,
     If turn 2, Prog5, Prog4, Prog3, Prog2, Prog1}
Terminal set: {MoveUp, MoveDown, MoveTrans, Null}

The solution found was (population=800, T=350, iterations=23420):

 (Prog3 (Prog2 (IfProc_Trans (Prog3 (If_turn_0 MoveTrans)
                                    (If_turn_0 MoveDown)
                                    (If_turn_1 MoveUp)))
               (IfProc_Down  (Prog4 (If_turn_0 MoveTrans)
                                    (If_turn_0 MoveUp)
                                    (If_turn_1 MoveUp)
                                    (If_turn_2 MoveDown))))
        (IfProc_Up   (Prog3 (If_turn_0 MoveTrans)
                            (If_turn_0 MoveDown)
                            (If_turn_1 MoveDown)))
        (IfOri       (Prog3 (If_turn_0 MoveTrans)
                            (If_turn_1 MoveDown)
                            (If_turn_2 MoveUp))))

If we remove the redundant functions, we obtain the optimal algorithm: “first relay the message to the hypercube neighbour (MoveTrans function), then to the right neighbour of the ring(MoveDown function), then to the left neighbour (MoveUp function)”.

5.5 Butterfly graph

For these graphs no optimal broadcasting algorithm is known. The best previously known upper bound was given by Klasing, Monien, Peine and Stöhr [7]: BF_{k} ≤ 2k −1. Here we improve the upper bound to BF_{k} ≤ 2k −2 for, at least, 7 ≤ k < 16.

[figure: 0; 1; 2; 0; 000; 100; 010; 110; 001; 101; 011; 111]

Fig. 5: Butterfly graph BF_{3}

The graphical representation of butterflies suggests the following choice:

Function set: {IfOri, IfProc VertSup, IfProc VertInf, IfProc DiagSup,
     IfProc DiagInf, If turn 0, If turn 1, If turn 2, If turn 3,
     Prog6, Prog5, Prog4, Prog3, Prog2, Prog1}
Terminal set: {MoveVertSup, MoveVertInf, MoveDiagSup, MoveDiagInf, Null}

For k = 7 and with a population of 800 individuals, T=350 and 32424 iterations we found the following solution that improved the best known broadcasting time for this graph by one:

 (Prog5 (IfProc_VInf (Prog3 (If_turn_0 MoveDiagSup)
                            (If_turn_0 MoveVertSup)
                            (If_turn_1 MoveVertSup)))
        (IfProc_DiagInf (Prog3 (If_turn_0 MoveDiagSup)
                               (If_turn_0 MoveVertInf)
                               (Prog3 (If_turn_0 MoveVertSup)
                                      (If_turn_1 MoveVertSup)
                                      (If_turn_2 MoveVertInf))))
        (IfProc_DiagSup (Prog5 (If_turn_0 MoveDiagInf)
                               (If_turn_0 MoveVertSup)
                               (If_turn_0 MoveVertInf)
                               (If_turn_1 MoveVertInf)
                               (If_turn_2 MoveVertSup)))
        (IfOri (Prog4 (If_turn_0 MoveDiagInf)
                      (If_turn_1 MoveDiagSup)
                      (If_turn_2 MoveVertSup)
                      (If_turn_3 MoveVertInf)))
        (IfProc_VSup (Prog3 (If_turn_0 MoveDiagInf)
                            (If_turn_0 MoveVertInf)
                            (If_turn_1 MoveVertInf))))

We tested this scheme for other graphs of the same family with 7 ≤ k < 16 and for all these graphs the broadcasting time was one unit less than the time obtained by the algorithm of Klasing et al., see Table 1. For butterflies with k < 7 our algorithm gives the known times. Figure 6 shows its execution on BF_{5}.

k lower bound upper bound  order
2  3  3  8
3  5  5  24
4  7  7  64
5  8  9  160
6  10  11  384
7  11  12 *  896
8  13  14 *  2048
9  15  16 *  4608
10  16  18 *  10240
11  18  20 *  22528
12  19  22 *  49152
13  21  24 *  106496
14  23  26 *  229376
15  24  28 *  491520

using GP.

Table 1: New upper bounds for the broadcasting time of BF_{k}. Values with an asterisk were found

step 0                                  step 1
0ooooooooooooooooooooooooooooooo        *ooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooo        o1oooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooo        oooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooo        oooooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooo        oooooooooooooooooooooooooooooooo
step 2                                  step 3
*ooooooooooooooooooooooooooooooo        *ooooooooooooooooooooooooooooooo
o*oooooooooooooooooooooooooooooo        o*oooooooooooooooooooooooooooooo
ooo2oooooooooooooooooooooooooooo        o3o*oooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooooo        ooooooo3oooooooooooooooo3ooooooo
oooooooooooooooo2ooooooooooooooo        3ooooooooooooooo*ooooooooooooooo
step 4                                  step 5
*4oooooooooooooooooooooooooooooo        **oooooooooooooo5oooooooooooooo5
4*oooooooooooooooooooooooooooooo        **o5oooooooooooooooooooooooooo5o
o*o*oooooooooooooooooooooooo4ooo        o*5*oooooooo5ooooooo5ooo5ooo*ooo
ooo4o4o*4ooooooo4ooooooo*ooooooo        55o*o*o**ooooooo*ooooooo*ooooooo
*oooooooooooooo4*ooooooooooooooo        *oooooo5ooo5o5o**5oooooooooooooo
step 6                                  step 7
**6oooooooooooo6*oooooo6ooo6o6o*        ***7ooo77oo7o7o**oo7o7o*o7o*7*7*
**o*oooooooooo6oo6oooo6ooo6o6o*o        **o*o77ooo7o7o*77*7o7o*o7o*o*o*7
6***6oo66ooo*ooo6ooo*ooo*ooo*o6o        *****7o**ooo*o7o*oo7*o7o*o7o*7*o
**o*o*6**ooooooo*ooooooo*6oooooo        **7*7****7ooooo7*7ooooo7**7o7ooo
*6o6o6o*o6o*o*o***oooooo6oooooo6        **o*o*o*7*o*o*7***7oooo7*oo7o7o*
step 8                                  step 9
****88o**8o*8*8**88*8*8*8*8*****        ******9***9*********************
**8*8**888*8*8*****8*o*8*o*8*8**        *********************9***9******
******8**o88*8*8*88**8*8*8*o***8        *********9*****************9****
**********88888***88888****8*888        ********************************
**8*o*8***8*8******888o**88*8*8*        ****9*****************9*********

Fig. 6: Broadcasting process for the BF_{5} on 160 vertices.

6 Conclusions

Genetic programming has proved successful by easily finding optimal broadcasting algorithms for several well known networks. An example of its potential is that we were able to find in a straightforward way a new upper bound for the broadcasting time of butterfly graphs. GP uses a genetic algorithm that it is a robust technique that works for a wide range of parameters. Therefore, it is possible to look for new communication schemes without expending time tuning these parameters. On the other hand, the choice of the function and terminal sets is also non-critical (considering extra functions, for example, affects the running time to find an acceptable solution, but not its quality).

We expect that simple variations of the algorithm presented here should be useful to find new upper bounds for the broadcasting time of networks such as the de Bruijn, Kautz or star graphs, where improvement is possible. It should also be possible to adapt GP to deal with other models of broadcasting such as the linear time model, or for use in other communication problems like gossiping.

References

1. G. Chartrand and L. Lesniak. Graphs & Digraphs. 2nd edition, Wadworth and Brooks Cole Advanced Books and Software, Monterey, California, USA, 1986. ISBN 0-534-06324-1.

2. F. Comellas and J. Ozón,. Graph coloring algorithms for assignment problems in radio networks. Applications of Neural Networks to Telecommunications 2. J. Alspector, R. Goodman and T.X. Brown (Eds.), Lawrence Erlbaum Ass., Inc., Publis., Hillsdale, NJ (1995), pp. 49–56; ISBN 0-8058-2084-1.

3. F. Comellas. Using genetic algorithms for planarization problems. Computational and Applied Mathematics, I. Algorithms and Theory., C. Brezinski and U. Kulish (Eds.), Elsevier Science Publishers B.V. (1992), pp. 93–100; ISBN 0-444-89701-1.

4. P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks. Discrete Appl. Math. C-53, pp. 79–133, 1994.

5. D. E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, 1989, ISBN 0-201-15767-5.

6. J.H. Holland. Genetic algorithms, Scientific American, 267, 44-50, 1992.

7. R. Klasing, B. Monien, R. Peine and E. A. Stöhr, Broadcasting in butterfly and de Bruijn networks. Discrete Applied Math., 53, pp. 183-197, 1994.

8. J. Koza, Genetic Programming, MIT Press, 1992. ISBN 0-262-11170-5

9. A. Singleton, Genetic Programming with C++. BYTE, February 1994, pp. 171-176.