Enhanced Computation Method for Laconic Path with the Genetic Automation Imitation

Enhanced Computation Method for Laconic Path with the Genetic Automation Imitation

K. A. Thousief

School of Computing Sciences and Engineering

VIT University

B. Vinod Kumar

School of Computing Sciences and Engineering

VIT University

Abstract

The calculation of the optimal track among two nodes in a web graphs is a central question for various applications in the real world, whether it may be road networks or social collaboration networks or biological networks and so forth. The minimum answer time, the fewer space cost and the high exactness are three important valuation metrics in the inexact estimation of the minimum path. To accomplish a speedy and true computation of an estimated shortest lane span, this paper takes forward step into an Enhanced computation method for laconic path by using the biological automation imitation, which is intended to look for the smallest path from one node to another node. The cellular state is adjusted with the combination of mature and breeding states. In this paper the developed rule is better to improve its parallelism. At the same time, tape manner of cellular state turnover is customized to record all information sources.

Introduction

The computing of optimal lane has always been an important task in the graph theory, because it has a thick application track, continuing from operational research to the regulations of geography, involuntary organize computer science and traffic in networks. Depending up on its actual function, researchers in related track have proposed various designs, but nearly all of them are wholly enhancement on the basis of Dijkstra algorithm. Now, probe on shortest lane are principally pinpoint on the following five aspects: primary, by amendment process arrangement and improving algorithm competence according to explicit network configuration; second, restrictive network uniqueness; third, select loss-algorithm, for example, restricting the investigate collection; fourth, choosing direct topological analysis to stock shortest lane with partial instantiation code; finally, endorse parallel algorithm to offer service for

equivalent computing. In this paper we used the genetic algorithm to calibrate the cellular automation imitation to catch the optimal path.

Genetic automata (GA) for short, is a self- motivated scheme. It is a usual motivated parallel model . GA is clear on, the genetic space contains cellular which having detached and narrow event, based on the certain local rules grow on the detached time dimension. The designing method of GA is contrasting the conventional scheme. In the latter, it is based on voluminous-data, through which complicated obstacles are clear up by using analytical equation and extremely inattentive on the basis of assumption; however, the earlier is a category of revise technique opening from the foundation to the top, with which the observable consequence is formulate by the adding of individual microcosmic which are preoccupied and created from the analysis entities [1].

