1

我正在测试一本关于遗传算法的书中找到的代码,我想出了一个奇怪的错误。代码如下:

import time
import random
import math

people = [('Seymour','BOS'),
          ('Franny','DAL'),
          ('Zooey','CAK'),
          ('Walt','MIA'),
          ('Buddy','ORD'),
          ('Les','OMA')]
# Laguardia
destination='LGA'

flights={}
# 
for line in file('schedule.txt'):
  origin,dest,depart,arrive,price=line.strip().split(',')
  flights.setdefault((origin,dest),[])

  # Add details to the list of possible flights
  flights[(origin,dest)].append((depart,arrive,int(price)))

def getminutes(t):
  x=time.strptime(t,'%H:%M')
  return x[3]*60+x[4]

def printschedule(r):
  for d in range(len(r)/2):
    name=people[d][0]
    origin=people[d][1]
    out=flights[(origin,destination)][int(r[d])]
    ret=flights[(destination,origin)][int(r[d+1])]
    print '%10s%10s %5s-%5s $%3s %5s-%5s $%3s' % (name,origin,
                                                  out[0],out[1],out[2],
                                                  ret[0],ret[1],ret[2])

def schedulecost(sol):
  totalprice=0
  latestarrival=0
  earliestdep=24*60

  for d in range(len(sol)/2):
    # Get the inbound and outbound flights
    origin=people[d][1]
    outbound=flights[(origin,destination)][int(sol[d])]
    returnf=flights[(destination,origin)][int(sol[d+1])]

    # Total price is the price of all outbound and return flights
    totalprice+=outbound[2]
    totalprice+=returnf[2]

    # Track the latest arrival and earliest departure
    if latestarrival<getminutes(outbound[1]): latestarrival=getminutes(outbound[1])
    if earliestdep>getminutes(returnf[0]): earliestdep=getminutes(returnf[0])

  # Every person must wait at the airport until the latest person arrives.
  # They also must arrive at the same time and wait for their flights.
  totalwait=0  
  for d in range(len(sol)/2):
    origin=people[d][1]
    outbound=flights[(origin,destination)][int(sol[d])]
    returnf=flights[(destination,origin)][int(sol[d+1])]
    totalwait+=latestarrival-getminutes(outbound[1])
    totalwait+=getminutes(returnf[0])-earliestdep  

  # Does this solution require an extra day of car rental? That'll be $50!
  if latestarrival>earliestdep: totalprice+=50

  return totalprice+totalwait


def geneticoptimize(domain,costf,popsize=50,step=1,
                    mutprob=0.2,elite=0.2,maxiter=100):
  # Mutation Operation
  def mutate(vec):
    i=random.randint(0,len(domain)-1)
    if random.random()<0.5 and vec[i]>domain[i][0]:
      return vec[0:i]+[vec[i]-step]+vec[i+1:] 
    elif vec[i]<domain[i][1]:
      return vec[0:i]+[vec[i]+step]+vec[i+1:]

  # Crossover Operation
  def crossover(r1,r2):
    i=random.randint(1,len(domain)-2)
    return r1[0:i]+r2[i:]

  # Build the initial population
  pop=[]
  for i in range(popsize):
    vec=[random.randint(domain[i][0],domain[i][1]) 
         for i in range(len(domain))]
    pop.append(vec)

  # How many winners from each generation?
  topelite=int(elite*popsize)

  # Main loop 
  for i in range(maxiter):
    scores=[(costf(v),v) for v in pop]
    scores.sort()
    ranked=[v for (s,v) in scores]

    # Start with the pure winners
    pop=ranked[0:topelite]

    # Add mutated and bred forms of the winners
    while len(pop)<popsize:
      if random.random()<mutprob:

        # Mutation
        c=random.randint(0,topelite)
        pop.append(mutate(ranked[c]))
      else:

        # Crossover
        c1=random.randint(0,topelite)
        c2=random.randint(0,topelite)
        pop.append(crossover(ranked[c1],ranked[c2]))

    # Print current best score
    print scores[0][0]

  return scores[0][1]

此代码使用名为 schedule.txt 的 .txt 文件,可从http://kiwitobes.com/optimize/schedule.txt下载

根据本书,当我运行代码时,我输入了以下内容:

>>> domain=[(0,8)]*(len(optimization.people)*2)
>>> s=optimization.geneticoptimize(domain,optimization.schedulecost)

但我得到的错误是:

Traceback (most recent call last):
  File "<pyshell#12>", line 1, in <module>
    s=optimization.geneticoptimize(domain,optimization.schedulecost)
  File "optimization.py", line 99, in geneticoptimize
    scores=[(costf(v),v) for v in pop]
  File "optimization.py", line 42, in schedulecost
    for d in range(len(sol)/2):
TypeError: object of type 'NoneType' has no len()

问题是错误消息有时会出现,有时则不会。我检查了代码,但看不出哪里有问题,因为 pop 永远不会填充空向量。有什么帮助吗?谢谢

4

2 回答 2

2

如果函数中的任何一个条件都不满足,您就可以进入None您的列表。在这种情况下,控件在函数的末尾运行,这与返回相同。您需要将代码更新为只有一个条件,或者在单独的块中处理不满足其中任何一个条件的情况:popmutateNone

def mutate(vec):
    i=random.randint(0,len(domain)-1)
    if random.random()<0.5 and vec[i]>domain[i][0]:
        return vec[0:i]+[vec[i]-step]+vec[i+1:] 
    elif vec[i]<domain[i][1]:
        return vec[0:i]+[vec[i]+step]+vec[i+1:]
    else:
        # new code needed here!
于 2012-12-16T01:00:15.913 回答
0

这不是一个答案,但我会捕获这个错误并在它出现时打印出pop数组,看看它当时的样子。正如您所指出的,从代码中看起来它永远不应该进入这种状态,所以首先看看它是否确实进入了那种状态,然后回溯,直到找到它发生的条件。

据推测,这种情况有时只会发生,因为您的代码中有随机因素?

于 2012-12-16T00:46:37.130 回答