Evoluční algoritmus

genetics.coffee

#======================================================================#
# Biologicke algoritmy (2) - Evoluční algoritmy                        #
# http://www.root.cz/clanky/biologicke-algoritmy-2-evolucni-algoritmy/ #
#======================================================================#
#
# hledame kruznice, ktere nejvic sedi na danou mnozinu bodu
#
# ----------------------------------------------------------
#
# jedinec = trojice kruznic
#         = vektor o 9 hodnotach
#
#         [ x1, y1, r1,
#           x2, y2, r2, 
#           x3, y3, r3  ]
#
# http://i.iinfo.cz/images/26/evolucni-algoritmy-2-2.png

# hodnoty
bodyX = [127, 41, 54, 76, 82, 125, 30, 128, 68, 34, 29, 95, 30, 34, 128, 93, 45, 29, 105, 40, 39, 106, 55, 120, 117, 129, 128, 92, 125, 125, 69, 117, 32, 125, 91, 116, 108, 127, 58, 88, 119, 51, 123, 126, 100, 60, 29, 37, 121, 45, 77, 96, 30, 119, 111, 30, 112, 129, 109, 108, 84, 130, 54, 127, 65, 47, 30, 79, 121, 92, 101, 92, 111, 45, 129, 128, 107, 52, 116, 54, 84, 109, 108, 48, 39, 42, 48, 117, 44, 31, 29, 128, 33, 86, 129, 110, 118, 101, 129, 63, 69, 82, 88, 80, 133, 129, 103, 70, 121, 129, 70, 92, 78, 118, 133, 115, 97, 89, 122, 134, 86, 119, 71, 93, 125, 135, 107, 75, 127, 79, 135, 108, 70, 68, 103, 73, 70, 83, 95, 135, 100, 73, 134, 125, 77, 72, 93, 122, 133, 131, 88, 121, 120, 136, 71, 77, 131, 95, 119, 130, 95, 111, 75, 96, 135, 136, 115, 113, 76, 79, 129, 133, 74, 120, 123, 87, 126, 82, 135, 74, 119, 81, 131, 125, 76, 124, 132, 71, 92, 122, 136, 132, 129, 120, 113, 136, 136, 70, 69, 99, 31, 82, 153, 125, 23, 47, 131, 75, 25, 149, 20, 21, 20, 156, 27, 60, 45, 32, 141, 78, 26, 123, 47, 104, 157, 77, 148, 21, 139, 32, 65, 88, 37, 30, 127, 27, 35, 149, 134, 113, 98, 51, 127, 143, 84, 46, 106, 21, 106, 156, 137, 130, 156, 21, 116, 64, 25, 65, 126, 26, 27, 89, 122, 21, 84, 122, 19, 39, 157, 29, 139, 80, 142, 140, 143, 64, 22, 152, 158, 74, 151, 156, 119, 152, 82, 24, 20, 138, 49, 134, 47, 122, 27, 128, 151, 114, 135, 35, 120, 96];
bodyY = [89, 67, 141, 50, 149, 81, 92, 110, 149, 120, 104, 146, 89, 77, 90, 148, 63, 105, 142, 69, 69, 58, 144, 72, 66, 103, 107, 51, 80, 78, 50, 131, 85, 119, 149, 133, 59, 114, 54, 50, 128, 140, 123, 119, 145, 146, 97, 73, 127, 63, 51, 51, 105, 131, 138, 88, 61, 97, 59, 137, 150, 95, 57, 87, 54, 62, 92, 150, 128, 148, 54, 51, 138, 135, 109, 92, 141, 142, 134, 142, 50, 60, 58, 61, 128, 133, 62, 67, 134, 84, 97, 110, 119, 148, 93, 61, 69, 55, 94, 52, 65, 35, 31, 87, 74, 81, 95, 52, 90, 83, 72, 29, 38, 32, 48, 93, 95, 92, 88, 51, 32, 91, 50, 30, 87, 59, 95, 82, 85, 39, 60, 29, 55, 59, 28, 45, 70, 34, 29, 58, 27, 45, 53, 38, 84, 47, 95, 89, 76, 45, 92, 89, 33, 57, 51, 39, 43, 94, 89, 80, 29, 93, 42, 95, 60, 62, 31, 94, 83, 87, 41, 75, 42, 89, 89, 32, 38, 35, 68, 43, 90, 88, 79, 36, 83, 87, 46, 77, 30, 35, 61, 46, 81, 90, 94, 65, 60, 50, 61, 28, 39, 146, 54, 136, 59, 131, 24, 10, 106, 46, 64, 59, 88, 66, 49, 16, 130, 39, 122, 145, 47, 136, 134, 144, 68, 144, 112, 75, 30, 38, 143, 145, 121, 42, 133, 107, 35, 46, 26, 12, 145, 135, 133, 38, 146, 130, 143, 68, 13, 86, 30, 132, 85, 72, 16, 14, 103, 13, 22, 104, 50, 9, 137, 84, 9, 138, 77, 125, 75, 44, 34, 146, 34, 123, 36, 142, 91, 53, 74, 11, 51, 91, 138, 50, 145, 52, 86, 30, 133, 28, 131, 16, 47, 22, 105, 141, 28, 119, 17, 10];

