Genetic Algorithm and Tabu Search attack on the Mono-Alphabetic Subsitution Cipher in Adhoc networks

Journal of Computer Science,  March, 2007  by A. K. Verma,  Mayank Dave,  R. C. Joshi

• E-mail
• Print
• Link

[FIGURE 2 OMITTED]

During each iteration of the algorithm the processes of selection, reproduction and mutation each take place in order to produce the next generation of solution. The actual method used to perform each of these operations is very much dependent upon the problem being solved and the representation of the solution.

Tabu search: Glover (8) was pioneer in use of the Tabu search and has published many articles discussing its numerous applications. Others were quick to adopt the technique, which has been used for such purposes as sequencing, scheduling, oil exploration, routing etc.

The properties of Tabu search can be used to enhance other procedure by preventing them becoming stuck in the regions of local minima (Fig. 3). The Tabu search, like the genetic algorithm, introduces memory structures into its workings. In this case, the purpose of the memory is multi-faceted. The genetic algorithm utilizes its solution pool as a mechanism for introducing diversity into breeding process. The Tabu search utilizes memory for a additional purpose, namely to prevent the search from returning to a previously explored regions of the solution space too quickly. This is achieved by retaining a list of possible solutions that have been previously encountered. These solutions are considered Tabu-hence the name of the technique. The size of the Tabu list is one of the parameters of the Tabu search.

1.Initialize algorithmvariable: Gthe maximum number of generations to consider,M the solution pool size and any other problem dependent variable.

2.Generate aninitial solution pool containing M candidate solution. This initial pool can be generated randomly or by using a simple known heuristic for generating solutions to the problem in hand. This solution pool is now referred to as the current solution pool.

3.For G iterations, using the current pool: a. Select a breeding pool from the current solution pool from the current solution pool and make pairing of parents. b. For each parental pairing, generate a pair of children using a suitable mating function. c. Apply a mutation operation to each of the newly created children. d. Evaluate the fitness function of each of the children. e. Based on the fitness of each of the children and the fitness of each of the solutions in the current pool, decide which solution will be placed in the new solution pool. Copy the chosen solutions into the new solution pool. f. Replace the current solution pool with new one. So, the new solution pool becomes the current one.

4.Choose the fittest solution of the final generation as the best solution.

The genetic algorithm

The Tabu search also contains mechanism for controlling the search. The Tabu list ensures that some solution will be unacceptable; however, the restriction provided by the Tabu list may become too limiting in some cases causing the algorithm to become trapped at a locally optimum solution. The Tabu search introduces the notion of aspiration criteria in order to overcome this problem. The aspiration criteria override the Tabu restrictions making it possible to broaden the search for the global optimum.