SA-E4-5

SCIS & ISIS 2008

Heterogeneous Multi Agents Learning using Improved
Genetic Network Programming
Hirotaka Itoh
Nagoya Institute of Technology
Gokiso-cho, Showa-ku,
Nagoya, Japane-mail: ht-itoh@nitech.ac.jp

Naoki Ikeda
Nagoya University
Furo-cho, Tikusa-ku,
Nagoya , Japane-mail: icenine84@hotmail.com

Abstract— The heterogeneous multi agent system is a systemthat cooperates intensively in one place by two or more agents andachieves the task. There is Genetic Network Programming as an
automatic generation technique of the heterogeneous multi agent
system. In this paper, the authors proposes IGNP and GNPIAM as
automatic generation technique of the heterogeneous multi agent
system. And the authors propose both co-evolution method andnon-co-evolution method as agent's evolution method and compare
the performance of two methods.
I. INTRODUCTION
Recently, the multi agent system is widely researched. The
multi agent system is a system that solves the problem by using
two or more agents. An individual agent perceives theenvironment and behaves to archive the task. The environmentchanges from a certain agent's behavior. The change of theenvironment decides another agent's behavior. In the multi agent
system, the entire system is not collectively managed. The
individual agent cooperates with other agents. There is anadvantage that the cost of the entire system is lower by such
distributed management. The individual agent has two abilities ofperception and operation. The perception ability is an ability torecognize the environment, and the operation ability is an ability
to influence the environment. The action when the task is given
to the agent is decided by the procedure of perception andoperation. The action of the agent who achieves a simple task can
be designed by the hand work. On the other hand, it costs a lot oftime and the cost for the complex task. In addition, the design ofthe behavior of two or more agents becomes a more complex
problem, and it is difficult in the hand work.
The Genetic Network Programming (GNP)[1],[2] exists as atechnique for generating the agent's behavior automatically. GNP
is an improvement technique of Genetic Programming (GP)[1].
GNP has a network structure and can make the agent who cancorrespond to a dynamic environment that changes by the agent's
behavior. The evolution algorithm of GNP is the same as the oneof Genetic Algorithm (GA). The initial convergence and poor
local search capability are pointed out as the defect of GA.
Evolutionary adaptation algorithms focusing on the workings ofKenji Funahashi
Nagoaya Institute of Technology
Gokiso-cho, Showa-ku,
Nagoya, Japane-mail: kenji@nitech.ac.jp

the immune system have been devised to improve the defect of
GA. These are Immune Algorithm (IA)[3]and Genetic Algorithmwith Immune Adjustment Mechanism (GAIAM)[4]. Then, theauthor proposed Immune evolved Genetic Network
Programming (IGNP)[5] that had used IA as an evolution
algorithm of GNP in the past. In this paper, authors propose
Genetic Network Programming with Immune Adjustment
Mechanism (GNPIAM) that uses GAIAM.
In the research of the past on the multi agent system that used
GNP[6],[7], the one to raise efficiency by using two or moreagents for the task that was able to be achieved by a single agent
was the main. However, the system that assumes the purpose ofthis research is not the one that raises efficiency as two or moreagents and is the one that achieves the task as two or more agentscooperate and archive the task. The targeting task can’t beachieved by single agent and can be archived by multi agents.
The heterogeneous multi agents system is the system by which
an individual agent individually has the operation program.
Authors propose both co-evolution technique andnon-co-evolution technique as agent's evolution technique.
Co-evolution technique is the method to which the evaluation
value corresponding to the task contribution level is given to eachagent, and each agent evolves individually. On the other hand,
non-co-evolution technique is the method to which the wholeevolves according to the evaluation value to which is given to theentire system.
In this paper, authors compare both co-evolution method andnon-co-evolution method using GNP, IGNP and GNPIAM.
Authors describe GNP, IGNP and GNPIAM in chapter II, III andIV, respectively. And propose co-evolution technique andnon-co-evololution technique as agent's evolution technique inchapter V. The proposed technique are experimented in chapter
VI. In chapter VII, the conclusion is described.

1625

II. GNP: GENETIC NETWORK PROGRAMMING
A. The Structure of GNP
GNP[1],[2] is one of the automatic programming techniquesID1 : Processing function 1
ID2 : Processing function 2: start node
: processing nodeIDx : Processing function x
IDx+1 : Judgment function x+1: judgment node

IDy

: Judgment function y

