# Genetic Algorithm

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

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