README.md

遺伝的アルゴリズムでナップサック問題

ナップサック問題

遺伝子型の設計

アイテムをナップサックに入れるかどうか各ビットの値で指定する。
例えば、アイテム1を入れる場合は 1 ビット目が立つ。

遺伝子 1 本は 32 ビットで表される。

評価関数

ナップサックに入れたアイテムの価値の総和を適応度とする。 ただし、ナップサックに入りきらない場合は、適応度 1 とする。

個体数

2048 体とする。

選択

エリート保存選択とルーレット選択を採用する。
計 128 体選択する。

交叉

ランダムに生成するマスクを利用して行う一様交叉を採用する。

突然変異

1% の確率で、ランダムに選択した 1 ビットを反転する。

これを 64 世代繰り返す。

fool.coffee

###
単純比較計算
###

knapsack = require "./knapsack.json"
item_size = knapsack.items.length

masks = []
mask = 2 ** (item_size - 1)
while mask >= 1
  masks.push mask
  mask /= 2

value_max = 0

st_time = Date.now()

for x in [0...2 ** item_size]
  weight = 0
  value = 0
  for mask, i in masks
    if x & mask
      ks = knapsack.items[i]
      weight += ks.weight
      value += ks.value
      break if weight > knapsack.capacity
  if weight <= knapsack.capacity && value > value_max
    value_max = value
    console.log x, value

ed_time = Date.now()
console.log ed_time - st_time + "ms"

GA.coffee

###
GeneticAlgorithm Class
###

Gene = require "./Gene"

class GA
  # 個体数, 評価関数
  constructor: (@population, @gene_size) ->
    @genes = (new Gene(null, @gene_size) for x in [0...population])

  # 評価
  measure: (measure) ->
    gene.value = measure gene for gene in @genes
    # 適応度降順ソート
    @genes.sort (a, b) ->
      b.value - a.value

    return @

  # 選択
  select: (type, elite, selection) ->
    selected = []

    if elite
      selected.push @genes.shift()

    switch type
      when "roulette"
        # 適応度の総和
        value_sum = @genes.reduce (a, b) ->
          (a.value or a) + b.value
        # 選択
        while 1
          for gene, i in @genes
            break unless gene
            if Math.floor(Math.random() * value_sum) < gene.value
              selected.push gene
              @genes.splice i, 1
              if selected.length is selection
                @genes = selected
                return @

  # 交叉
  cross: ->
    size = @genes.length
    count = @population / size / 2

    # シャッフル
    for gene, i in @genes
      index = ~~(Math.random() * size)
      continue if index is i
      temp = @genes[index]
      @genes[index] = @genes[i]
      @genes[i] = temp

    # 交叉
    genes = []
    @genes = for gene, i in @genes
      for x in [0...count]
        Array::push.apply genes, gene.cross @genes[(i * count + x) % size]
    @genes = genes

    return @

  # 突然変異
  mutate: (rate, size) ->
    @genes = for gene in @genes
      if Math.random() < rate
        gene.mutate(size)
      else
        gene

    return @

module.exports = GA

Gene.coffee

###
Gene Class
###

class Gene
  constructor: (init, @size) ->
    @size = 32 unless @size

    if typeof init is "number"
      @gene = init
    else if typeof init is "string"
      @gene = parseInt init, 2
      @size = init.length
    else
      @gene = ~~(Math.random() * 2 ** @size)

  # ビット反転
  invert: ->
    gene = 2 ** @size + ~ @gene
    new Gene gene, @size

  # ビット列の二進表示 25 -> 00011001
  display: ->
    gene = @gene
    gene += 2 ** 31 * 2 if @gene < 0
    (new Array(@size).join(0) + gene.toString(2)).slice(- @size)

  # 交叉
  cross: (gene, mask) ->
    gene = new Gene(gene, @size) unless gene instanceof Gene
    gene = gene.gene

    mask = ~~(Math.random() * 2 ** @size) unless mask
    mask = new Gene mask, @size
    mask =
      a: mask.gene
      b: mask.invert().gene

    [
      new Gene @gene & mask.a | gene & mask.b, @size
      new Gene @gene & mask.b | gene & mask.a, @size
    ]

  # 突然変異
  mutate: (size) ->
    throw new RangeError "size is over the range" if size > @size
    
    indexes = [0...@size]
    for x, i in indexes
      index = ~~ (Math.random() * @size)
      continue if index is i
      indexes[i] ^= indexes[index]
      indexes[index] ^= indexes[i]
      indexes[i] ^= indexes[index]
    indexes = indexes.slice 0, size

    gene = (Number(x) for x in @display().split "")
    for x in indexes
      gene[x] ^= 1

    new Gene gene.join ""

