Exploiting Genetic algorithms by Optimizing Industrial Site clustering and Telecommunication networks - - EGOIST

(project ISC-MED-35 - EGOIST)

Partners:

The EGOIST project is based on the experiences and results gained by Cap Volmac and ICS in the ESPRIT-III project PAPAGENA (Programming Environment for Applications of Parallel Genetic Algorithms, project_No: 6857). PAPAGENA aimed at developing a programming environment for Parallel Genetic Algorithms and demonstrating applications. The applications underscore the usefulness of Genetic Algorithms in European industry, while the programming environment is motivated by the desire to establish a European standard.

The Programming environment, called GAME (Genetic Algorithm Manipulation Environment) provides a general-purpose toolkit for the programming and simulation of a wide range of Genetic Algorithm applications. It comprises a library of common Genetic Algorithms and a powerful graphic interface.

The objectives of EGOIST is to enhance GAME by including new commercial and administrative application areas, i.e., optimal telecommunication network layouts and apply them to developing countries.

The basic structure of a telephone network is depicted in figure 1:

Fig. 1 : Principle structure of a telephone network

The transportation network transports messages from the switch board to the so called Cross Connection Points (CCP). The CCP on its turn connects several subscribers to the telephone network, this part is called the distribution network. The CCP is connected through cables to Distribution Points (DIPs). The DIPs are connected directly to a group of subscribers (telephone customers). If a cable splits or a cable is bend within a certain angle, an Underground Room (UGR) is build.

The focus of the EGOIST project is on the optimization of the distribution network. In other words: "How can all subscribers be connected to the network by traveling from the CCP through all DIPs with a minimum of costs for cables and underground rooms?".

In a geographical area a CCP is given together with several DIPs. There are certain connection allowed depending on given rules (constraints) resulting in a potential network which mathematically represents a graph, viz.

 

Fig. 1 : A potential network (P-NW) with all allowed connection between a given CCP and the DIPs.

While the potential network (P-NW) is represented by a graph with three types of nodes (CCP, UGR, DIP). The potential network has to be optimized resulting in the optimized network (O-NW) which corresponds to a tree with the CCP as root and the DIPs as leaves. A solution of the P-NW given in fig.1 is shown in fig.2.

 

Fig. 2a : An optimized network (O-NW)

 

 

Fig. 2b : The optimized network depends on the cable capacities and the type of UGR.

The capacity of a cable is equal to 7*2ⁿ, where 7 is the number of pairs in the cable and n has a value of {0,1,2,3,4,5,6,7,8}. In Tunisia, the maximum capacity of a distribution cable is 448 pairs, which corresponds to 7*2⁶. Cables connecting CCP to DIPs can be splitted into halves or quarters as described by the numbers in Fig.3. The costs of the cable layout strongly depends on the special configuration, for example, the costs for 3 cables with 7 pairs are different from one cable with 21 pairs, etc. For more details about the constraints see "Alternative Methods for the Optimization of Telecommunication Networks".

In order to work with the optimization tools developed within the project, an engineer has first to design a potential network (P-NW). The P-NW contains all possible connections, all underground rooms (UGR) that are necessary for the realization of the P-NW. It also contains the CCP (central connection point). From the P-NW the optimized network (O-NW) can be calculated using the optimization tools implemented into a CAD system..

In the past, the P-NW had to be drawn by hand on a paper copy of a map that contains buildings, streets, and footpaths. From these manually drawn maps the P-NW had to be extracted again by hand(!) on a digitizing board using an appropriate software tool.

This procedure for the design of an optimal telecommunication network (O-NW) is not acceptable. Therefore two alternative possible ways have been envisaged which could be used in the future by the engineers in Tunis and/or by other providers:

In this approach the manually drawn geographical map, the drawing, is scanned and the resulting bitmap gives the basis, i.e., the graphical background, for the construction of the P-NW using adequate CAD software tools.

In this way the P-NW is obtained as a vector data file which can be transferred as DXF file for the optimization process. The resulting O-NW again can be transferred as DXF file into the CAD system and can be plotted (in a correct scale) either separately or together with the underlying bitmap using standard CAD options.