Fig.1 The structure of the GNP
Fig. 3 The node library
based on GP[2]. GP has the tree structure, it returns to the root in
GP after it changes from the root to the terminal. Therefore, GP is
suitable for study to a static environment. On the other hand,
GNP uses the network structure. Because the state transition isdone in the sub network, GNP is suitable for the study of a
dynamic environment. Fig.1 shows the structure of GNP. GNP
has start node, judgment node and processing node. The startnode is displayed by a square in Fig.1 is a point where processing
begins. The processing node is displayed by an open circle inFig.1 is agent's operation part. The judgment node is displayed bya diamond in Fig.1 is agent's sensor.
The network as the individual is composed of many nodes.
Fig.2 shows the representation of the node. Each node consists
node gene and connection gene.
In the node gene, NTi is the type of the node, IDi is the function
number of the node and di is the delay time takes to process thefunction of node i. If NTi =0, the node type is the processing node.
If NTi =1, it is the judgment node. The network has the node
library. The node library is shown in Fig.3. If the number ofprocessing is x and the number of judgment is y, x processing
functions and y judgment functions are defined in the node
library.
In the connection gene, Cij is the j-th connection from the nodei. Nik shows the number of connections from the node i. When thenode type is the processing node, Nik=1, because the processing
node has only one connection. When the node type is the
judgment node, Nik>=2, because the judgment node has several
connections according to its condition. d ij is the transition delay

connection between nodes is changed.
C. Algorithm of GNP
In this section authors describe the evolutionary algorithm of
GNP.
Step.1 Generation of an initial group of individuals
N individuals are generated for the initial group ofindividuals.
Step 2 Calculation of fitness
Fitness for each individual is calculated. The fitness is theevaluated value for the solution. And an elitist individual with thebest fitness value in the population is found.
Step 3 Selection
Select parents for crossover by the tournament selection from
N individuals.
Step 4 Crossover and mutation
Apply the crossover based on crossover probability Pc to theselected parents in Step 3. Then, these undergo mutation basedon mutation probability Pm.
Step 5 Replacement
Replace the newly generated population with the previous
population. But the elitist individual found in Step 2 or Step 6 ispreserved.
Step 6 Calculation of fitness
Fitness for each individual is calculated and an elitist
individual with the best fitness value in the population is found.
Step 7 Repetition of Steps 3 to 6 for a determined number ofgenerations.

time that passes Cij from node i.
The start node is defined node 0.
B. Genetic operation of GNP
The genetic operation of GNP is crossover and mutation. Fig.4
shows the crossover. As shown in Fig.4, the replacement of thenodes and changes the connections are done by replacing thespecific area. Fig.5 shows the mutation. On the mutation, theIII. IGNP: IMMUNE EVOLVED GENETIC NETWORKPROGRAMMING
A. The outline of IGNPGNP uses GA as the evolutionary algorithm, but GA has thedefects. IGNP[5] uses IA[3] as the evolutionary algorithm. IA isnode genenode i

NTi

IDi

di

connection gene
Ci1

di1

Cij

dij

Fig. 2 The representation of the node

1626

Ci ni

k

di ni

k

1 N
(2)
∑ ay i , j
N j =1
ayi,j is the similarity of antibodies i and j ( i = 1,…,N, j =1,…,N )and is set appropriately depending on the problem used. N /2
antibodies with low expected values are eliminated. However,
the top 10% of antibodies with high affinities for antigens are
excluded from elimination.
Step 5 Antibody production
New antibodies are produced in place of N / 2 antibodies
eliminated in Step 4. New antibodies are produced by randomly
determining their genes.
Step 6 Crossover and mutation
Antibodies are randomly selected, duplication permitted, fromN antibodies and undergo crossover based on crossoverprobability Pc, producing N /2 antibodies. Then, these undergo
mutation based on mutation probability Pm, and affinity for theantigen is calculated.
Step 7 Repetition of Steps 3 to 6 for a determined number ofgenerations.
Because of Step 5, the IA avoided narrowing the search to
local solutions.
Ci =crossoverFig.4 crossover

IV. GNPIAM: GENETIC NETWORK PROGRAMMING
WITH IMMUNE ADJUSTMENT MECHANISM

mutation

Fig.5 mutation

the evolutionary adaptation algorithms focusing on theworkings of the immune system have been devised to improvethe defect of GA.
B. Algorithm of IGNP
Step 1 Generation of an initial group of antibodies
N antibodies are generated for the initial group of antibodies.
The antibodies are the same as individuals for the GA and aresolutions to an optimization problem.
Step 2 Calculation of affinities
Affinity axi (i= 1,…, N) for antigens are calculated. axi is set inaccordance with the problem used. Affinity for the antigen is thesame as fitness for GNP.
Step 3 Differentiation into memory cells
For details, see reference [3].
Step 4 Calculation of expected values
The expected value ei (i= 1,…, N) for antibodies surviving into
the next generation is calculated.
axi
(1)
ei =
Ci

