One Max

The one max problem is a starter problem for genetic algorithms. The optimization goal is to maximize the number of ones in a list. It is simple but contains all the components you need for genetic algorithms.

In a nutshell you

Generate a randomized initial population
Sort the population by fitness
Group the population into parents
Generate children from parent pairs
Repeat from step 2 until optimization goal is met

APL Setup

Initial Population

Each member of the population is a list. Each element in the lists are a 1 or 0. The apl operator ? is called roll and rolls a die up to the given number.

? 2

Because APL is 1 indexed we get a 1 or a 2. To generate a list of 1s or 2s we roll against a vector.

? 2 2 2 2 2 2 2 2 2

┌→────────────────┐ │2 2 2 1 2 2 1 1 2│ └~────────────────┘

We can use ⍴ to create a list of the correct size

?10⍴2

┌→──────────────────┐ │2 2 2 2 2 2 1 2 2 1│ └~──────────────────┘

We can use extend this to generate the entire population of p0

?10 10 ⍴ 2

┌→──────────────────┐ ↓2 1 1 2 2 2 1 2 2 1│ │1 2 2 1 2 1 1 2 2 1│ │2 1 2 2 2 2 1 1 2 2│ │1 1 1 2 1 2 2 2 1 2│ │1 2 2 1 1 2 2 1 2 2│ │1 1 1 2 2 2 2 2 2 1│ │1 1 2 1 1 2 2 2 1 2│ │1 1 1 1 1 1 1 1 2 2│ │2 2 1 1 1 1 2 2 1 2│ │1 2 1 2 1 1 1 1 2 2│ └~──────────────────┘

To get 1s and 0s we subtract one

⎕←p0←1 -⍨ ?10 10 ⍴ 2

┌→──────────────────┐ ↓1 1 1 0 1 0 0 0 0 0│ │1 0 0 0 1 0 0 0 1 0│ │0 1 0 1 1 1 1 0 0 0│ │0 0 0 1 0 1 1 0 0 0│ │1 1 1 0 1 0 1 1 1 1│ │1 1 0 1 0 0 0 1 1 1│ │1 0 0 1 1 0 1 0 0 0│ │0 1 1 1 0 1 1 0 1 1│ │1 0 0 1 0 1 0 1 0 1│ │0 0 1 1 1 0 1 1 0 0│ └~──────────────────┘

Sort

To sort we need to identify a fitness function relevant to our optimization goal. We want to maximize the number of 1s in the list. Lets use the number of 1s in the list.

+/p0 ⍝ Sums across each row

┌→──────────────────┐ │4 3 5 3 8 6 4 7 5 5│ └~──────────────────┘

⍒+/p0 ⍝ Indices in decreasing order

┌→───────────────────┐ │5 8 6 3 9 10 1 7 2 4│ └~───────────────────┘

p0⌷⍨⊂⍒+/p0 ⍝ Use the indices to reorder p0

┌→──────────────────┐ ↓1 1 1 0 1 0 1 1 1 1│ │0 1 1 1 0 1 1 0 1 1│ │1 1 0 1 0 0 0 1 1 1│ │0 1 0 1 1 1 1 0 0 0│ │1 0 0 1 0 1 0 1 0 1│ │0 0 1 1 1 0 1 1 0 0│ │1 1 1 0 1 0 0 0 0 0│ │1 0 0 1 1 0 1 0 0 0│ │1 0 0 0 1 0 0 0 1 0│ │0 0 0 1 0 1 1 0 0 0│ └~──────────────────┘

sort←{⍵⌷⍨⊂⍒+/⍵}

Group into parents

Once the population is sorted we group into parents. The two fittest members will be used to generate two children. Third and fourth will be grouped etc. APL has ⌺ the sliding window operator.

⊢⌺(⍪2 2)⊢sort p0 ⍝ Window size of 2 and step size of 2

┌┌→──────────────────┐ ↓↓1 1 1 0 1 0 1 1 1 1│ ││0 1 1 1 0 1 1 0 1 1│ ││ │ ││1 1 0 1 0 0 0 1 1 1│ ││0 1 0 1 1 1 1 0 0 0│ ││ │ ││1 0 0 1 0 1 0 1 0 1│ ││0 0 1 1 1 0 1 1 0 0│ ││ │ ││1 1 1 0 1 0 0 0 0 0│ ││1 0 0 1 1 0 1 0 0 0│ ││ │ ││1 0 0 0 1 0 0 0 1 0│ ││0 0 0 1 0 1 1 0 0 0│ └└~──────────────────┘

group ← {⊢⌺(⍪2 2)⊢⍵}

group sort p0

Crossover

This is a function that generates children from parents. This problem generally takes a pair of parents. Splits them at the same point (a different point for different pairs) and then swaps the tails.

[1,1,1,1]    [1,1,1] [1]    [1,1,1,2]
          ->             ->
[2,2,2,2]    [2,2,2] [2]    [2,2,2,1]

Do this for every pair of parents and you have your new population

Instead of splitting we are going to use ⌽ the rotation operator. ⌽ wraps around.

[1,1,1,1] [2,2,2,2] -> [1,1,1,1,2,2,2,2] -> [2,1,1,1,1,2,2,2] -> [2,1,1,1] [1,2,2,2]

Probably close enough

↓⍤2⊢group sort p0 ⍝ reshape

