Application of Fuzzy Heuristic Techniques to Computer Network Design

APPLICATION OF FUZZY HEURISTIC TECHNIQUF.S TO COMPUTER NETWORK DESIGN

S.I.Samoylenko, Moscow, USSR

Paper [2] discussed a solution search me­ thod based on fuzzy heuristics. The pre­ sent paper describes some results obtain~ by applying the above method to the selec­ tion of multipoint communication network topologies.

The problem is formulated as follows. We have an ensemble of M+1 sites S={s 1 ,s?··· ··· ,s } with known distances between each ~ilr of the sites. One of the sites is central. It is required to connect M sites to the centre via communication li­ nes so that any line passes through not more than Mo sites, M 0 <M, provided the total lengtfi of the lines is minimal.

Problems of this class are uaue.lly handled by means of heuristic methods. In the p~ sence of constraints (M 0 < M) the heuristic solutions may be significantly inferiorto the optimal solution.

Fuzzy heuristics make it posible to e~ at the problem solver's discretion the search area in the neighborhood of solu­ tions suggested by the heuristics emplo~. The procedure is implemented through con~ rolled expansion of the search area cir­ cumscribed by heuristics while the extent of the fuzziness of the area may be var.Un to meet the search time limit or other constraints.

It will be supposed that the procedure of search for a feasible solution g=(g 1 ,g?··· ··· ,g ) includes M steps, with the local solut¥on g1 selected at each of the step& When the c~nventional heuristic search procedure is employed, the selection of& with known g 1 , g 2 , ··· ,g. 1 is unamb:iguouer, due to which the searchJprocedure produ­ ces a single solution. Fuzzy heuristics introduce controlled indetermintion in tie selection of g · and, therefore, can be used toJgenerate a class of subop­ timal solutions and improve the solution derived by means of the conventional heu­ ristic search procedure if this solution is not optimal.

Let all the sites of the communication network be divided at the jth search step into the three sets: sa - a set of sites wlich are not yet connected to the centre, S - a set of sites which are connected t the centre via lines.with the number of sites · < M 0 , and S~ - a set of si tea connected to the centre through lines with the number of sites equal to M 0 , j=1,2, ··· ,M. Then a conventional procedu­ re of heuristic selection at the jth step can consist in selecting a pair of the closest sites s. E S~ and s t S~ and in connecting thea~ si~es by ~ communication line. This procedure will produce a s~

solution which will differ from the opti­ mal solution in .different degrees depen­ ding on a specific problem.

With the method of fuzzy heuristics, the procedure of selection of a local deci­ sion at each step is not unambiguous. For example, we may assign to each site s 1 E S~ a weighting coefiicient w. propor­ t~ona~.to its distance to the nearest siw from sJ and select connected sites with prob~bflities p.=c./w. where c. is a normalization factor.~ ~ ~

The degree of fuzziness of the heauristic:, search can be varied by modifying the distribution according to which selection of local solutions is performed. If the initial local distribution has the form P=(p 1 ,p?, ··· , pM) at the jth step, the search area can be chang~d by introducing ~ mod~fied distribution_P=(~J'p 2 , ··· ,pM), ~n wh~ch, for example, P·=P· p , L~u 1 1 .t

M L where P. = I: p . · The search area is narE i=1 1

rowed if L > 1 and expanded if L < 1. With L=O the procedure is transformed into equiprobable selection.

The search procedure was implemented in PL/1 and applied for solving test prohl~ of different dimensionality with M=25,40, 60,100; M 0 =5-7. The location of sites was generated by random selection of coordi­ nates within a 1x1 square similar to the procedure employed in [1] · The results obtBined were compared with the results derived by the conventional heuristic search procedure described above. The ~m­ parison has shown that in all the protilems the fuzzy heuristic technique produced solutions superior ·to those obtained by means of conventional heuristic search. Depending on specific problems, the imp­ rovement achieved was within several per cent to about 15 per cent of the total length of the communication linea.