module.exports = Gene

knapsack.coffee

###
knapsack.json 生成スクリプト
###

random = (size) ->
  ~~ (Math.random() * size)

list = (x for x in [2..52] by 2)
list = (list[random 25] for x in [0...32])

knapsack =
  capacity: 300
  items: ((
    weight: x
    value: random 100
  ) for x in list)

console.log JSON.stringify knapsack, null, "  "

knapsack.json

{
  "capacity": 300,
  "items": [
    {
      "weight": 48,
      "value": 20
    },
    {
      "weight": 4,
      "value": 47
    },
    {
      "weight": 4,
      "value": 66
    },
    {
      "weight": 40,
      "value": 15
    },
    {
      "weight": 42,
      "value": 88
    },
    {
      "weight": 32,
      "value": 33
    },
    {
      "weight": 40,
      "value": 38
    },
    {
      "weight": 26,
      "value": 39
    },
    {
      "weight": 4,
      "value": 52
    },
    {
      "weight": 10,
      "value": 51
    },
    {
      "weight": 34,
      "value": 5
    },
    {
      "weight": 50,
      "value": 21
    },
    {
      "weight": 16,
      "value": 33
    },
    {
      "weight": 34,
      "value": 24
    },
    {
      "weight": 32,
      "value": 1
    },
    {
      "weight": 16,
      "value": 73
    },
    {
      "weight": 38,
      "value": 37
    },
    {
      "weight": 16,
      "value": 98
    },
    {
      "weight": 2,
      "value": 82
    },
    {
      "weight": 48,
      "value": 31
    },
    {
      "weight": 20,
      "value": 84
    },
    {
      "weight": 36,
      "value": 62
    },
    {
      "weight": 10,
      "value": 70
    },
    {
      "weight": 18,
      "value": 83
    },
    {
      "weight": 18,
      "value": 87
    },
    {
      "weight": 6,
      "value": 67
    },
    {
      "weight": 36,
      "value": 69
    },
    {
      "weight": 8,
      "value": 84
    },
    {
      "weight": 40,
      "value": 29
    },
    {
      "weight": 18,
      "value": 35
    },
    {
      "weight": 40,
      "value": 92
    },
    {
      "weight": 40,
      "value": 5
    }
  ]
}

main.coffee

###
遺伝的アルゴリズムでナップサック問題 
###

GA = require "./GA"
knapsack = require "./knapsack.json"

# 個体数
population = 2048
# 選択数
selection = 128
# 世代数
generation = 64
# 突然変異率
mutation_rate = 0.01
# 突然変異で反転するビット数
mutation_size = 1

# 評価関数
measure = (gene) ->
  gene = (Number(x) for x in gene.display().split(""))
  weight = value = 0
  for item, i in knapsack.items
    continue unless gene[i]
    weight += item.weight
    value += item.value
  value = 1 if weight > knapsack.capacity

  return value

# main
(->
  st_time = Date.now()

  ga = new GA population, 32
  
  for x in [0...generation]
    ga.measure(measure)
    
    elite = ga.genes[0]

    ga.select "roulette", true, selection
    ga.cross()
      .mutate mutation_rate, mutation_size

    console.log elite.display(), elite.value

  ed_time = Date.now()

  console.log ed_time - st_time + "ms"
)()