Word conversion using a genetic algorithm

The emulator turns the given word into another given word step by step, replacing one letter in the previous word, so that at each step the correct word is obtained. The emulator works with words that consist of 4 letters. The user sets the maximum number of generations and the size of the population. After the calculations, the whole chain of transformations with the interpretation of each word is displayed. Recently a child brought a puzzle from school. In the fifth grade, in Russian literature classes, children are given the following tasks: to make a chain of words, each subsequent of which differs from the previous one only by one letter. Initially set the first and last word of the chain. Having decided to stop the torment of my beloved daughter, who for several hours tried in vain to make an elephant out of a fly, I wrote the following algorithm. Solution Description At first, I applied "brute force" and tried to solve the problem head on. The essence of my naive method was to build a tree of words obtained by iterating through all the letters of the Russian alphabet and substituting them instead of one of the letters of the previous word (see figure). Uncontrolled population increase using the naive algorithm Each new word was tested for absence among ancestors, as well as for availability in the dictionary, which I transferred from the site of fans of crosswords to our directory Words from 4 letters (I hope the authors of the site will forgive me for this liberty). Further, the successfully verified word was included in the tree and a similar procedure was performed for it again until the desired word was found. From the first time, of course, nothing worked - my recursive algorithm quickly filled the limited stack of javascript. The transformation of the recursive algorithm into a cyclical gave a more successful result - the fly was transformed into an elephant for about 10 minutes. The result was suitable for a daughter, but not for me. In addition, while the program was working, I had enough time to think about improving the algorithm and the hypothetical possibility of the fly to evolve into an elephant. This program-biological delusion ultimately led me to a genetic algorithm, which came at the right time to solve this problem and transformed a fly into an elephant within a few seconds. Genetic Algorithm The genetic algorithm was named so because of the similarity of the process of finding a solution with biological evolution. The solution of the problem is a vector of words satisfying a certain criterion (chromosome). At each step, we generate several such vectors (population), after which we select the most suitable variants (viable individuals), i.e. we carry out selection. At the next step, the previously obtained variants are modified again, new variants are generated (a mutation occurs) and so on until the criterion for stopping the algorithm is fulfilled (in our case, the fly will be converted into an elephant). In fact, my initial algorithm could also be attributed to genetic ones (selection was carried out by dictionary checking), but since the number of generated variants increased at each step, then eventually the entire population of new individuals did not have a living space left for further existence ). In the modified algorithm, an improved selection function was applied, which selects only the most similar to the final word variants. The number of the most viable options is set by the Population Size parameter, the smaller this number is, the faster the algorithm works, the more - the better the result is obtained. As an additional stop criterion, a limit was imposed on the maximum size of the chain; another parameter was introduced for this. The algorithm will stop if after the reproduction of a given number of generations the desired result is not obtained. The fitness function (similarity of the current word to the final one) was evaluated by each variant on a 12-point scale. for each letter that matches the position and value of the final result, 3 points were awarded if the vowel letter of a word was in the same place as the other vowel letter of the desired word - 2 points and one point was accrued simply for the presence of a vowel. Thus, the final word ELEPHANT was estimated at 12 points, and the initial word MUHA was only 2.