kuasawan-murbawan / improved-greedy-crossover

Improved Greedy-Crossover

The Improved Greedy Crossover (IGX) algorithm works by combining elements of genetic algorithms and greedy algorithms to solve combinatorial optimization problems. The algorithm operates in generations, where each generation consists of a population of candidate solutions. The IGX algorithm uses a greedy search technique to initialize the population, followed by the application of genetic operators such as crossover and mutation to generate new solutions.

In each iteration, the IGX algorithm evaluates the fitness of each solution in the population and selects the best ones as parents. The parents are then combined using crossover to generate offspring, which are mutated to produce new solutions. The new solutions are then added to the population and evaluated, and the best ones are selected for the next iteration.

The IGX algorithm repeats this process until a stopping criterion is met, such as reaching a maximum number of generations or finding a solution with sufficient fitness. The final solution is typically the best solution found in the last generation.

The code for the example of IGX can be seen in the main code

Example Problem

In this problem, we are given a set of cities and we want to find the shortest possible route that visits each city exactly once and returns to the starting city.

To find the shortest path between two cities, the input might include:

• The number of cities
• The distance between each pair of cities

The output would be:

• The shortest path between the two cities, represented as a list of city indices
• The total distance of the path

The main steps of the algorithm are as follows:

1. Initialization: A population of solutions is generated, each solution representing a possible TSP route between a set of cities. The fitness of each solution is calculated and stored, where the fitness is defined as the total length of the route.

2. Selection: Two solutions are selected from the population based on their fitness, where the solutions with lower fitness have a higher probability of being selected.

3. Crossover: The two selected solutions are used to generate two offspring solutions using the improved greedy crossover operation. The improved greedy crossover operation tries to improve the offspring solutions by swapping cities in the routes if the swap results in a lower total length of the route.

4. Mutation: Each offspring solution is mutated by randomly swapping two cities in the route.

5. Replacement: The two worst solutions in the population are replaced by the two offspring solutions, which are now considered as the new candidate solutions for the TSP.

6. Repeat: The algorithm is repeated for a fixed number of iterations (e.g., NUM_ITERATIONS in the code) or until a satisfactory solution is found.

7. Result: The best solution in the final population is printed as the result of the IGC algorithm.

This code also includes some helper functions such as calculateFitness, generateInitialSolution, and selectSolutions, which perform auxiliary tasks such as calculating the fitness of a solution, generating an initial solution, and selecting solutions from the population, respectively. The code uses a random number generator (RNG) to generate random numbers, and the RNG is seeded with a random seed to ensure that different runs of the algorithm produce different results. ¹

The difference between the Improved Greedy Crossover (IGX) and the Greedy Crossover (GX)

The main difference between the GX and the IGX is that the IGX adds a local search operation to improve the offspring solutions generated by the GX. The IGX has been shown to produce better results than the GX in solving the traveling salesman problem and other combinatorial optimization problems.

Greedy Crossover	Improved Greedy Crossover
In the GX, two parent solutions are selected and the offspring solutions are created by taking the first city from one parent and then selecting the next closest city from both parents until all cities have been assigned to the offspring. This method generates offspring solutions that are similar to the parent solutions, but it may not produce optimal solutions, as the process does not consider the overall fitness of the offspring solution.	In contrast, the IGX algorithm improves the offspring solutions generated by the GX by applying a local search operation after the crossover operation. The local search operation swaps two cities in the offspring solution and calculates the fitness of the offspring after each swap. If a swap results in a lower fitness, the swap is accepted and the offspring solution is updated. This process is repeated until no further improvement can be made. By performing the local search operation, the IGX algorithm is able to generate offspring solutions that are more optimal than those generated by the GX.
In the GX, the crossover operation is relatively simple and only involves selecting cities from both parent solutions to create the offspring solution. The GC code would look something like this:	In the IGX, the crossover operation is followed by a local search operation that performs swaps on the offspring solution to improve its fitness. The local search operation can be implemented as a simple function that tries swapping two cities in the offspring solution, calculates the new fitness, and accepts the swap if the new fitness is lower than the current fitness. The IGX code would look something like this:
Code Example	Code Example

Footnotes

1. Note that this code is just an example to demonstrate the idea of the IGC algorithm and may not be suitable for solving TSP problems with large numbers of cities. In practice, more sophisticated optimization methods, such as genetic algorithms, are used to solve TSP problems. ↩