Genetic Algorithm

Array programming
1

Just getting a better feel for APL. This is a basic implementation of the hello world of genetic algorithms - one max.

Starting with an initial population. Each member is a list containing ones and zeros.

Initial setup

]box on -style=max
]rows on
⎕io←0

The task basically breaks down into

  1. Generate initial population
      ⎕←p0←?10 10 ⍴ 2
┌→──────────────────┐
↓1 1 0 1 0 0 0 1 0 0│
│0 0 1 1 0 0 0 0 0 1│
│0 0 1 1 0 0 0 0 1 0│
│1 0 1 0 0 1 0 0 0 1│
│0 1 0 1 1 0 0 1 0 0│
│0 0 1 1 1 1 1 1 0 0│
│0 1 1 0 1 1 0 1 1 0│
│1 0 0 0 0 0 1 0 1 1│
│0 1 1 1 1 0 1 1 0 1│
│0 1 1 0 0 0 0 0 1 1│
└~──────────────────┘

p0 is the initial population.

  1. Sort the population by fitness
      sort←{⍵⌷⍨⊂⍒+/[1]⍵}
      sort p0
┌→──────────────────┐
↓0 1 1 1 1 0 1 1 0 1│
│0 0 1 1 1 1 1 1 0 0│
│0 1 1 0 1 1 0 1 1 0│
│1 1 0 1 0 0 0 1 0 0│
│1 0 1 0 0 1 0 0 0 1│
│0 1 0 1 1 0 0 1 0 0│
│1 0 0 0 0 0 1 0 1 1│
│0 1 1 0 0 0 0 0 1 1│
│0 0 1 1 0 0 0 0 0 1│
│0 0 1 1 0 0 0 0 1 0│
└~──────────────────┘
  1. Group into parents
     group←{↓{⍵}⌺(⍪2 2)⊢⍵}

     group sort p0

┌→────────────────────────────────────────────┐
↓ ┌→──────────────────┐ ┌→──────────────────┐ │
│ │0 1 1 1 1 0 1 1 0 1│ │0 0 1 1 1 1 1 1 0 0│ │
│ └~──────────────────┘ └~──────────────────┘ │
│ ┌→──────────────────┐ ┌→──────────────────┐ │
│ │0 1 1 0 1 1 0 1 1 0│ │1 1 0 1 0 0 0 1 0 0│ │
│ └~──────────────────┘ └~──────────────────┘ │
│ ┌→──────────────────┐ ┌→──────────────────┐ │
│ │1 0 1 0 0 1 0 0 0 1│ │0 1 0 1 1 0 0 1 0 0│ │
│ └~──────────────────┘ └~──────────────────┘ │
│ ┌→──────────────────┐ ┌→──────────────────┐ │
│ │1 0 0 0 0 0 1 0 1 1│ │0 1 1 0 0 0 0 0 1 1│ │
│ └~──────────────────┘ └~──────────────────┘ │
│ ┌→──────────────────┐ ┌→──────────────────┐ │
│ │0 0 1 1 0 0 0 0 0 1│ │0 0 1 1 0 0 0 0 1 0│ │
│ └~──────────────────┘ └~──────────────────┘ │
└∊────────────────────────────────────────────┘
  1. Mutate into children
    split←{⍵⊆⍨1+⍺<⍳⍴⍵}
    {c l←⍴⍵⋄↑⊃,/{(l-1) split ⊃,/(⊂0 3 2 1)⌷⍵}¨,/↑⊃(?(l-1)⍴⍨c÷2) ,.{⊂⍺split¨⍵} ↓group sort ⍵ } p0
┌→──────────────────┐
↓0 1 1 1 1 0 1 1 0 0│
│0 0 1 1 1 1 1 1 0 1│
│0 1 1 0 1 0 0 1 0 0│
│1 1 0 1 0 1 0 1 1 0│
│1 0 0 1 1 0 0 1 0 0│
│0 1 1 0 0 1 0 0 0 1│
│1 1 1 0 0 0 0 0 1 1│
│0 0 0 0 0 0 1 0 1 1│
│0 0 1 1 0 0 0 0 1 0│
│0 0 1 1 0 0 0 0 0 1│
└~──────────────────┘

Pondering how best to simplify this step.

  1. Goto 2
({c l←⍴⍵⋄sort ↑⊃,/{(l-1) split ⊃,/(⊂0 3 2 1)⌷⍵}¨,/↑⊃(?(l-1)⍴⍨c÷2) ,.{⊂⍺split¨⍵} ↓group ⍵ }⍣100)sort p0

┌→──────────────────┐
↓1 1 1 1 1 1 1 1 1 1│
│0 1 1 1 1 1 1 1 1 1│
│0 1 1 1 0 1 1 1 1 1│
│1 1 1 1 1 0 0 0 1 1│
│0 1 1 1 1 0 0 1 0 1│
│1 0 1 1 0 0 0 0 0 0│
│0 0 1 0 0 0 0 0 0 0│
│0 0 0 0 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│
└~──────────────────┘

Got some experiments to run. I feel like there should be a cleaner way to create the children.

4 Likes
2

Improved the crossover bit, still think there is a better way. Im going to rethink the whole approach ive been using.

      sort
{⍵⌷⍨⊂⍒+/[1]⍵}
      group
{⍪{⊂↓⍵}⌺(⍪2 2)⊢⍵}
      split
{⍵⊆⍨1+⍺<⍳⍴⍵}
      crossover
{↑⊃(?(⊃⍴⍵)⍴(1-⍨⊃⍴⊃⊃⍵)),.{a b←⍵ ⋄ ,/2 2⍴(⊂0 3 2 1)⌷(⍺ split a),(⍺ split b)}⍵}
      ({sort crossover group ⍵}⍣100) sort p0
┌→──────────────────┐
↓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│
│0 1 1 1 1 0 1 0 0 1│
│0 1 1 1 0 0 0 0 1 0│
│0 0 1 1 0 0 0 1 0 1│
│0 0 1 0 0 0 0 0 0 0│
│0 0 0 0 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│
└~──────────────────┘
2 Likes