Accompanying isolated spatial, discrete moment in time, fixed and discrete state, typical GA properties are uniformity, temporal and spatial locality, parallelism, and huge magnitude. With the advance in the computer knowledge, GA has been applied to the fields of natural science, ecology, topography, environment, state transaction, transportation studies, and various disciplines. GA became tremendous in the probe of network and path by the use of uniqueness of parallelism and huge magnitude. In the real time environment, two kinds of networks are used. One is tangible (wired) and the other is invisible (wireless). Day by day most of the network troubles are evaluated and rectified by GA hypothesis. In the unseen network, various complex troubles, that are the complete performance of the systems in computer network [2], transmission latency and mode of packet transfer [3], enlargement circumstance of intricate network with its number of systems are increasing (4, routing strategy [5], and way of transmitting of

virus and malicious software [6], have been effectively analyzed and clear up with GA hypothesis., GA approach has also been imported to the visible networks for the study of network of the railway system and road networks. Taking into consideration of the mixed running of dissimilar trains, [7] place forward a tracking design to follow and interpret the trains delay circulation. On the basis of cell communication schema, [8] studied the problem of optimal assignment of dynamic network users. In [9], person behind that developed a genetic automaton civic traffic flow design model by taking into consideration of harbor-shaped bus stop and also on single way is used for the combined various-high-speed vehicles, and understand the mixed traffic flow uniqueness. In

[10] author proposed the optimal lane algorithm based on cellular automaton premise. In [11] author

,based on GA continuing model in 2004 shaped a shortest lane algorithm, in which they gave description of cellular state and genetic progress rules to manage the progress of cellular state to obtain the shortest lane of graph . Still there is no technique to obtain the shortest lane value; but, by this algorithm only the node order of receiving the shortest lane might be achieved. In the year 2006, based on the study of [11] projected an enhanced algorithm, in which the author introduce supplementary recording data of cellular state takings. In [12], taking into consideration of study of Li, in which subtraction of the least surplus weight was left out of author enhanced one method, while the effect of the algorithm is disproved by the considering of example in this document. From the above studies basis, this document produces betterment to the actual algorithms.

1. Introduction of optimal lane algorithm based on GA

   1. Mathematical characterization of GA

      GA consists of six parts: cellular state, cellular, neighbours; rules, cellular space, and time. Defination of standard GA by mathematical symbols, A: A = (Ld, C, N, f), where

      A GA system, L cellular space,

      d is a positive integer (the dimension of cellular space) ,

      Cdiscrete and finite set of cellular states, N is a combination of the entire neighbour cellulars and the center cellular,

      f local conversion function in cellular space .

   2. Explanation of optimal lane algorithm based on GA

      To find the shortest lane the problems are converted into weighted graph: the nodes are indicating as a cellular set, with every node as a cellular. The neighbours are defined by the node connected with the cellular boundaries.

2. Shortest lane algorithm on the basis of GA by Wu Xiaojun

   1. Evaluation regulations of the algorithm

      Cellular state: It consists of 4 states,

      Which are

      null (C_N),

      growth(C_G), breeding(C_B),and mature (C_M).

      The current state of center cellular is as follows:

      • C_N state: It means that the cellular is in null state. Its next neighbour is checked at this moment. If there is any neighbour ( J ) in C_B state ,then the center cellular ( I ) will be turned in to C_G state in next step. The surplus weight of center cellular (I) is amended as follows:

        Ri=distance (I,J);

        Here distance (I,J) denotes the edge weight between the node I to J.

      • C_G state: It means that the cellular state is in growth state. If the condition RI=minr is satisfied then it will be changed to C_B state in next step; else if its in the Same line ,then there exit any neighbour J in the C_B state ,and distance (I,J)<Ri , then update Ri=distance(I,J).Then adjust minr=min{Ri}.

      • C_B state : It means that the cellular is in breading state. In this state it has found optimal lane. The optimal lane will be changed in to C_M state at next step.

      • C_M state : It means that the cellular is in mature state. In this state it has found optimal lane The optimal lane will not be changed in next coming states.

        Based on the above rules the cellular state turnover is shown in figure1.

   2. Example

      Obtain the optimal lane from A1 to A10 in Figure 2 with Wu Xiaojuns optimal lane algorithm.

      The Evolution procedure of cellular state is shown in Table I. Obtain the optimal lane from A1 to A10 as A1 A3 A6 A9 A10.

   3. Troubles in the algorithm (Table I)

      • In Table I, few number of cellulars are converted into C_B state in steps of 2, 4, 6, 8, 10, 12, and the least additional weight is adjusted to zero. some cellular states are not turned, due to which it wastes the time. In step 5, A9 cellular state is changed. In this algorithm it takes any neighbour cellular j in C_B state to adjust the additional weight of central cellular. Since there are only two neighbour cellulars such as A4 and A6 meets the condition.

      • While taking A4, the additional weight of cellular Ri ¼ 6, when taking A6, the additional weight of cellular Ri ¼ 3. When taking A4 the result obtained is incorrect when tested in Dijkstra algorithm, which shows that algorithm is not accurate enough to solve this type of problems. In step 5, the additional weight of A8 cellular is turned. Since both cellular A5 and A6 are connected to the center A8 cellular and the weight is 4. Since we cannot find the one who copies the information to center cellular. If the optimal lane from A1 to A10 passes through the node A8, the optimal lane node chain cannot be read out.

        Figure 1 Cellular state turnover diagram of the Wu Xiaojuns shortest path algorithm.

        Figure 2. Weighted graph.

      • During step 11, the state of A10 cellular does not change, distance (7, 10) = 1 = R10. When the condition is meet i.e distance (7, 10) <R10, then the source of information will be recorded which is based on the algorithms rules, which leads to impractical use of algorithm to solve multi-path problems.

3. Optimal lane algorithm based on GA by Sun Qiangs

   1. Evolution rules of the algorithm

      The definition of cellular state set in present algorithm is same of the former algorithm, but the step of subtracting least additional weight is rule out. When central cellular is in C_M, C_B, and C_N state, the present rules are the same that of the above. If it is present in C_G state, which represents the cellular is in emerging state. In the same line there is no cellular in C_B state, the cellular is in emerging state with the least additional weight is found, which will be changed into

      Table I .Evolution table of cellular State of Sun Qiang

      STEP	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	Minr
      0	C_B	C_N	C_N	C_N	C_ N	C_ N	C_ N	C_ N	C_ N	C_ N	0
      1	C_M	C_G/4 0	C_G/ 8	C_G/1 0	C_ N	C_ N	C_ N	C_ N	C_ N	C_ N	8
      2	C_M	C_G/3 2	C_B	C_G/2	C_ N	C_ N	C_ N	C_ N	C_ N	C_ N	0
      3	C_M	C_G/4	C_M	C_G/2	C_ G/2	C_ G/2	C_ N	C_ N	C_ N	C_ N	2
      4	C_M	C_G/2	C_M	C_B	C_ B	C_ B	C_ N	C_ N	C_ N	C_ N	0
      5	C_M	C_G/2	C_M	C_M	C_ M	C- _M	C_ G/4	C_ G/4	C_ G/3	C_ N	2
      6	C_M	C_B	C_M	C_M	C_ M	C- _M	C_ G/2	C_ G/2	C_ G/1	C_ N	0
      7	C_M	C_M	C_M	C_M	C- _M	C- _M	C_ G/2	C_ G/2	C_ G/1	C_ N	1
      8	C_M	C_M	C_M	C_M	C- _M	C- _M	C_ G/1	C_ G/1	C_ B	C_ N	0
      9	C_M	C_M	C_M	C_M	C- _M	C- _M	C_ G/1	C_ G/1	C_ M	C_ G/2	1
      10	C_M	C_M	C_M	C_M	C- _M	C- _M	C_ B	C_ B	C_ M	C_ G/1	0
      11	C_M	C_M	C_M	C_M	C- _M	C- _M	C_ M	C_ M	C_ M	C_ G/1	1

      Notes: C_G/4 specifies that the status of the cellular is C_G; surplus load is 4

      C_B state in the further step, otherwise it will be in same line and there exits any neighbor j cellular in the C_B state and the distance (k, j) <Rk, then update RK = distance (k, j). At the same time adjust the minr = min{Ri} .

   2. Example

      Obtain the optimal lane from A1 to A10 as in Figure 2 with the Qiangs algorithm and obtain the optimal lane from A1 to A10 as A1 A3 A6 A9 A10.

      4 .3 Troubles in algorithm (Table II)

      • In Table II, few number of cellulars are converted into C_B state in steps of 2, 4, 6, 8, 10, and the least additional weight is adjusted to zero. But in cellular space, the left over cellular states takes no change, which wastes the time.

      • In step 5, the additional weight of the A8 cellular is changed, but both cellular A5 and A6 are connected with the central cellular A8 and the weight of edges are 4.

      • By this it cant be able to determine which node copies all the information to the cellular. If the node A8 is in the optimal lane A1 to A10,then the node sequence of the optimal path cant be identified. This is similar to the problems defined in Wuxiaojuns algorithm.

      • In step 3, the cellular A4 weight is changed, because cellular A3 the neighbor of A4 is converted into C_B state. The distance (3, 4) = 3 but R4 =10, which satisfies distance (3, 4)

      <R4, the cellular A4 is updated as R4 = distance (3, 4)= 3, that is A4 copies the information from A3. By using Sun Qiangs algorithm we found that the optimal path from A1 to A4 is A1 A3 A4, but when verified with Dijkstra algorithm, it becomes false. Thecorrect verified path from A1 to A4 is A1 A4.

4. Improved algorithm proposed in this paper

   1. Proposed Method:

      The role of C_B is to write the information to the other neighbors in null C_N .The surplus weight is zero if the cellular is in C_B state. C_B Is only changing state of _G to C_M.the other cellular states will no change. In this paper we have presented the combination of C_B and C_M .It will reduce the time cellular turn over and increase the performance of the algorithm. To avoid the uncertainty of the path it will record all the information about cellular state of optimal path. This algorithm will allow to solve multi-path.

   2. Improved evolution rules of the algorithm

      This model proposes 3 cellular states: Null (C_N) ,

      Growth (C_G) and Mature (C_M) .

      Mature state (C_M)The initial state of starting point and the other are null state(C_N) in the graph.

      The current state of cellular is as follows:

      • C_N state: It means that the cellular is in mature state. Its next neighbor is checked at this step.

      1. If there is any other neighbor ( J ) in C_M state ,then the center cellular ( I ) will be turned in to C_G state in next step.

         The weight of center cellular (I) is calculated as follows:

         RI= distance (I,J);

         Where distance (I,J) denotes the weight of the edge between the node I to J.

      2. Otherwise, the cellular J with least weight will be checked. If it is neighbor of center cellular (I) and satisfies the condition distance (I,J)+RI < = RI, verify RI = distance(I,J). Then

         Table II. Evolution table of cellular state of Sun Qiang

         Step	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	Minr
         0	C_B	C_N	C_N	C_N	C_N	C_N	C_N	C_N	C_N	C_N	0
         1	C_M	C_G/ 40	C_G/ 8	C_G/ 10	C_N	C_N	C_N	C_N	C_N	C_N	8
         2	C_M	C_G/ 40	C_B	C_G/ 10	C_N	C_N	C_N	C_N	C_N	C_N	0
         3	C_M	C_G/ 40	C_M	C_G/ 3	C_G/ 2	C_G/ 2	C_N	C_N	C_N	C_N	2
         4	C_M	C_G/ 4	C_M	C_G/ 3	C_B	C_B	C_N	C_N	C_N	C_N	0
         5	C_M	C_G/ 4	C_M	C_G/ 3	C_M	C_M	C_G /4	C_G /4	C_G/ 3	C_N	3
         6	C_M	C_G/ 4	C_M	C_B	C_M	C_M	C_G /4	C_G /4	C_B	C_N	0
         7	C_M	C_G/ 4	C_M	C_M	C_M	C_M	C_G /4	C_G /4	C_M	C_G/ 2	2
         8	C_M	C_G/ 4	C_M	C_M	C_M	C_M	C_G /4	C_G /4	C_M	C_B	0
         9	C_M	C_G/ 4	C_M	C_M	C_M	C_M	C_G /4	C_G /4	C_M	C_M	4
         10	C_M	C_B	C_M	C_M	C_M	C_M	C_B	C_B	C_M	C_M	0

         Note: C_G/4 indicates that the cellular status is C_G; surplus weight is 4

         Record point J from where information is copied. we have to check one by one and record all information if there are more cellular that have least weight .

         • C_G state: It means that the cellular state is in growth state.

      1. If the weight of center cellular is least, chage it to C_M at next step, otherwise change to (b).

      2. The cellular J with least weight will be checked. If it is the neighbor of center cellular I and satisfies the condition distance(I,J)+RI < = RI, verify RI = distance(I,J). Then record point J from where information is copied.

      3. If the above two conditions are not satisfied then the state of center cellular will not change.

      C_M state: It means that the cellular is in mature state. In this state it has found optimal path

      The optimal path will not be changed in next coming states.

   3. Example

      . Obtain the optimal path from A1 to A10 in Figure 2 with the proposed algorithm. The evolution procedure is shown in Table III

      Obtain the optimal path from A1 to A10 as A1 A3 A6 A9 A10 and A1 A3 A5 A7 A10. Then Compare Table III with Table I, we can observes that the cellular state turnover is decreased, the performance is increased, the path information is recorded, solves multi-path problem, from the

      Table we can get the optimal path value.

      Table III. Evolution table of cellular state of the algorithm proposed in this paper

      Ste p	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10	Min r
      0	C_ M *	C_N	C_N	C_N	C_N	C_N	C_N	C_N	C_N	C_N	0
      1	C_ M *	C_G/40 1	C_G/8 1	C_G/101	C_N	C_N	C_N	C_N	C_N	C_N	8
      2	C_ M *	C_G/12 3	C_M	C_G/101, 3 C_G/103	C_G/10 3	C_N	C_N	C_N	C_N	C_N	1
      3	C_ M *	C_G/12 3	C_M	C_M	C_M	C_ M	C_G/14 5	C_G/14 6	C_G/13 6	C_N	12
      4	C_ M *	C_M	C_M	C_M	C_M	C_ M	C_G/14 5	C_G/14 6	C_G/13 6	C_N	13
      5	C_ M *	C_M	C_M	C_M	C_M	C_ M	C_G/14 5	C_G/14 6	C_M	C_G/159	14
      6	C_ M *	C_M	C_M	C_M	C_M	C_ M	C_M	C_M	C_M	C_G/159, 7 15	10
      7	C_ M *	C_M	C_M	C_M	C_M	C_ M	C_M	C_M	C_M	C_M	0

      Notes: C_M* indicates this is the source point; C_G/81 indicates that it is in the C_G state, the Surplus weight is 8, the information is copied from A1; C_M1 indicates that it is in the C_M State , the information is copied from A1.

      Table IV. Demonstration of Dijkstra algorithm

      Step	A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
      1	0*	+	+	+	+	+	+	+	+	+
      2		401	8*1	101	+	+	+	+	+	+
      3		123		10*1;3	103	103	+	+	+	+
      4		123			10*3	103	+	+	164	+
      5		123				10*3	145	145	164	+
      6		12*3					145	145;6	136	+
      7							145	145;6	13*6	+
      8							14*5	145;6		159
      9								14*5;6		157;9
      10										15*7;9

   4. Examination of the model

      Identify the path from A1 to A10 in Figure 2 with Dijkstra algorithm. The detailed explanation is as follows (Table IV).

      We will get the optimal path from A1 to A10 i.e., A1 A3 A6 A9 or A1 A3 A5 A7, which will be same as the algorithm explained in this paper. From this it can be proved that this algorithm is efficient and correct. Due to rational combination of cellular states and parallelism of this algorithm, there will be at least one cellular would be changed to C_M state in the process of path search. By which cellulars in the cellular space changing in to C_M increases rapidly.

5. Conclusion

The proposed algorithm is improved of the existing algorithms. In this algorithm with the combination of breeding and mature states the cellular state turnover will be reduced. The final result will be same as Dijkstra algorithm.

This algorithm is parallel and decomposes into subtasks which is operated concurrently and

the new method in this paper records all the path information .The proposed algorithm consists of cellulars with additional weight and C_G state

.These states can be changed into C_M state, and reduce the runtime. The asymptotic time

complexity is T = O (n2/p), but that of Dijkstra algorithm is T =O (n2).

References:

[1]: Zhang, T., Gao, B.J. and Xuan, H.Y. (2006), A

review of innovation diffusion models based on cellular automata, systems Engineering, Vol. 24 No. 12, pp. 6-

15.

[2]: Yuan, J., Ren, Y., Liu, F. and Shan, X.M. (2001),

Phase transition and collective correlation behavior in the complex computer network, Acta Physica Sinica, Vol. 50 No. 7, pp. 1221-4.

[3]: Liu, F., Ren, Y. and Shan, X.M. (2002), A simple cellular automata model for packet transport in the internet, Acta Physica Sinica, Vol. 51 No. 6, pp. 1175- 80.

[4]: Li, J., Wang, B.H., Jiang, P.Q., Zhou, T. and Wang,

W.X. (2006), Growing complex network model with

acceleratingly increasing number of nodes, Acta Physica Sinica, Vol. 55 No. 8, pp. 4051-7.

[5]: Chen, H.L., Liu, Z.X., Chen, Z.Q. and Yuan, Z.Z. (2009), Research on one weighted routing strategy for complex networks, Acta Physica Sinica, Vol. 58 No. 9, pp. 6068-73.

[6]: Song, Y.R. and Jiang, G.P. (2009), Research of aware propagation in complex networks based on cellular automata, Acta Physica Sinica, Vol. 58 No. 9, pp. 5911- 18.

[7]: Xun, J., Ning, B. and Li, K.P. (2007), Network based on train following model and study of trains delay propagation, Acta Physica Sinica, Vol. 56 No. 9, pp. 5158-64.

[8]: Lian, A.P., Gao, Z.Y. and Long, J.C. (2007), A

dynamic user optimal assignment problem of link variables based on the cell transmission model, Acta Automatica Sinica, Vol. 33 No. 8, pp. 852-9.

[9]: Qian, Y.S., Wang, H.L. and Wang, C.L. (2008),

The study of a cellular automaton traffic flow model with public transit, harbor-shaped bus stop and mixed different-maximum-speed vehicles on single lane, Acta Physica Sinica, Vol. 57 No. 4, pp. 2115-21.

[10]: Adamatzky, A.I. (1996), Computation of shortest path in cellular automata, Mathl. Comput. Modelling, Vol. 23, pp. 105-13.

[11]: Wu, X.J. and Xue, H.F. (2004), Shortest path algorithm based on cellular automata extend model, Computer Applications, Vol. 24 No. 5, pp. 92-3.

[12]: Sun, Q. and Dai, Z.J. (2009), A new shortest path algorithm using cellular automata model, Computer Technology and Development, Vol. 19 No. 2, pp. 42-4.

Biography:

K.A.THOUSIEF: Is a student pursing MTech in computer science from VIT University .He received his B.Tech in computer science from JNTU university Andhra Pradesh – India

B.VINOD KUMAR: Is a student pursing MTech in computer science from VIT University. He received his B.Tech in Information Techology from Nagarjuna University Andhra Pradesh -India