# konstanty
P_ZKRIZENI     = 0.70 # vetsinou 0.7 az 1.0
P_MUTACE       = 0.05
VEL_POPULACE   = 80
POCET_GENERACI = 500  # doba hledani reseni

BARVA_ORIG = "#000"
BARVA_POP  = "rgba(221,221,221,0.3)" # "#DDD"
BARVA_NEJ  = "#F00"

# napojeni na canvas
canvas = $("#canvas")[0]
ctx = canvas.getContext '2d'

# canvas helpery
circle = (x,y,r) ->
  ctx.beginPath()
  ctx.arc(x,y,r,0,Math.PI*2,true)
  ctx.closePath()
  ctx.stroke()

point = (x,y) ->
  circle(x,y,1)

vykresli = ->

  # resetujeme canvas
  canvas.width = canvas.width

  # vykreslime vsechny populace krome prvni
  ctx.strokeStyle = BARVA_POP
  for i in [1...VEL_POPULACE]
    circle populace[i][0], populace[i][1], populace[i][2]
    circle populace[i][3], populace[i][4], populace[i][5]
    circle populace[i][6], populace[i][7], populace[i][8]

  # prvni je nejlepsi
  ctx.strokeStyle = BARVA_NEJ
  circle populace[0][0], populace[0][1], populace[0][2]
  circle populace[0][3], populace[0][4], populace[0][5]
  circle populace[0][6], populace[0][7], populace[0][8]

  # vykreslime puvodni body
  ctx.strokeStyle = BARVA_ORIG
  for i in [0...bodyX.length]
    point bodyX[i], bodyY[i]

# --------------------------------

populace = (100 * Math.random() for i in [0...9] for j in [0...VEL_POPULACE])

# --------------------------------

fitness = (jedinec) ->

  # bodove ohodnoceni
  # maximum: 300
  #
  # hledame cim jak nejmensi vzdalenosti od orig. bodu
  # sigme a normalnimu rozdeleni opravdu nerozumim :)

  kvalita = 0
  sigma = 15

  for i in [0...bodyX.length]
    dx = bodyX[i] - jedinec[0]
    dy = bodyY[i] - jedinec[1]
    d1 = Math.abs(Math.sqrt(dx*dx + dy*dy) - jedinec[2])

    dx = bodyX[i] - jedinec[3]
    dy = bodyY[i] - jedinec[4]
    d2 = Math.abs(Math.sqrt(dx*dx + dy*dy) - jedinec[5])

    dx = bodyX[i] - jedinec[6]
    dy = bodyY[i] - jedinec[7]
    d3 = Math.abs(Math.sqrt(dx*dx + dy*dy) - jedinec[8])

    x = Math.min(Math.min(d1,d2),d3)
    kvalita += Math.exp(-(x*x)/(2.0*sigma*sigma))

  return kvalita

# --------------------------------