A. The outline of IGNPIAMGNPIAM uses GAIAM[4] as the evolutionary algorithm.
GAIAM is an algorithm to take two features of immune system to
GA.
There are various antibodies present in the body. As antigens
invade the body from the outside, antibodies corresponding tothese antigens proliferate and eliminate the antigens. The
immune system has the following 2 features:[Feature 1] Capacity to adapt to mutations in antigens
Preparing matching antibodies for every antigen beforehand isdifficult. When antibodies matching an antigen do not exist, thegenes of the best matching antibodies respond by mutating.
Antibodies adapted to the antigen are produced by repeatedmutations of these genes.
[Feature2] Mechanism to adjust antibodies via antibodies
Proliferation of antibodies matching a given antigen is notunlimited; rather, antibodies recognize one another based on theirstructure. When a given antibody proliferates, inhibiting
antibodies recognizing that antibody as an antigen also
proliferate and respond. Overall, balance is maintained.
B. Algorithm of GAIAM
Step 1 Generation of an initial group of antibodies
Same as Step 1 in the IGNP
Step 2 Calculation of affinities
Same as Step 2 in the IGNP
Step 3 Calculation of expected values
Same as Step 4 in the IGNP

Ci is the density of antibody i (i= 1,…, N).

1627

Step 4 Antibody production
New antibodies are produced in place of N /2 antibodies
eliminated in (3). N /2 are selected from surviving antibodies inaccordance with expected values. Then, the N/2 antibodies selected
are mutated, after which affinities for antigen are calculated.

Step 5 Crossover and mutation
Same as Step 6 in the IGNP
Step 6 Adjustment of antibodies
With respect to each antibody i of the N /2 antibodies newly
produced in Step 5, antibody j with the greatest affinity for i aresought from among existing N antibodies. Of antibodies i and j,
those with a high affinity for the antigen survives to the next
generation while those with a low affinity are removed.
Step 7 Repetition of Steps 3 to 6 for a determined number ofgenerations.
Step 4 models [Feature 1] of the immune system and Step 6
models [Feature 2] of the immune system. With GNPIAM,
antibodies with a high affinity for the antigen and low density
tend to remain to maintain diversity. Moreover, such antibodies
proliferate with GNPIAM; effective antibodies with a highaffinity for the antigen are produced by mutation. That is, local
search capability is improved. Moreover, narrowing of the searchrange is avoided by Step 6. Thus, narrowing of the search to thevicinity of a single local solution is avoided.
V. LEARNING OF THE HETEROGENEOUS MULTIAGENTS SYSTEM
A. Heterogeneous multi agents system
In the multi agents system, the entire system is composed byusing two or more agents who move individually andautonomous. If the agent can cooperate mutually, the big taskthat won't be done in a single agent can be achieved. The multiagents system is divided into the heterogeneous multi agents[6]and homogeneous multi agents. In the heterogeneous multiagents, an individual agent has an individual operation program.
On the other hand, all agents in the system have the same
operation program in the homogeneous multi agents. The multiagents system that this research targets is the heterogeneous multiagents. In the text, the learning method of the heterogeneous
multi agents is examined by using GNP, IGNP and GAIAM. The
author
proposes
both
co-evolution
techniqueandnon-co-evolution technique as the learning method of theheterogeneous multi agents.

solution 1

1-1

2-1

p-1

solution 2

1-2

2-2

p-2

solution n

1-n

2-n

p-n

group ofagent 1group ofagent 2group ofagent pFig.6. The agent’s groupingco-evolution in the agent group, and a certain agent's evolution
influences another agent's evolution. Each agent learns own
behavior by being influenced by other agents' behavior andco-evolving.
The process of co-evolution is as follows.
Step.1 The initial group is generated.
Step.2 The initial group is divided into groups of the same
number as agents, one individual is selected from each group,and the agent group is made (Fig.6). This agent group is notchanged by the evolution processing.
Step.3 The task is executed in the agent group.
Step.4 The fitness of the individual agent is calculated according
to the contribution level to the task.
Step.5 Each agent group does the evolution processing.
Step.6 Repetition of Steps 3 to 6 until it meets the end
requirement.
C. Non-co-evolution heterogeneous multi agents
In non-co-evolution heterogeneous multi agents, but theindividual agent individually has a directed graph, but the agent
doesn't have the distinction according to the evaluation value. As
shown in Fig.7, one directed graph is divided into two or more
sub directed graphs. The number of sub graphs is the same as thenumber of agents. There is the start node in each sub graph, andthe connection is not between sub graphs, and is sub graphs are
independent. It is possible to think this heterogeneous multi agent
to be one directed graph that includes sub graphs. One directed
graph becomes one of the solution candidates of the entire multi

