<p>我认为在这种情况下,<a href="https://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">genetic algorithm</a>可能会很好地工作。下面是一个使用<a href="http://deap.readthedocs.org/en/master/index.html" rel="nofollow noreferrer">^{<cd1>}</a>组合起来的快速示例,大致基于他们的示例<a href="https://github.com/DEAP/deap/blob/b46dde2b74a3876142fdcc40fdf7b5caaa5ea1f4/examples/ga/onemax_numpy.py" rel="nofollow noreferrer">here</a>:</p>
<pre><code>import numpy as np
import deap
from deap import algorithms, base, tools
import imp
class GeneticDetMinimizer(object):
def __init__(self, N=30, popsize=500):
# we want the creator module to be local to this instance, since
# creator.create() directly adds new classes to the module's globals()
# (yuck!)
cr = imp.load_module('cr', *imp.find_module('creator', deap.__path__))
self._cr = cr
self._cr.create("FitnessMin", base.Fitness, weights=(-1.0,))
self._cr.create("Individual", np.ndarray, fitness=self._cr.FitnessMin)
self._tb = base.Toolbox()
# an 'individual' consists of an (N^2,) flat numpy array of 0s and 1s
self.N = N
self.indiv_size = N * N
self._tb.register("attr_bool", np.random.random_integers, 0, 1)
self._tb.register("individual", tools.initRepeat, self._cr.Individual,
self._tb.attr_bool, n=self.indiv_size)
# the 'population' consists of a list of such individuals
self._tb.register("population", tools.initRepeat, list,
self._tb.individual)
self._tb.register("evaluate", self.fitness)
self._tb.register("mate", self.crossover)
self._tb.register("mutate", tools.mutFlipBit, indpb=0.025)
self._tb.register("select", tools.selTournament, tournsize=3)
# create an initial population, and initialize a hall-of-fame to store
# the best individual
self.pop = self._tb.population(n=popsize)
self.hof = tools.HallOfFame(1, similar=np.array_equal)
# print summary statistics for the population on each iteration
self.stats = tools.Statistics(lambda ind: ind.fitness.values)
self.stats.register("avg", np.mean)
self.stats.register("std", np.std)
self.stats.register("min", np.min)
self.stats.register("max", np.max)
def fitness(self, individual):
"""
assigns a fitness value to each individual, based on the determinant
"""
return np.linalg.det(individual.reshape(self.N, self.N)),
def crossover(self, ind1, ind2):
"""
randomly swaps a subset of array values between two individuals
"""
size = self.indiv_size
cx1 = np.random.random_integers(0, size - 2)
cx2 = np.random.random_integers(cx1, size - 1)
ind1[cx1:cx2], ind2[cx1:cx2] = (
ind2[cx1:cx2].copy(), ind1[cx1:cx2].copy())
return ind1, ind2
def run(self, ngen=int(1E6), mutation_rate=0.3, crossover_rate=0.7):
np.random.seed(seed)
pop, log = algorithms.eaSimple(self.pop, self._tb,
cxpb=crossover_rate,
mutpb=mutation_rate,
ngen=ngen,
stats=self.stats,
halloffame=self.hof)
self.log = log
return self.hof[0].reshape(self.N, self.N), log
if __name__ == "__main__":
np.random.seed(0)
gd = GeneticDetMinimizer()
best, log = gd.run()
</code></pre>
<p>在我的笔记本电脑上运行1000代大约需要40秒,这使我从最小决定值约为-5.7845x10<sup>8</sup>到-6.41504x10<sup>11</sup>。我对元参数(种群大小、突变率、交叉率等)并没有做太多的研究,所以我相信可以做得更好。在</p>
<hr/>
<p>这是一个大大改进的版本,它实现了一个更智能的交叉函数,它可以在个体之间交换行或列的块,并使用<a href="http://pythonhosted.org/cachetools/#cachetools.LRUCache" rel="nofollow noreferrer">^{<cd2>}</a>来保证每一个变异步骤都会产生一个新的配置,并跳过对已经尝试过的配置的行列式的评估:</p>
^{pr2}$
<p>到目前为止,我的最佳成绩是<s>-3.23718x10<sup>13</sup>-3.92366x10<sup>13</sup>1000代,这在我的机器上大约需要45秒。在</p>
<p>根据注释中链接的解,31x31哈达玛矩阵的最大行列式必须至少为75960984159088×2<sup>30</sup>~=8.1562x10<sup>22</sup>(尚未证明该解是否最优)。(n-1×n-1)二元矩阵的最大行列式为2<sup>1-n</sup>乘以(n×n)Hadamard矩阵的值,即8.1562x10<sup>22</sup>x2<sup>-30</sup>~=7.5961x10<sup>13</sup>,因此遗传算法在当前已知解的数量级内。在</p>
<p>然而,健身功能似乎在这里趋于平稳,我很难打破-4x10<sup>13</sup>。由于这是一种启发式搜索,因此不能保证它最终会找到全局最优。在</p>
<p><img src="https://i.stack.imgur.com/GucFx.png" alt="enter image description here"/></p>