8000 完成遗传算法示例 · mohuishou/go-algorithm@79e9994 · GitHub
[go: up one dir, main page]
Skip to content

Commit 79e9994

Browse files
mohuishoumohuishou
committed
完成遗传算法示例
1 parent 6198788 commit 79e9994

File tree

3 files changed

+128
-9
lines changed

3 files changed

+128
-9
lines changed

‎GA/GA.go

Lines changed: 116 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,53 +1,160 @@
11
package GA
22

3+
import (
4+
"fmt"
5+
"math"
6+
"math/rand"
7+
"time"
8+
)
9+
310
var (
4-
groupSize int //种群大小
5-
selectRand int //轮盘选择概率
6-
crossRand int //交叉概率
7-
mutationRand int //变异概率
11+
groupSize int //种群大小
12+
chromosomeSize int //染色体长度
13+
selectRand float64 //轮盘选择概率
14+
crossRand float64 //交叉概率
15+
mutationRand float64 //变异概率
16+
group []Person //种群
17+
bestPerson Person //当前最好的个体
18+
r *rand.Rand
819
)
920

1021
//Person 个体
1122
type Person struct {
12-
chromosomes []int //染色体
23+
chromosome []int //染色体
24+
value float64 //适应值
1325
}
1426

1527
//Init 初始化函数
1628
//初始化设置种群大小、轮盘选择概率、交叉概率 10000 经变异的概率
17-
func Init(GroupSize, SelectRand, CrossRand, MutationRand int) {
29+
func Init(GroupSize, ChromosomeSize int, SelectRand, CrossRand, MutationRand float64) {
1830
groupSize = GroupSize
1931
crossRand = CrossRand
2032
selectRand = SelectRand
2133
mutationRand = MutationRand
34+
chromosomeSize = ChromosomeSize
35+
r = rand.New(rand.NewSource(time.Now().UnixNano()))
36+
bestPerson.chromosome = make([]int, chromosomeSize)
2237
}
2338

2439
//InitGroup 初始化种群
2540
//根据种群大小随机产生一些个体填充
2641
func InitGroup() {
27-
42+
group = make([]Person, groupSize)
43+
for i := 0; i < groupSize; i++ {
44+
group[i].chromosome = make([]int, chromosomeSize)
45+
for j := 0; j < chromosomeSize; j++ {
46+
if r.Float64() > selectRand {
47+
group[i].chromosome[j] = 1
48+
}
49+
}
50+
}
2851
}
2952

3053
//Fitness 计算适应值
31-
func Fitness() {
54+
func Fitness(person Person) float64 {
55+
x := decode(person)
56+
return x + 10*math.Sin(5*x) + 7*math.Cos(4*x)
57+
}
3258

59+
//解码
60+
func decode(person Person) float64 {
61+
var sum float64
62+
//解码
63+
for i := 0; i < chromosomeSize; i++ {
64+
//二进制染色体转十进制值
65+
if person.chromosome[i] == 1 {
66+
sum = sum + math.Pow(2.0, float64(i))
67+
}
68+
}
69+
return sum * 9 / (math.Pow(2.0, 14.0) - 1)
3370
}
3471

3572
//Select 选择
3673
func Select() {
74+
newGroup := make([]Person, groupSize)
75+
for i := 0; i < groupSize; i++ {
76+
newGroup[i].chromosome = make([]int, chromosomeSize)
77+
rnd := r.Float64()
3778

79+
A:
80+
for j := 0; j < groupSize; j++ {
81+
if group[j].value > rnd*bestPerson.value {
82+
copy(newGroup[i].chromosome, group[j].chromosome)
83+
break A
84+
}
85+
if j == groupSize-1 {
86+
copy(newGroup[i].chromosome, bestPerson.chromosome)
87+
}
88+
}
89+
}
90+
group = newGroup
91+
newGroup = nil
3892
}
3993

4094
//Cross 交叉
4195
func Cross() {
42-
96+
for i := 0; i < groupSize; i = i + 2 {
97+
if r.Float64() < crossRand {
98+
crossPosition := r.Intn(chromosomeSize - 1)
99+
if crossPosition == 0 || crossPosition == 1 {
100+
continue
101+
}
102+
//交叉
103+
for j := crossPosition; j < chromosomeSize; j++ {
104+
tmp := group[i].chromosome[j]
105+
group[i].chromosome[j] = group[i+1].chromosome[j]
106+
group[i+1].chromosome[j] = tmp
107+
}
108+
}
109+
}
43110
}
44111

45112
//Mutation 变异
46113
func Mutation() {
114+
for i := 0; i < groupSize; i++ {
115+
if r.Float64() < mutationRand {
116+
mutationPosition := r.Intn(chromosomeSize - 1)
47117

118+
//单点变异
119+
if group[i].chromosome[mutationPosition] == 0 {
120+
group[i].chromosome[mutationPosition] = 1
121+
} else {
122+
group[i].chromosome[mutationPosition] = 0
123+
}
124+
}
125+
}
48126
}
49127

50128
//GA 遗传算法
51129
func GA() {
130+
//初始化
131+
Init(100, 14, 0.5, 0.6, 0.05)
132+
//初始化种群
133+
InitGroup()
134+
135+
//遗传循环
136+
for i := 0; i < 1000; i++ {
137+
138+
//计算适应值
139+
for j := 0; j < groupSize; j++ {
140+
group[j].value = Fitness(group[j])
141+
142+
//保存当前最好的个体
143+
if group[j].value > bestPerson.value {
144+
copy(bestPerson.chromosome, group[j].chromosome)
145+
bestPerson.value = group[j].value
146+
}
147+
}
148+
149+
fmt.Println("第", i, "代最好个体：", bestPerson.value, " ", decode(bestPerson))
150+
151+
//选择
152+
Select()
153+
154+
//交叉
155+
Cross()
52156

157+
//变异
158+
Mutation()
159+
}
53160
}

‎GA/GA_test.go

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package GA
2+
3+
import (
4+
"testing"
5+
)
6+
7+
func Test(t *testing.T) {
8+
GA()
9+
}

‎GA/doc.go

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,7 @@
11
//Package GA 遗传算法的Golang实现
22
//遗传算法的计算流程 编码->获得初始群体->计算适应值->产生新的群体(选择、交叉、变异等)->满足要求->解码->获得近似解
33
//例子：求解函数 f(x) = x + 10*sin(5*x) + 7*cos(4*x) 在区间[0,9]的最大值。
4+
//假设求解精度为3，那么需要求解的值可能为 0.000-9.000 可能性在2^13-2^14这个范围之内
5+
//使用一个14为的二进制字符串即可表示，最终的求解域
6+
//解码 f(x), x∈[lower_bound, upper_bound] x = lower_bound + decimal(chromosome)×(upper_bound-lower_bound)/( 2 ^chromosome_size- 1 )
47
package GA

0 commit comments

Comments
 (0)
0