The different steps of the procedure have been depicted in Fig. 3. A DEMO version of the software integrated into a CAD system is available from:

< vgo@xpertnet.de > or < ics@ics.prima.ruhr.de >

If the geographical map already exists in a vectorized and interpreted form, as it is the case for a Geographical Information System (GIS), the optimization tool can be designed in such a way that the O-NW will be calculated without the foregoing manual construction of a P-NW. The results about this approach will be reported in the future.

Fig. 3 : (a) (c) (d) (e) (f) (b)	Steps toward an optimized telephone network (within the bitmap approach): from (a) to (c) to (d) to (e) to (b). the map of the geographical area of interest (as bitmap background); the distribution points and the CCP have been added to (a) using the CAD functions of the tool; the potential network resulting from (b); the potential network with undergroundrooms (UGR); the optimized network using the optimization functions of the tool; the result which can be plotted and electronically archived.
( a ) geographical area of interest (as bitmap)		( b ) geographical area + telecommunication network
( c ) geographical area +distribution points (DIPs)		( d ) the portential network for a set of given DIPs
( e ) the network of (d) together with UGRs		( f ) an optimal network configuration (cf. fig. (b))

Data Acquisition

Within the EGOIST project the data acquisition of the P-NW has been performed by IRSIT on a digitizing board with the help of ArcView resulting in a XXX.ur and a XXX.con file. Unfortunately both data files were not compatible with the DXF format defined previously in our workpackages. A program that transforms the XXX.ur and XXX.con files into a well defined DXF file has been developed by ICS.

The optimization tools and the cost functions

Two different optimization tools have been implemented into a CAD system: EGONET and MSTA. EGONET is a Genetic Algorithm which can be used as add on for all CAD systems since it is independent on the operating system. MSTA stands for ´mutation-selection-threshold-algorithm´. Again this algorithm can be used for all platforms as an add on tool. A description of the cost functions and constraints which have been implemented into EGONET and MSTA is described in "Alternative Methods for the Optimization of Telecommunication Networks" and within the demonstration software available from the ICS:
< vgo@xpertnet.de > or < ics@ics.prima.ruhr.de >

For both algorithms the same fitness functions are used. In order to generalize the cost functions a dBase application has been developed by the ICS on the basis of an depository catalogue. The main parts of the data base application are given by the cable costs, the costs for installation, the costs for cable division and the installation of underground rooms (UGR). With the data base application the tools became more flexible, i.e., they can be used for cases where labor costs and/or ground conditions have to be considered for the installation of the cables. In other words, these data not only define the optimal telecommunication network, they are used for the deviation (calculation) of the constraints for the calculation of the optimal network.

The optimization tools (EGONET, MSTA) developed by the ICS have been implemented as EXE-files into a commercial CAD-system. Special tools for a proper CAD design of the distribution points (DIPs), the underground rooms (UGRs), the cable connections (including their capacity) have been implemented into the CAD-system. With the help of these tools it is possible to design a P-NW on the background of a scanned bitmap that contains all geographical information such as the position of houses, streets, sidewalks, etc. The CAD system was modified in such way that the calculation of the O-NW can be started immediately from the CAD system. The O-NW is visualized on the bitmap and can be plotted either separately or together with the geographical background (the bitmap representing houses, streets, etc.) using standard CAD functions. Since the CAD software is running in a German version, the system was designed in such way that the optimization tools can be combined with any other (CAD) system, i.e., it easily may be integrated (as an EXE file) in the system used at Cap Volmac. For EGONET a graphical interface for Windows (EGOWIN) was developed.

For more details concerning the tools, which also can be used (with some minor modifications) for the optimization of utility networks, see ´THE APPROACH OF ICS WITHIN EGOIST´ in: "Alternative Methods for the Optimization of Telecommunication Networks" or order the DEMO version (for Windows 3.11, Windows95) from the ICS :
< vgo@xpertnet.de > or < ics@ics.prima.ruhr.de >

webmaster@xpertnet.de
Copyright ©: 1996, ICS
last revised Jan. '97