17 height=36.3849992752075 /> (1)
where Int() is the integer operator, that is an operator which rounds the argument () to the nearest integer towards infinity.
Due to the design vincula, it is not possible to reach this number and it is necessary to consider a proper multiplicative coefficient c so that the maximum of hubs is equal to c. Good results are obtained if c is equal to 2.
To allow the maximum efficiency of the genetic process, the sensor/hub connections, represented as a number into the genes, are coded with a binary alphabet so that in the presence of the crossing and the mutation operation, the data can be exchanged at the inter-gene level more that at the intra-gene level. If is the number of hubs that ought to be used (according to the criteria expressed above) the minimum number of bits necessary to codify can be demonstrated to be:
In Table 2 the codification of the gene is shown.
The fitness function F(C) (where C is the generic chromosome) represents the cost of the installation and it is composed by the cost of wire installation and by the cost of hubs:
being costm the cost per meter of installation, LC the total length of the installation of the solution represented by the chromosome C, costH the cost of each hub, NHC the number of hubs of the solution represented by the chromosome C. Therefore the system evolves to reduce, as more as possibile, the fitness function, or cost function, represented by Equation (3).
Once defined the chromosome as shown in Table 2, an initial population of 80 - 100 chromosomes is randomly generated and let evolve according to the genetic scheme shown in Figure 6.
In Figure 7 the general scheme of encoding of the solution parameters as genes of a chromosome is shown.
In Figure 8 three significant examples of chromosomes obtained during the evolution process are shown.
The first chromosome represents the most efficient solution in term of shorter sum of connections between
Table 2. Details of the scheme of codification of the gene.
Figure 6. Base cycle of a genetic algorithm.
Figure 7. Encoding of the solution parameters as genes of a chromosome.
Figure 8. Three significant examples of chromosomes obtained during the genetic evolution process.
sensors and hubs (55 meters), as it is possible to verify from Table 1, using anyway all the three hubs.
The second chromosome represents the most efficient solution in term of both number of hubs (2) and shorter sum of connections between sensors and hubs (67 meters): if the cost of the hub is higher than the cost of the difference of length of the connections (67 - 55 = 12 meters), this chromosome tends to extinct during the evolution while the first chromosome tends to dominate and to become the most numerous of the final population. If the mentioned cost is lower an opposite situation takes place.
The third chromosome represents a good solution in term of reduction of the sum of the length of connections with the only exception of genes 4 and 8 where the connections sensor 4—hub 1 and sensor 8—hub 2 are respectively attempted. Since these connections are not allowed, as it is possible to deduce from Table 1, this chromosome immediately extinct at the first fitness evaluation process, because of its inadequacy to represent a valid solution for our problem.
The used GA ensures to obtain the most optimised solution as a function of the input parameters. The optimised solution is generally found after a certain number of cycles, called generations: this number has demonstrated to vary with the number of sensors, as shown in Figure 9.
The important result of this genetic design method is represented by the cost reduction. Different simulations related to different cost of wire installation and hub and to different real situations were made. In Figure 10, the cost reduction of the installation (in percentage) as a function of the number of sensors is shown. The cost used as a base to calculate the cost reduction is represented by the more expensive solution, that is an initial number of hubs that is double with respect to the value expressed by Equation (1) and a connection scheme that is optimized, by means of another GA, to reach the maximum cost.
It is interesting to note that the cost reduces with the number of sensors, that is the more complex is the in-
Figure 9. Number of generations necessary to obtain the optimised solution as a function of the input sensors.
Figure 10. Cost reduction of the installation (in percentage) as a function of the number of sensors.
stallation and the greater is the cost reduction, since the GA optimisation is capable of showing all its efficiency on large scale.
The full cost solution is represented by the initial use of a number of hubs that is the double of the minimal number, as explained before.
The realization of security fixed network is very critical when it must be installed in an environment full of restrictions such as historical palaces, characterized by unique architectural features.
In this paper it has been shown a system which was designed using a very advanced technique based on genetic algorithm optimisation.
The proposed system has demonstrated to be able of ensuring high performances in term of high reduction of the installation cost, in particular way when the number of sensors is greater than 100, that is a normal condition in historical buildings.
The same algorithm can be used in other kind of building where connection restrictions are present.