Lecture 3 min.
Genetic Algorithm: Cat Jumping
The Cat Jumping genetic algorithm is an optimization algorithm inspired by the ability of cats to jump nimbly and efficiently to various heights and distances.
The algorithm is based on imitating a cat's movements when jumping different distances and heights. It uses a population of "cats", each of which represents a solution to the optimization problem. During evolution, the population goes through genetic operators such as crossover and mutation to produce new "cats" with higher objective function values.
When the algorithm starts, a population of "cats" is generated at random. Then each "cat" is evaluated by the objective function, and the best solutions are selected. Genetic operators are applied to the selected solutions to generate new "cats". The process is repeated until a given stopping condition is reached.
The Cat Jumping algorithm can be applied to various optimization problems, such as optimizing neural network weights, finding the best path in routing networks, tuning control parameters in robotics, and many others.
The main advantage of the Cat Jumping genetic algorithm is its ability to find a globally optimal solution in complex, multidimensional optimization problems. In addition, this algorithm does not require knowing the gradient of the objective function, which makes it applicable to a wide range of optimization problems.
A simple genetic algorithm generates the initial population at random. The genetic algorithm is an iterative process that continues until a given number of generations has been reached or some other stopping criterion is met. In each generation, the genetic algorithm performs fitness-proportionate selection, single-point crossover and mutation. First, proportional selection assigns each structure a probability Ps(i) equal to the ratio of its fitness to the total fitness of the population:
Then all n individuals are selected (with replacement) for further genetic processing, according to the value of Ps(i). The simplest proportional selection, the roulette wheel, selects individuals by n "spins" of the roulette wheel. The wheel has one sector for each member of the population. The size of the i-th sector is proportional to the corresponding value of Ps(i). With this kind of selection, members of the population with higher fitness are more likely to be chosen, and chosen more often, than individuals with low fitness.
After selection, the n chosen individuals undergo crossover (sometimes called recombination) with a given probability Pc.
The n strings are randomly split into n/2 pairs. Crossover may be applied to each pair with probability Pc. Accordingly, with probability 1-Pc no crossover takes place, and the unchanged individuals go on to the mutation stage. If crossover does take place, the resulting offspring replace the parents and go on to mutation.
Single-point crossover works as follows. First, one of the l-1 break points is chosen at random. (A break point is the gap between adjacent bits in a string.) Both parent structures are broken into two segments at this point. Then the corresponding segments of different parents are glued together, giving two offspring genotypes.
Once the crossover stage is finished, the mutation operators are applied. In each string that undergoes mutation, each bit is flipped to its opposite with probability Pm. The population obtained after mutation is written over the old one, and this completes the cycle of one generation. Subsequent generations are processed the same way: selection, crossover and mutation.
Comments