<p>出于兴趣,我将其编码为基因搜索:</p>
<pre><code>import numpy as np
from random import choice, randrange
from string import ascii_uppercase
# volunteer requirements for each of the 7 events
NEEDED = np.array([6, 12, 14, 14, 12, 16, 10], dtype=np.int32)
# available schedules where 0 = hour off and 1 = hour working
SCHEDULES = np.array([
[0,1,1,1,1,0,0],
[0,0,1,1,1,1,0],
[0,0,0,1,1,1,1],
[1,1,1,1,0,0,0],
[1,1,0,0,0,1,1],
[1,1,1,0,0,0,1],
[1,0,0,0,1,1,1]
], dtype=np.int32)
NAMES = ["Schedule {}".format(ch) for ch in ascii_uppercase[:len(SCHEDULES)]]
def alloc_random(num, schedules):
"""
Create a random allocation of schedules
"""
num_schedules = len(schedules)
alloc = np.zeros(num_schedules, dtype=np.int32)
for _ in range(num):
alloc[randrange(num_schedules)] += 1
return alloc
def alloc_mutate(alloc):
"""
Randomly replace one schedule with another
"""
alloc = np.copy(alloc) # make a new allocation (instead of modifying the parent)
num_schedules = len(alloc)
while True:
from_ = randrange(num_schedules)
to_ = randrange(num_schedules)
if from_ != to_ and alloc[from_] > 0:
alloc[from_] -= 1
alloc[to_] += 1
return alloc
def alloc_fitness(alloc):
"""
Given a schedule allocation,
return the minimum (volunteers present / needed) of any period
"""
return np.min(alloc.dot(SCHEDULES) / NEEDED)
def alloc_find_best(num_volunteers, needed, schedules, population=20, children=100, generations=1000):
"""
Find the best way to assign schedules to volunteers
"""
# generate starting population
pop = [alloc_random(num_volunteers, schedules) for _ in range(population)]
# evolve!
for gen in range(generations):
# create evolved children
ch = [alloc_mutate(choice(pop)) for _ in range(children)]
# add the parents to the evaluation pool
ch.extend(pop)
# sort from most to least fit
ch.sort(key=alloc_fitness, reverse=True)
# decimate
pop = ch[:population]
# return the best solution found
return pop[0]
def main():
for num_volunteers in range(21, 25):
best = alloc_find_best(num_volunteers, NEEDED, SCHEDULES)
print("\n{:>2d} volunteers: fitness = {:0.1f}%".format(num_volunteers, 100. * alloc_fitness(best)))
for label,val in zip(NAMES, best):
print("{:>14s}: {:>2d}".format(label, val))
if __name__ == "__main__":
main()
</code></pre>
<p>输出如下</p>
<pre><code>21 volunteers: fitness = 92.9%
Schedule A: 4
Schedule B: 7
Schedule C: 2
Schedule D: 0
Schedule E: 6
Schedule F: 2
Schedule G: 0
22 volunteers: fitness = 100.0%
Schedule A: 3
Schedule B: 8
Schedule C: 2
Schedule D: 1
Schedule E: 6
Schedule F: 2
Schedule G: 0
23 volunteers: fitness = 100.0%
Schedule A: 2
Schedule B: 9
Schedule C: 2
Schedule D: 2
Schedule E: 6
Schedule F: 2
Schedule G: 0
24 volunteers: fitness = 107.1%
Schedule A: 4
Schedule B: 9
Schedule C: 2
Schedule D: 0
Schedule E: 7
Schedule F: 2
Schedule G: 0
</code></pre>
<p>有几个有趣的地方:</p>
<ul>
<li><p>只要把需要的志愿者名额加起来,你就至少需要84/4==21名志愿者</p></li>
<li><p>运行几次表明,您至少需要22名志愿者才能真正安排好一切,至少需要24名志愿者才能在每个时间段都有空闲时间</p></li>
<li><p>你随机发现的解决方案实际上与我得到的完全相同,但是我的算法运行得更快-0.8秒,而平均36秒(在我的测试中从12秒到86秒)。</p></li>
</ul>
<p>为了得到你想要的最终结果格式</p>
<pre><code>for name,num,sched in zip(NAMES, best, SCHEDULES):
for _ in range(num):
print(name + " " + str(sched))
</code></pre>
<p>这就好像</p>
<pre><code>Schedule A [0 1 1 1 1 0 0]
Schedule A [0 1 1 1 1 0 0]
Schedule A [0 1 1 1 1 0 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule B [0 0 1 1 1 1 0]
Schedule C [0 0 0 1 1 1 1]
Schedule C [0 0 0 1 1 1 1]
Schedule D [1 1 1 1 0 0 0]
Schedule E [1 1 0 0 0 1 1]
Schedule E [1 1 0 0 0 1 1]
Schedule E [1 1 0 0 0 1 1]
Schedule E [1 1 0 0 0 1 1]
Schedule E [1 1 0 0 0 1 1]
Schedule E [1 1 0 0 0 1 1]
Schedule F [1 1 1 0 0 0 1]
Schedule F [1 1 1 0 0 0 1]
</code></pre>
<p>我还做了一些敏感性分析,比如</p>
<pre><code>from collections import Counter
Counter(tuple(alloc_find_best(22, NEEDED, SCHEDULES)) for _ in range(100))
</code></pre>
<p>这给了</p>
<pre><code>{
(2, 8, 2, 2, 6, 2, 0): 32,
(3, 8, 2, 1, 6, 2, 0): 39,
(4, 8, 2, 0, 6, 2, 0): 29
}
</code></pre>
<p>也就是说,在100次试验中只发现了3种解决方案,第二种解决方案被发现的频率略高,但这三种解决方案的可能性大致相同。值得注意的是,它们之间的唯一区别是附表a和D==时隙1和5之间的权衡。你知道吗</p>