GA Optimization Problem using a permutation restraint

I am currently working on an optimization problem which requires me to find the best train set which minimizes the forces to which it's subjected. What I'd require the genetic algorithm to do is, having a set of 29 vehicles for the train, to find the best combination which gives the lowest value of the fitness function, which takes into account both compressive and tensile forces.

However in every combination which has to be created, there have to be three fixed positions, which correspond to the three locomotives that are included in this train set (pos 1, 15 and 29). I'd like to put this condition, followed by the necessity to have each combination different from each other, into the algorithm, but I don't know how to do so.

To give an example of the structure this is an hypothetical train set:

1 4 12 6 10 8 7 9 2 3 14 11 5 13 15 25 18 21 24 19 26 28 23 16 27 20 17 22 29

and this its fitness function value: 1.1042

Any help would be much appreciated.

Answer 1

[Hassaan]

you want to ensure that:

1. Three positions in the train set are fixed for the locomotives (positions 1, 15, and 29).
2. Each combination of train vehicles is unique.

Representation of Solutions: Define a chromosome structure that represents a solution. Each chromosome can be an array of 29 integers, where the positions of the three locomotives are fixed. For example:

[Locomotive1, Vehicle2, Vehicle3, ..., Vehicle14, Locomotive2, Vehicle16, ..., Vehicle28, Locomotive3]

1. Initialization: When generating the initial population, create random permutations of the vehicles for the non-fixed positions, while the locomotives' positions remain constant.
2. Fitness Function: This should calculate the forces and return a value representing the fitness of the arrangement. You already have this function, which evaluates to, for example, 1.1042.
3. Selection: Use a selection method like tournament selection or roulette wheel selection to choose which individuals to reproduce based on their fitness.
4. Crossover: Implement a crossover function that respects the fixed positions. One way to do this is to use a two-point crossover that only swaps the non-fixed positions between two parents.
5. Mutation: Define a mutation operation that only alters the non-fixed positions, ensuring that the locomotives remain in their designated spots.
6. Uniqueness: To maintain a unique population, you could check each new offspring against the current population before adding it. If an identical chromosome already exists, you can reject the new one and generate another or mutate the existing one slightly.
7. Termination: Decide on a termination criterion, such as a maximum number of generations or a satisfactory fitness level.

Crossover Example:

function offspring = crossover(parent1, parent2)
    % Assuming parent1 and parent2 are arrays of length 29 with fixed locomotives
    % at positions 1, 15, and 29.
    
    % Define crossover points that avoid the fixed locomotive positions.
    crossoverPoints = [2, 14; 16, 28];
    
    % Choose a crossover point randomly.
    point = crossoverPoints(randi(size(crossoverPoints, 1)), :);
    
    % Create offspring by combining parts of the two parents.
    offspring = parent1;
    offspring(point(1):point(2)) = parent2(point(1):point(2));
    
    % Ensure the offspring has no duplicate vehicles.
    % This step may require a more complex handling to ensure that no duplicates exist
    % and that the vehicle arrangement is valid.
end

Mutation Example:

function mutated = mutate(individual)
    % Assuming individual is an array of length 29 with fixed locomotives.
    
    % Choose two mutation points randomly that avoid the fixed locomotive positions.
    mutationPoints = randsample(setdiff(2:29, [15]), 2);
    
    % Swap the vehicles at these positions.
    mutated = individual;
    temp = mutated(mutationPoints(1));
    mutated(mutationPoints(1)) = mutated(mutationPoints(2));
    mutated(mutationPoints(2)) = temp;
end

You would need to embed these functions within the larger structure of your genetic algorithm and ensure they are called appropriately during the reproduction phase.

Implementing a genetic algorithm can be quite complex, especially when you have specific constraints like this. The pseudocode provided is a simplified version to help you understand how you might begin to integrate these constraints. You will likely need to refine and debug the algorithm to ensure that it functions correctly for your specific use case.

---------------------------------------------------------------------------------------------------------------------------------------------------

If you find the solution helpful and it resolves your issue, it would be greatly appreciated if you could accept the answer. Also, leaving an upvote and a comment are also wonderful ways to provide feedback.

Professional Interests

• Technical Services and Consulting
• Embedded Systems | Firmware Developement | Simulations
• Electrical and Electronics Engineering

Feel free to contact me.

[Lorenzo Merlino]

What a great response! I'd have never expected such a complete answer. Based on what you are saying, I ought to embed those snippets of code into the whole algorithm, though I doubt that it could be the one available in Matlab's toolbox, as it is far too vast and, relying on my basic knowledge of coding, complicated.

I will try to write one on my own using the solutions you gave me, which have been extremely helpful. I was wondering if you'd be available in the future, in case I stumbled upon other intricacies which this project is slowly unveiling.