![](https://csdnimg.cn/release/download_crawler_static/10395696/bg4.jpg)
332 A.F.R. Araújo, C. Garrozi
Fig. 1 A representation example: (a) A network with source node S
and twelve unidirectional links. The gray nodes form the multicast
group; (b) An individual with three chromosomes (routes) and a vari-
able number of genes (links)
links. A viable route (a feasible chromosome) must have
a sequence of links from the initial node to a destination
node which are topologically connected, i.e., each pair of
links must share a common node, so that, at the end of each
feasible chromosome, the destination node is reached. Fig-
ure 1 shows an instance of an individual with three chromo-
somes. From this point onwards, a route is defined as a set of
paths from the source-node (S) to a destination node (D
i
),
whereas a multicast route is defined as the routes from S
(starting node) to the multicast group (D
i
,i =1,...,M).
The randomly generated initial population takes into ac-
count the existence of actual connections between two con-
secutive network nodes as a local constraint. An empty chro-
mosome is filled as follows: choose randomly a link, from
the source node to any other node in the network, and place it
at the first locus; fill the subsequent loci following the same
procedure. A link cannot be selected more than once, hence,
whenever there are no viable links to be chosen at any step,
the chromosome is not completely filled and the destination
node is not reached. Thereafter, variation operators will act
to improve incomplete paths.
2.2 Multiobjective optimization problems
A general multiobjective optimization problem (MOP) com-
bines two or more objectives to determine the overall goal.
Such objectives often affect each other in complex and non-
linear ways [27]. Formally, a MOP can be stated as:
Find the vector X
∗
=[x
∗
1
,x
∗
2
,...,x
∗
u
]
T
that optimizes the
function:
G(X) =(g
1
(X), g
2
(X),...,g
u
(X)) (1)
satisfying the constraints of m inequality
h
i
(X) ≥0 i =1, 2,...,m (2)
and the constraints of (z −m) equality
h
j
(X) =0 j =m +1,m+2,...,z (3)
where X is the vector of decision variables [28], and g
v
(X)
with v = 1,...,u are objective functions often mutually
conflicting in nature. In some approaches, the constraints
are also treated as objective functions. There are also ap-
proaches in which a number of objectives are treated as con-
straints in order to reduce the dimensionality of the objective
space [29].
The current problem takes into consideration three ob-
jectives, hence the aim is to maximize the function G(X) =
(g
1
(X), g
2
(X), g
3
(X)) in which g
1
(X), g
2
(X), and g
3
(X)
consider the number of common paths, the total length of the
route, and a reward for viable routes (or absence of violated
constraints), respectively. Hence, the objective function is
given as follows
G(X) =1 −
ω
1
g
1
(X)
ω
2
g
2
(X)
+ω
3
g
3
(X) (4)
where ω
1
,ω
2
,ω
3
are the weights of real value functions.
Equation (4) is subject to constraints which limit the maxi-
mum and the minimum number of links of a route and es-
tablish the connections of each route, as follows:
q,r∈H
i
l
qr
≤L
max
(5)
q,r∈H
i
l
qr
≥L
min
(6)
q,r,s∈H
i
l
qr
·l
rs
=1 with q =s (7)
where q,r,s are indices of the network nodes in each chro-
mosome (route) H
i
,i =1,...,M, and l
jk
is a potential link
(gene) from node j to node k within route H , i.e., l
jk
is an
element of the network connection matrix which has values
of 0 for each link absent or of 1 for each existing link. For
this case, L
max
=L;L
min
=1. Equations (5)–(6) restrict the
minimum and maximum number of paths and (7) checks if
each path is actually connected within the network, taking
the value 1 if it is fully connected and value 0 otherwise.
2.3 Fitness function
In this paper we propose the following fitness function. The
objective function (4) is transformed into a fitness function