B. Co-evolution heterogeneous multi agentsIn the heterogeneous multi agents, an individual agent has adirected graph individually. The directed graph here is the agent's
operation program, and it is shown in Fig.1. By giving theevaluation value to an individual agent according to thecontribution level to the task, the agent is individually evolved. It
is thought that the agent with low contribution level can bestudied to contribute to the task by giving the evaluation value tothe individual agent. The co-evolution here is to mean, that is, the1628

Fig.7 agent groupagents system, and the evaluation value is given to the solution.
Therefore, the evolution processing can be done just like usual
GNP.
A : agent

VI. EXPERIMENT OF PROPOSED METHOD
T2 : tile with
two weights

A. Tile World
Authors experimented by using the tile world to evaluate theproposed methods. The tile world is known well as an exampleof simulating a dynamic environment. As shown in Fig.8, the tile
world is two-dimension lattice plane where agent, tile, floor, hole,and obstacle are arranged. An individual division in the lattice iscalled a cell, and the agent can move by one cell at one unit time.
In Fig.8, the agent, the tile, the hole and the obstacle are denotedby “A”, “T2”, an open circle and a full square, respectively. A
blank cell in the tile world is a floor. In this experiment, weights
are set to the tile for the cooperation of the agents. In Fig.8, thenumber after “T” shows the weights, and “T2” is a tile with twoweights. Two agents are necessary to carry the tile with twoweights. In this tile world, the agents who corporate with othersand drop the tile to the hole are made. Two agents gather in thecell of the tile, two agents grip the tile, and these move to the cellof the hole together. The tile falls into the hole in two agents'
releasing the tile.
B. Experiment Environment
The experiment was executed by initial arrangement of Fig.8.
There are one tile with two weights, one hole and two agents.
Two agents' initial positions are the same.
Table.1 shows the nodes used to the experiment. In Table.1,
NT is the node type, d is delay time, and Nn is the number ofnodes. On the judgment nodes, there are condition branching.
Table.2 shows the condition branching of the judgment nodes.
The delay time between nodes is assumed to be 0.
The evaluation value of the agent in the tile world, that is, thefitness is calculated by the following equation.
fitness = 45 × DropTile × TileWeight
InitialDist − LastDist+ 5×× TileWeight
InitialDist+ 10 × GrabTile + 0.01× MoveArea
DropTile is number of tiles that agent dropped. TileWeight is
the weight of the tile. InitialDist is the shortest distance between
the tile and the hole in the initial state. LastDist is the shortest
distance between the tile and the hole after time limits passes.
GrabTile is whether the tile is gripped after the time limit or not?
MoveArea is the number of cells that the agent moved. 45,5,10
and 0.01 are the weight of each paragraph. The agents could drop
the tile to the hole if the fitness exceeds 100. The agents wereable to grip the tile if the fitness exceeds 10. Agents could takethe tile to the hole if the fitness exceeds 20. Table.3 showsparameters of the experiment.

: hole: obstacle

Fig.8 Tile world
Table.1 The nodes used to the experimentnode name
GO_FORWARD
GRAB
RELEASETURN_LEFTTURN_RIGHTNOPHAVE_TILE
FIND_TILE
FIND_HOLEFIND_AGENT
TRANS_FAIL

meaning
Go ahead by one cell.
Grab the tile
Release the title
Turn left
Turn right
Nothing is done
Does the agent has the title?
Where is the tile?
Where is the hole?
Where is other agent?
Did the previous action fail?

NT
Processing
Processing
Processing
Processing
Processing
Processing
Judgment
Judgment
Judgment
Judgment
Judgment

d
1
1
1
1
1
1
2
6
5
5
2

Nn
2
3
3
2
2
2
1
2
2
1
2

Table.2 The condition branching of the judgment nodes
node name
HAVE_TILE
FIND_TILE
FIND_HOLEFIND_AGENT
TRANS_FAIL

Nd
2
5
5
5
2

answerYes, No
upper, lower, left, right, prevent place
upper, lower, left, right, prevent place
upper, lower, left, right, prevent place
Yes, No

Table.3 Parameters of experiment
generation number
individual number
limits time
mutation probability
crossover probability
trial number