┌→────────────────────────────────────────────┐ ↓ ┌→──────────────────┐ ┌→──────────────────┐ │ │ │1 1 1 0 1 0 1 1 1 1│ │0 1 1 1 0 1 1 0 1 1│ │ │ └~──────────────────┘ └~──────────────────┘ │ │ ┌→──────────────────┐ ┌→──────────────────┐ │ │ │1 1 0 1 0 0 0 1 1 1│ │0 1 0 1 1 1 1 0 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ │ │ ┌→──────────────────┐ ┌→──────────────────┐ │ │ │1 0 0 1 0 1 0 1 0 1│ │0 0 1 1 1 0 1 1 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ │ │ ┌→──────────────────┐ ┌→──────────────────┐ │ │ │1 1 1 0 1 0 0 0 0 0│ │1 0 0 1 1 0 1 0 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ │ │ ┌→──────────────────┐ ┌→──────────────────┐ │ │ │1 0 0 0 1 0 0 0 1 0│ │0 0 0 1 0 1 1 0 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ │ └∊────────────────────────────────────────────┘

,/↓⍤2⊢group sort p0 ⍝ ravel each pair of parents together

┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→──────────────────────────────────────┐ ┌→──────────────────────────────────────┐ ┌→──────────────────────────────────────┐ ┌→──────────────────────────────────────┐ ┌→──────────────────────────────────────┐ │ │ │1 1 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1│ │1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 0│ │1 0 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0│ │1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0│ │1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0│ │ │ └~──────────────────────────────────────┘ └~──────────────────────────────────────┘ └~──────────────────────────────────────┘ └~──────────────────────────────────────┘ └~──────────────────────────────────────┘ │ └∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

↑(?5⍴10) ,.(⊂2 10⍴⌽) ,/↓⍤2⊢group sort p0 ⍝ apply a different rotation to each pair of parents↑

┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ │ │ ↓1 1 0 1 0 1 1 1 1 0│ ↓1 1 0 1 0 1 1 1 1 0│ ↓1 0 0 1 1 1 0 1 1 0│ ↓0 1 0 0 0 0 0 1 0 0│ ↓1 0 0 0 1 0 0 0 0 1│ │ │ │1 1 1 0 1 1 0 1 1 1│ │0 0 1 1 0 1 0 0 0 1│ │0 1 0 0 1 0 1 0 1 0│ │1 1 0 1 0 0 0 1 1 1│ │0 1 1 0 0 0 1 0 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ │ └∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

↑⍪/⎕←↑(?5⍴10) ,.(⊂2 10⍴⌽) ,/↓⍤2⊢group sort p0 ⍝ reshape into a new population

┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────┐ │ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ ┌→──────────────────┐ │ │ ↓1 1 1 0 1 1 1 0 1 1│ ↓0 0 1 1 1 0 1 0 1 1│ ↓0 0 1 0 1 0 1 0 1 0│ ↓1 1 0 1 0 0 0 0 0 1│ ↓0 1 0 0 0 1 0 0 0 0│ │ │ │0 1 1 1 1 1 0 1 0 1│ │1 1 0 0 0 1 1 0 1 0│ │0 1 1 1 0 1 1 0 0 1│ │0 0 1 1 0 1 0 0 0 1│ │1 0 1 1 0 0 0 1 0 0│ │ │ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ └~──────────────────┘ │ └∊──────────────────────────────────────────────────────────────────────────────────────────────────────────────┘ ┌→──────────────────┐ ↓1 1 1 0 1 1 1 0 1 1│ │0 1 1 1 1 1 0 1 0 1│ │0 0 1 1 1 0 1 0 1 1│ │1 1 0 0 0 1 1 0 1 0│ │0 0 1 0 1 0 1 0 1 0│ │0 1 1 1 0 1 1 0 0 1│ │1 1 0 1 0 0 0 0 0 1│ │0 0 1 1 0 1 0 0 0 1│ │0 1 0 0 0 1 0 0 0 0│ │1 0 1 1 0 0 0 1 0 0│ └~──────────────────┘

crossover←{count len←⍺⋄↑⍪/↑(?count⍴len) ,.(⊂2 len⍴⌽) ,/↓⍤2⊢⍵}

(5 10) crossover group sort p0

┌→──────────────────┐ ↓0 1 1 1 0 1 1 0 1 1│ │1 1 1 0 1 0 1 1 1 1│ │1 0 0 0 1 1 1 0 1 0│ │1 1 1 1 0 0 0 1 1 0│ │1 0 0 1 1 1 0 1 1 0│ │0 1 0 0 1 0 1 0 1 0│ │0 1 0 0 0 0 0 1 0 0│ │1 1 0 1 0 0 0 1 1 1│ │0 0 0 1 0 0 0 1 0 0│ │0 0 1 0 1 1 0 0 0 1│ └~──────────────────┘

Repeat

APL make this easy we use ⍣ to specify function repetition

{(10 10) crossover group sort ⍵} ⍣ 100 ⊢ 1 -⍨ ?20 10 ⍴ 2

┌→──────────────────┐ ↓1 1 1 1 1 1 1 1 1 1│ │1 1 1 1 1 1 1 1 1 1│ │1 1 1 1 1 1 1 1 1 1│ │1 1 1 1 1 1 1 1 1 1│ │1 1 1 1 1 1 1 1 1 1│ │0 1 1 1 1 1 1 1 1 1│ │1 1 1 1 1 0 1 1 1 1│ │1 0 1 1 1 1 1 0 1 1│ │1 1 1 1 1 0 1 0 1 1│ │1 1 0 1 0 1 1 0 1 0│ │1 1 1 0 0 1 1 0 0 1│ │1 1 1 0 0 1 1 0 0 1│ │1 0 0 0 0 1 0 1 0 0│ │0 1 0 1 1 1 0 1 0 0│ │0 0 0 0 1 0 0 0 1 0│ │0 0 0 0 0 0 0 1 0 0│ │0 1 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0│ │0 0 0 0 0 0 0 0 0 0│ └~──────────────────┘