Genetic Algorithm: Evolving Perfect Sorting

Sorting is a cornerstone of computer science. Classic algorithms like Bubble Sort, Quick Sort, and Merge Sort have been optimized and widely used for years. But there's also an unusual method: Genetic AlgorithmWe'll explore this creative approach to sorting lists, inspired by natural selection and evolution. In this article, I'll explain the basics of the genetic algorithm, how it works, and how it's implemented in Python. I'll explain this interesting method with examples from my own experience. If you're ready, let's get started!

What is a Genetic Algorithm?

Genetic algorithms (GAs) are optimization algorithms inspired by natural selection. The term "genetic algorithm" in Turkish is directly used for the English "genetic algorithm" and is well-established in the literature. They produce approximate solutions to solve complex problems. Here are their basic components:

• Population: A set of possible solutions (individuals).
• Fitness Function: A function that measures how well each individual solves a problem. In Turkish, the term "fitness function" is standard.
• Vote: More suitable individuals are selected as parents for new generations.
• CrossGenetic recombination occurs to create new individuals (children) from parents. The term "crossover" is common in Turkish.
• Mutation: Random changes are made to add diversity to the population.
• TerminationThe algorithm stops when it reaches a certain number of generations or when a sufficient solution is found.

Now let's see how we apply the genetic algorithm to the sorting problem.

Genetic Sequencing Algorithm

The genetic sorting algorithm uses evolutionary principles to sort a list. Instead of traditional comparison-based methods, it finds the best sorting step by step, starting from random lists. The term "genetic sorting" is appropriate for this particular application. Here's how it works:

• Beginning: A population of randomly sorted lists is generated. Each list represents a possible solution.
• Fitness Function: Measures how "correctly" the list is sorted. For example, how many elements are in the correct positions.
• Vote: Better ranked lists are chosen as parents for new generations.
• Cross: A new list is created from two parent lists.
• Mutation: Minor random changes are made to new lists.
• Termination: Stops when a certain number of generations are reached or when perfect ordering is found.

Let's implement this with Python!

Genetic Sequencing with Python

Below is an example of a genetic algorithm to sort a list of integers in ascending order:

import random def fitness(array): """Calculate the fitness of the array based on the number of elements in the correct position.""" return sum(1 for i in range(len(array)) if array[i] == i) def crossover(parent1, parent2): """Creates a new array from the two parents.""" crossover_point = random.randint(0, len(parent1) - 1) child = parent1[:crossover_point] + parent2[crossover_point:] return child def mutation(array, mutation_rate): """Applies random changes to the array.""" for i in range(len(array)): if random.random() < mutation_rate: j = random.randint(0, len(array) - 1) array[i], array[j] = array[j], array[i] def genetic_sort(array, max_generation=1000, mutation_rate=0.01): """Sorts the array with genetic algorithm.""" population = [random.sample(array, len(array)) for _ in range(100)] for generation in range(max_generation): population.sort(key=fitness, reverse=True) best_array = population[0] if fitness(best_array) == len(array): return best_array # Select parents and create new generation parents = population[:10] children = [crossover(random.choice(parents), random.choice(parents)) for _ in range(90)] # Apply mutation to children for child in children: mutation(child, mutation_rate) # Replace old population with new population = parents + children return population[0] # Example usage array = [5, 2, 9, 1, 5, 6] sorted_array = genetic_sort(array) print("Original Array:", array) print("Sorted Array:", sorted_array)

In this code:

• The fitness function counts the elements in the array in the correct position.
• Crossover creates a new sequence from two parent sequences.
• A mutation makes random changes in a sequence.
• genetic_sorting finds the best sorting starting from random sequences.

In a data analysis project, I tested alternative solutions to a complex sorting problem using a genetic algorithm, and the results were quite creative!

Conclusion

The genetic sorting algorithm is an unusual but fascinating method for sorting. While not as fast as Quick Sort for small lists, it demonstrates the power of evolutionary algorithms. This nature-inspired approach demonstrates the thrill of finding creative solutions in computer science.

What problems have you solved with genetic algorithms? Have an interesting experience? Share it in the comments, and let's discuss it together! For more algorithm tips, check out my blog or contact me!

Notes

• Turkish Equivalents of Terms:
  • Genetic algorithm (genetic algorithm): Established, correct and widespread in Turkish.
  • Population (population), fitness function (fitness function), cross (crossover), mutation (mutation): Standard in machine learning and algorithm literature.
  • Genetic sequencing: An appropriate and understandable term in this context.