vyberJedince = (poleF, soucetF) ->

  # Roulette selection
  #
  # vybereme si nejaky bod (cislo < soucetF)
  # postupne scitame fitness a kdo je nejbliz, toho vyberem
  # 
  # http://en.wikipedia.org/wiki/Fitness_proportionate_selection
  # http://stackoverflow.com/questions/177271/roulette-selection-in-genetic-algorithms

  soucet = 0
  vybranyBod = Math.random() * soucetF

  for i in [0...VEL_POPULACE]
    soucet += poleF[i]
    if soucet > vybranyBod then return i

# --------------------------------

poleF = (0 for i in [0...VEL_POPULACE])

# jako funkce + setTimeout udelano proto, aby canvas vykresloval
# pri kazdem projeti cyklem a ne jen az to vse skonci
#
# window, aby to slo zavolat pres setTimeout
window.udelejGen = (iGen) ->

  minF = Number.MAX_VALUE
  maxF = 0
  maxF_i = 0
  novaPop = (0 for i in [0...9] for j in [0...VEL_POPULACE])

  for i in [0...VEL_POPULACE]

    poleF[i] = fitness(populace[i])

    # nasli jsme nove maximum?
    if poleF[i] > maxF
      maxF = poleF[i]
      maxF_i = i

    # nasli jsme nove minimum?
    if poleF[i] < minF
      minF = poleF[i]

  # znormalizujeme a spocteme sumu
  soucetF = 0
  for i in [0...VEL_POPULACE]
    poleF[i] -= minF
    soucetF += poleF[i]

  # michame...
  for jedinec in [0...VEL_POPULACE] by 2
    jedinec_i_1 = vyberJedince(poleF, soucetF)
    jedinec_i_2 = vyberJedince(poleF, soucetF)

    # krizime
    if Math.random() < P_ZKRIZENI

      for i in [0...9]

        if Math.random() < 0.5
          # prohodime tam
          novaPop[jedinec    ][i] = populace[jedinec_i_1][i]
          novaPop[jedinec + 1][i] = populace[jedinec_i_2][i]
        else
          # nebo naopak
          novaPop[jedinec    ][i] = populace[jedinec_i_2][i]
          novaPop[jedinec + 1][i] = populace[jedinec_i_1][i]

        # mutace
        for potomek in [0,1]
          for i in [0...9]
            if Math.random() < P_MUTACE

              # netusim co to je za vzorec :)
              randomValue = 8.0 *
                            Math.sqrt(-2 * Math.log(Math.random())) *
                            Math.sin(2 * Math.PI * Math.random())

              # zmutujeme
              novaPop[jedinec + potomek][i] += randomValue

              # neprekrocil mantinely?
              if novaPop[jedinec + potomek][i] < 0
                novaPop[jedinec + potomek][i] = 0

              else if novaPop[jedinec + potomek][i] > 100
                novaPop[jedinec + potomek][i] = 100

    else # nekrizime, jedinec zustava stejny
      for i in [0...9]
        novaPop[jedinec    ][i] = populace[jedinec_i_1][i]
        novaPop[jedinec + 1][i] = populace[jedinec_i_2][i]

  # nejlepsi -> na zacatek pole
  for i in [0...9]
    novaPop[0][i] = populace[maxF_i][i]

  populace = novaPop

  # jako funkce + setTimeout udelano proto, aby canvas vykresloval
  # pri kazdem projeti cyklem a ne jen az to vse skonci
  vykresli()

  if iGen < POCET_GENERACI # if maxF < 299
    iGen += 1
    setTimeout("udelejGen(" + iGen + ")",0)
  else
    console.log "Konec! Dosazene fitness: " + maxF

# spustime
udelejGen(0)

index.htm

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>Biologické algoritmy (2)</title>    
        
        <script type="text/javascript" src="http://code.jquery.com/jquery-latest.min.js"></script>
        <script type="text/javascript" src="http://jashkenas.github.com/coffee-script/extras/coffee-script.js"></script>
        
        <script type="text/coffeescript" src="./genetics.coffee"> </script>
    </head>
    <body>

      <noscript>Potřebuji prohlížeč s JavaScriptem!</noscript>

      <canvas id="canvas" width="300" height="200" style="border: 1px solid #333;">
        Potřebuji prohlížeč s Canvasem!
      </canvas>

    </body>
</html>