Magic Squares
Magic Squares 问题要求我们计算如何使给定行数的方阵的各行、各列、各个对角线之和相同。方阵中的数字取值范围与行数 n 有关，取值为 1～n² 之间。
其中 genetic.py 的完整代码如下：
import random
import statistics
import sys
import time
from bisect import bisect_left
from math import exp
def _generate_parent(length, geneSet, get_fitness):
genes = []
while len(genes) < length:
sampleSize = min(length - len(genes), len(geneSet))
genes.extend(random.sample(geneSet, sampleSize))
fitness = get_fitness(genes)
return Chromosome(genes, fitness)
def _mutate(parent, geneSet, get_fitness):
childGenes = parent.Genes[:]
index = random.randrange(0, len(parent.Genes))
newGene, alternate = random.sample(geneSet, 2)
childGenes[index] = alternate if newGene == childGenes[index] else newGene
fitness = get_fitness(childGenes)
return Chromosome(childGenes, fitness)
def _mutate_custom(parent, custom_mutate, get_fitness):
childGenes = parent.Genes[:]
custom_mutate(childGenes)
fitness = get_fitness(childGenes)
return Chromosome(childGenes, fitness)
def get_best(get_fitness, targetLen, optimalFitness, geneSet, display,
custom_mutate=None, custom_create=None, maxAge=None):
if custom_mutate is None:
def fnMutate(parent):
return _mutate(parent, geneSet, get_fitness)
else:
def fnMutate(parent):
return _mutate_custom(parent, custom_mutate, get_fitness)
if custom_create is None:
def fnGenerateParent():
return _generate_parent(targetLen, geneSet, get_fitness)
else:
def fnGenerateParent():
genes = custom_create()
return Chromosome(genes, get_fitness(genes))
for improvement in _get_improvement(fnMutate, fnGenerateParent, maxAge):
display(improvement)
if not optimalFitness > improvement.Fitness:
return improvement
def _get_improvement(new_child, generate_parent, maxAge):
parent = bestParent = generate_parent()
yield bestParent
historicalFitness = [bestParent.Fitness]
while True:
child = new_child(parent)
if parent.Fitness > child.Fitness:
if maxAge is None:
continue
parent.Age += 1
if maxAge > parent.Age:
continue
index = bisect_left(historicalFitness, child.Fitness, 0, len(historicalFitness))
proportionSimilar = index / len(historicalFitness)
if random.random() < exp(-proportionSimilar):
parent = child
continue
bestParent.Age = 0
parent = bestParent
continue
if not child.Fitness > parent.Fitness:
child.Age = parent.Age + 1
parent = child
continue
child.Age = 0
parent = child
if child.Fitness > bestParent.Fitness:
bestParent = child
yield bestParent
historicalFitness.append(bestParent.Fitness)
class Chromosome:
def __init__(self, genes, fitness):
self.Genes = genes
self.Fitness = fitness
self.Age = 0
class Benchmark:
@staticmethod
def run(function):
timings = []
stdout = sys.stdout
for i in range(100):
sys.stdout = None
startTime = time.time()
function()
seconds = time.time() - startTime
sys.stdout = stdout
timings.append(seconds)
mean = statistics.mean(timings)
if i < 10 or i % 10 == 9:
print("{} {:3.2f} {:3.2f}".format(
1 + i, mean,
statistics.stdev(timings, mean) if i > 1 else 0))
上述代码中比较重要并且具有较大的变动的是函数 _get_improvement 。
def _get_improvement(new_child, generate_parent, maxAge):
parent = bestParent = generate_parent()
yield bestParent
historicalFitness = [bestParent.Fitness]
while True:
child = new_child(parent)
if parent.Fitness > child.Fitness:
if maxAge is None:
continue
parent.Age += 1
if maxAge > parent.Age:
continue
index = bisect_left(historicalFitness, child.Fitness, 0, len(historicalFitness))
proportionSimilar = index / len(historicalFitness)
if random.random() < exp(-proportionSimilar):
parent = child
continue
bestParent.Age = 0
parent = bestParent
continue
if not child.Fitness > parent.Fitness:
child.Age = parent.Age + 1
parent = child
continue
child.Age = 0
parent = child
if child.Fitness > bestParent.Fitness:
bestParent = child
yield bestParent
historicalFitness.append(bestParent.Fitness)
由于经过多次实验发现，利用之前的engine求解容易陷入局部最优解，因此这里采用模拟退火（ https://www.cnblogs.com/no-true/p/9737193.html ）的思想。函数增加了参数 Age ，一定程度上可以接受差解因此可以跳出局部最优。
下面是 magicSquareTests.py 的完整代码：
import unittest
import datetime
import genetic
import random
class MagicSquareTests(unittest.TestCase):
def test_size_4(self):
self.generate(4, 50)
def test_benchmark(self):
genetic.Benchmark.run(self.test_size_4)
def generate(self, diagonalSize, maxAge):
nSquard = diagonalSize * diagonalSize
geneSet = [i for i in range(1, nSquard+1)]
expectedSum = diagonalSize * (nSquard + 1) / 2
def fnGetFitness(genes):
return get_fitness(genes, diagonalSize, expectedSum)
def fnDisplay(candidate):
display(candidate, diagonalSize, startTime)
geneIndexes = [i for i in range(0,len(geneSet))]
def fnMutate(genes):
mutate(genes, geneIndexes)
def fnCustomCreate():
return random.sample(geneSet, len(geneSet))
optimalValue = Fitness(0)
startTime = datetime.datetime.now()
best = genetic.get_best(fnGetFitness, nSquard, optimalValue, geneSet,
fnDisplay, fnMutate,
fnCustomCreate, maxAge)
self.assertTrue(not optimalValue > best.Fitness)
def get_fitness(genes, diagonalSize, expectedSum):
rows, columns, northeastDiagonalSum, southeastDiagonalSum =
get_sums(genes, diagonalSize)
sumOfDifferences = sum(int(abs(s - expectedSum))
for s in rows + columns +
[southeastDiagonalSum, northeastDiagonalSum]
if s != expectedSum)
return Fitness(sumOfDifferences)
def get_sums(genes, diagonalSize):
rows = [0 for _ in range(diagonalSize)]
columns = [0 for _ in range(diagonalSize)]
southeastDiagonalSum = 0
northeastDiagonalSum = 0
for row in range(diagonalSize):
for column in range(diagonalSize):
value = genes[row * diagonalSize + column]
rows[row] += value
columns[column] += value
southeastDiagonalSum += genes[row * diagonalSize + row]
northeastDiagonalSum += genes[row * diagonalSize + (diagonalSize - 1 - row)]
return rows, columns, northeastDiagonalSum, southeastDiagonalSum
def display(candidate, diagonalSize, startTime):
timeDiff = datetime.datetime.now() - startTime
rows, columns, northeastDiagonalSum, southeastDiagonalSum =
get_sums(candidate.Genes, diagonalSize)
for rowNumber in range(diagonalSize):
row = candidate.Genes[rowNumber * diagonalSize:(rowNumber + 1) * diagonalSize]
print(" ", row, "=", rows[rowNumber])
print(northeastDiagonalSum, " ", columns, " ", southeastDiagonalSum)
print("------------------", candidate.Fitness, timeDiff)
def mutate(genes, indexes):
indexA, indexB =random.sample(indexes, 2)
genes[indexA], genes[indexB] = genes[indexB], genes[indexA]
class Fitness:
def __init__(self, sumOfDifference):
self.SumOfDifferences = sumOfDifference
def __gt__(self, other):
return self.SumOfDifferences < other.SumOfDifferences
def __str__(self):
return "{}".format(self.SumOfDifferences)
基因设置为一个列表，将整个矩阵化成一维存入。
适应值计算各行、各列、各对角线之和于最终和的差。