package main
import (
"fmt"
"math/rand"
"time"
)
type DNA map[int64]int64
type Point struct {
X int64
Y int64
Op int64 //1:移动 2:停止 3:清理
}
var action map[int64] func (point Point) (ret Point)
func main() {
//初始化动作序列
action = map[int64]func(point Point) (ret Point){}
action[0] = MoveEast
action[1] = MoveNorth
action[2] = MoveSouth
action[3] = MoveRandom
action[4] = MoveWest
action[5] = Stop
action[6] = Clear
//打印地图
//printMap(initMap)
//初始化种群
n := NewNaturel(200,7,243)
//外层种群迭代次数 1000次
for c:=0;c < 200; c++ {
//执行100次随机地图生成
for pi:=0; pi<50;pi++ {
//初始化地图 地图初始化策略
initMap := NewMap(10,10, 50)
p := Point{
X: 0,
Y: 0,
}
var cn int64
for ; cn < n.MemberCnt; cn++ {
TestRobot(initMap, n.robots[cn], p, 200, false)
//printData(c,cn,n.robots[cn].score,n.robots[cn].Clear)
}
}
//种群迭代
n.Cycle()
}
//输出当前种群最优DNA及其分数
//初始化地图
initMap1 := NewMap(10,10, 50)
p := Point{
X: 0,
Y: 0,
}
fmt.Printf("\n===============================TOP===========================\n")
fmt.Printf("Old:\n")
printMap(initMap1)
newMap := TestRobot(initMap1, n.GetTop(), p , 200, true)
fmt.Printf("New:\n")
printMap(newMap)
fmt.Printf("\n================================DNA===========================\n")
printDNA(n.GetTop())
}
func printData(cycle int,id int64, score int64, clear int64) {
fmt.Printf("%d,%d,%d,%d\n",cycle, id, score, clear)
}
func printMap(s scene) {
var i,j,x int64
fmt.Printf("+")
for i=0;i<s.maxWidth;i++ {
fmt.Printf("-+")
}
fmt.Printf("\n")
for i=0;i<s.maxHeight;i++ {
fmt.Printf("|")
for j=0;j<s.maxWidth;j++{
fmt.Printf("%d|",s.M[i][j]-1)
}
fmt.Printf("\n")
fmt.Printf("+")
for x=0;x<s.maxWidth;x++ {
fmt.Printf("-+")
}
fmt.Printf("\n")
}
}
func cloneMap(robotMap scene) (ret scene) {
ret = &sceneRaw{
M: make([][]int64, robotMap.maxHeight),
maxWidth: robotMap.maxWidth,
maxHeight: robotMap.maxHeight,
Has: robotMap.Has,
}
var i,j int64
for i=0;i< robotMap.maxHeight;i++ {
ret.M[i] = make([]int64, robotMap.maxWidth)
for j=0;j<robotMap.maxWidth;j++{
ret.M[i][j] = robotMap.M[i][j]
}
}
return
}
//机器人评分程序=====
func TestRobot(robotMap scene, robot *Robot, before Point, maxStep int64, printX bool) (newMap scene) {
robotMap = cloneMap(robotMap)
var s = &scoreP{}
var after Point
//地图迭代
var i int64
for ;i < maxStep; i++ {
var opResult bool
var beforeS string
var beforeX,beforeY int64
if robotMap.M[before.Y][before.X] == 1 {
beforeS = "空"
beforeX = before.X
beforeY = before.Y
} else {
beforeS = "非空"
beforeX = before.X
beforeY = before.Y
}
after = robot.Action(robotMap, before)
//移动
if after.Op == 1 {
if after.X >= 0 && after.X < robotMap.maxWidth && after.Y >= 0 && after.Y < robotMap.maxHeight {
opResult = true
before = after
} else {
after = before
opResult = false
}
s.MoveCheck(opResult)
} else if after.Op == 2 {
opResult = true
s.MoveStop(opResult)
//收集
} else if after.Op == 3 {
if robotMap.M[after.Y][after.X] == 2 {
robotMap.M[after.Y][after.X] = 1
opResult = true
} else {
opResult = false
}
s.Collect(opResult)
}
if printX {
var OpS string
var OpR string
var afterS string
if after.Op == 1 {
OpS = "移动"
} else if after.Op == 2 {
OpS = "暂停"
} else if after.Op == 3 {
OpS = "收集"
}
if opResult {
OpR = "成功"
} else {
OpR = "失败"
}
if robotMap.M[after.Y][after.X] == 1 {
afterS = "空"
} else {
afterS = "非空"
}
if OpS == "收集" {
fmt.Printf("===> %s%s: befor:[%d,%d,%s] after:[%d,%d,%s]\n", OpS, OpR, beforeX, beforeY, beforeS, after.X, after.Y, afterS)
}
}
}
//分值选择，选择最大值
if robot.score != 0 {
if robot.score < s.Score {
robot.score = s.Score
}
} else {
robot.score = s.Score
}
newMap = robotMap
return
}
//地图=======
type sceneRaw struct {
M [][]int64
maxWidth int64
maxHeight int64
Has int64
}
type scene *sceneRaw
//地图生成器
func NewMap(width int64, height int64, goods int64) (s scene) {
s = &sceneRaw{
M : make([][]int64, height),
maxHeight: height,
maxWidth: width,
Has: goods,
}
for i:=0;i< int(height);i++ {
s.M[i] = make([]int64, width)
for j:=0;j<int(width);j++{
s.M[i][j] = 1
}
}
for goods > 0 {
var rX int64
var rY int64
rY = rand.Int63() % height
rX = rand.Int63() % width
if s.M[rY][rX] == 1 {
s.M[rY][rX] = 2
goods--
}
}
return
}
//选择系统=====================================
type naturel struct {
robots []*Robot //机器人种群
cycleTime int64 //繁殖周期
MemberCnt int64 //种群数量
}
//创建种群
func NewNaturel(cn int64,maxOp int64, maxDnaLength int64) (n *naturel) {
n = &naturel{
robots: make([]*Robot, cn),
MemberCnt: cn,
cycleTime: 1,
}
var i int64
for ;i<cn;i++ {
n.robots[i] = &Robot{
score: 0,
T:n.RandomDNA(maxOp, maxDnaLength),
}
}
return
}
//种群迭代
func (n *naturel) Cycle() {
n.cycleTime++
n.Sort()
//2.基因杂交
var i,j,x int64
list := make([]*Robot, n.MemberCnt)
for i = n.MemberCnt - 1; i > n.MemberCnt - 23; i-- {
for j = i - 1; j > n.MemberCnt - 23; j-- {
list[x] = &Robot{
T:n.AdvanceDNA(n.robots[i].T,n.robots[j].T),
score: 0,
}
list[x].T = n.VariateDNA(list[x].T, 5)
x++
if x >= n.MemberCnt {
goto end
}
}
}
end:
n.robots = list
}
func printDNA(robot *Robot) {
for s,p := range robot.T {
fmt.Printf("s:%d => p:%d ,",s,p)
}
}
//生成随机基因序列
func (n *naturel) RandomDNA (maxOp int64, dnaLen int64) (ret DNA) {
ret = map[int64]int64{}
var i int64
for ; i< dnaLen; i++ {
r := rand.New(rand.NewSource(time.Now().UnixNano()))
ret[i] = int64(r.Int31()) % maxOp
}
return ret
}
//基因进化序列
func (n *naturel) AdvanceDNA(ParentL DNA, ParentR DNA) (ret DNA) {
ret = DNA{}
max := int64(len(ParentR))
var i int64
for ;i<max;i++ {
if i%2 == 1 {
ret[i] = ParentL[i]
} else {
ret[i] = ParentR[i]
}
}
return
}
//基因变异
func (n *naturel) VariateDNA(origin DNA, x int) (ret DNA) {
ret = origin
for i:=0;i<x;i++ {
ret[rand.Int63() % 243] = rand.Int63() % 7
}
return
}
//获取最优基因序列
func (n *naturel) GetTop()(r *Robot) {
n.Sort()
r = n.robots[n.MemberCnt - 1]
return
}
//基因排序
func (n *naturel) Sort() {
//1.选出最优基因20，基因分值排序
var i,j int64
for i = n.MemberCnt; i > 1;i-- {
for j =0; j < i-1; j++ {
if n.robots[j].score > n.robots[j+1].score {
var temp *Robot
temp = n.robots[j]
n.robots[j] = n.robots[j+1]
n.robots[j+1] = temp
}
}
}
}
//评分系统====================================
type scoreP struct {
Score int64
}
//移动评分
func (s *scoreP) MoveCheck(OpType bool) {
if OpType {
s.Score += 1
} else {
s.Score -= 5
}
}
//停止评分
func (s *scoreP) MoveStop(OpType bool) {
s.Score -= 1
return
}
//收集评分
func (s *scoreP) Collect(OpType bool) {
if OpType {
s.Score += 5
} else {
s.Score -= 1
}
}
//机器人系统===================================
type Robot struct {
T DNA
score int64
Clear int64
}
//场景
func(r Robot) getActionID (origin scene, point Point) (actionId int64) {
//东
actionId += r.GetActionBit(origin, point.X, point.Y - 1)
//南
actionId += r.GetActionBit(origin, point.X + 1, point.Y) * 3
//西
actionId += r.GetActionBit(origin, point.X, point.Y + 1) * 9
//北
actionId += r.GetActionBit(origin, point.X - 1, point.Y) * 27
//中
actionId += r.GetActionBit(origin, point.X, point.Y) * 81
return
}
//获取当前状态
func (r Robot) GetActionBit(origin scene, x int64, y int64) (score int64) {
if x < 0 || x >= origin.maxWidth {
score = 0
} else if y < 0 || y >= origin.maxHeight {
score = 0
} else {
score = origin.M[y][x]
}
return
}
//执行操作
func (r Robot) Action(origin scene, point Point) (ret Point) {
//1.根据point计算指令序列ID
var actionId int64
actionId = r.getActionID(origin, point)
//执行指令序列
p := r.T[actionId]
ret = action[p](point)
return
}
//向北
func MoveNorth (point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.X = ret.X - 1
ret.Op = 1
return
}
//向南
func MoveSouth ( point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.X = ret.X + 1
ret.Op = 1
return
}
//向东
func MoveEast (point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.Y = ret.Y - 1
ret.Op = 1
return
}
//向西
func MoveWest (point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.Y = ret.Y + 1
ret.Op = 1
return
}
//随机移动
func MoveRandom ( point Point) (ret Point) {
ran := rand.Int63() % 4
switch ran {
case 0:
ret = MoveEast(point)
break
case 1:
ret = MoveWest(point)
break
case 2:
ret = MoveSouth( point)
break
case 3:
ret = MoveNorth( point)
break
}
return
}
//停止移动
func Stop (point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.Op = 2
return
}
//清理操作
func Clear ( point Point) (ret Point) {
ret = Point{
X: point.X,
Y: point.Y,
}
ret.Op = 3
return
}
//计算Clear数量
func CountCn(origin scene) (ret int64) {
var i,j,total int64
for i=0;i< origin.maxHeight; i++ {
for j= 0;j<origin.maxWidth;j++ {
if origin.M[i][j] == 2 {
total++
}
}
}
ret = origin.Has - total
return
}
遗传算法
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
推荐阅读更多精彩内容
- 经常被用来作为研究智能优化算法时的测试函数。 为了更好地理解上述表达式，这样的函数形式到底描绘怎样的图像，以及是否...
- 前言 在用基于DEAP设计的遗传算法求解函数极值后，我们想要进一步解决一些更加困难点的问题。TSP问题就是很好的实...
- 遗传算法(genetic algorithm, GA)是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生...
