discard """
遺伝的アルゴリズムで OneMax問題 を解く

2018/06/23

(c) 2018 kapifuji
"""

import random, system, algorithm, sequtils
# random を使用する際、これがないと毎回同じ値が生成される
randomize()

# ランダムな遺伝子を得る
proc getRandomGenom(length: uint): seq[int8] =
  var genom: seq[int8] = @[]

  for i in 1..length:
    genom.add(random.rand(1).toU8)

  result = genom

# 遺伝子を評価する
proc evaluateGenom(genom: seq[int8]): float =
  var sum = 0

  for i, value in genom:
    sum += value

  result = sum / genom.len

# 親となる遺伝子を選択する
proc selectGenom(genomList: seq[seq[int8]], length: uint): seq[seq[int8]] =
  var selectedGenomList = genomList

  selectedGenomList.sort(proc (x, y: seq[int8]): int = system.cmp(y.evaluateGenom, x.evaluateGenom))

  result = selectedGenomList[0..(length - 1)]

# 遺伝子を交叉させる
proc crossoverGenom(genom1, genom2: seq[int8]): tuple[first: seq[int8], second: seq[int8]]=
  var
    first: seq[int8] = genom1
    second: seq[int8] = genom2
  let
    point1 = random.rand(genom1.high)
    point2 = random.rand(point1..genom1.high)

  sequtils.delete(first, point1, point2)
  sequtils.delete(second, point1, point2)
  sequtils.insert(first, genom2[point1..point2], point1)
  sequtils.insert(second, genom1[point1..point2], point1)

  result = (first, second)

# 次世代の遺伝子リストを得る（現行の遺伝子リストから低評価遺伝子を子孫と入れ替える）
proc getNextGenomList(genomList, progenyGenomList: seq[seq[int8]]): seq[seq[int8]] =
  var nextGenomList: seq[seq[int8]] = genomList

  nextGenomList.sort(proc (x, y: seq[int8]): int = system.cmp(x.evaluateGenom, y.evaluateGenom))
  sequtils.delete(nextGenomList, 0, progenyGenomList.high)
  nextGenomList.add(progenyGenomList)

  result = nextGenomList

# 突然変異を適用
proc mutateGenom(genom: seq[int8], individualMutation, genomMutation: float): seq[int8] =
  var mutatedGenom: seq[int8] = genom

  if individualMutation > random.rand(100.0):
    for i, value in mutatedGenom:
      if genomMutation > random.rand(100.0):
        mutatedGenom[i] = random.rand(1).toU8

  result = mutatedGenom

# 始めの遺伝子リストを作る
proc getInitialGenom(genomLength, genomListLength: uint): seq[seq[int8]] =
  var genomList: seq[seq[int8]] = @[]

  for i in 1..genomListLength:
    genomList.add(getRandomGenom(genomLength))

  result = genomList

# 子孫となる遺伝子のリストを得る
proc getProgenyGenom(selectedGenomList: seq[seq[int8]]): seq[seq[int8]] =
  var progenyGenomList: seq[seq[int8]] = @[]

  for i in 0..selectedGenomList.high:
    let
      first = selectedGenomList[i]
      second =
        if i == selectedGenomList.high: selectedGenomList[0]
        else: selectedGenomList[i + 1]
      progenyGenoms = crossoverGenom(first, second)

    progenyGenomList.add(progenyGenoms.first)
    progenyGenomList.add(progenyGenoms.second)

  result = progenyGenomList

# 突然変異を適用した遺伝子リストを得る
proc getMutateGenomList(genomList: seq[seq[int8]], individualMutation, genomMutation: float): seq[seq[int8]] =
  var mutatedGenomList = genomList

  for i, genom in mutatedGenomList:
    mutatedGenomList[i] = genom.mutateGenom(individualMutation, genomMutation)

  result = mutatedGenomList

# 遺伝子の評価値リストを得る
proc getEvaluationList(genomList: seq[seq[int8]]): seq[float] =
  var evaluationList: seq[float] = @[]

  for i, genom in genomList:
    evaluationList.add(genom.evaluateGenom)

  result = evaluationList

# 結果の表示
proc viewResult(genomList: seq[seq[int8]], generation: uint) =
  var
    sortedGenomList = genomList
    sum = 0.0

  let
    evaluations = genomList.getEvaluationList
    minEvaluation = evaluations.min
    maxEvaluation = evaluations.max

  sortedGenomList.sort(proc (x, y: seq[int8]): int = system.cmp(y.evaluateGenom, x.evaluateGenom))
  for j, value in evaluations:
    sum += value

  let averageEvaluation = sum / evaluations.len.toFloat

  echo ">>>  generation " & $generation & "  <<<"
  echo "min: " & $minEvaluation
  echo "max: " & $maxEvaluation
  echo "avg: " & $averageEvaluation
  echo "optimumGenom -> " & $sortedGenomList[0] & "\n"

proc main =
  const
    # 遺伝子の長さ
    GenomLength = 100
    # 個体の数
    GenomListLength = 100
    # 親となる個体の数（子孫はこの2倍生成される）
    SelectGenomLength = 20
    # 個体の突然変異確率 [%]
    IndividualMutation = 1
    # 遺伝子の1要素の突然変異確率 [%]
    GenomMutation = 1
    # 世代数
    Generation = 100

  # 初期の遺伝子
  var genomList = getInitialGenom(GenomLength, GenomListLength)

  for i in 1..Generation:
    # 結果の出力
    viewResult(genomList, i.uint)

    # 選択、交叉と変異、世代交代
    let
      selectedGenomList = genomList.selectGenom(SelectGenomLength)
      progenyGenomList = selectedGenomList.getProgenyGenom.getMutateGenomList(IndividualMutation, GenomMutation)
      nextGenomList = getNextGenomList(genomList, progenyGenomList)

    # 次の世代へ
    genomList = nextGenomList

when isMainModule:
  main()