500
100
2000
0.01
0.65
10

C. Experiment results
The learning result of the co-evolution heterogeneous multiagents using GNP, IGNP and GNPIAM is shown in Fig.9. And,each progress of ten trials is shown in Table.4 how the learning isadvanced.
The learning result of the non-co-evolution heterogeneous
multi agents using GNP, IGNP and GNPIAM is shown in Fig.10.
And, each progress of ten trials is shown in Table.5 how thelearning is advanced.

1629

considering it from Fig.9 and Fig.11, in the both methods ofco-evolution and non-co-evolution, IGNP and GNPIAM are
more excellent than GNP. GNP is thought that it settles to the
local solution, and the evaluation value did not go up. IGNP and
GNPIAM is thought that these obtained better fitness because
these search area is wide. IGNP and GNPIAM are compared byusing Table.4 and Table.5. It is understood that the learning of
GNPIAM is better than that of IGNP from Table.4 and Table.5.
This is because the local search ability of GNPIAM is higher(describe in Chapter 3).
When co-evolution and non-co-evolution are compared,
co-evolution is more successful. In the non-co-evolution, thefitness of a certain agent becomes the fitness of the entire agent.
Therefore, evolution settles if the agent with high fitness appears.
VII. CONCLUSION
The heterogeneous multi agents was learned by using GNP,
IGNP and GNPIAM. The targeting task can’t be achieved bysingle agent and can be archived by multi agents. As a result, thelearning of GNPIAM is the best. GNPIAM has the high local
search ability and can search for wide area. The authors proposed
the co-evolution and the non-co-evolution as the learning methodof the heterogeneous multi agents. The co-evolution method isbetter than the non-co-evolution method.
The future work is that the method is improved and the agent
who achieves the task by the higher percentage is made becauseof the task cannot be achieved in all the trials.

Fig. 9 The Learning result of co-evolution method
Table.4 Progress of the learning
All agents grip the tile.
Agents move gripping the tile.
Agents reache the cell of the hole.
Agents drop the tile into the hole

GNP
7
3
0
0

IGNP
10
8
2
1

GNPIAM
101051REFERENCES
[1]

[2]

[3]

[4]

Fig. 10 The Learning result of non-co-evolution method[5]

Table.5 Progress of the learning[6]

All agents grip the tile.
Agents move gripping the tile.
Agents reache the cell of the hole.
Agents drop the tile into the hole

GNP
3
1
0
0

IGNP
9
6
0
0

GNPIAM
10
9
0
0

[7]

In Fig.9 and Fig.10 “max” shows the transition of theevaluation value of times that obtain the maximum fitness of ten
trials. “avg” is an average of the fitness in ten trials. When

1630

K.Hirasawa, M.Okubo, H.Katagiri, J.Hu and J.Murata, "Comparison
between Genetic Network Programming and Genetic Programming Using
Evolution of Ant's Behaviors (in Japanese)", The Transactions of theInstitute of Electrical Engineers of Japan, Vol.121-C, No.6, pp.1001-1009,
2001
T.Murata, T.Nakamura, “Genetic Network Programming with
Automatically Defined Groups for Assigning Proper Roles to Multiple
Agents”, Proceedings of Genetic and Evolutionary Computation (GECCO2005), pp.25-29, pp.1705-1712, 2005
K.Mori, M.Tsukiyama and T.Fukuda, “Immune Algorithm with Searching
Diversity and its Application to Resource Allocation Problem”, The
Transactions of the Institute of Electrical Engineers of Japan, Vo1.113-C
No.10, pp. 872-878, 1997
H.Itoh, “Genetic Algorithm with Immune Adjustment Mechanism”,
Proceedings of the 3rd IASTED Conference Computational Intelligence,
pp.79-84,2007
H.Itoh, T.Mase, Y.Iwahori, “Agent Learning using Immune Evolved
Genetic Network Programming”, Transactions of the Institute of ElectricalEngineers of Japan , Vol.125-C, No.4, pp.537-5442005
K.Hirasawa, M.Okubo, J.Hu, J.Murata and Y.Matsuya, "Co-evolution of
Heteo-Multiagent Systems Using Genetic Network Programming",
Transactions of the Institute of Electrical Engineers of Japan,, Vol.123-C,
No.3, pp.544-551, 2003.
T.Eguchi, K.Hirasawa and T.Furuzuki, “Construction of Symbiotic
Evolutional Model in Multiagent Systems”, IPSJ TOM , Vol.45, No.SIG2,
pp144-156, 2004