/* GAでTSP問題を解くときの超定番である、 「ルート表現から順序条件に変換するアルゴリズム」と 「順序表現からルート表現に変換するアルゴリズム (前記の逆変換)」に加えて、 「交叉:2つの遺伝子をランダムな位置で交叉させる」 「変異:遺伝子の中でランダムに2点を交換する」 「遺伝子を作る」をサブルーチンにしてみた件 */

Golangのサブルーチン化って、結構面倒くさい

■mainの後に記載しないと、文句言われる(VSCodeから)

/* GAでTSP問題を解くときの超定番である、 
「ルート表現から順序条件に変換するアルゴリズム」と 
「順序表現からルート表現に変換するアルゴリズム (前記の逆変換)」に加えて、
「交叉:2つの遺伝子をランダムな位置で交叉させる」
「変異:遺伝子の中でランダムに2点を交換する」
「遺伝子を作る」をサブルーチンにしてみた件 */

package main

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

func main() {

	rand.Seed(time.Now().UnixNano()) //シード変更可

	var sliceZ = [100][]int{} // 100固体

	for i := 0; i < 100; i++ {
		sliceZ[i] = getInitDNA()
		fmt.Printf("sliceZ[%v]: %v\n", i, sliceZ[i])
	}

	var sliceX = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	var sliceY = []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

	sliceX = mutatePath(sliceX)
	fmt.Printf("mutate sliceX: %v\n", sliceX)

	//var sliceZ = []int{} // 念のための初期化
	//var sliceW = []int{}

	fmt.Printf("old sliceX: %v\n", sliceX)
	fmt.Printf("old sliceX: %v\n", sliceY)

	sliceX, sliceY = crossPath(sliceX, sliceY)
	fmt.Printf("new sliceX: %v\n", sliceX)
	fmt.Printf("new sliceX: %v\n", sliceY)

	fmt.Printf("=======\n")

	// ルート表現から順序条件に変換するアルゴリズム

	var sliceA = []int{7, 8, 0, 4, 1, 6, 3, 9, 5, 2} // ルート表現
	//var sliceB = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	var sliceC = []int{} // 順序条件が入るところ

	fmt.Printf("sliceA: %v\n", sliceA)

	sliceC = encodePath(sliceA)

	fmt.Printf("sliceC: %v\n", sliceC)

	fmt.Printf("=======\n")

	sliceA = []int{} // sliceAのリセット
	sliceA = decodePath(sliceC)

	fmt.Printf("sliceA: %v\n", sliceA)
}

// 遺伝子を作る
func getInitDNA() []int {
	var sliceA = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	var sliceB = []int{}

	length := len(sliceA)

	// 参考: http://okwave.jp/qa/q7687312.html
	for i := 0; i < length; i++ {
		k := rand.Intn(len(sliceA))
		j := sliceA[k]
		sliceA = append(sliceA[:k], sliceA[k+1:]...) // k番目の要素を削除
		sliceB = append(sliceB, j)
	}

	return sliceB
}

// 変異:遺伝子の中でランダムに2点を交換する
func mutatePath(sliceA []int) []int {
	length := len(sliceA)

	pos1 := rand.Intn(length)
	pos2 := rand.Intn(length)

	tmp1 := sliceA[pos1]
	tmp2 := sliceA[pos2]

	sliceA[pos1] = tmp2
	sliceA[pos2] = tmp1

	return sliceA
}

// 交叉:2つの遺伝子をランダムな位置で交叉させる
func crossPath(sliceA []int, sliceB []int) ([]int, []int) {

	length := len(sliceA)

	pos := rand.Intn(length-1) + 1
	fmt.Printf("pos: %v\n", pos)

	sliceA1 := make([]int, length)
	copy(sliceA1, sliceA)
	sliceB1 := make([]int, length)
	copy(sliceB1, sliceB)
	var sliceC = append(sliceA1[:pos], sliceB1[pos:]...)

	sliceA2 := make([]int, length)
	copy(sliceA2, sliceA)
	sliceB2 := make([]int, length)
	copy(sliceB2, sliceB)
	var sliceD = append(sliceB2[:pos], sliceA2[pos:]...)

	return sliceC, sliceD
}

// パスを順序表現から戻す
func decodePath(sliceC []int) []int {

	var sliceB = []int{}

	// スライスBを作る 抜き出すための数値列 0,1,2,3,4,
	for i := 0; i < len(sliceC); i++ {
		sliceB = append(sliceB, i)
	}

	var sliceA = []int{} // 今からルート表現を入れるところ

	for i := 0; i < len(sliceC); i++ {
		k := sliceC[i]
		j := sliceB[k]

		sliceA = append(sliceA, j)
		sliceB = append(sliceB[:k], sliceB[k+1:]...) // k番目の要素を削除

	}

	return sliceA
}

// パスを順序表現に符号化する
func encodePath(sliceA []int) []int {
	var sliceB = []int{} // 抜き出すための数値列 0,1,2,3,4,
	var sliceC = []int{} // 順序条件が入るところ

	// スライスBを作る
	for i := 0; i < len(sliceA); i++ {
		sliceB = append(sliceB, i)
	}

	// ルート表現から順列表現に変換
	for i := 0; i < len(sliceA); i++ {
		for k := 0; k < len(sliceB); k++ {
			if sliceA[i] == sliceB[k] {

				sliceC = append(sliceC, k)
				sliceB = append(sliceB[:k], sliceB[k+1:]...) // k番目の要素を削除

				break
			}
		}

	}
	return sliceC
}

その他golangに関してVSCodeから文句を言われる項目としては、

■変数に"_"使うと怒られる

■記載方法にケチをつけられる

func subroutine()

{

...

}

と記載すると怒られる。

func subroutine(){

...

}

としなければならない

 

2021/02,江端さんの技術メモ

Posted by ebata