Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 36 ยท Representation and Fitness

Permutation Encoding for Ordering Problems

Represent tours, schedules and orderings as permutations in a genetic algorithm, evaluate them on a traveling salesman problem, and see why bit-string operators break them.

Many real problems are about order. Which city do I visit first, second, third? Which job should the machine run next? In what sequence should a robot drill 200 holes? The solution is not a set of independent choices but an arrangement of the same items, each used exactly once. The natural representation is a permutation: a list in which every item appears once.

Permutations behave differently from bit strings and real vectors. The usual operators fail, so this lesson explains why, builds a fitness function for the classic traveling salesman problem (TSP), and shows the mutation operators that keep a permutation valid. Crossover for permutations comes in its own lesson.

What a permutation chromosome looks like

For five cities numbered 0 to 4, a tour is a list such as [2, 0, 4, 1, 3]: visit city 2 first, then 0, and so on, returning to 2 at the end. There are n! permutations, and for a closed tour that does not matter where you start or which direction you travel, there are (n-1)!/2 truly different tours.

A valid chromosome must contain each city exactly once. That one rule is the whole difficulty.

Why bit-string operators break permutations

Try ordinary one-point crossover on two perfectly good tours:

Python One-point crossover ruins a permutation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The child repeats cities 0 and 2 and misses cities 3 and 5, so it is not a tour at all. Mutation by changing a gene to a random city has the same problem. We need operators that rearrange without duplicating. Two choices exist: write operators that always output permutations (the usual approach), or fix invalid chromosomes afterwards with a repair step (see repair and decoders).

Fitness for the traveling salesman problem

In the TSP, a salesman must visit every city once and return home, minimizing total distance. The cost of a tour is the sum of Euclidean distances between consecutive cities, including the leg back to the start. Since we want a short tour, use cost directly with a minimizing selector, or fitness = 1 / length.

Python Tour length and random tours

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A typical random tour (median about 656) zigzags across the map and is much longer than a sensible one. With only 12 cities, sampling 2,000 tours can still stumble on a good one, but that luck vanishes quickly as the number of cities grows, because the space grows factorially. A GA beats blind sampling by building on good tours.

Mutation operators for permutations

All of these keep the chromosome a valid permutation.

Operator What it does Example on [0 1 2 3 4 5]
Swap Exchange two random positions [0 4 2 3 1 5]
Insert Remove one gene and put it elsewhere [0 2 3 1 4 5]
Inversion (2-opt move) Reverse a random segment [0 3 2 1 4 5]
Scramble Shuffle the genes in a random segment [0 3 1 2 4 5]

For the TSP, inversion is especially good because reversing a segment replaces only two edges of the tour and keeps the rest intact, which is a small change to the quality. A swap of two distant cities changes up to four edges.

Python Four permutation mutations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Other permutation problems

Permutations appear far beyond TSP, but the meaning of position changes:

  • Scheduling: position = order in which jobs run; fitness = total lateness or finish time.
  • Assignment: position i = facility, value = location (the quadratic assignment problem). Here absolute position matters, not adjacency.
  • Vehicle routing: one permutation of all customers, split into routes by a decoder.
  • Sequencing in bioinformatics or manufacturing: any "order the parts" task.

Whether adjacency (which item is next to which, as in TSP) or absolute position (which slot an item sits in, as in assignment) or relative order (which comes before which, as in scheduling) matters decides which crossover to use.

What matters in an ordering?

Adjacency Who sits next to whom (TSP)
Absolute position Which slot holds which item
Relative order Who comes before whom

Pick operators that preserve what your problem cares about.

1 / 2

Alternatives to direct permutations

Some designs avoid the validity problem by evolving something simpler and decoding it into a permutation:

  • Random keys: each item gets a real number (its key); sorting the items by key gives the permutation. Any real-valued operator works, and every chromosome decodes to a valid permutation. Fitness landscape side effects exist, but it is very convenient.
  • Lehmer code / factorial number system: encode a permutation as a list where gene i is an index into the remaining items.
Python Random keys: any real vector is a valid tour

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What rule must every permutation chromosome satisfy?

    A permutation uses every item once. Standard bit-string crossover and mutation can break that rule, creating duplicates and gaps.
  2. 2. Why is inversion a good mutation for the TSP?

    Reversing a segment leaves the inside of the segment's edges intact and replaces only the two boundary edges, a small change in tour length.
  3. 3. In the random keys representation, what does the decoder do?

    The ordering of the keys defines the permutation, so every real vector decodes to a valid ordering and ordinary real operators can be used.
  4. 4. In the quadratic assignment problem, what matters most?

    Each position stands for a facility and the value for its location, so what slot an item occupies matters rather than its neighbors.

Summary

  • A permutation chromosome holds each item exactly once and encodes tours, schedules and assignments.
  • Standard crossover and gene-replacement mutation create duplicates and gaps.
  • TSP fitness is the closed-tour length; shorter is better.
  • Use swap, insert, inversion or scramble mutations; inversion is gentle for TSP.
  • Random keys let you use real-valued operators and decode to a valid permutation.

Next: Designing Fitness Functions