Genetic Programming

A thesis by A. J. Bagnall described the ciphertext-only solution of some simple rotor machines by means of the technique of genetic programming.

Genetic programming is a method by which a computer produces an answer to a question, or even a computer program to perform a task, by mimicing the process of natural selection. As noted in the thesis, and in the book Artificial Life by Stephen Levy, this technique was originated by John Holland in the mid-1960s, and his student David Goldberg was one of the first to refine the technique so that it could be used in practice with real problems of importance.

It can be thought of as a special case of the hill-climbing algorithm, in that a quantitative measure of how " warm" the computer is in approaching the desired solution is required.

Programs or answers must be in the form of a chain of discrete elements, such that there is at least a reasonable likelihood that a chain formed by taking one chain, and replacing a span of elements within it by the corresponding elements from another chain, will " make sense". Random mutations are also usually used, although genetic crossover has been found to be much more important.

Starting with a random selection of solutions, those that work best are retained, and used as the parents of the next generation of solutions to be tried. Often, this retention is also randomized, so that better solutions have a higher probability of being retained.

One type of mutation that happens in real life has not, to my knowledge, been used for genetic programming yet. Occasionally, plants and animals will increase the size of their genetic inheritance by duplicating part of it. Thus, a finite state machine could mutate by becoming a machine with twice as many states. It might be useful to make provision for this where a problem might be more complex to solve than initially realized.

Answer the following questions.

What automated aids to cryptanalysis do you remember? Characterize them in a few words.

What are the approaches to cryptanalysis?

What are the specific feature and potential of AI approach?

What fact is the idea of hill-climbing algorithm based on?

What does avalanche property of DES mean?

What are the tendencies in genetic programming?

Vocabulary tasks

Form different parts of speech and translate them.

Give as many word combinations as possible and translate them.

Key, solution, cipher.