遺伝的アルゴリズム

ga.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
)

const (
	// 淘汰率, 交差率, 突然変異率
	selectionRate, crossRate, mutateRate = 0.2, 0.2, 0.05
)

// Gene : 遺伝子情報
type Gene struct {
	gene  []int // 遺伝子配列
	nOnes int   // ターゲットの数
}

func main() {
	// 遺伝子長, 集団の大きさ
	nGene, nIndividual := 50, 100
	population := createPopulation(nGene, nIndividual)
	for i := 0; ; i++ {
		population = changeGeneration(population)
		sortGenes(population)
		fmt.Println(population[0].gene, population[0].nOnes)
		if population[0].nOnes == nGene {
			fmt.Println(i+1, "世代")
			break
		}
	}
}

func changeGeneration(gs []Gene) []Gene {
	var nextGeneration []Gene
	sortGenes(gs)

	// 選択, 淘汰
	elites := gs[:int((1-selectionRate)*float64(len(gs)))]
	for {
		pos := rand.Intn(len(elites))
		switch n := rand.Float64(); {
		case n < mutateRate:
			// 突然変異
			nextGeneration = append(nextGeneration, mutate(elites[pos]))
		case n > 1-crossRate:
			// 交差
			nextGeneration = append(nextGeneration, crossing(elites[pos], elites[rand.Intn(len(elites))]))
		default:
			// コピー
			nextGeneration = append(nextGeneration, elites[pos])
		}
		if len(nextGeneration) == len(gs) {
			break
		}
	}
	return nextGeneration
}

func createPopulation(nGene, nIndividual int) []Gene {
	var population []Gene
	for i := 0; i < nIndividual; i++ {
		gene := make([]int, nGene)
		for j := 0; j < nGene; j++ {
			gene[j] = rand.Intn(2)
		}
		population = append(population, Gene{gene: gene, nOnes: countOnes(gene)})
	}
	return population
}

func countOnes(gene []int) int {
	var ans int
	for i := 0; i < len(gene); i++ {
		ans += gene[i]
	}
	return ans
}

// 破壊的ソート
func sortGenes(gs []Gene) {
	sort.SliceStable(gs, func(i, j int) bool {
		return gs[i].nOnes > gs[j].nOnes
	})
}

func mutate(g Gene) Gene {
	position := rand.Intn(len(g.gene))
	if g.gene[position] == 0 {
		g.gene[position] = 1
	} else {
		g.gene[position] = 0
	}
	g.nOnes = countOnes(g.gene)
	return g
}

func crossing(parent1, parent2 Gene) Gene {
	var child1 []int
	// 二点交差
	splitR := rand.Intn(len(parent1.gene)-1) + 1
	splitL := rand.Intn(splitR)

	child1 = append(child1, parent1.gene[:splitL]...)
	child1 = append(child1, parent2.gene[splitL:splitR]...)
	child1 = append(child1, parent1.gene[splitR:]...)

	return Gene{gene: child1, nOnes: countOnes(child1)}
}