md`# 遗传算法 简单计算器
https://wenku.baidu.com/view/7e6b0b319ec3d5bbfc0a7463.html
假设每个变量的长度一致
\`\`\`js
var calculator = new GACalculator({
groupMemberCount: 8, // should be even
varPerGen: 2,
varInitFn: () => _.random(7),
toBin: n => _.padStart(n.toString(2), 3, '0'),
toVar: str => parseInt(str, 2),
// 支持直接计算分数，也支持离线（异步）计算分数，下面两个方法传一个即可
calcScore: vars => vars.map(v => v * v).reduce((acc, v) => acc + v, 0),
computeOffline: function (group) {
return new Promise(resolve => setTimeout(() => resolve(this.calcGroupScore()), 500))
}
})
calculator.calcGroupScore() // show init score
calculator.iterate() // run several times
\`\`\`
`
class GACalculator {
constructor(opt) {
this.groupMemberCount = 8
this.varPerGen = 2
this.exchangeMask = 1/3
this.mutateMask = 1/10
this.mutateChance = 1/2
this.softmaxPicker = false
Object.assign(this, opt)
this.binLen = this.toBin(this.varInitFn()).length
this.splitGenRegex = new RegExp(`\\d{${this.binLen}}`, 'g')
this.binLenTotal = this.varPerGen * this.binLen
let group = this.init()
this.state = {group, historyBestScore: 0, term: 0}
}
varInitFn() { return _.random(7) }
toBin(n){ return _.padStart(n.toString(2), 3, '0') }
toVar(str) { return parseInt(str, 2) }
calcScore(vars){ return vars.map(v => v * v).reduce((acc, v) => acc + v, 0) }
calcGroupScore(gt0) {
let scores = this.state.group.map(gen => this.calcScore(this.decode(gen)))
if (!gt0) {
return scores
}
let min = _.min(scores)
return scores.map(v => v - min)
}
async computeOffline(group) {
return this.calcGroupScore()
}
init(n = this.groupMemberCount) {
if (n % 2 === 1) {
throw new Error('n should be even')
}
return _.range(n).map(()=> this.encode(_.range(this.varPerGen).map(this.varInitFn)))
}
encode(args){
return args.map(v => this.toBin(v)).join('')
}
decode(gen) {
return gen.match(this.splitGenRegex).map(this.toVar)
}
selectByScore(group){
let scores = this.calcGroupScore(true)
if (this.softmaxPicker) {
let {exp} = Math
scores = scores.map(v => exp(v))
}
let sum = _.sum(scores)
let pArr = sum <= 1e-6 ? scores.map(v => (v + 1)/(sum + 2)) : scores.map(v => v/sum)
return this.roulette(group,pArr)
}
roulette(group, pArr){
let merged = group.map((gen,i) => ({gen,chance:pArr[i]}))
let acc = 0
let sorted = _.orderBy(merged, o=>o.chance,'desc')
.map(o => {
acc+=o.chance
o.pLevel = acc
return o
})
return _.range(group.length)
.map(()=>_.random(0,1,true))
.map(p => _.find(sorted, o=>p <= o.pLevel)?.gen)
}
exchange(gen1, gen2, mask){
let nextG1 = gen1.split('')
.map((c,i) => mask[i]==='1'? gen2[i]:c)
.join('')
let nextG2 = gen2.split('')
.map((c,i) => mask[i]==='1'?gen1[i]:c)
.join('')
return [nextG1, nextG2]
}
mutate(gen, mask) {
return gen.split('')
.map((c,i) => mask[i]==='1'? (c === '1' ? '0' : '1') : c)
.join('')
}
makeMask(len, p) {
return _.range(len)
.map(i => _.random(0,1,true) <= p ? 1 :0)
.join('')
}
async iterate() {
let state = this.state
let nextGroup = this.selectByScore(state.group)
let exchangeMask = this.makeMask(this.binLenTotal, this.exchangeMask)
let mutationMask = this.makeMask(this.binLenTotal, this.mutateMask)
let mutationChance = this.mutateChance
let exchanged = _(_.range(state.group.length))
.shuffle()
.map(pos=>nextGroup[pos])
.chunk(2)
.flatMap(([g1,g2]) => this.exchange(g1, g2, exchangeMask))
.value()
let mutated = exchanged.map(g => _.random(0,1,true) <= mutationChance ? this.mutate(g, mutationMask) : g)
this.scores = await this.computeOffline(mutated)
let bestScore = _.max(this.scores)
let nextBest = mutated[_.findIndex(this.scores, s => s === bestScore)]
Object.assign(state, {
group: mutated,
bestGen: nextBest,
historyBestScore: state.historyBestScore <= bestScore ? bestScore : state.historyBestScore,
historyBestGen: state.historyBestScore <= bestScore ? nextBest : state.historyBestGen,
bestScore,
term: state.term + 1,
exchangeMask,
mutationMask
})
return state
}
}
calculator = new GACalculator({
computeOffline: function () {
return new Promise(resolve => setTimeout(() => resolve(this.calcGroupScore()), 500))
}
})
calculator.calcGroupScore()
calculator.iterate()
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.